git @ Cat's Eye Technologies Jaccia / rel_1_0_2009_0411
Initial import of Jaccia[ta] version 1.0 revision 2009.0411. Cat's Eye Technologies 12 years ago
9 changed file(s) with 444 addition(s) and 0 deletion(s). Raw diff Collapse all Expand all
+80
-0
doc/jaccia.html less more
0 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/2002/REC-xhtml1-20020801/DTD/xhtml1-strict.dtd">
1 <html xmlns="http://www.w3.org/1999/xhtml" lang="en">
2 <head>
3 <title>The Jaccia and Jacciata Cellular Automata</title>
4 </head>
5
6 <h1>The Jaccia and Jacciata Cellular Automata</h1>
7
8 <h2>Overview</h2>
9
10 <p><dfn>Jaccia</dfn> and <dfn>Jacciata</dfn> are cellular automata inspired by the
11 <a class="external" href="http://www.riken.go.jp/lab-www/frontier-div/NEWSLETTER/feb2001/ameboid_e.htm">Announcement
12 of Scientific Proof that Slime Molds are Intelligent Maze Solvers</a>.</p>
13
14 <p>Basically, the slime mold solves the maze by:</p>
15 <ul>
16 <li>initially being everywhere in the maze</li>
17 <li>there being food at the entrance and exit of the maze</li>
18 <li>minimizing its surface area by retreating from anywhere it can't get food.</li>
19 </ul>
20
21 <p>Jaccia operates the same way. In the Jaccia automaton, slime cells survive if they have
22 immediate neighbours in at least two cardinal directions that provide sustenance, i.e. are
23 either food or other slime cells. The result is the same: paths of slime cells that lead down
24 dead ends have one end which provides no sustenance and dies off. Eventually, only paths
25 of slime cells that reach from food to food (or uninterrupted circular paths of slime cells)
26 remain. Jacciata is a more involved automaton which finds only the shortest path.</p>
27
28 <h2>Properties</h2>
29
30 <p>Jaccia has the property that, when started from this condition (entire maze filled
31 with slime cells), the automaton will eventually reach a fixed point (steady state) which
32 contains all possible paths from food to food.</p>
33
34 <p>Jacciata is similar, but has the property that when it reaches a fixed point, it will contain
35 the <em>shortest</em> path from food to food, if such a path exists and is unique. If no
36 such path exists, or is not unique, the result is undefined. It is otherwise similar to Jaccia.</p>
37
38 <p>The behaviour of both automata is also undefined if the slime configurations are not orthogonal
39 (that is, if there are any diagonal slime paths.)</p>
40
41 <h2>Definition</h2>
42
43 <p>Both Jaccia and Jacciata are defined in ALPACA v0.94. Jaccia is defined in
44 the file <code>jaccia.alp</code> and Jacciata in <code>jacciata.alp</code>.
45 The ALPACA definition is authoritative; what is given here is merely advisory.</p>
46
47 <p>Both automata use basically the same set of symbols. An initial Jaccia playfield
48 generally serves as an initial Jacciata playfield with the same kind of solution.</p>
49
50 <ul>
51 <li><code>&nbsp;</code> - empty space</li>
52 <li><code>#</code> - wall (purely decorative)</li>
53 <li><code>%</code> - slime mold</li>
54 <li><code>F</code> - food</li>
55 <li><code>S</code> - "start" food (needed in Jacciata, optional in Jaccia)</li>
56 <li><code>-</code> - exploratory head (Jacciata only)</li>
57 <li><code>?</code> - exploratory body (Jacciata only)</li>
58 <li><code>@</code> - solved (Jacciata only)</li>
59 </ul>
60
61 <h2>Discussion</h2>
62
63 <p>Jacciata's definition is not very elegant, especially when compared to Jaccia. In order for it to work, the
64 two sources of food need to be labelled differently (S and F), there needs to be a "head" of
65 an exploratory shoot that looks for solutions, and so on. It could probably be made more elegant with
66 some work.</p>
67
68 <p>The definition of these automata in ALPACA suggests some
69 possible improvements to that meta-language, particularly the definition of neighbourhoods
70 different from the assumed von Neumann neighbourhood, and their use in the count
71 operator.</p>
72
73 <p>Happy intelligence! Such as it is.
74 <br/>Chris Pressey
75 <br/>April 11, 2009
76 <br/>Bellevue, WA</p>
77
78 </body>
79 </html>
+7
-0
eg/nonunique.jac less more
0 ####S####
1 #%%%%%%%#
2 #%#####%#
3 #%#%#%#%#
4 #%#%#%#%#
5 #%%%%%%%#
6 ####F####
+11
-0
eg/nowalls.jac less more
0 F
1 %%%%%%%%%
2 % % %
3 % % %%% %
4 % % % %
5 %%% % % %
6 % % %
7 % %%% %%%
8 % % %
9 %%% %%%%%
10 F
+11
-0
eg/solveit.jac less more
0 ########S##
1 #%%%%%%%%%#
2 #%###%###%#
3 #%#%#%%%#%#
4 #%#%#%#%###
5 #%%%#%#%#%#
6 #####%#%#%#
7 #%#%%%#%%%#
8 #%#%###%###
9 #%%%#%%%%%#
10 #########F#
+7
-0
eg/unique.jac less more
0 ####S####
1 #%%%%%%%#
2 #%#####%#
3 #%#%%%#%#
4 #%#%#%#%#
5 #%%%#%%%#
6 ##F######
+82
-0
script/jaccia.pl less more
0 #!/usr/bin/perl
1 # - automatically generated from by:
2 # alpaca.pl v0.93
3 # http://catseye.webhop.net/projects/alpaca/
4 ######################################################
5
6 use Alpaca qw(true false guess
7 adjacent_state adjacent_class
8 load_playfield display_playfield process_playfield);
9
10 sub SustainerClassRules {
11 return 0
12 };
13
14 sub SpaceStateRules {
15 return 'Space'
16 };
17
18 sub WallStateRules {
19 return 'Wall'
20 };
21
22 sub FoodStateRules {
23 return SustainerClassRules() || 'Food'
24 };
25
26 sub Food2StateRules {
27 return SustainerClassRules() || 'Food2'
28 };
29
30 sub SlimeStateRules {
31 return 'Space' if ((not ((SustainerClassMember($Playfield->[$x][$y-1]) and SustainerClassMember($Playfield->[$x+1][$y])) or (SustainerClassMember($Playfield->[$x][$y-1]) and SustainerClassMember($Playfield->[$x][$y+1])) or (SustainerClassMember($Playfield->[$x][$y-1]) and SustainerClassMember($Playfield->[$x-1][$y])) or (SustainerClassMember($Playfield->[$x+1][$y]) and SustainerClassMember($Playfield->[$x][$y+1])) or (SustainerClassMember($Playfield->[$x+1][$y]) and SustainerClassMember($Playfield->[$x-1][$y])) or (SustainerClassMember($Playfield->[$x][$y+1]) and SustainerClassMember($Playfield->[$x-1][$y])))));
32 return SustainerClassRules() || 'Slime'
33 };
34
35 sub SustainerClassMember {
36 return $_[0] eq 'Food' ||
37 $_[0] eq 'Food2' ||
38 $_[0] eq 'Slime' ||
39 0
40 };
41
42 $Appearance = {
43 'Food' => 'F',
44 'Food2' => 'S',
45 'Slime' => '%',
46 'Space' => ' ',
47 'Wall' => '#',
48
49 };
50
51 $InputCodec = {
52 'F' => 'Food',
53 'S' => 'Food2',
54 '%' => 'Slime',
55 ' ' => 'Space',
56 '#' => 'Wall',
57
58 };
59
60 $StateRule = {
61 'Food' => \&main::FoodStateRules,
62 'Food2' => \&main::Food2StateRules,
63 'Slime' => \&main::SlimeStateRules,
64 'Space' => \&main::SpaceStateRules,
65 'Wall' => \&main::WallStateRules,
66
67 };
68
69 load_playfield($ARGV[0]);
70
71 display_playfield();
72
73 while (!$done)
74 {
75 process_playfield();
76 display_playfield();
77 }
78
79 exit(0);
80
81 ### END ###
+143
-0
script/jacciata.pl less more
0 #!/usr/bin/perl
1 # - automatically generated from by:
2 # alpaca.pl v0.93
3 # http://catseye.webhop.net/projects/alpaca/
4 ######################################################
5
6 use Alpaca qw(true false guess
7 adjacent_state adjacent_class
8 load_playfield display_playfield process_playfield);
9
10 sub StarterClassRules {
11 return 0
12 };
13
14 sub SustainerClassRules {
15 return 0
16 };
17
18 sub SassyClassRules {
19 return 0
20 };
21
22 sub SolutionClassRules {
23 return 0
24 };
25
26 sub SpaceStateRules {
27 return 'Space'
28 };
29
30 sub WallStateRules {
31 return 'Wall'
32 };
33
34 sub SlimeStateRules {
35 return 'Space' if ((not ((SustainerClassMember($Playfield->[$x][$y-1]) and SustainerClassMember($Playfield->[$x+1][$y])) or (SustainerClassMember($Playfield->[$x][$y-1]) and SustainerClassMember($Playfield->[$x][$y+1])) or (SustainerClassMember($Playfield->[$x][$y-1]) and SustainerClassMember($Playfield->[$x-1][$y])) or (SustainerClassMember($Playfield->[$x+1][$y]) and SustainerClassMember($Playfield->[$x][$y+1])) or (SustainerClassMember($Playfield->[$x+1][$y]) and SustainerClassMember($Playfield->[$x-1][$y])) or (SustainerClassMember($Playfield->[$x][$y+1]) and SustainerClassMember($Playfield->[$x-1][$y])))) or (($Playfield->[$x][$y-1] eq 'Head' and $Playfield->[$x+1][$y] eq 'Head') or ($Playfield->[$x][$y-1] eq 'Head' and $Playfield->[$x][$y+1] eq 'Head') or ($Playfield->[$x][$y-1] eq 'Head' and $Playfield->[$x-1][$y] eq 'Head') or ($Playfield->[$x+1][$y] eq 'Head' and $Playfield->[$x][$y+1] eq 'Head') or ($Playfield->[$x+1][$y] eq 'Head' and $Playfield->[$x-1][$y] eq 'Head') or ($Playfield->[$x][$y+1] eq 'Head' and $Playfield->[$x-1][$y] eq 'Head')));
36 return 'Head' if ((StarterClassMember($Playfield->[$x][$y+1]) or StarterClassMember($Playfield->[$x][$y-1]) or StarterClassMember($Playfield->[$x+1][$y]) or StarterClassMember($Playfield->[$x-1][$y])));
37 return SustainerClassRules() || 'Slime'
38 };
39
40 sub HeadStateRules {
41 return 'Body' if (1);
42 return StarterClassRules() || SustainerClassRules() || SassyClassRules() || 'Head'
43 };
44
45 sub BodyStateRules {
46 return 'Solved' if ((SolutionClassMember($Playfield->[$x][$y+1]) or SolutionClassMember($Playfield->[$x][$y-1]) or SolutionClassMember($Playfield->[$x+1][$y]) or SolutionClassMember($Playfield->[$x-1][$y])));
47 return 'Space' if ((not ((SassyClassMember($Playfield->[$x][$y-1]) and SassyClassMember($Playfield->[$x+1][$y])) or (SassyClassMember($Playfield->[$x][$y-1]) and SassyClassMember($Playfield->[$x][$y+1])) or (SassyClassMember($Playfield->[$x][$y-1]) and SassyClassMember($Playfield->[$x-1][$y])) or (SassyClassMember($Playfield->[$x+1][$y]) and SassyClassMember($Playfield->[$x][$y+1])) or (SassyClassMember($Playfield->[$x+1][$y]) and SassyClassMember($Playfield->[$x-1][$y])) or (SassyClassMember($Playfield->[$x][$y+1]) and SassyClassMember($Playfield->[$x-1][$y])))));
48 return StarterClassRules() || SassyClassRules() || 'Body'
49 };
50
51 sub SolvedStateRules {
52 return 'Space' if ((not ((SassyClassMember($Playfield->[$x][$y-1]) and SassyClassMember($Playfield->[$x+1][$y])) or (SassyClassMember($Playfield->[$x][$y-1]) and SassyClassMember($Playfield->[$x][$y+1])) or (SassyClassMember($Playfield->[$x][$y-1]) and SassyClassMember($Playfield->[$x-1][$y])) or (SassyClassMember($Playfield->[$x+1][$y]) and SassyClassMember($Playfield->[$x][$y+1])) or (SassyClassMember($Playfield->[$x+1][$y]) and SassyClassMember($Playfield->[$x-1][$y])) or (SassyClassMember($Playfield->[$x][$y+1]) and SassyClassMember($Playfield->[$x-1][$y])))));
53 return SassyClassRules() || SolutionClassRules() || 'Solved'
54 };
55
56 sub StartStateRules {
57 return StarterClassRules() || SustainerClassRules() || SassyClassRules() || 'Start'
58 };
59
60 sub FinishStateRules {
61 return SustainerClassRules() || SassyClassRules() || SolutionClassRules() || 'Finish'
62 };
63
64 sub SassyClassMember {
65 return $_[0] eq 'Head' ||
66 $_[0] eq 'Body' ||
67 $_[0] eq 'Solved' ||
68 $_[0] eq 'Start' ||
69 $_[0] eq 'Finish' ||
70 0
71 };
72
73 sub SolutionClassMember {
74 return $_[0] eq 'Solved' ||
75 $_[0] eq 'Finish' ||
76 0
77 };
78
79 sub StarterClassMember {
80 return $_[0] eq 'Head' ||
81 $_[0] eq 'Body' ||
82 $_[0] eq 'Start' ||
83 0
84 };
85
86 sub SustainerClassMember {
87 return $_[0] eq 'Slime' ||
88 $_[0] eq 'Head' ||
89 $_[0] eq 'Start' ||
90 $_[0] eq 'Finish' ||
91 0
92 };
93
94 $Appearance = {
95 'Body' => '?',
96 'Finish' => 'F',
97 'Head' => '-',
98 'Slime' => '%',
99 'Solved' => '@',
100 'Space' => ' ',
101 'Start' => 'S',
102 'Wall' => '#',
103
104 };
105
106 $InputCodec = {
107 '?' => 'Body',
108 'F' => 'Finish',
109 '-' => 'Head',
110 '%' => 'Slime',
111 '@' => 'Solved',
112 ' ' => 'Space',
113 'S' => 'Start',
114 '#' => 'Wall',
115
116 };
117
118 $StateRule = {
119 'Body' => \&main::BodyStateRules,
120 'Finish' => \&main::FinishStateRules,
121 'Head' => \&main::HeadStateRules,
122 'Slime' => \&main::SlimeStateRules,
123 'Solved' => \&main::SolvedStateRules,
124 'Space' => \&main::SpaceStateRules,
125 'Start' => \&main::StartStateRules,
126 'Wall' => \&main::WallStateRules,
127
128 };
129
130 load_playfield($ARGV[0]);
131
132 display_playfield();
133
134 while (!$done)
135 {
136 process_playfield();
137 display_playfield();
138 }
139
140 exit(0);
141
142 ### END ###
+23
-0
src/jaccia.alp less more
0 /*
1 * The Jaccia automaton, expressed in ALPACA.
2 * Inspired by the Scientific Announcement that
3 * Slime Molds are Intelligent Maze-Solvers.
4 * April 11 2009, Chris Pressey, Cat's Eye Technologies.
5 */
6
7 class Sustainer;
8
9 state Space " ";
10 state Wall "#"; /* purely decorative */
11 state Food "F"
12 is Sustainer;
13 state Food2 "S"
14 is Sustainer;
15 state Slime "%"
16 is Sustainer
17 to Space when not ((^ is Sustainer and > is Sustainer) or
18 (^ is Sustainer and v is Sustainer) or
19 (^ is Sustainer and < is Sustainer) or
20 (> is Sustainer and v is Sustainer) or
21 (> is Sustainer and < is Sustainer) or
22 (v is Sustainer and < is Sustainer)).
+80
-0
src/jacciata.alp less more
0 /*
1 * The Jacciata automaton, expressed in ALPACA.
2 * Inspired by Jaccia.
3 * April 11 2009, Chris Pressey, Cat's Eye Technologies.
4 */
5
6 class Starter;
7 class Sustainer;
8 class Sassy;
9 class Solution;
10
11 state Space " ";
12 state Wall "#"; /* purely decorative */
13
14 /*
15 * Slime stays alive so long as there is sustenance (food, or more slime, or the
16 * head of an exploratory shoot) on at least two sides. Slime turns into an
17 * exploratory head if there is adjacent starter material.
18 */
19 state Slime "%"
20 is Sustainer
21 to Space when not ((^ is Sustainer and > is Sustainer) or
22 (^ is Sustainer and v is Sustainer) or
23 (^ is Sustainer and < is Sustainer) or
24 (> is Sustainer and v is Sustainer) or
25 (> is Sustainer and < is Sustainer) or
26 (v is Sustainer and < is Sustainer))
27 or /* this part lets conflicts be resolved */
28 ((^ Head and > Head) or
29 (^ Head and v Head) or
30 (^ Head and < Head) or
31 (> Head and v Head) or
32 (> Head and < Head) or
33 (v Head and < Head)),
34 to Head when (v is Starter or ^ is Starter or > is Starter or < is Starter);
35
36 state Head "-"
37 is Starter
38 is Sustainer
39 is Sassy
40 to Body;
41
42 /*
43 * Body does not provide sustenance for slime.
44 * Body becomes solved cells when adjacent to a solution.
45 * Body stays alive so long as there is sassy on at least two sides;
46 * sassy is head, more body, or food, or a solved cell.
47 */
48 state Body "?"
49 is Starter
50 is Sassy
51 to Solved when (v is Solution or ^ is Solution or > is Solution or < is Solution),
52 to Space when not ((^ is Sassy and > is Sassy) or
53 (^ is Sassy and v is Sassy) or
54 (^ is Sassy and < is Sassy) or
55 (> is Sassy and v is Sassy) or
56 (> is Sassy and < is Sassy) or
57 (v is Sassy and < is Sassy));
58
59 /*
60 * Solved cells survive on the same rules as body cells.
61 */
62 state Solved "@"
63 is Sassy
64 is Solution
65 to Space when not ((^ is Sassy and > is Sassy) or
66 (^ is Sassy and v is Sassy) or
67 (^ is Sassy and < is Sassy) or
68 (> is Sassy and v is Sassy) or
69 (> is Sassy and < is Sassy) or
70 (v is Sassy and < is Sassy));
71
72 state Start "S"
73 is Starter
74 is Sustainer
75 is Sassy;
76 state Finish "F"
77 is Sustainer
78 is Sassy
79 is Solution.