# User:Duerig/Archive8

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

# 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