So, at the moment the serialization works and the game starts in debug in a few seconds, loading lots of stuff from disk. Territories, routes, cities, etc are all pre-created and serialized in. What’s next? The overworld-level play, in the beginning played at a coarse-simulation level by NPCs. This should be fun. So, it goes as follows:

Generate every so often adventure locations (uncovered tombs, unearthed creatures in mines, dungeons, bandit camps, you name it)

Cities and guilds occasionally give quests

Heroes can accept quests and travel to locations, and succeed or die trying.

Overworld travel applies some coarse simulation based on level, skills, biome, chances of ambush, etc

Dungeon clearing applies some coarse simulation based on level, skills and dungeon traits

Heroes can join other heroes and form parties

I can watch them play and die, eating popcorn

Filter the logs to track individual heroes and parties

What becomes apparent from the above is the need for everything in the title: parties, quests, adventure locations, levels, stats and skills. This is fun stuff, and very very prone to change, but we need to start from somewhere. For quests and adventure locations I have a few books full of good ideas (Tome of Adventure Design, Ultimate Toolbox, Sly Flourish’s Fantastic Locations), so they will be utilized. For stats and skills, I like DnD but I also like some cRPG systems, like Might and Magic series (especially the skill mastery levels and how you need to find trainers to advance a tier). Further posts will target and expand on these subjects

This is a good point for actually using a first form of save state, as the initialization is now computationally intensive. So far, the following things take place:

Load configuration files to create/initialize systems

In the above, ‘or use cached’ implies an adhoc piece of code that looks for a cache file with the results of the process and uses that, or runs the calculations and dumps the results in the end. It exists only in certain parts, when the outputs are very contained, e.g. a 2D array of data.

At this point, I need to serialize the entire “Create world” process, but now the generated results are not simple anymore:

Some new resources

Completely new state of several systems

State of existing resources (initialized now, not initialized before)

I’ve already prepared for that, and I’m using the library cereal for serialization. Currently the process is mostly complete, so the whole “Create world” process takes very little time, as it just serializes data from a 6MB file.

Currently I need to “standardize” serialization of GPU resources (textures, buffer objects), which is a bit trickier but doable. The way it’s getting implemented is as follows:

JSON configuration initializes a config structure, specific to the GPU object, e.g. cTextureConfig has ( dims, target, format, iformat, dtype, miplevels, data, etc)

The config structure is used to initialize the object

A member function can update the config structure from the current state of the GPU resource (this is mainly for textures/buffers that have been updated)

cereal out: update the config structure from current state, then serialize out the config structure

cereal in: load from disk to the config structure, then call Init()

json in: load from the json file to the config structure, then call Init()

I can also implement GPU resource cloning using this config update mechanism

So, this follows straight from the last post about the change of heart regarding HPA*. The new system is slightly different, but generally simpler. Below, I’m going to describe how it works.

Prerequisites

The basic input of this system is a move cost map (a value per pixel) as well as the city locations. To implement this system, we need A* for graphs and grids, as well as a function to calculate a delaunay triangulation as well as a dijkstra map.

Part 1: Connectivity

First calculate a delaunay triangulation of the cities. This looks something like the below (ignore the red edges)

From the triangulation we make a graph. For each graph edge (which is a city-to-city path), we run A*-grid at max quality settings. This calculates a nice path of least-resistance, it’s the “road” if you wish. The path results look like the first image of the post. For 250 cities, we get about 750 paths. For each of those paths, we also calculate and store the traversal cost.

Part 2: Arbitrary point-to-city support

When we need to go from A to B, where the distance between A and B is great, we naturally want to stop at cities to restock etc. So, the final path will look like A -> city0 -> city1 -> … -> cityN -> B. This step precalculates infromation for fast calculation of A -> city0 and cityN -> B.

For each of the eight directions, we calculate a dijkstra map using a slightly customized move cost function: movement towards the direction has less cost, therefore is preferred. The targets of each dijkstra map are all the city locations.

After we calculate all dijkstra maps, we now need to calculate, for each point in the map and for each of the eight directions/maps, the direction towards the least cost. The direction needs 4 bits to store (eight directions plus 1 bit to mark if it’s a no-direction), so direction maps for 8 directions will then cost 32 bits per pixel, which is not bad. And we won’t need the dijkstra maps any more; these direction maps can provide us with a best path to a city given a main, general direction.

This concludes the precalculations, and it will hopefully make sense in the next part.

Part 3: Runtime pathfinding

We have points A and B. From point A, we calculate which of the 8 directions leads more towards B. We pick the dijkstra direction map computed in part 2 above and traverse it till we reach a node, also recording the path while we’re at it. We apply the same process with point B, but we use the inverse direction. So now, we have 2 nodes in the graph, and we run A*-graph to calculate the best path between them. The cost function uses the precalculated traversal costs from part 1. So now, we have: 1) fine path from A to closest city c0 2) fine path from B to closest city cN 3) coarse path between cities c0 and cN. This is all we need to calculate a continuous path from A to B. Some examples below — Red is A -> city0, Black is cityN -> B and magenta is the concatenation of precalculated city-to-city paths. If you zoom in, white points along the path are the cities.

Notes, failure cases and future work

On average, using a Ryzen desktop processor, at max A* quality, it takes 0.22ms per path in Release configuration, or 3.37ms in Debug. For future reference. The cached memory needed for the entire pathfinder (graphs, precalculated paths and direction maps) is about 1.5 MB.

Path coalescing. When calculating the fine paths, every time we calculate one, we can reduce the cost of traversing those tiles just by a little bit. This is akin to making a natural forest path. The first path it’s traversed, it’s wild and kinda tough to get through. Make 1000 people walk on the path, and it’s now a bit easier. Make 1000000 walk the path and it should now be very distinct compared to its surroundings. By reducing the cost a little bit, the path network looks a bit “neater”. Following are images of non-coalesced, slightly coalesced and heavily coalesced. More is not always better.

Embarking/disembarking at random locations. If I want to go to Hawaii, I don’t take the road to the nearest beach and drop a ship and sail. I’d go to a port. So, when calculating movecosts, we can add an additional embark/disembark costs if we’re about to make a change from a water tile to a land tile and vice-versa, unless one of the two tiles is a city. This beautifully controls the movement via the cost multiplier. Set it to infinity, and we’re just not allowed to change to water/land unless via a port. Set it very high, and embarking at any other point is only when absolutely necessary. The good part is that we can identify those points and make them simple ports in the game, as apparently they are naturally exactly that!

Redundancy on short paths. Sometimes, to go from A to B we end up with the following:

This happens as we’re forced to find city nodes, and we pick nodes based on the general direction that we’re heading. Thankfully, we can just add a simple length check like:

2|AB| < (|Ac0| + |c0c1| + |c1B|)

to identify if the coarse path is unnecessary. In those cases, we run an A*-grid to calculate the path between A and B.

Backtracking. Sometimes we get the following sort of backtracking:

If you look at the black path, it goes backwards. Sometimes I can explain it as before we embark on a long trip, we make sure to go to a nearby city to restock, even if it takes us off-route. There are of course other ways to solve it, and they are easy but still need a bit of work, so this is marked as not-important.

More nodes. If the number of graph nodes is deemed too low, and I’m not happy with the large distance between cities, we can always add more nodes. The “optimal” way (not in terms of performance, but of results) of doing it is using a simple loop:

Calculate the dijkstra map

Find largest score (point furthest away from anything)

Add the scoring point into the feature list

Go to 1, until a desired max score is reached

This step should happen before the delaunay triangulation.