[OT] The algorithm (was Re: Making a maze....)

[Georgy Pruss]

"Phil Schmidt" <phil_nospam_schmidt at yahoo.com> wrote in message news:221e7b06.0311181038.65348fab at posting.google.com...
| "Georgy Pruss" <see_signature__ at hotmail.com> wrote in message news:<D3iub.11560$C14.852546 at twister.southeast.rr.com>...
| > Couldn't resist either :-)
| >
| >
| < -snip code- >
|
|
| Hey, that's very pretty too! Very cool!
|
| Would you care to explain the algorithm? Sure, I can read your
| references, or reverse-engineer it, but I'll have to save that
| exercise for later, when I have some more time. I want immediate
| gratification!  ;)

Hehe, you want me to have an exercise in English? :) OK.

Every cell of the maze remembers if the right and the bottom walls
are present. This information is already enough to draw the maze.
Then, for the recursive algorithm, it was enough that each cell could
tell if it was visited or not. If we want an iterative algorithm, then we
require more. We want each cell to save some useful information,
namely, the direction where we came from to this cell. Then we can
do backtracking just reading the maze itself. Thus, each cell should
contain the direction from where it was visited first, or if there's no
such data, the cell hasn't been visited yet (and will look green :)).

The algorithm starts at an arbitrary point. Then we determine where
it's possible to move physically, i.e. we consider only physical limits:
the outer walls of the maze. Then we go through all the potential
directions in random order and look for any adjacent cell that hasn't
been visited yet. If there's such a cell, we ruin the wall between the
cells, and save the direction *back* to the current cell in that new cell.
We move there and repeat from the beginning. If there's no free cell
around, we step one move back and try to repeat the algorithm.
This is when we need the direction where to return, and we take it
from the current cell. When we step back again and again and finally
reach to the first cell, it means that all the variants were tried and we
did all we could. Fortunatelly. it also means that all the cells were
visited and the full perfect path through the maze is built.

# We could save the original directions of the moves instead of the
# 'back' directions and inverse them while backtracking. It would just
# change the place of finding the inverse direction.

But probably the code is more precise and clear than my explanations. :)

G-:

p='p=;print p[:2]+chr(39)+p+chr(39)+p[2:]';print p[:2]+chr(39)+p+chr(39)+p[2:]

|
| I like the ASCII and HTML generation too.
|
| Thanks for the entertainment!
|
| (So, who's gonna tackle the hexagonal maze?)