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