Need some help getting my Dungeon generator to work right

**Thorbenn** · 03-12-2012

Hi All,

i am working on a Dungeon Generator for a roguelike that i am programming and i am having trouble with it because the rooms that should be carved out of the walls are spawning over each other.

I have been trying to fix this now for 2 days and haven't gotten anyware close of solving my Problem.

Maybe someone here has an idea how to help me :-)

To make things a bit easier i will first explain in word what it should do:

1. firstly i get me a random position X and Y
2. i generate a random length and width for the room size
3. i add the length and width to the random X and y to get the maximal X and Y position in the map
4. Now since i have these four positions i can make a square in my map with the corners X/Y , max X/Y, X/ max Y, max X/ Max Y.
5. I check once around this square to see that all is walls and if this is the case the room should be generated

So and now here my code:

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)); 
 
    // maximum of rooms
    const unsigned int maxRooms=8; 
    //Variable die hochgezählt wird bis maximale zimmmer erreicht sind 
    unsigned int roomCounter=0; 
 
    char floor='a'; 
    char door='+'; 
    char wall='#'; 
 
    //length of room
    int length2; 
 
    //the random position x and y
    int randomPosy; 
    int randomPosx; 
 
    //the width of the room
    int width; 
 
    //the maximum position of x and y in the map for the room
    int maxrandomPosy; 
    int maxrandomPosx; 
 
    //help variables for checking around the room
    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 ) 
    { 
 
        // this is only to help show how sometimes the rooms overlap 
        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' ; 
        } 
 
        if( roomCounter == 5 ) 
        { 
            floor = '6' ; 
        } 
 
        if( roomCounter == 6 ) 
        { 
            floor = '7' ; 
        } 
 
        if( roomCounter == 7 ) 
        { 
            floor = '8' ; 
        } 
 
 

        do 
        { 
            length2 = rand()% 5 + 5; 
 
            randomPosy = 1+rand()% 65; 
 
            randomPosx = 1+rand()% 14; 
 
            width = rand()%3+4; 
 
            maxrandomPosy = randomPosy+length2 ; 
 
            maxrandomPosx=randomPosx+width; 
 
        } 
        while(map[randomPosx][randomPosy]!=wall &&  map[randomPosx][maxrandomPosy]!=wall &&  map[maxrandomPosx][randomPosy]!=wall &&  map[maxrandomPosx][maxrandomPosy]!=wall); 
 
 
 
        //now i check around where the room should then be
 
        //this is the check for above the room
        for(int a = randomPosy ; a < maxrandomPosy + 1 ; a++) 
        { 
            if(map[ randomPosx-1 ][a]==wall) 
            { 
                //when theres a wall then it should count up 
                ++checker1; 
            } 
        } 
 
        // Wenn nun der Zähler die gleiche Anzahl an Stellen mit  Mauer hat wie die width (ja hätte da die width überprüfen können anstatt  das so kompliziert zu machen) 
        // dann wird der boolsche checker zu true gesetzt 
 
        if(checker1==maxrandomPosy-randomPosy+1) 
        { 
            check1=true; 
        } 
 
        // das gleiche Schema wie oben nur hier die rechte Seite des 4-Ecks 
        for(int b=randomPosx ; b < maxrandomPosx + 1 ; b++ ) 
        { 
            if(map[b][ maxrandomPosy + 1 ]==wall) 
            { 
                ++checker2; 
            } 
        } 
 
        if(checker2 == maxrandomPosx-randomPosx+1 ) 
        { 
            check2 = true; 
        } 
 
        for(int c = randomPosy ; c < maxrandomPosy + 1 ; c++ ) 
        { 
            if(map[ maxrandomPosx + 1][c] == wall ) 
            { 
                ++checker3; 
            } 
        } 
 
        if(checker3 == maxrandomPosy-randomPosy+1 ) 
        { 
            check3=true; 
        } 
 
 
        for(int d=randomPosx ; d < maxrandomPosx + 1; d++ ) 
        { 
            if(map[d][randomPosy-1] == wall ) 
            { 
                ++checker4; 
            } 
        } 
 
        if(checker4 == maxrandomPosx - randomPosx + 1 ) 
        { 
            check4=true; 
        } 
 
        // Nun wenn um das 4-Eck alles Mauern sind und die Ecken des 4-ecks etc. Mauern sind wird der Raum ausgehöhlt 
 
        if( check1 == true && check2 == true && check3 == true && check4 == true ) 
        { 
            if(map[randomPosx][randomPosy]==wall &&  map[maxrandomPosx][randomPosy]==wall &&  map[randomPosx][maxrandomPosy]==wall &&  map[maxrandomPosx][maxrandomPosy]==wall) 
            { 
                if(map[randomPosx-1][randomPosy]==wall &&  map[maxrandomPosx+1][randomPosy]==wall &&  map[randomPosx-1][maxrandomPosy]==wall &&  map[maxrandomPosx+1][maxrandomPosy]==wall) 
                { 
                    if(map[randomPosx][randomPosy-1]==wall  && map[maxrandomPosx][randomPosy-1]==wall &&  map[randomPosx][maxrandomPosy+1]==wall &&  map[maxrandomPosx][maxrandomPosy+1]==wall) 
                    { 
                        //Nun wird der Raum ausgehöhlt 
 
                        while(randomPosy<maxrandomPosy ) 
                        { 
 
                            for(int c=randomPosx; c< maxrandomPosx; c++) 
                            { 
                                map[c][randomPosy]=floor; 
 
                            } 
                            randomPosy++; 
                        } 
 
                        //wenn ein raum ausgehöhlt wurde die zähler variable um 1 addieren 
                        ++roomCounter; 
 
                         //print map 
                        for(int m=0; m<mapx; m++) 
                        { 
                            cout <<map[m]<<endl; 
                        } 
                        cout<<endl; 
                    } 
                } 
            } 
        } 
 
 
    } 
 
 
    return 0; 
 
}

