In this update I replace the over simple room generation code with something much better. Not only can we generate a vastly more interesting layout but also understand the resulting level topology to create zones, place keys, locked doors and goals.
Room Layout
The old room generation logic was extremely basic, it simply created a grid of values and picked a number of random coordinates. For point it picked, we would write a new value into the grid to form a “seed” where our room would grow from. Once all the seeds were picked we would grow the rooms by expanding them all by one grid cell in all directions, until a room bumped into a neighbouring room, or the edge of the gird. This of course created a number of rooms that were randomly placed and sized, but always square and having no logical layout or flow.
Once the rooms have been written into the layout grid, we can iterate over it and decide to place a floor when we find a room value, or a blocked tile when we find nothing. To build walls we walk from top to bottom and then from side to side looking for adjacent tiles with differing values and place wall between them. Placing a tile entails calculating its orientation and location and adding a new static mesh instance to array.
Separating layout and presentation using a intermediate buffer gives us a nice advantage here, in order to improve our level we need only work on what is essentially a floor plan for later conversion. In fact, we don’t even need to work inside of Unreal to do it and stepping out of the engine for a while let’s us focus on the problem at hand without worrying about correctness or adhering to Unreal’s preferred way of doing things.
Layout Goals
Where as the previous approach had no greater aim than “just building some rooms” we want something better for version two, so lets establish a few desirable goals for the generator.
Goals:
Define a single, well understood path through the level, from start to goal. This is the levels critical path and it must be long enough to challenge the player but not too long that it becomes dull or boring.
Permit locks and keys to be placed into the level. Locks prevent the player from just going directly to the level end, skipping much of the level. Keys require exploration or overcoming other challenges to acquire them. It’s an old idea but still a good one.
Keys must be placed into rooms that are accessible to the player. That is, all keys must be on the correct side (the players side) of the door that they unlock.
Separate up the level into zones, to help fuel our presentation code (to come later) and encourage more variety since each can be themed differently. Zones also let us creating clusters of rooms logically connected through some shared purpose, a kitchen grouped with store rooms of food and cooking fuel, for example.
Support narrative. This goal is a little harder to lock down, but in earlier posts I talked about how the world (or the game board) itself can be used to tell stories. The generation algorithm needs to provide enough topological information to allow for these story elements to be inserted into the final level.
Corridors. Doing an image search for floor plans shows that, where space permits, most rooms are connected by corridors. This is in contrast to rooms being strung together such that accessing one requires passing through another.
Generate varied and interesting layouts.
Well, thats a pretty decent list of goals. Some of them are quite hard to achieve but they all support each other quite well should give a decent foundation when it’s time for theming and decorating, even if it we don’t quite manage to nail all of them.
Generation
After some though I came up with an algorithm that builds levels as a binary tree. A tree gives the desired traits of a critical path from the root (the start) to some other leaf node, nominated as the goal. This path is fully defined so we can add locks into nodes higher up the path and be sure that they will be encountered and dealt with to progress. We can also safely place keys by simply traveling down the other path from a locked node until we find a leaf node that will contain it. Finally zones can be supported by assigning a property to some node in the tree and letting it cascade down to all nodes in its subtree.
So, topologically that sounds like it will meet all the desired goals, but how to actually layout it out? Where as the old approach treated the world as a full space that it should carve rooms out of, here we do the opposite. Starting with a single node, the root, we define a large empty space. Each time we split off child nodes we also subdivide this space into two smaller spaces and importantly a corridor linking them. So, lets see how it looks, walls are rendered in white, spaces in black and doors (unlocked) in grey.
Not too bad! Thats a pretty good layout created by just recursive subdivision with a random termination condition. However, its a little samey and as one of our goals was to produce interesting variety lets do something about that. By adding a step to look at the topology tree and spot patterns we can add in alternative layout choices, lets try adding a layout to create room clusters that could be a suite or similar.
Better, and of course over time we can add many such variations and produce more interesting layouts. These choices can actually be anything we want, so long as they don’t violate the topology described by the tree (don’t link rooms that shouldn’t be) then they will always be “safe”. OK now lets add our logical data, keys, locks and zones.
Nice, locked doors and the matching keys are rendered in lighter colours and zones, rendered in matching but darker colours, have been placed showing areas of the level that are bounded by locks. The critical path is also shown in brown. I’m quite happy with that and combined with the topological data, it hits most of the goals we set out.
Back In Unreal
Putting things back into Unreal is fairly simple thanks to the intermediate data array mentioned earlier. However, one big gotcha that hit me lies in how Unreal uses its build tool, the UBT, to decide what code should be compiled. Simply adding code into the Visual Studio solution (or presumably XCode) is not enough. It also has to be added to the project via creation of a new C++ class via the editor, failing to do this will cause problems and in some situation wont compile the new code reliably. Since I write in C mostly I didn’t have a class to add so needed to create a wrapper class and have it include the room code and headers using the preprocessor.
Anyway, whats it look like in 3D?
And seen from above you can clearly see the layout generated. Note, this is using a different random seed so wont match the earlier layouts.
Now that we have basic levels in place that should support theming well the next step should be realising a theme through materials and decoration, and of course thinking about how we might add those important story and narrative elements.
