Drunken Master cave generation

[Krice]

I took drunkard's walk routine and made three improvements:

1. Count the true amount of tiles generated to get a percentage coverage of the level (increase count when wall tile turns to floor tile)

2. Limit the generation to edges with first "soft" limiting (turning back when certain limit is reached) and then hard limit if edges of level hit

3. Occasionally walk straight a number of steps to produce corridors. The rule for corridor is that there is enough empty room ahead (to avoid too dense corridor generation).

I've implemented it and it works like anything! I've set 5-10 random steps for corridors and 20-30 steps for caverns, but it's just an example. Also, corridor/cavern mode is selected randomly, not one after another.

I will post some example levels later.

[RylandAlmanza]

Cool stuff. I look forward to your examples. I've made a couple cave-generating algorithm's based on drunkard walk, so it would be interesting to compare results.

[guest509]

Yeah man, we really made some interesting dungeons using the 'diggers' awhile back, this is an improvement on that right?

[rust]

I fiddled with this algorhitm in this year's 7DRL challenge. Your first improvement is implemented in my version as well, though when it comes to limiting the walker, I just reset its position when it hit the edge. I also figured that weighting the directions tends to give interesting results.

[Krice]

Yeah man, we really made some interesting dungeons using the 'diggers' awhile back, this is an improvement on that right?

It's a similar concept, but this time just for "regular" cavern type dungeons.

These are some examples:


It's kind of basic style, but there is nice amount of randomness in this routine. Sometimes you get big caverns and sometimes small ones plus more corridors.

[Endorya]

Instead of cavern systems, the images above reminds me of abandoned mines. I think it's the corridors and their general squary output that causes me that feeling.

[Krice]

Instead of cavern systems, the images above reminds me of abandoned mines.

It can be anything you want.

[Endorya]

It can be anything you want.

Cewl! I'm going with bewbs then!

[guest509]

It can be anything you want.

Cewl! I'm going with bewbs then!

Congratulations. You just won the internet.

[Endorya]

It can be anything you want.

Cewl! I'm going with bewbs then!

Congratulations. You just won the internet.

Alright!

[Endorya]

Just out of crystallized curiosity, why the majority of roguelikes don't have scrolling maps? Why are they usually confined to a particular screen size?

[Krice]

Let's put the source code here. It's not a complete one, but hopefully easy to figure out missing part which should be Coords (class with x, y variables) and K_Rect (class with x, y, w, h) and rng.

header:

Code: [Select]

#include "classes/coords.h"

class Level;
struct K_Rect;

class Drunkard
{
private:
Level *cave;
Coords location;
int direction;
int floor_tile;
bool sober;
int steps;

int Get_Edge_Direction();
bool Sober_Up();
void Think();
void Turn();

public:
Drunkard(Level *c, int percentage, int ft);
};

source:

Code: [Select]

#include "classes/kdir.h"
#include "drunkard.h"
#include "level.h"
#include "teemu.h"
#include "terrtype.h"

Drunkard::Drunkard(Level *c, int percentage, int ft)
{
cave=c;
floor_tile=ft;
int cleared_tiles=0;
const int bt=cave->lvltheme.Get_Base_Tile(); //level's wall tile
const int width=cave->Get_Width();
const int height=cave->Get_Height();

//count amount of tiles needed to clear
const int sz=width*height;
const double p=(double)percentage/100.0;
const int required_tiles=(int)(sz*p);

//set a safety limit after which the generation stops
const int max_steps=required_tiles*10;

//set start location at center of the level +/- 5 tiles
location=cave->Get_Random_Center(5);

direction=-1;
Turn(); //get first random direction

steps=-1;
Think(); //select initial walking mode

//walk until required number of tiles are cleared
int panic_steps=0;
while (cleared_tiles<required_tiles)
{
if (cave->Get_Terrain(location)==bt)
{
cave->Put_Terrain(location, floor_tile);
cleared_tiles++;
}

Think();

if (sober)
{
if (Get_Edge_Direction()!=-1) sober=false;
}

if (sober==false) Turn();

location.Move_Direction(direction);

//use hard limit check to preserve edges of level
if (location.x<1) location.x++;
else if (location.x>=width-1) location.x--;

if (location.y<1) location.y++;
else if (location.y>=height-1) location.y--;

//count all steps and panic exit if max reached
panic_steps++;
if (panic_steps>max_steps) break;
}
}

