One of the things I worked on last week was a solution to the procedural level generation that Team One’s game will make use of. Basically, a level is a 2D grid of walls and floors that the player will explore in first-person. The general layout is similar to old-school console rogue-likes, so I took some lessons from them into my level generation.
On a more technical note, I store the level grid as a 2D array of Ints, and bit shift around to store flags and other values.
The first step is to place the rooms. Right now rooms are defined by a min and max size; the number of rooms to place is the maximum number of rooms the level could fit if they were all maximum size, which is weighted by another value that can be used to control how sparse rooms are.
So, once I have the target number of rooms to place, I start randomly selecting positions and room sizes and check with the grid to see if it will fit. If it does fit, I flag those cells as a room and move onto the next, until all rooms are placed.
Once we have placed my rooms, I need to connect them with corridors. Here’s where I use some fun algorithms to get good results.
- Delaunay Triangulation
- Minimum spanning tree
- Tweaked A* pathing
First up is Delaunay Triangulation. I use this to connect rooms that are close to each other.
But I don’t want to use all of these connections as corridors – there’s way too many, and the player will just get confused. To remedy this, I use Minimum Spanning Tree on the room triangles to get a series of connections that will connect every room with the least travel cost overall.
So, I have rooms and the minimum amount of corridor space to connect those rooms. But I want to add a few more pathways, just to mix things up a little and make the level a bit more interesting. So the next step is to randomly add a few of the connections from the Delaunay Triangulation.
Now I have identified which rooms I want to connect with corridors, I have to actually create or tunnel the corridors.
This is where the AStar pathing comes in. I use this to add a bit of intelligence to creating the corridors. For example, if a corridor already connects room A and B, but then room C need to connect to A, it might use the A-B connection if the cost is lower, instead of creating a new corridor joining C-A.
A few things to note – we don’t want zigzagging corridors, because our planned character control scheme will have issues, so to fix this I just add a cost to turning while pathing, which straightens them out.
A great side effect of using this path-finding to create the corridors is this will intelligently create T-intersections where appropriate (which is rare, but awesome when it happens).
So there you have it – I’ve generated a level with rooms and corridors! While I’m making rooms and corridors, I’m also tagging them with a unique ID, so I can identify and locate them easily.
Let me know what you think in the comments.