wolf@mel.cipl.uiowa.edu (08/20/90)
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. Thanks! MJW
mnykanen@cc.helsinki.fi (08/21/90)
In article <1990Aug20.080738.1@mel.cipl.uiowa.edu>, 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. Seeing you post from .edu (University of Iowa?), let's get theoretical.. Let's turn the problem around: suppose that you have decided the number of the rooms in a level. Now build a complete graph with rooms as nodes and corridors as edges. Then simply apply any spanning tree algorithm selecting the next edge at random. There you have a maze in which each room is connected to each other (alhough there is only one route from one room to another, but you can add some random corridors for cycles if you wish) - just figure out how to draw it on a plane.. Or build a connected, planar graph (e.g. adding corridors between neighboring rooms only, assuming you fix the room coodinates beforehand) instead of the complete one to simplify drawing by making the initialization a bit trickier.. The probably are better methods, but the parts for this one can be found via (almost) any data structure book. I have tested this and it does generate correct mazes quite fast, but I haven't tested the 'playability' of the results.. -- Matti Nyk{nen CS Student at Helsinki U, Finland Trepanation! email: mnykanen@cc.helsinki.fi
trebor@biar.UUCP (Robert J Woodhead) (08/21/90)
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. |