int Drunkard::Get_Edge_Direction()
{
//turn around when reaching edge area of level
static const int Edge_Size=5;
int sd=-1;

if (location.y<Edge_Size) sd=D_South;
else if (location.y>cave->Get_Height()-Edge_Size) sd=D_North;

if (location.x<Edge_Size) sd=D_East;
else if (location.x>cave->Get_Width()-Edge_Size) sd=D_West;

return sd;
}

bool Drunkard::Sober_Up()
{
//don't sober up at edges of the level
if (Get_Edge_Direction()!=-1) return false;

//start by centering a rectangle on the location
K_Rect r(location.x-4, location.y-4, 9, 9);

//move the rectange from the origin and extend to current direction
switch (direction)
{
case D_North: r.y-=4; break;
case D_South: r.y+=4; break;
case D_West: r.x-=4; break;
case D_East: r.x+=4; break;
default: break;
}

//max 25% of tiles can be floor tiles
const int min_amount=r.Get_Size()/4;
int a=0;

//check the area ahead if it's empty enough to create a corridor
Coords c;
for (c.y=r.y; c.y<=r.y+r.h; c.y++)
{
for (c.x=r.x; c.x<=r.x+r.h; c.x++)
{
int tt=cave->Get_Terrain(c);
//outside level, don't sober up
if (tt==0) return false;
if (tt==floor_tile) a++;
//too many floor tiles, don't sober up
if (a>min_amount) return false;
}
}

return true;
}

void Drunkard::Think()
{
if (steps<=0)
{
if (Sober_Up() && rng->Sometimes())
{
sober=true;

//corridor steps
steps=rng->Get_Min_Max(5, 10);
}
else
{
sober=false;

//cavern steps
steps=rng->Get_Min_Max(20, 30);
}
}
else steps--;
}

void Drunkard::Turn()
{
int d=direction;

//select another direction until it's different than original
while (d==direction)
{
d=rng->Get_Random_Cardinal_Direction();
}

//try to limit the creation to edges of the level
int sd=Get_Edge_Direction();

//make it slightly random to avoid too blunt limit
if (sd!=-1 && rng->Flip_Coin()) d=sd;

direction=d;
}


[guest509]

Just out of crystallized curiosity, why the majority of roguelikes don't have scrolling maps? Why are they usually confined to a particular screen size?

Well the one screen level thing is traditional because of technical limitations, much like the ascii. It has stuck around now as a design decision (again, like ascii). I like quick tight levels, with a couple baddies and a couple goodies. You can see everything at once, no need for a minimap, scrolls of magic detection or monster detection tend to work better this way, etc...Some perfectly decent games have large maps though, like Crawl, Dungeons of Dreadmore, etc...exploration feels like more of a 'thing' in scrolling games.

[Endorya]

Well the one screen level thing is traditional because of technical limitations, much like the ascii. It has stuck around now as a design decision (again, like ascii). I like quick tight levels, with a couple baddies and a couple goodies. You can see everything at once, no need for a minimap, scrolls of magic detection or monster detection tend to work better this way, etc...Some perfectly decent games have large maps though, like Crawl, Dungeons of Dreadmore, etc...exploration feels like more of a 'thing' in scrolling games.

Thanks for the explanation. I had a feeling it was related to technical limitations. The main problem I personally get out of fixed sized maps is that it breaks the surprise factor as far as exploration goes; I know that when I reach one side of the screen the remaining options will mostly include going backwards or changing direction towards the still blank area (if applicable), not to mention I always know, more or less, how much longer it will take to have the whole level explored just by noticing the screen's remaining empty area. I'm applying this feeling to any map type, dungeons including, though dungeons are harder to predict, however still a victim of this feeling of mine.

[guest509]

Oh yes. If you are designing a game hoping for this feeling of exploration mystery, scrolling is a nice tool. Sometimes small side room or little hidden caves off the main corridor can give he same idea.

Even if the map scrolls there is often a minimap, you can still do a grid style exploration if you want, it just takes longer to get to the side of the map.

So in the end you can get the effects you want either way, with differences with each style. In Brogue you can often tell when there is a hidden area because of the 1 screen level scheme. Not always, but often.