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

[Jon Leonard]

On Sun, Dec 13, 1998 at 10:45:49PM -0800, quzah [softhome] wrote:
> Hiya all.
> 
> I'm finishing up a tiny maze generator, and all I need is a
> tad bit of a speed gain. (Or more than a tad. :) I'm using
> a 10x10x10 cube, generated a plane at a time (10x10). I am
> linking them through one exit per plane (up/down), with the
> bottom level's exit leading "out". Here's the basic rundown:

As has been pointed out, this is the sort of thing to check the web
for.  There's not a lot of point writing a maze generator unless you
want the experience of having writtten one.

I've done one myself, of course...  I just put up the source at
http://www.slimy.com/~jleonard/src/maze.html and you can see resulting
mazes at http://www.slimy.com/cgi-bin/cgiwrap/~jleonard/maze.  It's PD.

It runs quickly: the speed is adequate on my PalmIII (with its wimpy
processor) and a 20x30 maze takes 0.002 seconds on my main computer.

For this kind of problem, picking the right algorithm helps immensely.
My code keeps an list of things to look at (stored in an array for speed,
of course), and keeps from looking at the same edge twice by removing it
from the list when it gets checked.  I have a similar tweak in my
connectivity check code.  The amount of work done is at most a small
constant times the number of things to look at.

The other thing to consider is if you really want a maze with no loops...
There are simple maze-solving algorithms that fail with loops, and in
general carefule maze design can make better mazes.

You might also consider doing a maze where up and down are treated the
same way as north, south, east and west.

[Quzah's algorithm snipped]

> That about does it. The only thing I don't like about it is that
> that I have a crappy way of getting the new coords for the next
> recursive call. I'm currently using:
> 
>    mazePunch( number_range(0,9), number_range(0,9), FALSE );
> 
> Now, I know there has to be a much faster, non linear way to do
> this, but I haven't thought of it yet, so I though it time I got
> a bit of help for this snippet. :) The rest I'm pretty pleased
> with. I'm thinking it should be pretty fast if I get around the
> coord picking I'm using now. So, does anyone have a quick way
> to grab a zero coord? (Oh, hmm, I just thought of a way I'll
> try, but I'll post this anyway. I'll just run the list of used
> and grab a random one of those with a zero neighbor. -- Anyway
> while I try that, does anyone have any other faster/better ways
> to do the coord grabbing?)

Jon Leonard