I am Paul Scharf and Hexdef is an RTS game prototype I started in my last year of high school and worked on in my free-time for about a year.
The game had several interesting and well developed features and algorithms, and was quite playable, both alone and in multiplayer.
Some of these features I would like to highlight and describe in this technical overview.
As the name suggests, Hexdef is a tower defence game on a hexagonal tilemap. Tiles can have a number of different states, most importantly, they can be either blocked or open to movement for enemy units.
During busy periods, the map can easily contain hundreds of enemies, which all try to find their way to the main building of the player to destroy it. Further, the map can change dynamically:
The player can build new buildings to block of paths, but also destroy buildings, and blocking parts of the original level itself, potentially creating new paths.
Using regular pathfinding algorithms – like A* – for all enemies is possible, but not very efficient.
Instead, the game maintains a breadth first tree of the entire level, where the root is the goal of the enemies, and all nodes have as parent a node that leads towards that goal the fastest.
In fact, storing the direction to the parent node is all that is needed for each tile to allow enemies to proceed towards their goal.
Any time a tile in the map is updated, instead of recalculating the entire tree, only that specific tile is marked as changed, and the possible change is propagated towards the leaves of the tree. This propagation is done for only a few hundred tiles every frame to allow high frame rates even if large areas of the level change at the same time.
One feature that adds depth to Hexdef is that the players buildings cannot see and shoot enemies if they are obscured by blocked tiles.
When placing a building, its range and visible tiles are shown to the player in real time. Further, with the level being dynamic, the visibility of buildings has to be updated when tiles inside their range become blocked or unblocked.
The way this is done is by enumerating all tiles in range of the building by spiralling outwards from its position. While doing so, a list of blocked angular intervals is kept and updated for every blocking tile, by adding its visual angle to the list.
The intervals are also combined with ones they intersect to increase performance. This effectively decreases the worst case runtime of the algorithm from the O(n4) of a naive implementation to O(n3), where n is the maximum range considered.
Keeping track of what interval the currently enumerated tile (may) belong to further decreases the runtime to O(n2) which is optimal, since there are that many tiles to consider.
In practise the algorithm runs fast enough to update a number of buildings, even with large ranges every frame.
However, this is rarely needed. Since the player often changes more than one tile in sequence and in the same area, waiting a small time before updating visibility decreases the number of times the algorithm has to be executed drastically.
Additionally, to make targeting of enemies very cheap, each tile keeps a list of all the enemies located on it, so that the buildings only have to enumerate through their visible tiles to find a target. For nearest-target or furthest-target, either by distance to the building, or distance to the enemies goal, the tiles can additionally be sorted to allow for early termination of the search.
An important aspect of Hexdef is that it has procedurally generated levels.
The way this is done is by starting with a fully blocked map and generating a given number of points using stratified grid sampling, as well as one point for the enemies' goal, and their spawn locations.
These points serve as intersections of multiple paths in the map. The generate these paths, random points are connected by straight non-intersecting lines until all points are inside this graph. This generally results in good local connectivity and several loops which make the level more interesting.
To not make paths too straight, instead of clearing tiles in a straight line, tiles are cleared by performing a biased random walk for each path. In essence, the random walker prefers to continue walking in the same direction, not changing too often and is drawn back towards the direction leading towards its goal. This can easily be parametrised to achieve specific local behaviour and results.
In addition, when clearing a tile, a number of random tiles around it are cleared as well to make paths slightly wider and the nature of the generating algorithm less obvious.
Lastly, small areas around the spawn and goal locations are cleared as well, as are a small percentage of random tiles all over the level. This allows the player to utilise the generated level to their advantage, and makes closing off and opening new paths easy enough to be an important strategic decision.
The algorithm can be easily adapted and parametrised for different sizes of maps, and different desired topologies – for example from very open to very closed maps, or very random to very straight paths. Many of these parameters could be represented to the player in a user-friendly way to allow them to choose what kind of level to play.
To present the player with a variety of interesting and challenging waves of opponents, all enemies in HexDef are procedurally generated as well.
Enemies are loaded from script files, which each represent a class or range of possible enemies with similar characteristics but different strengths.
For example, there may be slow and strong enemies, as well as fast but weak ones. From these, a number of different enemies can be generated by scaling the different characteristics as specified in the script file.
This is done by using a window of enemies possible at any given time, as determined by game progress or time, and picking a certain value worth of enemies for each wave.
Each game uses a director, that has a steadily increasing income of credits it can spend on enemies. It spawns a new wave every time the accumulated a number of credits proportional to the income. It then tries to invest in a handful of groups of enemies, spawning a number of each, from the available window.
This system allows for a lot of variation, and while the difficulty increases fairly and steadily, it is random enough to make preparing for different possibilities an interesting challenge for the player.
If you are interested in more details of any of the these systems, or anything else related to the Hexdef or my other work, feel free to send me a mail at firstname.lastname@example.org.