Dungeon Generation Algorithm
Fenrir
placing rooms randomly about the map and connecting them with tunnels,
but pathfinding proved rather difficult. Now I'm trying Mike Aderson's
dungeon generation algorithm (http://
roguebasin.roguelikedevelopment.org/index.php?title=Dungeon-
Building_Algorithm), but I'm not having much more success. Is there a
simpler way? Should I keep trying to implement Mike Anderson's
algorithm, or maybe have another go at my initial plan?
Nik Coughlin
news:af83e555-3292-41a8...@d1g2000hsg.googlegroups.com...
Simon Richard Clarkstone
Note that some layouts won't happen with that algorithm. The smallest
example that comes to mind is:
+-----+
|111|2|
|---|2|
|3|4|2|
|3|---|
|3|555|
+-----+
But that shouldn't matter much.
--
Simon Richard Clarkstone:
s.r.cl?rkst?n?@dunelm.org.uk / s?m?n_cl?rkst?n?@yahoo.co.uk
| My half-daughter went to the GMH riots |
| But all I got was this stupid ･-shirt. |
jice
> "Fenrir" <siliconvik...@gmail.com> wrote in message
You even have a working C or C++ implementation of this algorithm in
libtcod 1.4 beta samples.
You can see it alive here (download the 1.4 beta and run
samples_c.exe, it's in the BSP module) :
http://jice.nospam.googlepages.com/thedoryenlibrary
Or you can watch the source code here (starting at line 750) :
http://code.google.com/p/libtcod/source/browse/trunk/samples_cpp.cpp
--
jice
Ray Dillinger
Here, have a cave generator. I wrote this, anybody can use it.
/* a simple program for generating caves. */
#include <stdio.h>
#include <stdlib.h>
#define X 60
#define XCENTER 30
#define Y 30
#define YCENTER 15
char map[X][Y];
int dieroll (int min, int max){
int randomnum;
int range = (max + 1 - min);
int divisor = RAND_MAX / range;
for (randomnum = random();
RAND_MAX-randomnum < RAND_MAX % range;
randomnum = random());
randomnum /= divisor;
return(randomnum + min);
}
void cavegen(){
int adjfloor;
int adjwall;
int uncommittedcount = X * Y - 1;
int wallcount = 0;
int floorcount = 1;
int x;
int y;
int xmin = XCENTER - 1;
int ymin = YCENTER - 1;
int xmax = XCENTER + 1;
int ymax = YCENTER + 1;
int iterationlimit = 0;
/* initialize to all uncommitted. */
for (x = 0; x < X; x++){
for (y = 0; y < Y; y++){
map[x][y]='?';
}
}
/* clear a center starting point. */
map[XCENTER][YCENTER] = '.';
do{
iterationlimit++;
x = dieroll (xmin, xmax);
y = dieroll (ymin, ymax);
if (map[x][y] == '?' || dieroll(1,100) == 1){
if (x == xmin && x > 1) xmin--;
if (x == xmax && x < X-2) xmax++;
if (y == ymin && y > 1) ymin--;
if (y == ymax && y < Y-2) ymax++;
adjfloor = 0;
if (map[x-1][y] == '.') adjfloor++;
if (map[x+1][y] == '.') adjfloor++;
if (map[x][y-1] == '.') adjfloor++;
if (map[x][y+1] == '.') adjfloor++;
adjwall = 0;
if (map[x-1][y] == '#') adjwall++;
if (map[x+1][y] == '#') adjwall++;
if (map[x][y-1] == '#') adjwall++;
if (map[x][y+1] == '#') adjwall++;
if (adjfloor){
if (uncommittedcount + floorcount > X * Y / 2 &&
(adjwall > adjfloor || wallcount * 3 < floorcount * 2)){
if (map[x][y] == '?')uncommittedcount--;
if (map[x][y] == '.') floorcount--;
if (map[x][y] != '#') wallcount++;
map[x][y]='#';
}
else {
if (map[x][y] == '?' ) uncommittedcount--;
if (map[x][y] == '#' ) wallcount--;
if (map[x][y] != '.' ) floorcount++;
map[x][y] = '.';
}
}
}
}while (iterationlimit < X * Y * 500 && floorcount < X * Y / 3);
for (x = 1; x < X-1; x++){
for (y = 1; y < Y-1; y++){
adjfloor = 0;
if (map[x-1][y] == '.') adjfloor++;
if (map[x+1][y] == '.') adjfloor++;
if (map[x][y-1] == '.') adjfloor++;
if (map[x][y+1] == '.') adjfloor++;
if (adjfloor && map[x][y] == '?') map[x][y] = '#';
if (adjfloor == 4) map[x][y] = '.';
if (!adjfloor) map[x][y] = ' ';
}
}
}
int main()
/* just a testing harness: hit spacebar to quit. */
{
int x;
int y;
do{
cavegen();
for (y = 1; y < Y-1; y++){
for (x = 1; x < X-1; x++){
printf("%c", map[x][y]);
}
printf("\n");
}
} while (getchar() != ' ');
return(0);
}
Jakub Debski
Look at the generators in roguelikelib:
http://sourceforge.net/projects/roguelikelib/
regards,
Jakub
dominik...@gmail.com
I use Jamis Buck's algorithm. I'd love to provide a working link to
the description, but it seems to be broken: http://www.aarg.net/~minam/dungeon.cgi
- maybe it moved to a different place?
If nobody finds information about it, I might try to recreate it on my
page (the algorithm included a labyrinth generator and a dungeon
generator), just let me know if you want to read about it and the
original text cannot be found anywhere.
Mingos.
Nik Coughlin
news:c09ae318-b596-4d6a...@t54g2000hsg.googlegroups.com...
> On 22 sep, 22:07, Fenrir <siliconvik...@gmail.com> wrote:
>> I'm having a hell of a time with dungeon generation. First I tried
>> placing rooms randomly about the map and connecting them with tunnels,
>> but pathfinding proved rather difficult. Now I'm trying Mike Aderson's
>> dungeon generation algorithm (http://
>> roguebasin.roguelikedevelopment.org/index.php?title=Dungeon-
>> Building_Algorithm), but I'm not having much more success. Is there a
>> simpler way? Should I keep trying to implement Mike Anderson's
>> algorithm, or maybe have another go at my initial plan?
>
> I use Jamis Buck's algorithm. I'd love to provide a working link to
> the description, but it seems to be broken:
> http://www.aarg.net/~minam/dungeon.cgi
> - maybe it moved to a different place?
http://web.archive.org/web/*/http://www.aarg.net/~minam/dungeon.cgi
Fenrir
generation. The source helped a VERY much, but I still have to fill in
some gaps since the example used the library. If this BSP-tree thing
frustrates me too much, I may temporarily use Ray Dillinger's cave-
generation algorithm and come back to dungeon generation later. Of
course, if I can't do this on my own, how am I to accomplish anything
else? I'd wager that it's only going to get harder from here...
Nahjor
> I'd wager that it's only going to get harder from here...
It doesn't so much get harder, as it gets...differently hard.
Different aspects of a RL project require different mindsets and
different skills. Keep plugging away at it, you never know, the next
part might be easy for you. :) It might help to remember that you
don't have to get everything 100% right on the first pass. It took
me...I think four or five versions of a dungeon generator, before I
got one I was happy with for MageGuild.
jice
Of course, having the dungeon code without the bsp module code would
be useless :)
It's here :
http://code.google.com/p/libtcod/source/browse/trunk/include/bsp.hpp
http://code.google.com/p/libtcod/source/browse/trunk/src/bsp.cpp
but it also uses other part of the library...
--
jice
Fenrir
> On 23 sep, 16:24, Fenrir <siliconvik...@gmail.com> wrote:
>
> > Thanks everyone! I'm now trying to implement jice's method of dungeon
> > generation. The source helped a VERY much, but I still have to fill in
> > some gaps since the example used the library. If this BSP-tree thing
> > frustrates me too much, I may temporarily use Ray Dillinger's cave-
> > generation algorithm and come back to dungeon generation later. Of
> > course, if I can't do this on my own, how am I to accomplish anything
> > else? I'd wager that it's only going to get harder from here...
>
> Of course, having the dungeon code without the bsp module code would
> be useless :)
> but it also uses other part of the library...
>
> --
> jice
Many thanks, jice! I'm already halfway through making the BSP-tree
code myself, though.
I Own The Letter O
tweaking as some of the rooms come out more like long wide corridors.
But over all it generates good looking dungeons without the need for
too much internal checks and balances as no room will ever overlap
another. I've added a few checks to make sure that all partitioned
sections are at least '4' squares wide in each direction to ensure
that rooms are at least 2x2 with walls.
From my (limited) experience BSP is the best for generating random
dungeons (and if combined with a cellular automata makes good winding
caves as well). It might need a bit more tweaking to make interesting
dungeons with 'themed' rooms (such as a prison block, mess hall,
barracks etc etc) but for a generic random dungeon it works really
well.
On another note... I made some desert islands yesterday. I used a
basic Cellular Automata (but didn't check that all areas were linked),
made what would normally be dug-out areas yellow and '~' and what
would normally be solid areas blue and '~', ran a few 'knights tour'
iterations adding green 'T' for palm trees. Not checking all areas are
linked means that there are some smaller islands around one or two
larger ones. A little more work to vary the colours of the sea to
represent waves (possibly a psuedo-animation) and it would be a great
little desert island - anybody for LostRL.
dominik...@gmail.com
> Just made my first (working) BSP Dungeon yesterday.
Congrats! I always found this the most difficult level generator.
> From my (limited) experience BSP is the best for generating random
> dungeons (and if combined with a cellular automata makes good winding
> caves as well).
I don't really feel like starting a flame war about this statement ;).
My experience is limited here as well, but I find BSP dungeons...
well, simplistic ;).
Mingos
I Own The Letter O
I've tried various simple methods as I'm quite new at RL (and my
programming is sporadic at best coming in a few weeks of enthusiasm
followed by months of apathy). The BSP dungeons are basic and generic,
and that is good or bad depending on what you want. At the moment I'm
at the stage of creating a few basic dungeon types, tieing them to my
'@' walking around and applying a few basic actions to doors and BSP
was the best I've tried for this role. I probably like them best as
they're easy to use and I'm not at the point where I want to much
complexity.
Later I'll want a bespoke system with the features I mentioned above
(i.e. themed rooms etc). But from all the methods I've tried so far
for making basic dungeons this one has given me the best results for
the smallest amounts of work.
I had another idea for something similar to BSP but also similar to
those games like 'Space Hulk' where you built the board as you go (I'm
not arrogant enough to think I came up with this idea first, I just
don't know what it's called). You divide your map into 5 by 5 sections
(my map area is 60 by 45 so 5 by 5 works), choose a section (randomly
or based on the previous level for stair coherence) and draw a stair-
room (3 by 3 plus walls). You then spread out around that section
filling each one either with a room, part of a room or a corridor, the
contents of the square is slightly swayed by it's surroundings so that
the parts of rooms can match up to make a bigger room (but possibly
not always so to generate some slightly unusual shaped rooms). Then
doors are placed where corridors meet rooms and randomly where rooms
met rooms (whatever methods you use to pick hidden/locked/special
doors can fit in here). Voila dungeon! With this method it is easy to
randomise or even force a themed room or set of rooms at a location
and work around it.
Does anybody know any RLs where this is used - (when I code it I'd
want to compare against somebody elses to help the learning).
Pointless
I used this method in an old un-released version of MetaCollider. I
made 10x10 blocks and filled each corner of that sector with 5x5
cells. And each cell had an exit that matched up with the
corresponding exit on the adjacent cell (even if the cell was in a
different sector). The 5x5 cells were then tunneled out with one of
three algorithms.
I got rid of it because it was boring. Everything looked the same...I
changed over to the method where the location of the corner of a room
is chosen at random, and then dimensions are chosen at random, and
then if there aren't any rooms pre-existing in that location, I create
the room with one of many algorithms. Since the level is not always
fully connected, I then run a series of floodfills that tell me where
the sections of the level are and then connect them with corridors.
This method vastly increases my options, because I can basically make
any algorithm I want. But it also makes the levels very...chaotic,
which I like :]
Jeff Lait
>
> I had another idea for something similar to BSP but also similar to
> those games like 'Space Hulk' where you built the board as you go (I'm
> not arrogant enough to think I came up with this idea first, I just
> don't know what it's called). You divide your map into 5 by 5 sections
> (my map area is 60 by 45 so 5 by 5 works), choose a section (randomly
> or based on the previous level for stair coherence) and draw a stair-
> room (3 by 3 plus walls). You then spread out around that section
> filling each one either with a room, part of a room or a corridor, the
> contents of the square is slightly swayed by it's surroundings so that
> the parts of rooms can match up to make a bigger room (but possibly
> not always so to generate some slightly unusual shaped rooms). Then
> doors are placed where corridors meet rooms and randomly where rooms
> met rooms (whatever methods you use to pick hidden/locked/special
> doors can fit in here). Voila dungeon! With this method it is easy to
> randomise or even force a themed room or set of rooms at a location
> and work around it.
>
> Does anybody know any RLs where this is used - (when I code it I'd
> want to compare against somebody elses to help the learning).
You Only Live Once, and the successor Letter Hunt and Save Scummer
used this for dungeon generation. Fatherhood used it for forest
generation.
http://www.zincland.com/7drl/liveonce
http://www.zincland.com/7drl/fatherhood
The trick with this system is to have enough interesting tiles to work
with. I think there is a lot of potential for it to also integrate
special themed room tiles, and even promote certain floor plans by
defining special matching characters for the tile boundaries.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)
dominik...@gmail.com
> On Oct 13, 7:54 am, I Own The Letter O <lord_h...@yahoo.co.uk> wrote:
>
>
>
>
>
> > I had another idea for something similar to BSP but also similar to
> > those games like 'Space Hulk' where you built the board as you go (I'm
> > not arrogant enough to think I came up with this idea first, I just
> > don't know what it's called). You divide your map into 5 by 5 sections
> > (my map area is 60 by 45 so 5 by 5 works), choose a section (randomly
> > or based on the previous level for stair coherence) and draw a stair-
> > room (3 by 3 plus walls). You then spread out around that section
> > filling each one either with a room, part of a room or a corridor, the
> > contents of the square is slightly swayed by it's surroundings so that
> > the parts of rooms can match up to make a bigger room (but possibly
> > not always so to generate some slightly unusual shaped rooms). Then
> > doors are placed where corridors meet rooms and randomly where rooms
> > met rooms (whatever methods you use to pick hidden/locked/special
> > doors can fit in here). Voila dungeon! With this method it is easy to
> > randomise or even force a themed room or set of rooms at a location
> > and work around it.
>
> > Does anybody know any RLs where this is used - (when I code it I'd
> > want to compare against somebody elses to help the learning).
>
> You Only Live Once, and the successor Letter Hunt and Save Scummer
> used this for dungeon generation. Fatherhood used it for forest
>
> The trick with this system is to have enough interesting tiles to work
> with. I think there is a lot of potential for it to also integrate
> special themed room tiles, and even promote certain floor plans by
> defining special matching characters for the tile boundaries.
> --
> Jeff Lait
> (POWDER:http://www.zincland.com/powder)
Aye, tiles were my first approach ever. Since they could be flipped
and rotated, each tile could come in up to 8 variants, so relatively
few hardcoded tiles were enough to make a potentially interesting
dungeon. The problem was that I had no control over the rooms' shape
nor number (sometimes there was just a big irregular room that was
occupying the whole screen), also the corridors often made no sense
(all looped...).
As for BSP, I agree that it's good for basic dungeon layouts. And
little more (though I *do* see some potential in BSP trees when it
comes to generating towns...).
Mingos.