Re: finite maze solving algorithm

From: conesetter (conesetter_at_btopenworld.com)
Date: 12/01/04 

Date: 1 Dec 2004 10:59:14 -0800

michalchik@aol.com (Michael Michalchik) wrote in message news:<20f4bb84.0411301849.18c69d1b@posting.google.com>...
> Kevin Saff <news@kevin.saff.net> wrote in message news:<I808DL.GF2@news.boeing.com>...
> > Michael Michalchik wrote:
> > > I was wondering if anyone knows if all possible topologies of finite
> > > 2d mazes can be solved by a finite algorithm. For example, we know
> > > that all fully connected mazes can be solved by picking a wall and
> > > exhaustively following it. Can a general solution work for all mazes
> > > including the ones that are piecewise disconnected? If this is
> > > possible, is the general solution a solved problem?
>
  A maze with n walls is homeomorphic to the n-times punctured plane.
So the method of cuts used by Cauchy to derive a simply-connected
domain can be applied. The cuts in this instance become barriers
joining the walls in some sequence, the last one getting a final
barrier going off to infinity. Then any two points in the maze can be
joined by a path which is homotopically unique.
  The method of Tremaux noted in the Wikipedia Maze article may amount
to the same thing but with the barriers introduced on the run rather
than in advance.

Relevant Pages

  • Re: How to improve my 3DMaze codes performance?
    ... My maze is 30*30, and there are about several hundreds of walls in the ... When i use the texture mapping for each wall, the fps drops to ...
    (comp.graphics.api.opengl)
  • Re: Making a maze....
    ... # I just removed some unused functions -- Georgy Pruss 20031118-002204 ... import Maze ... # A maze cell is a vector of three items: ... # (for top and left walls refer to upper and left cells resp.) ...
    (comp.lang.python)
  • Re: Mazes
    ... The exact characteristics of the maze can be ... You can increase the connectivity by later destroying some of the walls. ... You can put exits anywhere, as long as they align with rooms (i.e. have ... You could try a more free-from version of this algorithm -- that is, ...
    (rec.games.roguelike.development)
  • Re: Running Mazes
    ... >> Another point is that both need an abundance of clues. ... >it's not really a maze. ... A 200 ft x 200 ft empty room with the exit door on the far side isn't ... all the walls are painted so as to make each 5 ft section of wall ...
    (rec.games.frp.dnd)
  • Re: finite maze solving algorithm
    ... A maze with n walls is homeomorphic to the n-times punctured plane. ... So the method of cuts used by Cauchy to derive a simply-connected ... The cuts in this instance become barriers ...
    (comp.theory)