6 replies to this topic

[Mr Weird Guy]

I'm in the early stages of developing a Roguelike (or Dungeon Crawler, whatever you want to call it), and it's been going alright so far.
The way my dungeon generation currently works, is that there's a 4x3 grid of rooms that are randomly generated.
First the paths leading to/from the rooms are somewhat randomly generated, then rooms that are not fully connected are fixed, and then the tiles are placed.
For the most part, this works great. However, every now and then (probably every ~2% of the time), some rooms will be secluded, and inaccessable
without walking through walls. The way it's coded, it will never be just one room; it's always at least 2.
This becomes a problem, since the stairs down to the next level may spawn in this secluded area, preventing any further progress for the player.
Now that we've established the problem, here's my code for generating paths.

For each room, this script is run once.

hallN = irandom(1)
hallE = irandom(1)
hallS = irandom(1)
hallW = irandom(1)
if hallN = 0 && hallE = 0 && hallS = 0 && hallW = 0
    {
    if y != 0
        {
        hallN = 1
        }
    if x != room_width - 192
        {
        hallE = 1
        }
    if y != room_height - 192
        {
        hallS = 1
        }
    if x != 0
        {
        hallW = 1
        }
    }
if y = 0
    {
    if hallN = 1
        {
        hallN = 0
        hallS = 1
        }
    }
if x = room_width - 192
    {
    if hallE = 1
        {
        hallE = 0
        hallW = 1
        }
    }
if y = room_height - 192
    {
    if hallS = 1
        {
        hallS = 0
        hallN = 1
        }
    }
if x = 0
    {
    if hallW = 1
        {
        hallW = 0
        hallE = 1
        }
    }

//Top Left
if x = 0 && y = 0
    {
    if hallS = 0 && hallE = 0
        {
        hallS = 1
        hallE = 1
        }
    }

//Top Right
if x = room_width - 192 && y = 0
    {
    if hallS = 0 && hallW = 0
        {
        hallS = 1
        hallW = 1
        }
    }

//Bottom Left
if x = 0 && y = room_height - 192
    {
    if hallN = 0 && hallE = 0
        {
        hallN = 1
        hallE = 1
        }
    }

//Bottom Right
if x = room_width - 192 && y = room_height - 192
    {
    if hallN = 0 && hallW = 0
        {
        hallN = 1
        hallW = 1
        }
    }

//Left Mid
if x = 0 && y != 0 && y != room_height - 192
    {
    if hallN = 0 && hallE = 0 && hallS = 0
        {
        h = irandom(2)
        if h = 0
            {
            hallN = 1
            }
        if h = 1
            {
            hallE = 1
            }
        if h = 2
            {
            hallS = 1
            }
        }
    }

//Right Mid
if x = room_width - 192 && y != 0 && y != room_height - 192
    {
    if hallN = 0 && hallW = 0 && hallS = 0
        {
        h = irandom(2)
        if h = 0
            {
            hallN = 1
            }
        if h = 1
            {
            hallW = 1
            }
        if h = 2
            {
            hallS = 1
            }
        }
    }

//Top Mid
if y = 0 && x != 0 && x != room_width - 192
    {
    if hallE = 0 && hallW = 0 && hallS = 0
        {
        h = irandom(2)
        if h = 0
            {
            hallE = 1
            }
        if h = 1
            {
            hallW = 1
            }
        if h = 2
            {
            hallS = 1
            }
        }
    }

//Bottom Mid
if y = room_height - 192 && x != 0 && x != room_width - 192
    {
    if hallE = 0 && hallW = 0 && hallN = 0
        {
        h = irandom(2)
        if h = 0
            {
            hallE = 1
            }
        if h = 1
            {
            hallW = 1
            }
        if h = 2
            {
            hallN = 1
            }
        }
    }
global.hallN[x/192,y/192] = hallN
global.hallE[x/192,y/192] = hallE
global.hallS[x/192,y/192] = hallS
global.hallW[x/192,y/192] = hallW

And then an alarm one step later runs this code:

if y != 0
    {
    if global.hallS[x/192,(y/192) - 1] = 1
        {
        hallN = 1
        }
    }

