2

I am writing a maze generation algorithm, and this wikipedia article caught my eye. I decided to implement it in java, which was a cinch. The problem I am having is that while a maze-like picture is generated, the maze often is not solvable and is not often interesting. What I mean by interesting is that there are a vast number of unreachable places and often there are many solutions.

I implemented the 1234/3 rule (although is is changeable easily, see comments for an explanation) with a roughly 50/50 distribution in the start. The mazes always reach an equilibrium where there is no change between t-steps.

My question is, is there a way to guarantee the mazes solvability from a fixed start and endpoint? Also, is there a way to make the maze more interesting to solve (fewer/one solution and few/no unreachable places)? If this is not possible with cellular automata, please tell me. Thank you.

Eric Thoma
  • 5,905
  • 6
  • 30
  • 40

3 Answers3

3

I don't think it's possible to ensure a solvable, interesting maze through simple cellular automata, unless there's some specific criteria that can be placed on the starting state. The fact that cells have no knowledge of the overall shape because each cell won't be able to coordinate with the group as a whole.

If you're insistent on using them, you could do some combination of modification and pathfinding after generation is finished, but other methods (like the ones shown in the Wikipedia article or this question) are simpler to implement and won't result in walls that take up a whole cell (unless you want that).

Community
  • 1
  • 1
CheeseWarlock
  • 1,361
  • 1
  • 10
  • 11
1

the root of the problem is that "maze quality" is a global measure, but your automaton cells are restricted to a very local knowledge of the system.

to resolve this, you have three options:

  1. add the global information from outside. generate mazes using the automaton and random initial data, then measure the maze quality (eg using flood fill or a bunch of other maze solving techniques) and repeat until you get a result you like.

  2. use a much more complex set of explicit rules and state. you can work out a set of rules / cell values that encode both the presence of walls and the lengths / quality of paths. for example, -1 would be a wall and a positive value would be the sum of all neighbours above and to the left. then positive values encode the path distance from top left, roughly. that's not enough, but it shows the general idea... you need to encode an algorithm about the maze "directly" in the rules of the system.

  3. use a less complex, but still turing complete, set of rules, and encode the rules for maze generation in the initial state. for example, you could use conway's life and construct an initial state that is a "program" that implements maze generation via gliders etc etc.

if it helps any you could draw a parallel between the above and:

  1. ghost in the machine / external user
  2. FPGA
  3. programming a general purpose CPU
andrew cooke
  • 45,717
  • 10
  • 93
  • 143
0

Run a path finding algorithm over it. Dijkstra would give you a sure way to compute all solutions. A* would give you one good solution.

The difficulty of a maze can be measured by the speed at which these algorithms solve it.

You can add some dead-ends in order to shut down some solutions.

Samy Arous
  • 6,794
  • 13
  • 20
  • This is useful for determining the number of paths and the overall difficulty, but the cellular automata aren't generating mazes with any solutions- though Dijkstra's could be used to find a partial solution and decide where to alter the maze to keep it difficult. – CheeseWarlock May 18 '12 at 01:21
  • Both Dijkstra and A* will tell you if a solution exists, and if none exists, we still can generate one :) – Samy Arous May 18 '12 at 01:28