View source for User:Duerig/Archive8

= Fill-area-with-rooms & Maze - algorithms - Judy Wray [j.k.wray@worldnet.att.net] =

  Here is an algorithm I use (can't remember where I first saw the idea).
  It can generate a halfway decent castle-like environment with a few
tweaks, and can generate a maze as well. It's really simple. Just pick a
starting point within the array, choose a direction, and draw a wall in that
direction, stopping until you hit the edge of the maze or another wall. You
can tweak your maze by various means.


1) Selection of starting points.
  I use a setting, called Granularity, to choose points. If Granularity=1,
any old point can be chose, and the maze ends up as a solid chunk of wall in
most cases. If Granularity=2, then points are chosen on every other
row/column, so that spaces are left in between. Granularity=2 mazes generate
mazes with corridors one cell wide. The higher Granularity is, the wider the
corridors are made. Beware of "wierdness" if you choose Granularity which is
not a factor of maze size, or you can end up with skinny corridors on
borders, or doubled up walls.
(SX, SY) -- Wall starting point
SX=Granularity * (rand()%(MAPWIDTH/Granularity));
SY=Granularity * (rand()%(MAPHEIGHT/Granularity));

2) Wall length
  I like to set a minimum and maximum wall length when drawing walls. Many
walls, of course, will be stopped before the chosen length, but on average
your walls will fall within the range. Min=2 Max=4 would generate a maze
with a lot of tiny little walls, while Min=16 Max=32 would generate a maze
with generally long, straight corridors.

3) Number of walls
  You can modify maze density by changing the number of walls to draw. I
generally use N = number of walls to _attempt_ to draw, which will fail
gracefully if a suitable staring point can not be located. Starting points
are chosen only if the location is not already a wall, so it is possible to
get in an endless hang looking for a location when all available locations
are filled.
  A low number of walls results in lots of large, open rectangular areas,
while a high number progresses toward a full maze. For a perfect maze, pick
an arbitarily high number of walls (50000 or something like that) to attempt
to draw.
  The drawback to this as currently implemented is that the maps look only
generally castle-like. Enclosed, separate rooms are rare, as you'll see if
you try it. I like to mix this algorithm with one of placement of randomly
located "patterned" segments. In other words, I would place some special
rooms (vaults, thronerooms, dungeon cellblocks, etc...) then fill in the
remaining space with the former algorithm, using a Granularity of 4 or maybe
even 8, for broad corridors, and decent size siderrooms which could be store
rooms or the like. Levels tend to be rather boring if you don't mix algos.
  Anyway, hope this gives you some ideas of your own.

VertexNormal