Flag of the United Kingdom
Andreas Rejbrands webbplats

Aktuellt

Cellular automaton maze generation

Among the 262144 possible life-like cellular automaton rules, quite a few generate mazes of various kinds. Among these, two are particularly well-known and are even named: “Maze” (B3/S12345) and “Mazectric” (B3/S1234). From an initial soup, these quickly make stationary mazes with the occasional oscillating corner (not shown below):

Maze:

Maze

Mazectric:

Mazectric

I do not know why these two have been selected from the large number of maze-generating rules. In fact, I do not even consider them to be good examples of such rules, because the corridors they make are highly disconnected. This can be seen by trying a few flood-filling operations on the bitmaps:

Maze:

Maze

Mazectric:

Mazectric

Clearly, given two arbitrary points A and B in such a maze, it is highly unlikely that there is a path from A to B. (It appears like the situation gets better in the B3/S12345 (“Maze”) case if you reinterpret the white cells as the walls, but not very much.)

There are life-like maze-generating rules that create much better mazes in this regard, such as the B2(7)(8)/S(0)123(5)(6)(7)(8) rules. Below B2/S123 is shown:

B2/S123:

B2/S123

Trying a single flood-fill operation shows that this maze is much nicer (unless you are unlucky):

B2/S123:

B2/S123


Visa alla tidigare notiser.

Visa enbart de senaste notiserna.