Hello and welcome to another Blightmare development blog! Today’s post is a quick look at a programming topic: terrain outlines. In case anyone is wondering what this means, “terrain outlines” refers to the layer of tiles that completely rings the solid terrain in a level. The outline layer is a bit different than the interior tiles because it is just visual – it does not have collision. While it is possible to create sophisticated tile rules that can handle automatic outlining, doing this becomes a bit tricky in the editor from a user perspective because the tiles that you are placing for terrain may change between ground and outline depending on where other tiles are. Having a single master tile ruleset would also be very complex because it would now need to look +/- 2 tiles in all directions potentially to determine what the correct value should be.
Here’s an example of terrain without an outline in the editor, and how it looks outlined in game:
Instead of trying to be tricky, we decided to just generate the outline on-demand and bulk set tiles in a new tilemap layer on level load. This has the nice benefit of automatically being correct no matter what kind of terrain change has been made by the level designer, and it importantly saves them the work of having to paint in the outline while creating the level. In order to do this, we need to be able to generate the entire outline of our terrain logically.
The algorithm we have right now may not the most efficient way to solve this problem, but it is effective and simple which are often highly valuable properties in production code. The algorithm is based on a simple observation: the outline of a single tile is every adjacent tile
This observation can be extended to an arbitrary outline by taking a pass over all interior tiles and collecting all of the distinct locations of their outlines. We use a set data structure for this pass because it ensures that values added to it are never duplicated. A set requires a hashcode in order to work properly. A hashcode is just a number that identifies an object. If the number is chosen carefully, then objects can be entirely defined by their hash codes which allows for very efficient comparison. In Blightmare, we use a bit of a trick to smoosh down a 2-dimensional location into a single number. That trick is just to multiply one value by a large number and add it to the second value. In our case, we use the formula y * 65536 + x because we’re very sure that we won’t have any levels that are more than 65,536 tiles tall or wide.
Returning to the outline algorithm now with our set of the combined outlines of every interior tile, all we need to do is remove the interior tiles to leave just the outline in the set. This takes another pass over all the interior tiles to complete. Here’s a picture of how that process looks:
That’s really all there is to it. On larger levels, this process can take a pretty noticeable amount of time, so we will probably end up pre-calculating this data and baking it into the level before we actually ship the game, but that should be a simple task.
Thanks for taking the time to read this post! Please support the game by heading over to Steam and putting Blightmare on your wishlist. Our Twitter is the best way to keep up to date with this blog and all updates about the game. Have a great week!