He is Coming

A reddit user asked for help with generating procedural levels similar to a game called He is Coming (Steam). It got me curious how hard it would be to generate such levels with Frigga inside Unity. You can see an example of one level from the game in the screenshot below.

Procedural level from the game He is Coming

Analysis

From the screenshot above, it looks like the game is made of regions that are separated by paths. Notice that each path is exactly one tile wide, which proved to be the biggest challenge in my implementation. Random monsters, treasure, npcs and more are generated on top of paths, and the decorations inside regions are based on an underlying biome. The levels might be infinite or at least very large as I was not able to find a border of the world. There's probably much more to the level but I haven't played the demo for too long.

Goals

I was mostly curious about the about the regions and paths between them, so I set my goals like this:

• Generate finite levels
• Try to produce similar regions
• Aim for paths that are always one tile wide
• Produce very basic biomes and decorations

Regions via Voronoi diagrams

My first idea for the regions was to generate some random points and then compute a Voronoi diagram of the points. That should give us a good starting point for the regions.

Example of a Voronoi diagram for a bunch of random points

You can see in the picture that the diagram does not really conform to the 2D integer grid which means that we cannot directly use the edges from the diagram. Instead, for each edge in the diagram, we need to find a path between the two endpoints on the integer grid. At this point, I wasn't really thinking about it too much, I heard path-finding and my mind jumped directly to A*, so I used that. (I later scraped this solution.)

Connecting Voronoi endpoints via A* pathfinding

The issue with this approach is that it produces paths that are more than one tile wide.

Blue regions highlight some of the places where double paths were produced

Fixing A* double paths

Good news is that we can configure A* to prefer walking over existing paths, bad news is that it doesn't completely eliminate the issue. It definitely helps, but it also produces more dead ends in the level (mostly near the borders) because the algorithm now reuses an existing path instead of making a second path from the dead end.

Blue regions higlight double paths, red regions highlight dead ends

The issues get even more apparent if I force the algorithm to pick existing paths even here. Here I made it so that new paths are 5 times as costly as existing paths. You can see that there are now Voronoi edges with no direct connection as the algorithm picked a longer path on existing path tiles.

Red rectangles highlight Voronoi edges that

Getting rid of A*

I'm sure someone smart could fix the A* star issues but I realized that I can probably get rid of it. I have a level with no obstacles so it's fairly simple to find a short path between two points. Getting rid of the double paths is an entirely different problem though. So I wrote a piece of code that tries to detect that a double path would be created and instead reused an existing path nearby.

I won't even go into the detail of my algorithm as I later realized that there are some unhandled corner cases. Moreover, if I ever plan to attempt to make this work for infinite levels, I would probably have to throw this away this algorithm and start from scratch anyway.

Here's the result of my algorithm with the occasional double path highlighted in red:

Red squares highlight double paths

Using a tileset

Making the level look good was the easiest part as Frigga is very good at that. I decided to use the 1-bit pack from Kenney and setup some basic rules with perlin noise making two biomes - forests and hills.

Level with a tileset applied

Results

GIF with multiple generated levels

Animated results with gizmos enabled

Conclusion

I'm quite happy with the results even though there many aspects that could be improved. If I were to pick this generator again in the future, I would maybe try to make the generator infinite as I've never done that before.