[MUD-Dev] Re: AFAP: As fast as possible, non linear...

[quzah]

From: Mik Clarke <mikclrk at ibm.net>
Date: Tuesday, December 15, 1998 3:56 PM


>Thinking about it, I'm not convinced that your algorythm will always
>generate a solvable maze.  Condiser:
>
> A-O-O-O O-O
>   | | | | |
>   O-O-O O-O
>   |     | 
>   O-O O-O-O
>   | | | | |
>   O-O O-O-O-B
>
>I think this would meet your loop exit crietria (used = 100), but it is
>not possible to get from A to B.  This could pose something of a problem
>for your players...
>
>Mik


Greetings everyone. I've got a simple maze generator working if anyone
cares to take a peek at it. I replied to this message because it is the
last one in this thread that I have saved. Anyway, regarding the above,
yes, the old method was really bad and I scrapped it all together. This
is what I do now:

(1) Store only the inner E and S walls for each row. This fits nicely
into a short integer for an 8x8 maze, requiring only 15 bits of each
short integer. The even bits (starting with bit0) are used for "south
walls" and the odd bits (starting with bit1) are used for "east walls".

(2) I only check east and south when generating the maze. If the room
to the east is unused, or south is unused, pick one and remove the wall.

I "cheat recurrsion" by using a switch/loop, and avoid any overhead that
the recurrsion normally would produce. In addition, I was (I'm sure it
was very inefficient) running out of stack space in the early versions
of the old generator, and this avoids that aspect all together.

The outer wall of the maze is never used. In addition, it is not even
stored. It is assumed, and therefore it is never needed. Since it is
not needed, why bother keeping track of it?

I have uploaded the first releasable version (read: working, ok-ish)
to the below two links, if anyone wants to check it out/comment on it:

<url:http://members.xoom.com/quzah/qmaze1.c>
<url:http://members.xoom.com/quzah/qmaze1.h>

Its purpose is simplicity, with mock elegance, while retaining a vast
number overexplaining comments. Enjoy. (And feel free to comment on it,
as I like to have my stuff ripped to shreds ;)

Quzah.