This shows my Problem very nice how rooms get spawned over each other:

Code:

################################################################################ 
################################################################################ 
#################################################################11111########## 
#################################################################11111########## 
####44444444#####################################################11111########## 
####44444444#####################################################11111########## 
####44444444#####################################################11111########## 
####44444444#####################################################11111########## 
####44444444#################################################################### 
########################################55555################################### 
#############################66666######55555################################### 
#############################66666######55555######3333333###################### 
#############################66666######55555######3333333###################### 
########222222###############66666######55555######3333333###################### 
########222222###############66666######55555######3333333###################### 
########222222###############66666############################################## 
########222222################################################################## 
########222222################################################################## 
################################################################################ 
################################################################################ 
################################################################################ 
################################################################################ 
 
################################################################################ 
################################################################################ 
#################################################################11111########## 
#################################################################11111########## 
####44444444#####################################################11111########## 
####44444444#####################################################11111########## 
####44444444#####################################################11111########## 
####44444444#####################################################11111########## 
####44444444#################################################################### 
###########################7777777######55555################################### 
###########################7777777######55555################################### 
###########################7777777######55555######3333333###################### 
###########################7777777######55555######3333333###################### 
########222222#############7777777######55555######3333333###################### 
########222222###############66666######55555######3333333###################### 
########222222###############66666############################################## 
########222222################################################################## 
########222222################################################################## 
################################################################################ 
################################################################################ 
################################################################################ 
################################################################################ 
 
################################################################################ 
################################################################################ 
###############################################888888############11111########## 
###############################################888888############11111########## 
####44444444###################################888888############11111########## 
####44444444###################################888888############11111########## 
####44444444###################################888888############11111########## 
####44444444#####################################################11111########## 
####44444444#################################################################### 
###########################7777777######55555################################### 
###########################7777777######55555################################### 
###########################7777777######55555######3333333###################### 
###########################7777777######55555######3333333###################### 
########222222#############7777777######55555######3333333###################### 
########222222###############66666######55555######3333333###################### 
########222222###############66666############################################## 
########222222################################################################## 
########222222################################################################## 
################################################################################ 
################################################################################ 
################################################################################ 
################################################################################

