Xref: utzoo alt.sources.d:1199 rec.games.misc:12894 rec.games.programmer:2720 Path: utzoo!attcan!lsuc!xenitec!maytag!watmath!watserv1!utgpu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!think.com!linus!philabs!ttidca!alter From: alter@ttidca.TTI.COM (Steve Alter) Newsgroups: alt.sources.d,rec.games.misc,rec.games.programmer Subject: Re: Maze generation Keywords: how-to maze generate program wanted Message-ID: <21945@ttidca.TTI.COM> Date: 18 Dec 90 02:28:13 GMT References: <1215@syacus.acus.oz> <1990Dec15.122555.20420@cs.ubc.ca> <6WH^XJ_@rpi.edu> Organization: Citicorp/TTI, Santa Monica Lines: 33 In article <6WH^XJ_@rpi.edu> gordon@itsgw.rpi.edu (Gordon E. Greene) writes: } Even more general than this is to observe that any maze (in a plane) is a } conected planar graph. If one started the algorithm with a random connected } planar graph and then just drew it, one would have a maze. This method can } give mazes with loop corridors in them. The tree algorithms give only simple } mazes (right hand on the wall to get out). A more general planar graph can } give mazes which the trailing hand method won't solve.... } } gordon@rpi.edu USERF023@RPITSMTS USERF023@mts.rpi.edu 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. Related topic: I remember a program that generates a 2-level maze, in which passages can cross over each other, and to some extend, two passages can even run in vertical parallel because the upper one is painted narrower than the lower. The generator paints such a maze by growing all branches simultaneously, and the graphic effect is really strange! Rather than solving it, the program let's you mouse through it with no help. Anybody else heard of such a sadistic piece of code? -- Steve Alter {philabs,psivax,pyramid,quad1,rdlvax,retix,rutgers}!ttidca!alter Citicorp/TTI, Santa Monica CA (213) 450-9111 x2541