Notice: Any messages purporting to come from this site telling you that your password has expired, or that you need to verify your details, confirm your email, resolve issues, making threats, or asking for money, are
spam. We do not email users with any such messages. If you have lost your password you can obtain a new one by using the
password reset link.
Due to spam on this forum, all posts now need moderator approval.
Entire forum
➜ Programming
➜ General
➜ Dungeon Generation algorithm
|
Dungeon Generation algorithm
|
It is now over 60 days since the last post. This thread is closed.
Refresh page
| Posted by
| Thorbenn
(25 posts) Bio
|
| Date
| Thu 08 Mar 2012 05:09 PM (UTC) Amended on Thu 08 Mar 2012 05:11 PM (UTC) by Thorbenn
|
| Message
| 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;
}
| | Top |
|
| Posted by
| Nick Gammon
Australia (23,169 posts) Bio
Forum Administrator |
| Date
| Reply #1 on Thu 08 Mar 2012 07:18 PM (UTC) |
| Message
| 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. |
- Nick Gammon
www.gammon.com.au, www.mushclient.com | | Top |
|
| Posted by
| Thorbenn
(25 posts) Bio
|
| Date
| Reply #2 on Fri 09 Mar 2012 06:59 AM (UTC) Amended on Fri 09 Mar 2012 07:00 AM (UTC) by Thorbenn
|
| Message
| 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.
| | Top |
|
The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).
To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.
14,308 views.
It is now over 60 days since the last post. This thread is closed.
Refresh page
![[Go to top]](/images/gototop.gif)
top