Sorry for my bad English :-) I hope someone understands what i am trying to do and can help me with this

**Neo1** · 03-12-2012

Code:

#include <iostream> 
#include <fstream> 
#include "cstdlib" 
#include <ctime> 
#include <stdio.h> 
#include <termios.h> 
#include <string>

So to start off, theres a few issues with the headers you're including. I didn't know the termios.h header, so i googled it, heres what the linux man pages had to say about it:

the termios functions describes a general terminal interface that is provided to control asynchronous communications ports.

Now from what i can see, you're not using any of the functions this header provides, so why are you including it.

Also, "cstdlib" should be <cstdlib> and <stdio.h> should be <cstdio>. However, i can't find any places where you actually use any functions from this header, so again, why are you including it? And why are you including <string>, you're not using it for anything.

Okay so with that out of the way, from what i can see, the rooms seem to be generating just fine. So, the #'s are solid walls and the numbers are different rooms right? There doesn't seem to be any rooms overlapping, which is what you said was the problem, can you rephrase the question perhaps?

**Thorbenn** · 03-13-2012

Hi Neo1,

about the headers that i have included:

These are still from my main project where i am using them and need them. For example the termios i am using to block always having to push enter after getting a character via cin . I extracted the room generator to work on it and that is why i just copyied and pasted all the headers.

Okay so with that out of the way, from what i can see, the rooms seem to be generating just fine. So, the #'s are solid walls and the numbers are different rooms right? There doesn't seem to be any rooms overlapping, which is what you said was the problem, can you rephrase the question perhaps?

Yes the #'s are walls and the numbers are the diffrent rooms. A lot of times the rooms are generating fine and some of the times they overlap a lot too like in the example i posted in the first post. where the 7's overlap the 6's this shouldn't happen. i am trying to make the rooms be all individualy and not sitting right besides each other and not overlapping like in the example.

And this is my Problem i am trying to solve because by me the rooms overlap sometimes and i have no more ideas how to check that they don't overlap or lay right beside each other and merge to one huge room.

Here is another perfekt example what shouldn't happen. Once 2 and 4 are right beside each other without a wall or anything between them to merge to a single huge room and the 6's room is getting generated over the 5's room.
This is what i am trying to get rid of out of my code this overlapping and that the rooms are right beside each other without a # wall between them and making mega rooms

Code:

################################################################################
##################################################1111111#######################
##################################################1111111#######################
##################################################1111111#######################
##################################################1111111#######################
################################################################################
##################################33333333######################################
##################################33333333######################################
##################################33333333######################################
##################################33333333######################################
#######################################################444444###################
#######################################################444444###################
################################################2222222444444###################
################################################2222222444444###################
################################################2222222444444###################
################################################2222222444444###################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################

################################################################################
##################################################1111111#######################
##################################################1111111#######################
##################################################1111111#######################
##################################################1111111#######################
################################################################################
##################################33333333######################################
##################################33333333######################################
##################################33333333######################################
##################################33333333######################################
#######################################################444444###################
#######################################################444444###################
################################################2222222444444###################
################################################2222222444444###################
#############5555555############################2222222444444###################
#############5555555############################2222222444444###################
#############5555555############################################################
#############5555555############################################################
#############5555555############################################################
################################################################################
################################################################################
################################################################################

################################################################################
##################################################1111111#######################
##################################################1111111#######################
##################################################1111111#######################
##################################################1111111#######################
################################################################################
##################################33333333######################################
##################################33333333######################################
##################################33333333######################################
##################################33333333######################################
#######################################################444444###################
#######################################################444444###################
################################################2222222444444###################
#######66666666#################################2222222444444###################
#######6666666655555############################2222222444444###################
#######6666666655555############################2222222444444###################
#######6666666655555############################################################
#######6666666655555############################################################
#######6666666655555############################################################
################################################################################
################################################################################
################################################################################

