Procedural Map GenerationMy original procedural generation technique generated more open and random feeling maps which looked a little maze-like. It produces a result which looks something like this:
However, while this worked ok for the "kill everything that moves" style of game play, it didn't work so good for the new campaign mode I've been working on (which is more objective based). So I had to come up with something better for this mode which I'm going to tell you about now.
I came across a
great article by
adonaac on a procedural dungeon generation technique which was
originally described by the
TinyKeep dev, Phi Dinh (thanks guys!
). So I won't go into too much detail as these other articles already describe the technique very well, but I will give an overview of my approach and go into some detail about some things I did differently and why.
It's still a work in progress, but here's an example of what it currently looks like:
And here's how I've done it:
(Note that my explanation assumes that you're already familiar with Phi Dinh's technique)1. Generate RoomsWhen it came to generating the rooms, I had to use a different method as I'm restricted to a fixed grid for my maps. I also wanted control over the start and end points of the map which the original technique didn't really cover.
- First I randomly placed my start and end area pre-fabs in random corners of the map.
- Because I wanted my start and end areas to always be at the end of a path, I cheated slightly and added a small "joiner" room right next to them (more on this later).
- Finally, I randomly place random size rooms (I put some restrictions on width/height/area so the room sizes aren't too crazy). If the room is placed in an area which isn't completely free, then it's rejected. I keep doing this until at least 50% of the map space has been used, or after making 100 attempts.
2. Generate Room Graph Next, I generate the
Delaunay triangulation graph of the room mid-points to connect the rooms together, and the
minimum spanning tree of that graph to create a path between rooms which guarantees that every room is reachable (just as described in the original technique).
The one difference is that I've excluded my start and end area prefabs from all of this. This is where the "joiner" rooms come in. They are part of the graph so are joined to all the other rooms, but they also manually join to the start/end areas. This guarantees that the start/end areas are always at the end of a path.
And when it comes to adding edges back to the minimum spanning tree subgraph to create some loops and alternate paths, I've made a slight tweak again. I found that the edges from the Delaunay graph could sometimes be a bit extreme for my liking and could create connections between rooms that were too far away from each other. So to get around this, I instead generated a
Gabriel graph from the Delaunay graph. It has the effect of only creating connections between rooms which are next to each other. So I randomly take about 15% of the remaining edges of the Gabriel graph (after excluding the minimum spanning tree graph edges from it) and add them back in.
Here's an example visualisation of the room graphs:
(Legend: Thin dark red lines = Delaunay triangulation; Thick red lines = Gabriel graph; Green lines = Minimum spanning tree; Cyan lines = Re-added edges from Gabriel graph)Lastly, I create the hallways/entrances between rooms. Because I didn't want to let any hallways join together, I had to use a different technique. To achieve this, I ended up using the
A* search algorithm.
My process to join one room to another with a hallway is as follows:
- First mark all the currently used areas of the map (i.e. rooms and hallways) as "obstacles", EXCEPT for the areas used by the rooms we want to join together (you want to keep those areas free so the search algorithm can move through them)
- Select a random starting point in the area of the first room, and a random finishing point in the area of the second room
- Use A* to generate a path between those points (I'm disallowing diagonal movement, and also punishing direction changes to create straighter paths)
- Using this path, we can now create the hallway
And that pretty much covers it! If something doesn't make sense, or you want further details on anything in particular, then let me know and I'll do my best to clarify.
Thanks again to Phi Dinh and adonaac for the articles on the original technique!
Hope you found this interesting!
Community
