The Epic Tale of Level Generation Conundrum


Or so it seems right now. Ah, procedural generation, Oh how I love you, and how I loathe you. It's a great solution ensuring that no two playthroughs will be the same. It's a method that allows potentially infinite amount of different levels without the hassle of making as many by hand. But right now I oh so wish I went with handmade levels instead. Here's all the iterations I went though, why they didn't work, and what I intend to do about it.

1. Raycast-based generation on a grid, using streaming levels as rooms

The idea seemed simple at first. To have each room spawn an actor at each doorway, and have them raycast in cardinal directions looking for obstructions. Then to have them spawn a suitable room based on where the ubstructions are, so no two rooms spawn ontop of eachother.

What went wrong 

The raycasting is too expensive to be used like that. It caused a significant lag while generating the level. The raycasts, also, sometimes didn't register hits, or registered them improperly, which resulted in one room spawning in the same space another room was already occupying. It was a mess.

2. Array-based generation on a grid, using streaming levels as rooms

An iteration on the previous idea. To have the locations that are already occupied saved in an array, so an actor that spawns a room can instantly check whether or not a position at 4000,8000,0 is free. No raycasting, all math and logic.

What went wrong

Setting up itself was a pain. Unreal Engine likes to de-estimate (is that a word?) angle and position values. So when I wanted something to be at an 180° angle, the engine was making it 179.9999972°. In theory, a difference that doesn't make a difference. In practice, it makes an actor check if [4001,7999,0] is free. It is. But [4000,8000,0] isn't.

In the end, however, it wasn't this method's undoing, I got it sorted out by using IntVectors and a custom function library I had to create.

So what went wrong? The rooms sometimes refused to spawn. I was sending interface messages "spawn boss", "spawn treasure", "spawn shop", but in the end only the treasure would spawn. Or the boss and the shop. Or any combination of these three. According to people I've been talking to, the fault lies in using streaming levels, or more precisely – level instances being used as rooms. Apparently level instances aren't supposed to be working as instances. Go figure.

Besides that, this method would create issues with navigation volumes, and hence – AI pathfinding.

What went right

The levels that did spawn, were spawning correctly. Without any doorways opened to the void, without spawning on top of eachother, without doorways spawning into a solid wall of another room. The generation was also reasonably fast, and didn't lag the game as much as raycasting did.

3A. Array-based generation on a grid, using actors as rooms

Again, an iteration on the previous method. One of two methods I am trying to make work and refine right now. Yes, I'm working on two methods in paralell. Thanks to that, I hope to avoid burnout, and maybe have two methods to choose from. The only difference from the previous method, is that the rooms are created as actors, not as levels, which, in theory, should get rid of the issues with spawning, as well as those with navigation volumes.

Problems

This method isn't without fault, however. The actor editor isn't really suited for creating levels, and it's rather awkward to set it all up. Every room will take much, much more time than if I were to set them up as levels. Besides that, this method requires me to use only dynamic lighting, since baking lights on actors is impossible. What that means, is potentially massive performance issues.

To add insult to injury, Unreal doesn't cull those lights in such a setup. That means, even the lights on the other side of the map would be still taking up your GPU power. I'll need to create some custom culling mechanic to avoid that.

Chances

If done right, the generation time will be near-instant. This setup will also allow me to manipulate the rooms in many more ways.

3B. Collision-based randomly scattered generation, using actors as rooms

An iteration on 3A method. The rooms are still set up as actors, with all the drawbacks it poses. However the rooms are not being generated one next to another, in a snake-like pattern (if snakes had branches), but instead, the rooms are scattered around an area, and corridors connecting them are being generated later.

Problems

All the problems method 3A had, unfortunately. Besides that, modifying the algorithm so that it generates only rooms with doorways facing inwards on edges of the spawning area, and coming up with a way of connecting rooms in a cohesive and sane manner.

Chances

As 3A, plus it would maybe make the level more interesting? Hard to tell. Methods 3A and 3B are basically "Binding of Isaac method" and "Enter the Gungeon method".  

Afterword

It's tough. It's hella tough. Level generation is probably the most daunting task I've faced so far.