################################################################################
##################################################1111111#######################
##################################################1111111#######################
##################################################1111111#######################
##################################################1111111#######################
################################################################################
##################################33333333######################################
##########################77777###33333333######################################
##########################77777###33333333######################################
##########################77777###33333333######################################
##########################77777########################444444###################
#######################################################444444###################
################################################2222222444444###################
#######66666666#################################2222222444444###################
#######6666666655555############################2222222444444###################
#######6666666655555############################2222222444444###################
#######6666666655555############################################################
#######6666666655555############################################################
#######6666666655555############################################################
################################################################################
################################################################################
################################################################################

################################################################################
##################################################1111111#######################
##################################################1111111#######################
##################################################1111111#######################
##################################################1111111#######################
################################################################################
##################################33333333######################################
##########################77777###33333333######################################
##########################77777###33333333######################################
##########################77777###33333333######################################
##########################77777########################444444###################
#######################################################444444###################
################################################2222222444444###################
#######66666666#################################2222222444444###################
#######6666666655555############################2222222444444##88888888#########
#######6666666655555############################2222222444444##88888888#########
#######6666666655555###########################################88888888#########
#######6666666655555###########################################88888888#########
#######6666666655555###########################################88888888#########
################################################################################
################################################################################
################################################################################

**Neo1** · 03-13-2012

Okay, so try and break this problem into smaller bits first.

You don't want the rooms to overlap: For this you can use simple collision detection when generating rooms. Whenever you generate a new room in your 2D map, save the X+Y coordinates of the upper left corner, as well as the width and height of the room into some kind of data structure. (A vector of structs or something like that)

Then when you generate more rooms, before you commit them to the map, check that they don't collide with any of the bounding boxes you have already saved in your vector. If they do, drop them and try generating a new one, keep going until you find one that doesn't collide with any existing rooms.

If you want to guarantee that there are atleast 1 wall between rooms, you can just expand the bounding box to include a 1-tile thick wall all around the edges of each room. That is:

X += 1;
Y += 1;
W += 2;
H += 2;

This is kind of a brute force approach, i'm sure someone in here will have something more elegant, but this should work fine.

**Thorbenn** · 03-14-2012

Hi Neo1,

thanks for your reply. Your Idea has been going now through my head and i have been looking how to get this done. During my research i have come upon this link c++ - Determine if two rectangles overlap each other? - Stack Overflow where someone is checking to see if two rectangles overlap. I have never been good at making chained lists and i think i might need some help :-) . I have been reading about how to set one up and how i could fill it. but how could i convert the code found on the link to go through my chained list to delete all overlaping rooms and until all rooms do not overlap?

I know it is much asked but i really need help understanding chained lists and how to work with these because this would make the code more dinamic and better.

**Neo1** · 03-14-2012

Originally Posted by Thorbenn

Hi Neo1,

thanks for your reply. Your Idea has been going now through my head and i have been looking how to get this done. During my research i have come upon this link c++ - Determine if two rectangles overlap each other? - Stack Overflow where someone is checking to see if two rectangles overlap. I have never been good at making chained lists and i think i might need some help :-) . I have been reading about how to set one up and how i could fill it. but how could i convert the code found on the link to go through my chained list to delete all overlaping rooms and until all rooms do not overlap?

I know it is much asked but i really need help understanding chained lists and how to work with these because this would make the code more dinamic and better.

Okay, so a linked list is just a data structure, it is a way of storing your data in a structured way. A linked list can store any kind of data, and a rectangle is just 4 integers (position and size)

So first of all, why do you want a linked list for this? There is nothing wrong with a linked list, if you are using it for something performance critical it should be noted that nodes in a linked list are not guaranteed to be next to each other in memory, which decreases the chances of cache hits. A linked list is good however, if you want to insert elements, since this can be done in constant time.

But unless you have a good reason to use a linked list, consider using something else, they can be cumbersome to deal with. I would suggest a std::vector or perhaps one of the new std::array?

