<!-- MHonArc v2.4.4 -->
<!--X-Subject: [MUD-Dev] Re: AFAP: As fast as possible, non linear... -->
<!--X-From-R13: Xba Zrbaneq <wyrbaneqNqvipbz.fyvzl.pbz> -->
<!--X-Date: Mon, 14 Dec 1998 23:27:13 -0800 -->
<!--X-Message-Id: 19981214212336.A13390#divcom,slimy.com -->
<!--X-Content-Type: text/plain -->
<!--X-Reference: 002001be272d$64aca440$a3066520@k6 -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, [MUD-Dev] Re: AFAP: As fast as possible, non linear...</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:jleonard#divcom,slimy.com">
</head>
<body background="/backgrounds/paperback.gif" bgcolor="#ffffff"
text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000">
<font size="+4" color="#804040">
<strong><em>MUD-Dev<br>mailing list archive</em></strong>
</font>
<br>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
<br clear=all><hr>
<!--X-Body-Begin-->
<!--X-User-Header-->
<!--X-User-Header-End-->
<!--X-TopPNI-->
Date:
[ <a href="msg00967.html">Previous</a>
| <a href="msg00969.html">Next</a>
]
Thread:
[ <a href="msg00967.html">Previous</a>
| <a href="msg00972.html">Next</a>
]
Index:
[ <A HREF="author.html#00968">Author</A>
| <A HREF="#00968">Date</A>
| <A HREF="thread.html#00968">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>[MUD-Dev] Re: AFAP: As fast as possible, non linear...</H1>
<HR>
<!--X-Subject-Header-End-->
<!--X-Head-of-Message-->
<UL>
<LI><em>To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI>
<LI><em>Subject</em>: [MUD-Dev] Re: AFAP: As fast as possible, non linear...</LI>
<LI><em>From</em>: Jon Leonard <<A HREF="mailto:jleonard#divcom,slimy.com">jleonard#divcom,slimy.com</A>></LI>
<LI><em>Date</em>: Mon, 14 Dec 1998 21:23:36 -0800</LI>
<LI><em>Cc</em>: Jon Leonard <<A HREF="mailto:jleonard#divcom,slimy.com">jleonard#divcom,slimy.com</A>></LI>
<LI><em>Reply-To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
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
<A HREF="http://www.slimy.com/~jleonard/src/maze.html">http://www.slimy.com/~jleonard/src/maze.html</A> and you can see resulting
mazes at <A HREF="http://www.slimy.com/cgi-bin/cgiwrap/~jleonard/maze">http://www.slimy.com/cgi-bin/cgiwrap/~jleonard/maze</A>. 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
</PRE>
<!--X-Body-of-Message-End-->
<!--X-MsgBody-End-->
<!--X-Follow-Ups-->
<HR>
<!--X-Follow-Ups-End-->
<!--X-References-->
<UL><LI><STRONG>References</STRONG>:
<UL>
<LI><STRONG><A NAME="00963" HREF="msg00963.html">[MUD-Dev] AFAP: As fast as possible, non linear...</A></STRONG>
<UL><LI><EM>From:</EM> "quzah [softhome]" <quzah#softhome,net></LI></UL></LI>
</UL></LI></UL>
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg00967.html">[MUD-Dev] Re: AFAP: As fast as possible, non linear...</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00969.html">[MUD-Dev] Re: AFAP: As fast as possible, non linear...</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00967.html">[MUD-Dev] Re: AFAP: As fast as possible, non linear...</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00972.html">[MUD-Dev] Re: AFAP: As fast as possible, non linear...</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00968"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00968"><STRONG>Thread</STRONG></A></LI>
</UL>
</LI>
</UL>
<!--X-BotPNI-End-->
<!--X-User-Footer-->
<!--X-User-Footer-End-->
<ul><li>Thread context:
<BLOCKQUOTE><UL>
<LI><strong><A NAME="00963" HREF="msg00963.html">[MUD-Dev] AFAP: As fast as possible, non linear...</A></strong>,
quzah [softhome] <a href="mailto:quzah#softhome,net">quzah#softhome,net</a>, Mon 14 Dec 1998, 06:41 GMT
<UL>
<LI><strong><A NAME="00966" HREF="msg00966.html">[MUD-Dev] Re: AFAP: As fast as possible, non linear...</A></strong>,
Mik Clarke <a href="mailto:mikclrk#ibm,net">mikclrk#ibm,net</a>, Tue 15 Dec 1998, 04:05 GMT
<UL>
<LI><strong><A NAME="00969" HREF="msg00969.html">[MUD-Dev] Re: AFAP: As fast as possible, non linear...</A></strong>,
Alex Oren <a href="mailto:alexo#bigfoot,com">alexo#bigfoot,com</a>, Tue 15 Dec 1998, 10:01 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00967" HREF="msg00967.html">[MUD-Dev] Re: AFAP: As fast as possible, non linear...</A></strong>,
Dan Shiovitz <a href="mailto:dbs#cs,wisc.edu">dbs#cs,wisc.edu</a>, Tue 15 Dec 1998, 06:18 GMT
</LI>
<LI><strong><A NAME="00968" HREF="msg00968.html">[MUD-Dev] Re: AFAP: As fast as possible, non linear...</A></strong>,
Jon Leonard <a href="mailto:jleonard#divcom,slimy.com">jleonard#divcom,slimy.com</a>, Tue 15 Dec 1998, 07:27 GMT
</LI>
<LI><strong><A NAME="00972" HREF="msg00972.html">[MUD-Dev] Re: AFAP: As fast as possible, non linear...</A></strong>,
Mik Clarke <a href="mailto:mikclrk#ibm,net">mikclrk#ibm,net</a>, Tue 15 Dec 1998, 23:36 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00960" HREF="msg00960.html">[MUD-Dev] small dev-mud invite</A></strong>,
Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Sun 13 Dec 1998, 23:28 GMT
<UL>
<LI><strong><A NAME="00961" HREF="msg00961.html">[MUD-Dev] Re: small dev-mud invite</A></strong>,
J C Lawrence <a href="mailto:claw#kanga,nu">claw#kanga,nu</a>, Mon 14 Dec 1998, 03:42 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00955" HREF="msg00955.html">[MUD-Dev] Re: Hex grids.</A></strong>,
quzah [softhome] <a href="mailto:quzah#softhome,net">quzah#softhome,net</a>, Sat 12 Dec 1998, 18:58 GMT
</UL></BLOCKQUOTE>
</ul>
<hr>
<center>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
</center>
<hr>
</body>
</html>
