While
the size of the maze makes it particularly convenient for storage and manipulation
inside the controller, it is not the most friendly thing for people to work
with.

If you want to print a copy of a maze to fill in by hand (hey – it passes
time šŸ™‚ or if you want to post a maze to a newsgroup or send it to a friend,
then you will need to convert it to printable characters.

There are several schools of though on the best printed representation.
If you don’t like mine then you are free to pick an alternative.

Using a single character for a post and another character for a wall
will get the job done but it doesn’t look too good as the characters have
different heights and widths. You must use a fixed pitch font or there
is no guarantee that the characters will all turn out the same width anyway.
My preference is to use two characters for the NORTH/SOUTH walls and just
one for the EAST/WEST walls.

A typical maze might look like this:

+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+F0 | | + +–+–+–+–+–+–+–+–+–+–+–+ +–+ +–+E0 | | | | + + + +–+–+–+–+–+–+–+ +–+–+–+ + +D0 | | | | | | + + + +–+–+–+–+–+–+–+–+–+–+ + + +CO | | | | | | | | | + + + + + + +–+–+–+–+–+ + + + + +B0 | | | | | | | | | | | | + + + + + + + + +–+–+ + + + + + +A0 | | | | | | | | + +–+ + + + + + +–+–+ +–+–+ +–+ +90 | | | | | | | | | | | | + + + + + + + +–+–+ + + +–+–+ + +80 | | | | | | | | | | | | | | | + + + + + + + + + + + + + + + + +70 | | | | | | | | | | | + + + +–+–+–+ +–+ +–+–+ + + + +–+60 | | | | | | | | | | + + +–+ +–+ + +–+–+–+ + + +–+ + +50 | | | | | | | | | + + + + + + +–+ +–+ +–+–+–+ + + +40 | | | | | | | | + + + + +–+ +–+–+ +–+ +–+–+–+–+ +30 | | | | | | | +–+–+–+–+ +–+–+ +–+–+–+–+–+ +–+ +20 | | | | + +–+–+ +–+ +–+–+ +–+–+ +–+–+ + +10 | | | | | + + +–+–+–+–+–+ + +–+–+–+–+–+–+ +00 | | | | +–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+ 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F

The code needed to create this view of the maze is not too complicated.
All you have to do is run through the maze from top to bottom, row by
row. Each row is used to generate two strings -one for the north walls
and posts, the other for the west walls. At the end of the row, add on
the last post and wall to each string. Output the two strings and move
on to the next row. You will need to add the southern most wall as a special
case at the end.

Reading a text maze is not too hard either. It is worth taking the trouble
to handle common formats. The very first character will be the one used
for posts, the next character will be the one used for N/S walls. The
character after that will tell you if one or two characters are used per
cell. The first character of the next line tells you what is being used
for the W/E walls. After that, treat the file as pairs of lines. Examine
each one at predetermined positioned to check for the presence/absence
of walls.

 

This Post Has One Comment

  1. Tom Hunt

    Many thanks for taking the time to make all this great information available. I design and build small, cheap robots as a hobby. I rely heavily on great sites like this.

    I wrote a quick Python maze generator. It will place a virtual mouse and solve the maze step by step. It prints each step, using a version of your ASCII format. In the middle of each tile, I update the value the mouse currently knows for that cell. The “mouse” only becomes aware of cells/walls as it enters the cell.

    Like you, I found that I do not need to pre-value every cell in the map. Instead, I assign each cell an initial value of 255 as the “mouse” enters the cell. I found the depth of recursion and speed of solve to be much faster if I track what cells have been visited. If a cell has not been visited by the “mouse” before, It will not be placed on the floodFill stack.

    With this method, I was able to solve the APEC 1993 example you provided very quickly. The maximum stack level was 148. I was wondering, are there any pitfalls to this approach?

    As a side question, I noticed references to employing a Microchip Pic as the main processor/solver. As this type of exercise seems to require a minimum of 3 arrays/stacks of up to 256 for one, at least 148 for the stack ( probably larger ), and two of 256, I was wondering how this is managed on the 8 bit Pics? Do you use external Ram chips?

    Thanks again!

    Tom Hunt

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.