Second of all, if you insist on using a linked list: Why do you want to implement your own linked list? There is already a true and tested design for you, free and ready to use: std::list.

If you insist on using linked list, and insist on implementing it yourself, i would suggest you do the following:

Forget about collision detection, forget about dungeons and games and rooms and walls. Sit down, learn linked lists, period. There are a million tutorials about linked lists readily available through google, dont return to this project until you feel absolutely at home and comfortable with using singly and doubly linked lists, as well as possibly circularly linked lists. You can't build a program using a data structure that you don't know how to use.

Learning linked lists really well also greatly helps your understanding of pointers, so that's another upside to doing this.

Anyways, once you have practiced linked lists come back to this thread and consider the following pseudocode:

Code:

struct room
{
     unsigned int X, Y;
     unsigned int W, H;
} randomRoom;

randomRoom.X = (rand() % mapWidth);
randomRoom.Y = (rand() % mapHeight);

randomRoom.W = (rand() % maxRoomWidth);
randomRoom.H = (rand() % maxRoomHeight);

bool intersects = false;

for(unsigned int i = 0; i < rooms.size(); i++)
{
     if( CheckIntersection(rooms[i], randomRoom) )
     {
          intersects = true;
          break;
     }
}

if(!intersects) AddRoom(rooms, randomRoom);

The above code would add the newly generated room to an array or vector of rooms, where the CheckIntersection() tests for room collisions and returns false if everything is well, or true otherwise. AddRoom() just adds the room to the current collection of rooms. Then it's just a matter of running the above code until:

Code:

rooms.size() == DesiredNumberOfRooms

Now you just need to figure out how to do the same with linked lists (or change your mind and use a std::vector ;-) )

The collision checking itself is easy, check out the LazyFoo SDL tutorial on collision checking:

Lazy Foo' Productions

Just ignore the SDL specific code and scroll down to the check_collision() function.

**Thorbenn** · 03-14-2012

Hi Neo1,

thanks for your help I think i will take your advice and use a std::vector . I learned now all day about linked lists and maybe later on while making the game it might be useful.

I have though one Question to the Pseudo Code:

Here it says at the end of the

Code:

struct room{...}randomRoom;

wouldn't this create a error? or what is meant with this last randomRoom?

**Neo1** · 03-14-2012

Code:

struct room
{
     unsigned int X, Y;
     unsigned int W, H;
} randomRoom;

The above code defines the type "room", and then creates an instance of room called randomRoom. It is equivalent to this:

Code:

struct room
{
     unsigned int X, Y;
     unsigned int W, H;
};

room randomRoom;

Don't follow the code-snippet i posted earlier blindly, it was just meant as a way to get you on the right track. I've no idea how the rest of your game is designed, but it might make more sense to make room an entire class, instead of just a struct.

**VirtualAce** · 03-24-2012

Look up maze generation algorithms. Now instead of placing walls in a cell place your 'rooms' in the cell. In the algorithm now you only need to check directions that are available from the type of room you placed. This should generate a dungeon rather quickly.

**Thorbenn** · 03-25-2012

Hi Neo1 and Virtual Ace,

i have been trying now to get the dungeon generator to work like you suggested with the collision detection, but for some reason they are still overlapping. Could you have a look at my code and tell me maybe where i have my misstake? I read the Article from Lazyfoo with his collision detection and left the = away since he says in it that this way rooms wouldn't spawn right beside each other but for some reason this doesn't work.

Here is my code hopefully you understand it

I tried to comment it as much as i could while working on it

Code:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <string>
#include <stdio.h>

using namespace std;



 struct Coordinate
{
    int x;
    int y;
    //w=width
    int w;
    //h=height
    int h;
    //musste erstmals nicht beachten die spielen erst dann beim einzeichnen ins 2d array dann ne rolle
    int helper;
    int helper2;
};

struct rooms
{
     int x[8];
    int y[8];
    int w[8];
    int h[8];
    int helper[8];
    int helper2[8];
};

