Hello everyone and welcome to another (very delayed) update to the current openage development progress. This time, we have a lot to talk about a new larger feature implementation (and a few other cool things that are interesting for you nerds). So without further ado, let's look at the changes.

Pathfinding with Flow Fields

In mid-January, we started working on a new pathfinding algorithm based on flow fields. It is set to enhance our previous pathfinding logic which so far is a pure A* implementation.

For those unfamiliar with flow fields, here is a quick introduction: Flow field pathfinding is a technique that's specifically intended for large crowd movements, which is exactly what we are doing in most RTS games. In these games, you often have situations where a) multiple units are controlled at the same time and b) moved as a group to the same goal location. The key idea behind flow field pathfinding is that instead of finding the best path for every individual unit, as done in A*, we calculate the best paths for the whole grid as direction vectors. These vectors then steer units around obstacles and towards the goal. As a result, all units with the same goal can "flow" across the grid using these vectors, no matter where their starting positions are.

Explaining every detail about flow fields could warrant its own blogpost, so we will stop here and direct everyone interested enough to read the article that our implementation is based on. Currently, we are still demoing our flow field pathfinder to tweak it before we build it into the actual game simulation. The demo shows just the basic flow field functionality, but you should already be able to see where we are going with it.

green == less expensive, red == more expensive, black == impassible

Every flow field pathing request starts with a cost field that assigns each cell in the grid a cost value. This cost determines how expensive it is to move to a cell on the grid. The cost field changes infrequently during gameplay, e.g. when a building is placed.

target cell == (7,7); origin is left corner

yellow == less expensive, purple == more expensive, black == impassible

When we get a pathing request to a specific goal, another field called integration field is computed. The integrated costs of each cell contain the minimum movement cost required to reach the goal from the cell. To do this, we integrate outward starting with the target cell by checking each cell's direct neighbors and setting the cells integrated cost to own_cost + cheapest_neighbor_cost.

As a final step, we create the flow field that calculates steering vectors for each cell. The steering vectors point towards the neighbor cell with the lowest integrated cost. This way, units following the vectors should always take the path with the cheapest movement cost to the goal. This in independent from where their initial position is on the grid.

Optimizations

Since the beginning of this year, we have started optimizing some parts of the code in Python and C++ that were in need of a speedup. On the C++-side, this is mostly addressed by making our internal data structures more cache-friendly. This is especially relevant for our renderer, where cache-friendly data means more throughput and, as a consequence, more objects that can be shown on screen.

In our Python code, we have added multi-threading support to the final media export step in the conversion process. Previously, conversion of graphics data took a significant amount of time, especially for the newer game releases which require processing gigabytes of graphics files. Converting this data would often take up at least 30 minutes.

The new implementation of the media converter now parallelizes the conversion of graphics data using Python's multiprocessing module. This drastically speeds up the overall conversion process by utilizing all available CPU threads. Conversion should now take no longer than 5 minutes for any AoE release.

The table below shows conversion times before and after multi-threading was introduced. As you can see, the great beneficiaries are DE1 and DE2. The other games also profit, although not as much because some files convert so fast that the converter cannot spawn threads fast enough to keep up. This is also the reason why AoE1 is slightly slower now, although the difference is negligable.

Release	Before	After
AoE1 (1997)	28.410s	33.39s
AoE2 (1999)	81.186s	51.01s
SWGB	109.620s	62.07s
HD Edition	67.717s	53.23s
DE1	216.225s	66.48s
DE2	959.706s	250.63s

What's next?

We are going to put more effort into pathfinding, so that we can use it in the actual game simulation soon. That would also require us to properly design collision detection, so the feature might stay in a "work in progress" stage for a while.

Besides the new pathfinding, we also want to integrate more GUI and HUD features as that will become more relavant once we add more gameplay features.

Questions?

Any more questions? Let us know and discuss those ideas by visiting our subreddit /r/openage!

As always, if you want to reach us directly in the dev chatroom:

• Matrix: #sfttech:matrix.org