[qkrtjdwls91]

I am trying to program a Dungeon Crawler in C++ but I am having trouble coding a Random Dungeon Generator.

To create a dungeon, I figured that I would randomly place Rooms, then connect the rooms together with passages.
However, I am having trouble figuring out how to connect the rooms together

I posted some outputs of the generator I got up to this point... I told it to create 64x64 dungeon and mark the traversable paths with 'O'

The dungeon information is stored in a 2D array of 0s and 1s where 1 is the traversable paths and 0 is dead end

Attached File(s)

•  output1.txt (2.61K)
  Number of downloads: 29
•  output2.txt (3.01K)
  Number of downloads: 28
•  output3.txt (2.68K)
  Number of downloads: 21

[qkrtjdwls91]

What type of algorithm can I use to create passageways between the rooms

[qkrtjdwls91]

Some more info...

The rooms are stored with their x, y, width, height and can overlap.
I coded a recursive function that groups the rooms that are connected together, the output shows the groupings in numbers.

The output with rooms that are connected in groups...

note: is it possible to edit posts?

Attached File(s)

•  output.txt (1.05K)
  Number of downloads: 22

[ButchDean]

Yes it is possible to edit posts.

A question like this arose before and I suggested that a number of rooms/levels be created manually to ensure playability, and then randomly selected.

[jon.kiparsky]

ButchDean, on 27 December 2012 - 09:56 AM, said:

Yes it is possible to edit posts.

There is a threshold level of fifteen posts before that ability is enabled.

Quote

A question like this arose before and I suggested that a number of rooms/levels be created manually to ensure playability, and then randomly selected.

This is the strategy used in larn, and it's an okay one. If you're getting stuck on level generation, just do this and get on with the rest of the game. You can come back to level generation later.


To come up with a strategy for generating levels randomly, you're going to have to think about what your levels look like, but if we assume you're doing a rogue-like, then you're thinking about a problem in graphs, with a bit of geometry. You have some number of nodes, and you'd like them to make up a connected graph, but not a totally connected one. That is, there should be a path from any node n to each other node in the level. One way to do this would be to divide the total area of the level into some number of "zones", perhaps a 3X2 or 3X3 arrangement, and set one room in each "zone", randomly sized and placed. Now you have a pretty good trick for connecting rooms: start by connecting each room to the room in its orthagonally adjacent zone. That makes a connected graph. Now you can try removing connections at random. When you divide the graph into two non-connected areas, return the last hallway that you removed and call it a level.

To make all this work, you're really, really, really going to want to know the basics of graphs. If you haven't got there, you should at least review macxosnerd's tutorials on graph theory on this site. Better still, take a course in algorithms and data structures, it'll help a lot. A real-live in-person course is the best, second-best would be Robert Sedgewick's coursera version which will be offered again in February. This is a distant second, you will not learn nearly as much watching it as you will by attending a course in person, but it's better than nothing.

In any case, taking the course will spare you a lot of time spent reinventing other people's wheels and spinning your own.

[ButchDean]

jon.kiparsky, on 27 December 2012 - 03:20 PM, said:

This is the strategy used in larn, and it's an okay one. If you're getting stuck on level generation, just do this and get on with the rest of the game. You can come back to level generation later.

Actually, no. It's not just a strategy used to learn. Similar mechanisms have been used in games since the dark ages, where the form of the levels were fixed but things like textures and colors were randomized.

When games incorporate random levels they are almost always (or dare I say always) outdoor. Why? Because it is easier to randomize terrain height and form with the very low risk of rendering a level unplayable like it could very well be for an indoor level, where you have to consider object placement, entry and exit points. None of this needs to be considered for outdoor environments.

Random levels for indoor environments are more of a headache than they are worth for these reasons. Good game programming is not about creating problems for yourself, it's about eliminating them in clever ways.

[jon.kiparsky]

Larn

One of the classic dungeon crawlers. If you look at the source code, you'll find the pre-generated levels.


(As opposed to rogue or hack, which generate levels randomly)

[ButchDean]

Links to the source I've found to ftp sites appears to broken. Would like to see exactly how they've implemented 'pre-generated' levels.

[jon.kiparsky]

I'll try to dig it up. It wasn't super easy to find before, but I might still have it on my machine at home.

[ButchDean]

Sweet! Thanks!

[qkrtjdwls91]

Well, after some more thought, I think I came up with a solution...
I realized that I can ensure that all the rooms are connected together using some variation of Depth First Search (DFS) or Breath First Search (BFS)...

However, since I want them to look somewhat randomized and not a cookie cutter "clean cut" one way through, I am thinking of generating some random numbers to create random passage ways between rooms after a pass with DFS

[jon.kiparsky]

Be careful there - your graphs are going to be cyclical, so it'd be pretty easy to get into a loop.

This post has been edited by jon.kiparsky: 27 December 2012 - 01:02 PM

[ButchDean]

Some people learn the hard way thinking that they're doing something that hasn't been tried before.

[qkrtjdwls91]

ButchDean, on 27 December 2012 - 02:08 PM, said:

Some people learn the hard way thinking that they're doing something that hasn't been tried before.

Does this method not work?

[jon.kiparsky]

qkrtjdwls91, on 27 December 2012 - 05:42 PM, said:

ButchDean, on 27 December 2012 - 02:08 PM, said:

Some people learn the hard way thinking that they're doing something that hasn't been tried before.

Does this method not work?

I like you. You're going to do okay at this.