This past week I’ve been working on the first parts of the decorator algorithm for The Stranger in Kilstow. One of the most common complaints I see about games with procedurally-generated levels is that the map looks repetitive. If the map uses room templates, then the templates become immediately recognizable after a few plays through, and if the terrain is generated then every area tends to look very similar. To combat those issues, I’m working on an algorithm that can render any given set of geometry with sufficient variance based on a style template. The goal is to make each room look more interesting than just simple geometry, with backgrounds and decorative doodads sprinkled around in a coherent and sensible manner. This should hopefully add a good amount of variety to make the levels feel more unique within themselves and between runs, while also allowing me to do some more advanced things with level generation and using visual cues to tie remote locations together in the player’s mind.
To start things off, I needed a way for the algorithm to understand which parts of the geometry belong together. By getting the algorithm to understand how the pieces of the geometry fit together, it can make a smart decision about how to draw the backgrounds and supporting structures to make the room not feel so bland. I tried a variety of methods to turn a series of small rectangles into larger coherent zones, but what ended up working the best was a weird hybrid of a breadth-first search and a modified binary space partition.
I started by creating a list of bounding boxes for all of the terrain objects. For each item in the list, it looks for any other regions with any amount of overlap. If the two regions fully overlap, then the larger region is kept and the smaller one is discarded. This isn’t really relevant on the first pass, but once the regions start combining together it becomes very possible that a small piece is already covered by a larger area. After that it finds the nearest region and does a grouping check to see if they should be merged into a single region.
The grouping check is pretty simple. It calculates the smallest axis-aligned bounding box that contains both regions and then divides it in half twice. It calculates the number of objects contained within each region and checks the difference across each axis. If the resulting number of objects on either side of both axes is the same then it’s considered a good combination and the two regions are merged into one. If the number of objects are different across both axes, then it’s considered a batch combination and the algorithm stops processing that group and goes to the next nearest region. If there is a discrepancy only across one axis, then it randomly decides whether to keep the group, based on the room’s seed.
The end result is that the room’s geometry is transformed into a series of large regions on the map that all fit together. The next step is to use these regions of terrain to split up the empty space in the room into relevant corresponding regions for each terrain region. Hopefully once I have the empty space partitioning in relation to the terrain, I will be able to have it actually construct a visual representation of any room at least in regards to setting up the platforms and backgrounds to support them to create something that doesn’t look quite so bland.
