Tame the Wilderness

Tuesday 15 March 2016

Progress February (and a bit of March) 2016

The development of Ascent of Hintermark continued in February and the first two weeks of March.   Whilst development in January was dominated by tool development, the latest weeks have focused mostly on upgrading the dungeon generation code.  One of the goals of Hintermark is to provide a deeper tactical depth of how dungeons [1] are explored, so this part needs a lot of TLC.  February's work is just the start.

Generating Dungeons

Whilst generating beautiful dungeons is a popular endeavour in the roguelike community, this has not been the focus in February.  The focus has been more on reorganising the backend to handle a tactical underlying structure, and to ensure that dungeons are always traversable.  As some dungeons will be persistent it will break the game if one was unable to traverse through the dungeon during a quest.

The first quest (aka the ambush quest) is the "red thread" which development follows, and the first dungeon visited is a natural cavern.  To generate this cavern an erosion algorithm is used for each room, and then the rooms (and clusters of rooms) are connected by tunnels.

A challenge with the erosion algorithm was that the generated rooms could look quite odd due to the random nature of the erosion.  The general parameters into the generator gave quite varied results, but at room level there were frequently layouts that felt wrong. As a first step in trying to make this better, a set of algorithms were executed to "post-process" the rooms in order to make them fit an overall style of the cavern (e.g a rounded earth cave system needs to look different than a limestone cavern).  As different post-processing produced different results, the obvious step was to allow specification of which post-processing algorithms are used (and in what order) in the etage rules (json-files).

As the dungeon generation got more complex and post-processing became easier to tweak, it was obvious that the Etage Visualiser needed to be extended to inspect each generation step and post-processing for individual rooms.  A rewrite of the generation algorithms to track the steps was done, and the Etage Visualiser was extended with support for viewing each step in detail.  It was easy to then add support for generating each step as an image which could be combined into an animated GIF.

Tactical Structure

While the dungeon generation was making progress, steps were needed to add and maintain a tactical structure in a random environment.  Support for "Areas" was added last year, where an "area" is a prefab(ricated) area that can be added either by design or randomly picked by the generator.  Some examples are e.g the interior of the mayor's house or the town market:

Whilst "areas" have a limited amount of randomised elements, they hardcode specific floors, decor, etc and are too specific for a general dungeon generator.  Therefore, a method was needed to describe only the structure in more abstract terms, and where each etage/dungeon would fill in the specifics.

The easiest starting point was to look at the room structure itself and how it influences the tactical environment.  Imagine an end-room with a single hallway in and a small gang of defenders in the room.  They would most likely set up fortification in the hallway and possibly traps on the way in.  This behaviour would be the same regardless if it was in a fantasy-style dungeon, a castle or even in a dense forest.  Enemies capable of thinking tactically would shape their environment and set up defenses.  The generator needs rules to set up creatures, their tactical environment and most importantly a fun environment that the player can exploit.  After a few attempts and refactoring the mechanism got the inventive name "Structures", and can be combined with "Areas" for an even more powerful tool.

Area elements represent concrete floor types, decor, creatures, ..  Examples are e.g "right-side-wall-desert-style-terrain", "upper-right-corner-riverbank", "red-vase-yellow-flowers", .. Structure elements represent more abstract descriptions , e.g basic ones "permanent wall", "open floor", "optional floor", "stair upwards", .. It is a generator's job to fit in these mechanisms with the normal generation if it decides to (or is forced to) use a "structure".  Structures, like areas, are layered and can have overlapping rules for floors, decor, creatures, items, ..

This is still very much a work in progress, and will be the topic of a more extensive write-up later as I think it is a useful strategy for other TRPGs and roguelikes as well.

Other Dungeon Generation Fixes

Generally the entire backend of the dungeon generation has undergone a major upgrade, where almost no part has been left untouched.  This is not limited to structures and connecting graphs/rooms, but is also a key point in allowing the generators to be a lot more configurable from etage rules.  How to place stairs, the player, exits, room rules, .. are all now part of a very configurable format.

Simplification of the generator code and how we work on dungeons, nudged the underlying code to rely more on higher order lazy iterators to transform dungeons.  The downside of this is more garbage created compared to for-loops, but the readability and conciseness have been greatly increased.  As this is mainly used during the generation step, the extra garbage can be collected before the gameplay of the level.

Continuous Integration

As Hintermark has become bigger and more complex, with a growing test set, it was about time to set up a continuous integration server.  This would help run tests on a different machine than the development laptop (to avoid machine-specific files and behaviour) and ensure that things are working.  Thanks to KolibriFX I was allowed to borrow an older stationary Linux box that now runs Jenkins and happily builds things all day long.  Michael let me borrow a usb wifi-dongle to put it on the home network. When new code is pushed to the source repository, the server will build and test that everythng is (still) ok. Via Slack the server will also notify me on my mobile whenever things are built.

Naturally this took some work, but the hope is that it will save energy in the long run. An extra bonus is that things run great on Linux as well, and not just OSX.

An issue that popped up was that the RNG behaved slightly different on Linux, so the standard RNG was replaced with a modified XorShift+ algorithm where I can store the entire state of the RNG and restart it at any point.  This works regardless of platform now, so tests can rely on RNG behaviour on Linux, OSX, ...  This will also be useful for later save games where RNG state will be stored.

Ambush Quest

As mentioned above the first quest is what forces the development, and in February the focus was on the first cave system in the quest and the encounters there.  This is not finished, but is moving ahead with new dialogues and extending the quest.  The needs of the quest also plays into how we set up the tactical environment (e.g "structures" as explained earlier), but it also moved us more into the gameplay territory.

Component System

A trendy thing in game development these days are Entity Component Systems (ECS). Discussion persists on best practice and how to implement behaviour.  Hintermark had a preliminary component system for creatures (player, people and monsters), but as the tactical environment expanded the player also needed to interact with the environment.  After a refactoring the code, most entities (creatures, items, terrain, decor, ...) in the game can now be composed by arranging components.  The entities' attributes and behaviour is defined by the components it consist of, where the existence (or not) of the right components decide whether it can be attacked, destroyed, ..  This is a work in progress, and some parts of the code rely on types (Person, Monster, Player, ..) but this is gradually being phased out.

Generally ECS separates the code (system) and the data (entities consisting of components), but a more OO approach has behaviour in the components as well.  For now Hintermark uses components with behaviour to keep related concepts together.  As an example the Drop Component has the behaviour to drop items if the host entity (which can be a person, monster, decor, item, ..) is killed or destroyed.

This is still a work in process, but as of 12th of March the player can now target e.g wall-mounted torches.  The player can then shoot them down with an arrow with the same attack/health/drop components as would be used as when attacking a bandit.  This is going to be the focus for more of the March development, along with more work on structures.


  1. In this blog post I will use the word "dungeon" to refer to a generated etage/level, regardless of whether it is an actual fantasy-style dungeon, natural cave system, dense forest or even a town.