As the title suggests I'm trying to make a dungeon crawler, where the player can move from room to room. I vaguely remember posting about this a while ago. Anyway, I've spent hours on trying to make it work and it's making my head explode now.
Any advice on how to code it better, or how to fix the code, will be greatly appreciated (credited for the game). I know the code is broken atm - you get a hung script. I've annotated the code below, so hopefully it's easy to follow.
//Rooms are referred to as 'cells'
struct Cell
{
int door[4]; // Exit to the neighbouring cell. 0 = north, 1 = east, 2 = south, 3 = west. E.g. cell[1].door[0] = 2 leads to cell 2 at its northern edge
int x, y; // Cells are on a grid system
};
function DungeonGenerate(int quan) // quan is how many cells will be in the entire dungeon
{
// The number of the cell for given coords is stored: e.g. x[5].y[7] = 5 (cell 5 is at x5,y7)
struct Coord
{
int y[16];
};
Coord x[16];
// the grid runs from 0-15 on both axes
int i = 1; // start with 1, because cell[0] is never used. cell[1] is the starting room
// RESET all the cells, because the function can be called more than once
while (i <= quan)
{
cell[i].door[0] = 0; cell[i].door[1] = 0; cell[i].door[2] = 0; cell[i].door[3] = 0;
cell[i].x = 0; cell[i].y = 0;
i++;
}
i = 1;
// Now we can start building the dungeon (and get problems)
cell[1].x = 8; cell[1].y = 8;
x[8].y[8] = 1; // starting cell is at the centre: x8,y8
while (i <= quan)
{
int exits = Random(3)+1; // Randomise how many exits this cell will have (must have at least one, max 4...)
int o = 1; // Now, cycle through up to this number of exits
while (o <= exits) {
int d = Random(3); // Randomise the direction of the exit (0=N, 1=E, 2=S, 3=W)
if (d == 0 && cell[i].y < 15) // NORTH, and cell isn't at northern edge
{
if (!x[cell[i].x].y[cell[i].y+1]) // There is no cell present at the coord to the north, so there can be a cell added there
{
// !! NOTE !! the new cell index is i+o, because exits might be greater than 1. So we need to keep adding new cells, up to this maximum
cell[i].door[0] = o; cell[i+o].door[2] = i; // The N door of current and S door of new are linked
cell[i+o].x = cell[i].x; cell[i+o].y = cell[i].y+1;
x[cell[i].x].y[cell[i].y+1] = o; // New cell placed at these coords
o++;
}
}
else if (d == 1 && cell[i].x < 15) // EAST, and cell isn't at eastern edge
{
if (!x[cell[i].x+1].y[cell[i].y]) // There is no cell present at the coord to the east, so there can be a cell added there
{
cell[i].door[1] = o; cell[i+o].door[3] = i; // The E door of current and W door of new are linked
cell[i+o].x = cell[i].x+1; cell[i+o].y = cell[i].y;
x[cell[i].x+1].y[cell[i].y] = o; // New cell placed at these coords
o++;
}
}
else if (d == 2 && cell[i].y) // SOUTH, and cell isn't at southern edge
{
if (!x[cell[i].x].y[cell[i].y-1]) // There is no cell present at the coord to the south, so there can be a cell added there
{
cell[i].door[2] = o; cell[i+o].door[0] = i; // The S door of current and N door of new are linked
cell[i+o].x = cell[i].x; cell[i+o].y = cell[i].y-1;
x[cell[i].x].y[cell[i].y-1] = o; // New cell placed at these coords
o++;
}
}
else if (d == 3 && cell[i].x) // WEST, and cell isn't at western edge
{
if (!x[cell[i].x-1].y[cell[i].y]) // There is no cell present at the coord to the west, so there can be a cell added there
{
cell[i].door[3] = o; cell[i+o].door[1] = i; // The W door of current and E door of new are linked
cell[i+o].x = cell[i].x-1; cell[i+o].y = cell[i].y;
x[cell[i].x-1].y[cell[i].y] = o; // New cell placed at these coords
o++;
}
}
}
i++;
}
current = 1; //set the starting room to 1.
}
The problems I'm having with this method are:
• If no exit can be found, that cell is skipped so (a) you get drastically less than the number of cells you wanted, and (b) the next cell has its coords at x[0].y[0], because it hasn't been defined. This means the dungeon is split into two halves - the part that worked up until no exits were found, with cells clustered around x8,y8; then a cluster in the far southwestern corner (x0,y0).
• To get around this (force it to find at least one exit for every cell), I keep o++ outside the main body of the while loop, so it keeps triggering a different randomised direction to check. This obviously causes a hung script. But I don't understand it because every cell must have at least one of those directions free to branch out into, but because it hangs it implies no direction is ever found.
• You also get cells linking to distant cells that aren't even neighbours.
Bottom line, the code is flawed and I maxed out on brain power for this a long time ago, but I think some of the ideas can be salvaged.
Atelier
I think I remember this, and I coded my own generator; not sure what happened.
Here it is:
https://www.dropbox.com/s/6wz9k4dmuy240at/DungeonGenerator.scm
Import the script and press X to see a demo. Keep pressing X to generate another random dungeon.
(My code puts a cell at the center, than adds cells at random locations that have at least one neighboring cell.)
Did not look closely at the code yet, but the first thing that comes to my mind is recursion. If I have some time left later this evening I might give it a try.
A word of warning about recursion: AGS has a limit of 50 nested functions. Hopefully, that won't be a problem, but I thought I should mention this.
Khris that's awesome, thank you! I abandoned the project ages ago and when I came back to it recently I must have picked up on an old version - doh! I've adapted the draw function so the current cell is always drawn at the centre of the map:
(http://i.imgur.com/HAgLoXS.png?1)
Just a little thing, North and South appear to be inverted to the previous convention (now door 0 is S and door 2 is N). But this can just be taken into account in the code used to navigate rooms.
Thanks again!
Since the issue is already solved I don't know how helpful it is, but RogueBasin has a lot of dungeon-crawly articles, so I'll link this anyway:
http://roguebasin.roguelikedevelopment.org/index.php?title=Main_Page
Ah, I didn't know that the result should look like this, I thought it was supposed to be more maze like. Anyway, great that it is solved!
Quote from: Atelier on Mon 06/05/2013 20:03:52Just a little thing, North and South appear to be inverted to the previous convention (now door 0 is S and door 2 is N). But this can just be taken into account in the code used to navigate rooms.
Yeah, I used a lot of shortcuts in order to avoid if-else if-blocks, and probably screwed up somewhere. You should rather fix that in the generator code instead of adding a second error to "fix" the first though :)
(I'm too lazy right now, but if I find something later, I'll post it.)