Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!wuarchive!psuvax1!rutgers!rochester!cornell!biar!trebor
From: trebor@biar.UUCP (Robert J Woodhead)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Dungeon Creating Algorithms
Message-ID: <1165@biar.UUCP>
Date: 21 Aug 90 16:05:13 GMT
References: <1990Aug20.080738.1@mel.cipl.uiowa.edu>
Organization: Biar Games, Inc.
Lines: 47

wolf@mel.cipl.uiowa.edu writes:

>I would be interested in seeing a/some algorithm(s) that generate a dungeon
>maze, much the way the games NetHack and Moria do.  Does anyone have these just
>sitting around that they could send my way....Pascal source would be nice, Mac
>versions would be even better.

Here is how you do it.  What you really want to do is create functions that
tell you if there are walls n,s,e,w,u and d from your current x,y,z position
such that for a given xyz, you always get the same results, yet to the user,
the results look "good but random".  Consider a function such as this:

FUNCTION isWall(x,mx,dx,y,my,dy,z,mz,dz,cutoff:longInt):boolean;

var temp:integer;

begin

  temp := (x*mx) mod dx;
  temp := ((temp+y)*my) mod dy;
  temp := ((temp+z)*mz) mod dz;

  isWall:=((temp/32) mod 256)>=cutoff

end;

Where x,y,z are the coordinate you are interested in, mx,my,mz are "prime-ish"
multipliers (such as 173711 or 64591) and dx,dy,dz are also prime-ish.  Cutoff
is between 0 and 255.  A cutoff of 128 means there will be a wall there 
roughly half of the time.

Ok, now, for any xyz, there are only 3 directions you really need to worry
about, north, east and down.  This is because south, west and up are all
the same as n,e or d for an adjacent square.  For each of these directions
you whip up a different set of mx,my,mz,dx,dy,dz numbers, so the results
are different for the walls in a particular square.  Cutoffs can be adjusted
to change the "character" of the maze, depending on whether you want it
dense or sparse.  Oh, and don't forget about special-cases at the edges
of your maze.

This should get you started.  If you need further help, send me email.

-- 
+--------------------------------------------------------------------------+
| Robert J Woodhead, Biar Games, Inc.  !uunet!biar!trebor trebor@biar.UUCP |
| "The Force. It surrounds us; It enfolds us; It gets us dates on Saturday |
| Nights." -- Obi Wan Kenobi, Famous Jedi Knight and Party Animal.         |