This forum is a read-only archive of the Gammon Software forum (2000–2026). No new posts can be made. Search the archive.

Dungeon Generation algorithm

Posted by Thorbenn on Thu 08 Mar 2012 05:09 PM — 3 posts, 15,299 views.

Thorbenn #0
Hi All,

after getting the PvP function working under SimpleMud I have decided to take SimpleMuD to the next step and make a multiplayer roguelike out of it. So far the most important stuff works pretty well exept for my dungeon generation algorithm i am working on.

I started a new Cpp and am first trying to get nice dungeons in the console before implementing it to the mud.

My Problem is that when making the rooms of the dungeon for some reason they still are spawning in each other.

To understand my code better i will give some bullet points of how all works or should work :D

1. i fill my 2d array with walls
2. i get me a random position x and y in the map
3. i get a random width and height of the room that should be carved out

4. i check once around the room to see that there are walls

so for example if this should be the room i check the arrows to see that they are walls and so to say not floor.
^------>
|######|
|#1111#|
|######v
<-------

if these are walls then it should spawn

but they are still spawning together and i can't figure out why.

it would be neat if anyone could help me with this :)
here is my code:

#include <iostream>
#include <fstream>
#include "cstdlib"
#include <ctime>
#include <stdio.h>
#include <termios.h>
#include <string>
using namespace std;

int main()
{
const int mapx =22;
const int mapy =82;//69;
const int mapz =10;

char map[mapx][mapy]=
{
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                ",
    "                                                                                "
};
srand(time(NULL));
const unsigned int maxRooms=5;
unsigned int roomCounter=0;
unsigned int startX=1 +(rand()%(mapx-2));
unsigned int startY=1+(rand()%(mapy-5));
char floor='a';
char door='+';
//char wall='#';
char wall=' ';

int length2;
int randomPosy;
int randomPosx;
int width;
int maxrandomPosy;
int maxrandomPosx;

int checker1=0;
bool check1=false;
int checker2=0;
int check2=false;
int checker3=0;
bool check3=false;
int checker4=0;
bool check4=false;

while(roomCounter<maxRooms)
{
if(roomCounter==0)
{
    floor='1';
}

if(roomCounter==1)
{
    floor='2';
}

if(roomCounter==2)
{
    floor='3';
}

if(roomCounter==3)
{
    floor='4';
}

if(roomCounter==4)
{
    floor='5';
}

length2=rand()% 5 + 5;
randomPosy=1+rand()% 65;
randomPosx=1+rand()% 14;
width=rand()%3+4;
maxrandomPosy=randomPosy+length2;
maxrandomPosx=randomPosx+width;

for(int a=randomPosy; a<=maxrandomPosy;a++)
{
    if(map[randomPosx-1][a]==wall)
    {
        checker1++;
    }
}
if(checker1==maxrandomPosy-randomPosy+1)
{
    check1=true;
}


for(int b=randomPosx; b<=maxrandomPosx;b++)
{
    if(map[maxrandomPosy+1]==wall)
    {
        checker2++;
    }
}
if(checker2==maxrandomPosx-randomPosx+1)
{
    check2=true;
}

for(int c=randomPosy; c<=maxrandomPosy;c++)
{
    if(map[maxrandomPosx+1][c]==wall)
    {
        checker3++;
    }
}
if(checker3==maxrandomPosy-randomPosy+1)
{
    check3=true;
}


for(int d=randomPosx; d<=maxrandomPosx;d++)
{
    if(map[d][randomPosy-1]==wall)
    {
        checker4++;
    }
}
if(checker4==maxrandomPosx-randomPosx+1)
{
    check4=true;
}



if(check1==true && check2==true && check3==true && check4 == true)
{
  while(randomPosy<maxrandomPosy)
{
 for(int c=randomPosx;c< maxrandomPosx;c++)
{

        map[c][randomPosy]=floor;

}
randomPosy++;
}

++roomCounter;
}
}

//print map
for(int m=0;m<mapx;m++)
{
    cout <<map[m]<<endl;
}
    return 0;

}





