Maze generation

[Bernie Cosell]

gordon at itsgw.rpi.edu (Gordon E. Greene) writes:

}In article <21945 at ttidca.TTI.COM> alter at ttidca.TTI.COM (Steve Alter) writes:
}>The right-hand-on-the-wall algorithm, in its simple form, won't be able
}>to solve all mazes with loops in them (i.e. a maze that is not uniquely
}>connected) but a simple modification to the algorithm can fix that.
}>Just remember every room you've visited, and as you're walking around,
}>if you see that you're about to step into an already visited room, then
}>just pretend that there's a wall in front of you and continue to apply
}>the right-hand rule.  After that, you can forget about that piece of
}>phantom wall, because the rooms on both sides of it have been visited.
}>

}I'm not sure I see how this keeps you from getting stuck in loops unless you
}switch hands when you've gone around once.

You missed the part "just remember every room you've visited" --- he's
just magically converted the algorithm from being a simple finite-state
one to being order (N^2) Once you've scaled the automaton to include
enough memory to, in essence, map the whole maze, there are lots of
algorithms that become available.

Finding a *finite*state* algorithm for an arbitrary maze is very
difficult.  The best I've seen is Manny Blum's algorithm: it will solve
an arbitrary planar maze with a finite-state-automaton with *two*
markers.  That is, the automaton has a few new operations [besides
"move left", "move right", etc] which are "drop a marker" and  "pick up
a marker". and a new input condiion: there is a marker in teh cell
you're in.

  /Bernie\