Cerealization

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
  • Load/initialize resources: textures, texture atlases, shaders, renderers, framebuffers, widgets, application states, etc etc
  • Create world
    • Generate (or use cached) a biome map
    • Generate (or use cached) autotiling data
    • Generate (or use cached) a resource map
    • Generate cities, territory map, factions, mines, relationships, etc
    • Generate (or use cached) pathfinding routes

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

City-based pathfinding in the overworld

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:

  1. Calculate the dijkstra map
  2. Find largest score (point furthest away from anything)
  3. Add the scoring point into the feature list
  4. Go to 1, until a desired max score is reached

This step should happen before the delaunay triangulation.