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
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’
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
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.