Fill-area-with-rooms & Maze - algorithms?
Matti Hirvonen
I need help with these dungeon building algorithms:
1. Area completely filled with rooms (and possibly corridors)
Square area to be COMPLETELY filled with random sized rooms (and possibly
corridors), which are connected with doors or similar so that every room is
enterable. Examples could be a castle or a tower. Yes, it would be easy to
use the normal random dungeon generator inside the area bounds but then it
would leave most of the space unused.
2. Maze
Everyone knows mazes. How do you generate "interesting" mazes?
Hansjörg Malthaner
>
> (sorry for my bad english, I hope you'll get the point)
>
> I need help with these dungeon building algorithms:
>
> 1. Area completely filled with rooms (and possibly corridors)
>
> Square area to be COMPLETELY filled with random sized rooms (and possibly
> corridors), which are connected with doors or similar so that every room is
> enterable. Examples could be a castle or a tower. Yes, it would be easy to
> use the normal random dungeon generator inside the area bounds but then it
> would leave most of the space unused.
What about a subdivision method?
1) Make a big room.
2) Choose a random point inside
3) make walls from this point to the outer walls.
-> Now you got 4 different rooms of different size.
4) Recusrisoively apply 1-3 to the new rooms. Stop randomly or on a lower
bound of room size.
After this you 'just' need to put some doors into the walls.
> 2. Maze
>
> Everyone knows mazes. How do you generate "interesting" mazes?
No idea ... once I found a C code snippet on the web that generated fine,
but ordiray, mazes, but I have lost the links.
If an ordinary maze is not sufficient, what properties must a 'ineresting'
maze have?
c.u.
Hajo
VS
>> 2. Maze
>>
>> Everyone knows mazes. How do you generate "interesting" mazes?
> No idea ... once I found a C code snippet on the web that generated fine,
> but ordiray, mazes, but I have lost the links.
> If an ordinary maze is not sufficient, what properties must a 'ineresting'
> maze have?
An empty maze isn't interesting, no matter which algorithm made it.
+Cinquo
Chip Bell
news:aYzE7.217$iK1....@read2.inet.fi:
> (sorry for my bad english, I hope you'll get the point)
>
> I need help with these dungeon building algorithms:
>
> 1. Area completely filled with rooms (and possibly corridors)
>
> Square area to be COMPLETELY filled with random sized rooms (and
> possibly corridors), which are connected with doors or similar so that
> every room is enterable. Examples could be a castle or a tower. Yes, it
> would be easy to use the normal random dungeon generator inside the
> area bounds but then it would leave most of the space unused.
If all the rooms are rectangles, this should be pretty easy. Start in the
top left space, and generate a rectangle of random size. Then move along to
the right until you find the next unbuilt space, and make a new rectangle.
Continue, checking each space from left to right, top to bottom, making a
new room whenever there's empty space, until every space is filled. If a
rectangle ever doesn't fit in your bounds, rather than make a new random
size, shrink the size until it does fit. Then add your doors, doing flood-
fills to see if you can get to every room.
> 2. Maze
>
> Everyone knows mazes. How do you generate "interesting" mazes?
>
You could try a standard maze making algorithm, that I'm sure you can find
on the net, that fills an entire given area with corridors. Then you just
overlay your rooms onto the maze, essentially carving them out, to be the
interesting places to go.
Björn Bergström
"Matti Hirvonen" <matti.h...@pp1.inet.fi> skrev i meddelandet
news:aYzE7.217$iK1....@read2.inet.fi...
Take a look at http://www.ai.mit.edu/~shivers/mazes.html. This is a good
startingpoint with links to more sites of interest...
--
Björn Bergström - dungeon...@swipnet.se
Dungeondweller RLG and Roguelike Development Articles at
http://home.swipnet.se/dungeondweller/index.htm
Hansjörg Malthaner
>
> Matti Hirvonen wrote:
> >
> > (sorry for my bad english, I hope you'll get the point)
> >
> > I need help with these dungeon building algorithms:
> >
> > 1. Area completely filled with rooms (and possibly corridors)
> >
> > Square area to be COMPLETELY filled with random sized rooms (and possibly
> > corridors), which are connected with doors or similar so that every room is
> > enterable. Examples could be a castle or a tower. Yes, it would be easy to
> > use the normal random dungeon generator inside the area bounds but then it
> > would leave most of the space unused.
>
> What about a subdivision method?
>
> 1) Make a big room.
> 2) Choose a random point inside
> 3) make walls from this point to the outer walls.
> -> Now you got 4 different rooms of different size.
> 4) Recusrisoively apply 1-3 to the new rooms. Stop randomly or on a lower
> bound of room size.
>
> After this you 'just' need to put some doors into the walls.
Over the weekend I've tested this. It works ... it produces a sqaure full of
rooms of different size and shape. Somehow I don't like the result, but I
can't say why, it does exactly what is is supposed to do.
It seems to be tricky to place the doors so that every room can be reached
from a given starting point. Any ideas how to place the doors?
c.u.
Hajo
Andrew
> Take a look at http://www.ai.mit.edu/~shivers/mazes.html. This is a
good
> startingpoint with links to more sites of interest...
Having looked at one of the algorithms on this site yesterday, I would
highly recommend it. Starting from scratch I had a working program in 5
hours (using a rather inappropriate language, too), generating mazes of
any size. I think the algorithm would be very fast (~0.1s?) for an
80x20 screenful.
The concept is really simple, and the memory overhead is negligible when
generating.
edou...@gmx.net
> > After this you 'just' need to put some doors into the walls.
>
> Over the weekend I've tested this. It works ... it produces a sqaure full of
> rooms of different size and shape. Somehow I don't like the result, but I
> can't say why, it does exactly what is is supposed to do.
>
> It seems to be tricky to place the doors so that every room can be reached
> from a given starting point. Any ideas how to place the doors?
I would probably try placing them at the same time I placed the subdividing walls. If every subdivision wall has a door or hole in it, every room should be reachable. For variation you could have extra doors on long
walls, but I imagine this approach may prove limited in the long term...
--jude.
Judy Wray
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
Bru, Pierre
TIA,
Pierre.
"Judy Wray" <j.k....@worldnet.att.net> wrote in message news:<h9QO7.141876$WW.90...@bgtnsc05-news.ops.worldnet.att.net>...
Graeme Dice
>
> (sorry for my bad english, I hope you'll get the point)
>
> I need help with these dungeon building algorithms:
>
> 1. Area completely filled with rooms (and possibly corridors)
>
> Square area to be COMPLETELY filled with random sized rooms (and possibly
> corridors), which are connected with doors or similar so that every room is
> enterable. Examples could be a castle or a tower. Yes, it would be easy to
> use the normal random dungeon generator inside the area bounds but then it
> would leave most of the space unused.
I have a parameter in one of my algorithims that sets the percentage of
the map that you want to be filled with rooms and corridors. Set it
high enough, and use small enough rooms and hallways and it will fill
almost all of the map.
It also has a timeout counter though in case it can't fill the map in a
reasonable amount of time.
Graeme Dice
--
"READ THIS BEFORE OPENING PACKAGE: According to certain suggested
versions of the grand unified theory, the primary particles
constituting this product may decay to nothingness within the
next 10^32 Years." — Engineering warning labels.
Mark 'Kamikaze' Hughes
> 1. Area completely filled with rooms (and possibly corridors)
> Square area to be COMPLETELY filled with random sized rooms (and possibly
> corridors), which are connected with doors or similar so that every room is
> enterable. Examples could be a castle or a tower. Yes, it would be easy to
> use the normal random dungeon generator inside the area bounds but then it
> would leave most of the space unused.
The original Rogue algorithm works amazingly well for this:
1) Divide the map into a grid (Rogue uses 3x3, but any size will work).
2) Give each grid a flag indicating if it's "connected" or not, and an
array of which grid numbers it's connected to.
3) Pick a random room to start with, and mark it "connected".
4) While there are unconnected neighbor rooms, connect to one of them,
make that the current room, mark it "connected", and repeat.
5) While there are unconnected rooms, try to connect them to a random
connected neighbor (if a room has no connected neighbors yet, just
keep cycling, you'll fill out to it eventually).
6) All rooms are now connected at least once.
7) Make 0 or more random connections to taste; I find rnd(grid_width)
random connections looks good.
8) Draw the rooms onto the map, and draw a corridor from the center of
each room to the center of each connected room, changing wall blocks
into corridors. If your rooms fill most or all of the space of the
grid, your corridors will very short - just holes in the wall.
9) Scan the map for corridor squares with 2 bordering walls, 1-2
bordering rooms, and 0-1 bordering corridor, and change those to
doors.
10) Place your stairs up in the first room you chose, and your stairs
down in the last room chosen in step 5. This will almost always be
a LONG way away.
All done!
Rogue also has "gone rooms", which just put a corridor space instead
of the room, and draws L-shaped corridors instead of straight lines, but
those are just flavor.
This algorithm also has the virtues of being extremely fast (even on
MUCH bigger grid arrays than 3x3), and guaranteed to succeed.
--
<a href="http://kuoi.asui.uidaho.edu/~kamikaze/"> Mark Hughes </a>
"No one is safe. We will print no letters to the editor. We will give no
space to opposing points of view. They are wrong. The Underground Grammarian
is at war and will give the enemy nothing but battle." -TUG, v1n1