From: hiebeler@santafe.edu
Date: Wed Mar 24 1993 - 08:42:23 UTC
> Date: Mon, 22 Mar 93 00:46:03 MEX > From: "Harold V. McIntosh" <MCINTOSH@unamvm1.dgsca.unam.mx> > > There is a variant on this theme which might be called 'MazeWorld' > which is also two dimensional. Most cells are either background, and > never change, or define the layout; these can be modified slightly > to follow progress through the maze. Finally there are entrance and > exit cells. A couple of years ago, I wrote a simple rule on the CAM-PC which solved mazes; it was basically a parallel tree search, where there was an "active" cell at the entrance, and any hallway-cell next to the active cell became active. Dead-ends produced a "death" cell which would erase the trail back to the most recent branch. When you let it run, the thing would fan out down the hallways but erase dead-ends, leaving you with a marked trail from the entrance to the exit. There were some kinds of mazes which it wouldn't solve, but I forget just which kinds (or at least there were "messy" mazes which would cause some bad trails to not get erased). > It is probably harder to prepare good, large, intricate mazes than > it is to write the rules for this automaton. One way to generate > mazes is to let one of the growth-type rules produce something, then > switch over to the maze runner. That's for sure, generating the mazes was a real pain. I never came up with a good CA rule for automatically generating them, unfortunately. -- Dave Hiebeler Santa Fe Institute, and Thinking Machines Corporation hiebeler@santafe.edu, hiebeler@think.com
This archive was generated by hypermail 2.1.7 : Tue Oct 14 2003 - 21:44:10 UTC