Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!mips!decwrl!ucbvax!bloom-beacon!eru!luth!sunic!tut!hydra!hylka!mnykanen
From: mnykanen@cc.helsinki.fi
Newsgroups: comp.sys.mac.programmer
Subject: Re: Dungeon Creating Algorithms
Message-ID: <2944.26d0f821@cc.helsinki.fi>
Date: 21 Aug 90 09:00:16 GMT
References: <1990Aug20.080738.1@mel.cipl.uiowa.edu>
Organization: University of Helsinki
Lines: 22

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