We have a few more pathfinding updates for you this month. These are mostly about integrating pathfinding into the game simulation to test it under real gameplay conditions.

Pathfinding in Game Simulation

We finally got flow field pathfinding implemented in the game simulation! You can see the result below:

In the game simulation, not that much is being done beyond initializing the flow field grids when loading a modpack (as discussed in last month's post) and sending path requests from the movement system to the pathfinding subcomponent. In the movement system, we only have to create the path request consisting of grid ID (extracted from the moving game entity's Move ability), start location (current position of the game entity), and target location (position of the movement target). The request is forwarded to the Pathfinder object referenced in the game state which acts as an interface to the pathfinding subcomponent. After the pathfinding is finished, the movement system gets back a list of waypoints which can then be inserted into the game entity's movement curve.

While all of this sounds pretty simple now, there were still a bunch of fixes necessary to the main pathfinding algorithms to make it work properly. We will quickly go over the major problems that we faced in the next sections.

Diagonal Paths Blocking

When building a flow field, we want to point the vectors of each cell in the direction of the path with the minimum movement cost. The naive way of computing a direction vector for a cell in a flow field is pretty simple: For each cell, we check the integration values for the 8 surrounding neighbor cells and let the direction vector point in the direction of the neighbor with the lowest value. Do that for all the cells and the flow field is ready.

However, this solution is flawed in that it does not account for a specific edge case concerning diagonal movement. You may be able to spot the problem by looking at the example grid below.

Hint: Check the direction vectors in the top corner.

As you can see above, the problem here is that some diagonal paths at the top should not be possible. It's as if the path would literally slips through the cracks of the impassable cells. This behavior is cause by the naive implementation considering all neighbor cells individually. However, logically (or in AoE2 at least), a diagonal path should only be able to exist if an adjacent horizontal or vertical cell are passable. If neither of them are, then the corresponding diagonal cell should be considered "blocked".

The solution to this problem is actually pretty simple. We can find out which neighbor cells should be considered "blocked" by processing the 4 cardinal neighbor cells' integration values first and add an additional check that sets a flag if they are impassable. Afterwards, we process the 4 diagonal cells where we now also check whether their adjacent horizontal/vertical cells are impassable. If they both are impassable, the diagonal cell is considered "blocked" and the integration value comparison is skipped over.

The result then looks like this:

Start/Target Sector Refinements

As previously explained in an older devlog, the pathfinder executes in three stages:

1. High-level search: Search for a path on the sector level with A* using the portals connecting each sector.
2. Low-level search: Build flow fields for all sectors in the sector path found by the high-level search.
3. Waypoint creation: Follow the direction vectors in the flow fields from start to target cell.

The reason we do stage 1 is to save computation time by only creating and building flow fields for the sectors that are visited by the path.

In the inital implementation of stage 1, there were a few bugs that have to be ironed out. For example, one (wrong) assumption we made was that a start or target cell would automatically have access to all portals in their sector. There are some obvious counterexamples, e.g. when the start is on an island:

Ingame example of how such an island could look like. Note that terrain is only one way of creating this situation. Sorrounding the game entity with buildings would have the same effect.

In the situation shown above, we cannot even exit the sector and are confined to the island. Another example would be a situation where only partial access to portals exist:

Start cell (green) and target cell (orange) have access to different portals, even though they are in the same sector. The only way to reach the target from the start is to path through the portals to the neighboring sector on the left.

To avoid these problems, the pathfinder is now doing a preliminary check before the high-level search that determines which portals are accessible by the start cell and the target cell, respectively. This is done by calculating their sectors' integration fields and checking which portals are passable in said integration fields¹. When the A* algorithm in the high-level search is started, we use the portals reachable from the start sector as the starting nodes. The portals reachable by the target cell become possible end nodes.

¹ We can reuse these fields in stage 2 (low-level search) when building the flow fields for these sectors. Thus, it isn't even much of an overhead.

What's next?

You can be excited for more pathfinding updates next month, but then that's probably it. We promise! Other than pathfinding, we also have updates for the renderer pipeline queues up, so tune in if you are interested in more graphics-related progress.

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