bool collisionTest( Coordinate A, Coordinate B )
{
    //The sides of the rectangles
    int leftA, leftB;
    int rightA, rightB;
    int topA, topB;
    int bottomA, bottomB;

    //Calculate the sides of rect A
    leftA = A.x;
    rightA = A.x + A.w ;
    topA = A.y;
    bottomA = A.y + A.h ;

    //Calculate the sides of rect B
    leftB = B.x;
    rightB = B.x + B.w ;
    topB = B.y;
    bottomB = B.y + B.h ;

//If there are no collisions return false
if( bottomA < topB ) { return false; }
if( topA > bottomB ) { return false; }
if( rightA < leftB ) { return false; }
if( leftA > rightB ) { return false; }

//If theres a Collision return true
return true;

}





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

    char map[mapx][mapy]=
    {
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################"
    };

    char floor=' ';
    char wall='#';

    Coordinate top1,top2;
    rooms dungeon;


    //setting all values of the Array to 0 for no weird numbers in it :D
    for(int a=0;a<8;a++)
    {
        dungeon.x[a]=0;
        dungeon.y[a]=0;
        dungeon.w[a]=0;
        dungeon.h[a]=0;
    }


    srand(time(NULL));

    //setting first room in to the array
    dungeon.x[0] = (1+rand()% 14);
    dungeon.y[0] = (1+rand()% 65);
    dungeon.w[0] = (5+rand()% 5);
    dungeon.h[0] = (3+rand()% 3);
    dungeon.helper[0] = dungeon.x[0];
    dungeon.helper2[0] =dungeon.y[0] + dungeon.w[0];

    //logical variable that will be used further on in the code and is set to false
    bool intersects=false;
    //stting the variable to 1 because this will be the first spot to add a new room too since we first generate one room
    //in positon 0 of the struct room arrays with which we compare for intersections
    int placeInArray=1;








//do this so long till the maximum nuber of rooms is reached

 while(placeInArray<8)
 {




    //generating random room Coordinates
    top1.x= (1+rand()% 14);
    top1.y = (1+rand()% 65);
    top1.w = (5+rand()% 5);
    top1.h = (3+rand()% 3);

    //setting intersects again to false
    intersects=false;




    //check for collisions

    for(int b =0; b<8;b++)
    {
        top2.x=dungeon.x[b];
        top2.y=dungeon.y[b];
        top2.w=dungeon.w[b];
        top2.h=dungeon.h[b];

        //if theres a collision
        if (collisionTest(top1,top2)==true)
        {
        intersects=true;
        break;
        }

    }

         if(intersects==false)
         {
        //add room coordinates to arrays
        dungeon.x[placeInArray]=top1.x;
        dungeon.y[placeInArray]=top1.y;
        dungeon.w[placeInArray]=top1.w;
        dungeon.h[placeInArray]=top1.h;
        dungeon.helper[placeInArray] = top1.x;
        dungeon.helper2[placeInArray] =top1.y + top1.w;

        //go one space further
        placeInArray++;
         }

}



    //give out values of array
    for (int c=0;c<8;c++)
    {
        cout<<dungeon.x[c]<<endl;
        cout<<dungeon.y[c]<<endl;
        cout<<dungeon.w[c]<<endl;
        cout<<dungeon.h[c]<<endl;
        cout<<dungeon.helper[c]<<endl;
        cout<<dungeon.helper2[c]<<endl<<endl;

    }


    //lets carve the rooms :D
    placeInArray=0;
    for(int d=0;d<8;d++)
    {

    while(dungeon.helper[d] < (dungeon.x[d] + dungeon.h[d]) )
    {
        for(int e=dungeon.y[d]; e<(dungeon.helper2[d]);e++)
        {
            map[dungeon.helper[d]] [e]=floor;
        }
        dungeon.helper[d]++;
    }

    }





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










    return 0;

}

**Neo1** · 03-25-2012

