Hello everyone, and welcome to another (very delayed) update on 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 blog post, 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 a cost value to each cell in the grid. 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 of 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 is independent of 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 np 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 negligible.
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 that 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 relevant 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