For an overview of Oh God Why, including lots of screenshots for examples of the level generation at work, see my previous post.
The most promising of the other things I looked at was how caves are sometimes generated in rogue-like games, known as the cellular automata method. What this essentially does is randomise the map, then iteratively make every section of the map more like the surrounding sections. This tends to make large open spaces with rounded walls but again this wasn't really what I was looking for and didn't fit particularly well with the idea of working clockwise through connected rooms full of spikes. The cellular automata method is usually used for top-down games, eliminating the need to traverse the level under gravity.
The cellular automata method did lead me to the idea of carving out the level from solid areas, rather than connecting up spaces and filling in the gaps. This combined with the pathfinding algorithms from semester 1 eventually led to my final algorithm.
Pseudocode
The algorithm for creating a room is as follows:
- Set all areas as having no travel (solid block of tiles).
- Pick a starting area and end area based on the room type (top left/top right/bottom
left/bottom right).
- Randomise the travel for the start and end areas, taking into account the room type.
- Add the areas that can be travelled to from the start and end areas to a queue.
- For each area in the queue:
- Pick a random travel. This travel must not conflict with any existing travel. Conflicting travel would be if one area has travel to another but the other area does not have travel back. Travel is always possible in both directions.
- Add the areas that can be travelled to from the current area into the queue, unless they've already had their travel set.
An example
Since this is a top left room the start area is M and the end area is D. The start area of a top left room will either have travel up, travel right, or travel up and right. In this case the start area has travel up and right, since the player can move from M to both I and N. The end area of a top left room is guaranteed to have travel right and will additionally have either travel left, travel down, or travel left and down. In this case it was just travel left, from D to C.
The areas of this room we can travel to from the start and end areas are then added to a queue. In this case the queue will have areas N, I and C. The queue is then processed one element at a time until it's empty.
Let's say that the first element in the queue was N. Remember that every area starts out with no travel, so at this point the only areas with travel are M and D, the start and end areas. Before we pick a random travel for N we first want to make sure it doesn't conflict with any existing travels. O and J don't have any travel yet so we don't need to worry about them, but M does and it says that it can travel right. To avoid a conflict we have to be able to travel left, so that bit in N's bit-field gets turned on. Now we randomly decide whether to also travel up, travel right, travel up and right or have no additional travel. In this case we decide we can travel up, so we flip that bit on and push area J into the queue. At this point the queue contains I, C and J. To save you scrolling constantly here's the diagram again, with travel so far included:
This process continues until the queue is empty. At this point it is guaranteed that there are no conflicting travels, but there is no guarantee that every area has travel. In this example areas H, O and P still have no travel. This was one of the goals of the algorithm: that not every area is guaranteed to be part of the path. I think it makes the rooms much more interesting.Unfortunately there is also no guarantee that the set of areas connected to the start and the set of areas connected to the end are connected to each other. If any of the areas has both of the connection booleans set to true it means there is a valid path, which is great. If none of them do then the algorithm has failed and the whole thing resets and starts again. I'll come back to this in a minute.
The last thing I haven't mentioned is why areas B and J look different. Excluding the start area, end area and dead-ends (areas with only one travel, for example L) every area has a random chance of being a tunnel instead of being an open space. Tunnels are narrower and never have spikes or collectables in them. I added tunnels to increase the variety of level geometry created and to help mask the grid-based nature of the levels.
Improvements and next steps
- When the queue is empty check if it's possible to travel from the start area to the end area. If it isn't then restart the algorithm.
This is a pretty bad idea. It's not catastrophic in this case since the algorithm is only operating on 16 areas, but what if it were operating on hundreds, or thousands? I did this in my coursework because it was the simplest thing to do if the start and end aren't connected and I knew the potential repercussions on such a small set would be minimal. I had more pressing things to do, things which would actually gain me marks both in this and other courseworks. But I knew, and it bugged me.
So what to do? Simple: if the set of areas connected to the start and the set of areas connected to the end are not connected to each other, just keep randomly adding travel between areas. Whenever you add travel the connection booleans should be updated as before. Eventually an area will end up connected to both: at this point you're done. There are more elegant solutions of course but I think that'd do the job pretty well.
If you read my overview of Oh God Why, you'll remember I said there were 4 phases to the level generation:
- Generate the tile map.
- Generate the Box2D bodies to represent those tiles in the Box2D world, used for physics and collision detection.
- Place enemies (spikes).
- Place collectables (gold).