Hmm, your code is a bit messy, you should really try and be consistent with the indentation and naming-scheme. Also, you shouldn't be including <stdio.h>, you already included <cstdio> and they are the same header, and you don't seem to be using anything from this header so why include it?

You're using C++ for this, but you're also using alot of C-style raw arrays, which is something to avoid when you have the C++ STL at your disposal. It seems to me like you're over-thinking this problem, since this doesn't strike me as a homework assignment i've spend a few minutes throwing together my own take on this problem:

Code:

#include <vector>
#include <iostream>
#include <cstdlib>
#include <ctime>

struct room
{
	unsigned int X, Y;
	unsigned int W, H;
};

bool CheckIntersection(room A, room B)
{
	int leftA, leftB;
    int rightA, rightB;
    int topA, topB;
    int bottomA, bottomB;
	
	leftA = A.X;
    rightA = A.X + A.W;
    topA = A.Y;
    bottomA = A.Y + A.H;
	
	leftB = B.X;
    rightB = B.X + B.W;
    topB = B.Y;
    bottomB = B.Y + B.H;
	
	if( bottomA < topB ) return false;
    
    if( topA > bottomB ) return false;
    
    if( rightA < leftB ) return false;
    
    if( leftA > rightB ) return false;
    
    return true;
}

int main()
{
	srand(time(NULL));
	room randomRoom;
	
	std::vector <room> rooms;
	unsigned int nRooms = 8;
	unsigned int mapWidth = 82;
	unsigned int mapHeight = 22;
	unsigned int maxRoomWidth = 10;
	unsigned int maxRoomHeight = 10;

	while(rooms.size() != nRooms)
	{
		randomRoom.X = (rand() % mapWidth);
		randomRoom.Y = (rand() % mapHeight);

		randomRoom.W = (rand() % maxRoomWidth) + 1;
		randomRoom.H = (rand() % maxRoomHeight) + 1;

		bool intersects = false;

		for(unsigned int i = 0; i < rooms.size(); i++)
		{
			if( CheckIntersection(rooms[i], randomRoom) )
			{
				intersects = true;
				break;
			}
		}

		if(!intersects) rooms.push_back(randomRoom);
	}
	
	for(unsigned int i = 0; i < rooms.size(); ++i)
	{
		std::cout << "Room " << i+1 << ":" << std::endl;
		std::cout << "Coordinates: (" << rooms[i].X << "," << rooms[i].Y << ")" << std::endl;
		std::cout << "Dimensions: (" << rooms[i].W << "," << rooms[i].H << ")" << std::endl << std::endl;
	}
	
	return 0;
}

Now, there are atleast 1 field between each room in the rooms vector, all you need to do is add them to your map-array and you should be good to go.

**Thorbenn** · 03-26-2012

Hi Neo1,

thank you very much for your help. Yes i really must stick more to the indentation and naming-scheme i agree. Reason for so many unformalitys though is because i normaly have my variable names in german and i am translating them to try and fit them for you or others reading to understand them.

Your asumption was right that this isn't homework :-) because i am trying to programm this game as an exercise and hobby wise for learning the language of c++ better. So far i have only done smaller Projects for an hobby like a bubble sort or MergeSort Algorithm etc. like you learn in classes at University or in Books like Beginning C++ through Game Programming (where some of these things were repeated again as i took my programming course).

I may use the above code slightly modified in my own code or?

Thank you very much for your time and help i really appreciate it.

Greetings,

Thorbenn

**Neo1** · 03-26-2012

Originally Posted by Thorbenn

Hi Neo1,

thank you very much for your help. Yes i really must stick more to the indentation and naming-scheme i agree. Reason for so many unformalitys though is because i normaly have my variable names in german and i am translating them to try and fit them for you or others reading to understand them.

Your asumption was right that this isn't homework :-) because i am trying to programm this game as an exercise and hobby wise for learning the language of c++ better. So far i have only done smaller Projects for an hobby like a bubble sort or MergeSort Algorithm etc. like you learn in classes at University or in Books like Beginning C++ through Game Programming (where some of these things were repeated again as i took my programming course).