if x != 0
    {
    if global.hallE[x/192 - 1,(y/192)] = 1
        {
        hallW = 1
        }
    }

if y != room_height - 192
    {
    if global.hallN[x/192,(y/192) + 1] = 1
        {
        hallS = 1
        }
    }

if x != room_width - 192
    {
    if global.hallW[x/192 + 1,(y/192)] = 1
        {
        hallE = 1
        }
    }
global.hallN[x/192,y/192] = hallN
global.hallE[x/192,y/192] = hallE
global.hallS[x/192,y/192] = hallS
global.hallW[x/192,y/192] = hallW

The actual tile placement comes right after this, and tiles once placed cannot be removed or replaced.
So this means the solution has to come at some point between the script and the alarm.
I'm kinda lost here, so any suggestions would be helpful.

[torigara]

To my reading, a room can have an open "hall" at each side (up to four.) The posted code is to ensure that each room has at least one opening. Right? It seems that part should work, provided that every room exatly aligns with 192x192 grid and room_width and room_height are also exactly multiple of 192.

What I don't get is how you actually connect rooms depending on those variables and arrays. The second piece of code looks to ensure that two adjacent rooms have openings on the facing side each other:

+---------++--------+
|         ||        |
|    A     |   B    |
|         ||        |
+---------++--   ---+

           |
           v

+---------++--------+
|         ||        |
|    A  ...... B    |
|         ||        |
+---------++--   ---+

But what happens if they aren't next to each other?

+---------+          +--------+
|         |          |        |
|    A   ..........X |   B    |
|         |          |        |
+---------+          +--   ---+
How are yo going to connect these rooms?

Or these two?
+---------+
|         |
|    A  ........
|         |    .
+---------+    X
           +--------+
           |        |
           |   B    |
           |        |
           +--   ---+

Also, how do you handle the case that two rooms are adjacnet but have no opening at the shared edge?

+---------++--------+
|         ||        |
|    A    ||   B    |
|    .    ||   .    |
+--- . ---++-- . ---+
     .         .
     ...........
Do you have a code to connect rooms in this case?

Or this one?
     ...........
     X         .
+---------++-- . ---+
|         ||   .    |
|    A    ||   B    |
|    .    ||        |
+--- . ---++--------+
     .         X
     ...........

[Mr Weird Guy]

First off, I guess I should have explained that in this 4x3 grid of rooms, there are only straight paths.
Also, (kinda important) an instance of the object that runs this code is created for each room in the map, meaning 12 total.
The first lines of the code randomly add paths to each side of the room.

So if a room's paths are set to
hallN = 0; hallE = 1; hallS = 1; hallW = 0;
it would look like this.

+-----+
|     |
|  A  ---
|     |
+--|--+
   |

What I don't get is how you actually connect rooms depending on those variables and arrays. The second piece of code looks to ensure that two adjacent rooms have openings on the facing side each other:

Yeah, that's correct.

But what happens if they aren't next to each other?

The code in the alarm to connect rooms only checks other rooms that are adjacent to it, so it never checks a room that is not adjacent.

Also, how do you handle the case that two rooms are adjacent but have no opening at the shared edge?

Every space in the grid is filled with a room; there are no blank spaces. Every room will have adjacent rooms.
If I connected every adjacent room, it would look like this:

+-----+ +-----+ +-----+ +-----+
|     | |     | |     | |     |
|  A  ---  B  ---  C  ---  D  |
|     | |     | |     | |     |
+--|--+ +--|--+ +--|--+ +--|--+
   |       |       |       |
+--|--+ +--|--+ +--|--+ +--|--+
|     | |     | |     | |     |
|  E  ---  F  ---  G  ---  H  |
|     | |     | |     | |     |
+--|--+ +--|--+ +--|--+ +--|--+
   |       |       |       |
+--|--+ +--|--+ +--|--+ +--|--+
|     | |     | |     | |     |
|  I  ---  J  ---  K  ---  L  |
|     | |     | |     | |     |
+-----+ +-----+ +-----+ +-----+

