Xref: utzoo alt.sources.d:1218 rec.games.misc:12942 rec.games.programmer:2733 Path: utzoo!attcan!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!udel!rochester!bbn.com!cosell From: cosell@bbn.com (Bernie Cosell) Newsgroups: alt.sources.d,rec.games.misc,rec.games.programmer Subject: Re: Maze generation Keywords: how-to maze generate program wanted Message-ID: <61714@bbn.BBN.COM> Date: 21 Dec 90 02:54:15 GMT References: <1990Dec15.122555.20420@cs.ubc.ca> <6WH^XJ_@rpi.edu> <21945@ttidca.TTI.COM> Sender: news@bbn.com Followup-To: alt.sources.d Lines: 31 gordon@itsgw.rpi.edu (Gordon E. Greene) writes: }In article <21945@ttidca.TTI.COM> alter@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\