I may use the above code slightly modified in my own code or?

Thank you very much for your time and help i really appreciate it.

Greetings,

Thorbenn

You're welcome, yes you can use it any way you wish.

**Thorbenn** · 03-28-2012

Hi Neo1,

i now made me a function to carve the random rooms in to my map array but still the rooms are overlapping

i am using your code from above to generate the the random rooms. I am using the code from above in my last post how i carve the rooms now just instead of going through an array i am going through the vector.

**Thorbenn** · 03-28-2012

First off sorry for the double post but i can't find the edit button to edit my last post -.- where (if there is one i dont find it)

I just wanted to post the code in here. They are not overlapping any more but laying right beside each other without an wall between them (this only happens seldomly but still it happens) .

Code:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>

using namespace std;



struct Coordinate
{
    int x;
    int y;
    //w=width
    int w;
    //h=height
    int h;
    //these are helpers for later on to carve the rooms
    int helper;
    int helper2;
};



bool collisionTest( Coordinate A, Coordinate B )
{
    //The sides of the rectangles
    int leftA, leftB;
    int rightA, rightB;
    int topA, topB;
    int bottomA, bottomB;

    //Calculate the sides of rect A
    leftA = A.x ;
    rightA = A.x + A.w ;
    topA = A.y;
    bottomA = A.y + A.h ;

    //Calculate the sides of rect B
    leftB = B.x;
    rightB = B.x + B.w ;
    topB = B.y;
    bottomB = B.y + B.h ;

//If there are no collisions return false
    if( bottomA < topB )
    {
        return false;
    }
    if( topA > bottomB )
    {
        return false;
    }
    if( rightA < leftB )
    {
        return false;
    }
    if( leftA > rightB )
    {
        return false;
    }

//If theres a Collision return true
    return true;

}





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

    char map[mapx][mapy]=
    {
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################"
    };

    char floor=' ';
    char wall='#';

    Coordinate generatedRoom;

    //these are criterias for the rooms maxPosx and MaxPosy and describe where the maximum x/y coordinate can be
    //so that when generating rooms none are colliding with the sides of the map array!
    const int maxRooms=10;
    const int maxPosX= 13;
    const int maxPosY= 64;

    vector <Coordinate> rooms;
    bool intersects=false;

    srand(time(NULL));

    //generating random room Coordinates
    while(rooms.size() != maxRooms)
    {
        generatedRoom.x = 2 + rand() % maxPosX;
        generatedRoom.y = 2 + rand() % maxPosY;

        generatedRoom.w = (rand() % 4) + 6;
        generatedRoom.h = (rand() % 3) + 5;

        intersects = false;

        //check for collisions
        for(int i = 0; i < rooms.size(); i++)
        {
            if(collisionTest(rooms[i], generatedRoom))
            {
                intersects = true;
                break;
            }
        }

        //if no collisions add to vector
        if(!intersects) rooms.push_back(generatedRoom);
    }



    //lets carve the rooms
    int counterRooms=0;

    while(counterRooms != maxRooms)
    {
        rooms[counterRooms].helper = rooms[counterRooms].x+1;
        rooms[counterRooms].helper2 = rooms[counterRooms].x+1 + (rooms[counterRooms].h - 3) ;

        while(rooms[counterRooms].helper < (rooms[counterRooms].helper2) )
        {
            for(int a=rooms[counterRooms].y+1; a<(rooms[counterRooms].y+1 + (rooms[counterRooms].w -3) ); a++)
            {
                map[rooms[counterRooms].helper][a]=floor;
            }
            rooms[counterRooms].helper++;
        }


        ++counterRooms;

    }





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










    return 0;

}

Thread: Need some help getting my Dungeon generator to work right

Thread Tools

Search Thread

Display

Need some help getting my Dungeon generator to work right

Similar Threads

Random Dungeon generator - help please

dungeon siege 3

How exactly does the random number generator work?

Dungeon of Moria

Random dungeon generator...