Published: Sun 18 February 2024
By heinezen
In blog .
tags: devlog news nyan simulation
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
openage dev updates