It was clear from the outset that Struggle would need a procedural level generation system; in fact I must confess I’ve been positively giddy with the anticipation of writing this system.

What was also clear, however, was that the procedural level generation methods I’d read about simply would not suffice. The trouble with the many excellent dungeon generation algorithms is just that; they’re designed to generate more chaotic labyrinths, whereas I need to generate prisons, warehouses, factories and military bases.

The solution, I hope, is rather simple; pair a BSP tree with an A* implementation to create an orderly layout that isn’t too predictable, detailed below:

Step 1 : Create the BSP Rooms

struggle_screenshot_012

Using a simple BSP tree, we divide our initial map area recursively until we’re left with rooms that don’t exceed the maximum size or are below the minimum required size.

Step 2 : Create the ‘Critical Path’

struggle_screenshot_013

We mark all the rooms we’ve generated in Step 1 as inactive, unused. In practice they simply won’t exist at all, but for ease of visualization I’ve kept them in the diagram.

Now we create the critical path, that is to say the path from the room the player deploys their troops to, to the ‘goal room’ that contains their primary objective for this mission. Ensuring that the deployment room and goal room are both edge rooms and the goal room is chosen from among the farthest-away edge room, we use our A* implementation to get all the rooms between.

These rooms now constitute our critical path. We can store all non-obstacle tiles in the deployment room as potential spawn-points, and know that we can control the decoration and population of the rooms on the way.

Step 3 : Create branches

struggle_screenshot_014

The map isn’t complete just yet, but we have the essentials for a mission. Now that we have the critical path that players need to be able to complete the mission, we can add some surplus rooms to spice things up that might, for example, require skills or equipment to break into that we can’t always be certain the player has.

Once the rooms are added, we iterate through each of the ‘enabled’ rooms and – just for fun – enable one of their neighbours if it has one which isn’t already enabled. This could be driven by a percentage-based quota based on the length of the critical path.

  • Interesting discussion, but I’m diptspoinaed that the focus is on using procedural to create something “realistic” as opposed to make interesting and fun game spaces. Too many devs get sidetracked by making something that looks or behaves realistically, but isn’t ultimately fun to play. Getting the proceduralism to work with the game mechanics should be a core consideration.

  • Stew Trezise

    I absolutely agree, but very often these two goals align. Since this iteration I’ve built two new level generation systems, both leaning far more towards designing areas to facilitate the game’s turn-based combat and cover mechanics. I’m dreadfully tardy with posting about this stuff, but I really should be writing about it in a couple of weeks. It combines a tool to design sections of rooms with a generator that takes the room’s requirements.