Path: utzoo!attcan!utgpu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!rpi!gordon From: gordon@aix02.aix.rpi.edu (Gordon E. Greene) Newsgroups: alt.sources.d Subject: Re: Maze generation Keywords: how-to maze generate program wanted Message-ID: Date: 17 Dec 90 18:01:48 GMT References: <1215@syacus.acus.oz> <1990Dec13.190759.9297@craycos.com> <1990Dec14.001604.20990@informix.com> <1990Dec17.142513@avahi.inria.fr> Organization: Rensselaer Polytechnic Institute, Troy NY Lines: 22 Nntp-Posting-Host: aix02.aix.rpi.edu Perhaps a clarification is required about my posting. I received several messages about it. My contention that a non-tree maze is not solvable by trailing hand refers to mazes that don't have both the entry and exit on the outside. My starting point for this was an old book of mazes I once had. Many of the mazes had both entry and exit inside the maze. Some of them were not planar: that is they had corridors that passed over and under each other. It wouldn't be so tough to encode these mazes by labelling all the intersections, putting the maze into some graph representation, and then doing a path search through it from the start node to the end node. I think you'll agree that this would take a lot of the challenge out of doing mazes though. Breadth-first and depth-first searches would both find a path through, and variations to find the best (whatever best means) path could be implemented too. Sorry for any confusion that may have arisen from my incomplete description. -- --------- You can never have too many ferrets. ----------- gordon@rpi.edu USERF023@RPITSMTS USERF023@mts.rpi.edu