Which is fine, and it does happen from time to time, but this (below) is a much more interesting map:

+-----+ +-----+ +-----+ +-----+
|     | |     | |     | |     |
|  A  ---  B  | |  C  ---  D  |
|     | |     | |     | |     |
+-----+ +--|--+ +-----+ +--|--+
           |               |
+-----+ +--|--+ +-----+ +--|--+
|     | |     | |     | |     |
|  E  ---  F  ---  G  | |  H  |
|     | |     | |     | |     |
+-----+ +-----+ +--|--+ +--|--+
                   |       |
+-----+ +-----+ +--|--+ +--|--+
|     | |     | |     | |     |
|  I  ---  J  ---  K  ---  L  |
|     | |     | |     | |     |
+-----+ +-----+ +-----+ +-----+

[torigara]

Well, that setup will guarantee that every room is at least connected to one other room... but it doesn't necessarily mean that every room is connected together each other. An extreme example:

+-----+ +-----+ +-----+ +-----+
|     | |     | |     | |     |
|  A  ---  B  | |  C  ---  D  |
|     | |     | |     | |     |
+-----+ +-----+ +-----+ +--|--+
                           |
+-----+ +-----+ +-----+ +--|--+
|     | |     | |     | |     |
|  E  | |  F  | |  G  | |  H  |
|     | |     | |     | |     |
+--|--+ +--|--+ +--|--+ +-----+
   |       |       |        
+--|--+ +--|--+ +--|--+ +-----+
|     | |     | |     | |     |
|  I  | |  J  | |  K  ---  L  |
|     | |     | |     | |     |
+-----+ +-----+ +-----+ +-----+

You may have to use some of maze generating algorithm to ensure that there is always a path from the start to goal.

[Mr Weird Guy]

I just can't figure out a working algorithm, so I think I'm gonna opt for the easier but more time-consuming method: Manually creating like 50-100 different path setups, and just having the game create paths based on the setup chosen. Time consuming, sure. But at least it'll 100% prevent secluded rooms.

[Noshire]

I just can't figure out a working algorithm, so I think I'm gonna opt for the easier but more time-consuming method: Manually creating like 50-100 different path setups, and just having the game create paths based on the setup chosen. Time consuming, sure. But at least it'll 100% prevent secluded rooms.

While manual level design can be the better choice at times, a roguelike would typically be more enjoyable using randomly generated mazes. Since there's already extremely well-documented sources about basic and advanced maze generation algorithms, I feel it'd be most helpful to just provide some links on the subject:

The wikipedia entry, which features simple, non-programmati explanations on how the algorithms work: http://en.wikipedia....ation_algorithm

A few basic things: Probably one of the most essential parts of such an algorithm is the use of a recursive function. Start from one cell (either random or fix) and flag it as a "passage". Search for adjacent, not-yet-flagged cells that fall within your conditions, and let the script execute itself with the new target. This little loop will spread out further and further, until your conditions aren't met by any targeted cell anymore. It will then run out.

The simple algorithms will generate typical mazes with narrow corridors and no big rooms. You can, of course, change the conditions and behaviours of your algorithm to remodel your random dungeons. For example, defining the output of the generation as a "grid" which you would then scale up and place big nodes (rooms) at each junction would give you your desired "big rooms with small straigh corridors" look.

It takes quite some trial and error at first, but it can be more than worth it in the end.

One important note on recursive functions in some versions of GM (not sure which are all affected): Variables used in scripts without further definition are treated as object variables, and will mess up any script with multiple recursions. Define them as vars (var MyVar;) in the script in order to avoid this.

Hope I could give you some ideas.

[RPSR1994]

Mr Weird Guy you don't know (that's why I'm telling you xD) but you will be credited in my coming (still very far) game.

When I read part of your first post I immediately started building my own random dungeon generation code. Worked at the first try. Since you were the inspiration for it I am glad to provide it to you (only you) in case you haven't figured something out yet.

Maybe you can adapt it to fit your needs, since mine doesn't have the same goal as yours.

Edited by RPSR1994, 27 July 2012 - 05:58 PM.