Amended on Thu 08 Mar 2012 05:11 PM by Thorbenn
Nick Gammon Australia Forum Administrator #1
I was working on something like that recently for an adventure on a microprocessor. :)

See:

http://www.astrolog.org/labyrnth/algrithm.htm


First I used this:


// direction bits
enum { NORTH = 1, SOUTH = 2, EAST = 4, WEST = 8};

typedef struct 
  {
  byte exits;
  } room;

room rooms [WIDTH] [DEPTH] = { 0 };

const int getrandom (const int x)
{
long n;
 
   if (x <= 0)
     return 0;
   n = rand ();
   return (n % x);
}   // end of getrandom


/*------------------------------------------------------
                    Locations
  ------------------------------------------------------ */

// player/mob/item location
class loc
  {
  public:

    // default constructor
    loc () : x (0), y (0) {} 
    // copy constructor
    loc (const loc & rhs) : x (rhs.x), y (rhs.y) {}
    // constructor from coordinates
    loc (const byte newx, const byte newy) : x (newx), y ( newy) {}

    bool operator== (const loc & rhs) const;
    bool operator!= (const loc & rhs) const;

    void go (const byte direction);
    void rand ();

  byte x;
  byte y;
  };  // end of class loc

void loc::go (const byte direction)
  {
  switch (direction)
    {
    case NORTH: y--; break;
    case SOUTH: y++; break;
    case EAST:  x++; break;
    case WEST:  x--; break;
    } // end of switch

  } // end of loc::go

void loc::rand ()
  {
  x = getrandom (WIDTH);
  y = getrandom (DEPTH);
  } // end of loc::rand

bool loc::operator== (const loc & rhs) const
  {
  return x == rhs.x && y == rhs.y;
  }

bool loc::operator!= (const loc & rhs) const
  {
  return !(*this == rhs);
  }


/*------------------------------------------------------
                    Dungeon generation
  ------------------------------------------------------ */

// generate the maze
void MakePassage (loc where)
  {
  int exits [4] = { NORTH, SOUTH, EAST, WEST };
  shuffle (exits, 4);

  // make an exit in each direction, if the room in
  // that direction does not already have one
  for (int i = 0; i < 4; i++)
    {
    loc newloc (where);
    byte chosenExit = exits [i];
    newloc.go (chosenExit);

    if (newloc.x >= 0 && newloc.x < WIDTH &&
       newloc.y >= 0 && newloc.y < DEPTH &&
       rooms [newloc.x] [newloc.y].exits == 0)
     {
     rooms [where.x] [where.y].exits |= chosenExit;  // make an exit this way
     rooms [newloc.x] [newloc.y].exits |= opposite (chosenExit); // and the reverse exit
     MakePassage (newloc);
     }  // end of exit in range and room not yet processed

    }  // end of for
  } // end of  MakePassage



You start the process off like this:


MakePassage (loc ()); // start off at 0,0


I think this is the "recursive backtracker".

This worked fine, except that on a microprocessor it used too much stack (being recursive it keeps calling itself). However on a Linux/Windows box that should be fine.

But read the page I referenced, there are lots of different types there.

Also since this generates a maze, you might want to punch some extra exits in, otherwise the players may get frustrated if there is only exactly one way out of the dungeon.
Thorbenn #2
Hi Nick,

very interessting code you posted. I looked at the Maze that it generated and have to say it is nice but sadly not like i want my dungeon to look like :) . I am trying to make rectangular rooms that are then connected with a way.

Like this:
########################
########################
##...########.......########
##...########.......########
##........................########
##...########.......########
########################
########################
But somehow my rectangles get placed in each other some times in a way that shouldn't happen because they spawn in each other half way or even to a fourth.
I have tried when making a room to look if something is in the middle other than wall or not but then my results of the dugeon were even worse then before.

In the code i haven't made the room connection yet just for everyones info who is reading the posts because right now the carving of the rooms isn't working to well.