SHDL#04 Level-Generator

Whenever you say "I need extensive, reusable content but I have no time or resources", the cryptid of procedural generation slowly rises from its burrow.

I have a habit of heavily depending on PGC on my games, not out of lazynes but because Id rather spend 100h making a system that generates the perfect, generic game environment for some playthroughs than spending 10h handcrafting it myself. Its easier for me to think of systems instead of edge cases, Im not a good designer and I get bored easily whenever Im not problem-solving so... My 'thing' ended up being quick, arcade experiences that have enough meaningful variation in them for a player to explore most of what the game has to offer without feeling (too) repetitive.

Hell, my very first game project was a Zelda-like with procedurally generated dungeons and puzzles for players to play forever. And of course it was never finished.

That first project ended up helping me a lot on SH because, even tho I was a way worse dev than I am now, I had researched dungeon generation quite a bit for that project and my general idea for the generator system was sound. I brought it back for SH and, surprisingly, managed to not only make it work, but solved most of its problems.

The generator has two basic concepts: Tiles and Doors.

Tiles are prefabs, groups of stored objects where everything is set by hand, from colliders to visuals and internal entities like treasure chests and enemies. Its like a micro, playable level, with entrances and/or exits. Doors are the exits you handplace on the tile, that would connect to other tiles.

By crafting an Unity prefab in a way that the pivot for the group's parent sits exactly on the tile (single) entrance, I could just drop the whole thing inside another tile's door and they would fit perfectly, since both origins align.

With this, I only need to know where to instantiate (doors) and what to instantiate (tiles). What I ended up doing was: beginning with a Start Tile holding a list of its doors (there needs to be no practical difference between it and a normal tile, its just for categorization) and a Generator script, that holds the list of tile prefabs that can be generated and the methods used for generation. The Start Tile will check on each of its doors, calling generation for any thats unused yet while the Generator basically chooses which tile to instantiate and gives it to the called door to hold it, while storing it on an array of active tiles. Once all of a tile's doors are used, it will stop calling for generation. A tile instantiated at a door will come up, realize all its doors are also unused and do the same thing, so on and so forth. What it does in practice is: it decentralizes the blunt of the work of calling checks of availability and edge cases to the tiles themselves so that the actual code for it ends up being extremely simple, while centralizing the methods they call, so that the Generator script still knows everything thats happening, how much happened and where.

The rest of the work is applying level design and dealing with innate geometry mishaps.

The level design part comes into choosing which tile to be generated when and where.

If I want a climatic boss battle at the end of the level, and I know all my tiles branch out in order, calling for more generation once theyre done being generated, I know that the last generated tile on the list will surely be far away at the end of one of those branches, so it can be converted into an Arena for the climatic battle. I can also know which ones are dead-end tiles that ended up not using all of their doors, be it from lack of space around or due to tile limit being reached, and since theyre also at the end of their branches they can also be turned into special things like treasure troves, hard challenges and so on. The problem comes when dealing with geometry.

For example, when called to generate a tile at a door, the Generator checks the space in front of the door for existing tiles to avoid overlaps. This check can be broken down into different sizes so that even if a big check fails, you can still try a small one, and generate a smaller tile there that fits, or in the case there's simply no space at all call off generation on that door and keep it unused.

This creates a problem I couldnt solve before on my first project. If I set the Generator to limit tiles to a maximum number, so that the generation stops once it reaches it, I can guarantee it doesnt go beyond that maximum, but I cant guarantee it reaches the maximum. Even if I allow it to generate 100 tiles, if the geometry of the level creates enough of these cases where doors are kept unused due to lack of space, those doors can never be used and it wont reach the maximum no matter how many tiles you allow. The random generated layout has no space for more tiles in front of the existing doors. By just setting a limit Im still not accounting for geometry problems.

And there's no way to account for them in this system, really. Since the tiles are handmade, they can have all sorts of sizes and shapes while having predetermined numbers and positions of doors, and would require rigid standardization and categorization to allow the algorithm to solve every edge case. But thats not the strength of this approach, tho. This generator is made to be simple, small and readable, while allowing tiles to be handmade to make their design better and more informed instead of a completely procedurally generated one from the ground up that ends up more bland. (or requiring more robust algorithms to generate interesting variety).

What I did to solve it was simple: Adding more dungeon floors.

Since I know about all my tiles and their types, if I ever see my Generator stop generation below the limit I can check for one of my dead-ends and turn it to a special tile. The tile that has two parts, a 'head' and a 'tail' separated by a great distance, so that its entrance and its doors will for sure be distant enough that even if there's no space around the 'head', the generation can continue normally from its 'tail' to end up creating a whole separate floor, as if the tail part is a new Start Tile. I call these tiles "teleporters", because what they end up doing is sectioning parts of the dungeon away to give them more space to grow out, but it doesnt need to be an actual teleporter (even tho it can). An elevator, a long staircase, an actual portal with two sides, anything that physically distances the entrance of the tile from its exits will solve the problem and, since we know exactly when to call for it, we know how many of those are there, and can now count and control the floors, having a multilayered dungeon with a single change in the algorithm.