Hello, everyone, and welcome to another round of openage updates. If you enjoyed the pathfinding explanations from our last devlog, you can probably start getting excited because this month's
post will be
all about even more fun pathfinding features. However, we hope that those of you who are not avid pathfinding aficionados can have some fun, too. So, let's get to it.
Line of Sight Optimization
In
last month's update, we showed off the flow fields that are created by our new pathfinder implementation. Essentially, the idea behind flow fields is that instead of computing a single path from start A to target B, we generate a vector field for the whole grid where every cell gets assigned a vector that points towards the next cheapest cell for reaching B. As a result, units anywhere on the grid can follow (or
flow) along these vectors to eventually arrive at the target (see below).
target cell == (7,7); origin is left corner
- yellow == less expensive
- purple == more expensive
- black == impassible
In this example, you can see that the flow field vectors only support eight directions. A side effect of this is that paths become diamond-shaped, i.e., they have turns of at least 45 degrees. While this may not be as noticeable when you are just looking at the static flow field, it can be very annoying when observing units in motion. When controlling units, most players would expect them to go in a straight line if there are no obstacles between the start and target (and not take a detour into a castle's line of fire).
For this reason, we have to do some low-level optimization that smoothes out short-distance paths in these situations.
One of these optimizations is a so-called
line-of-sight pass. In this preliminary step, we flag every cell that can be reached from the target in a straight line with a "line-of-sight" flag. Units in these cells can then be pathed directly towards the target in a straight line without having to use the vector field. You can see the results of doing such a line-of-sight pass in the image below.
target cell == (1,4); origin is left corner
- white == line-of-sight flag
- light grey == blocked flag
- dark grey == passable, but no line-of-sight
- black == impassible
Impassable cells or cells with more than minimum cost are considered line-of-sight
blockers and are assigned a separate "blocked" flag. The same goes for cells that are only partially in line-of-sight, e.g., cells that are on the line between the blocker cells' outer corners and the edge of the grid. The cells marked as "blocked" form the boundaries of line-of-sight vision cones that span across the grid.
For cells with a "line-of-sight" flag, we can skip calculating flow field vectors as they are no longer necessary for finding a path.
Travelling with Portals
One advantage of flow fields is that the generated field may be reused for multiple path requests to the same target, e.g., group movement of units. While reusing the fields can save computation time in this context, the complexity of flow field calculations makes the initial cost of building the flow field much higher than for other pathfinding methods. On larger grids, this can make individual path requests incredibly slow.
To solve this problem, we can utilize a simple trick: We split the pathfinding grid into smaller
sectors, e.g., with size 16x16, and search for a high-level path through these sectors first. Afterward, we only calculate flow fields for the sectors that are visited and ignore the rest of the grid.
To accomplish this, sectors are connected via so-called
portals. Portals are created on the pathable edges between two sectors. Additionally, portals in the same sector are connected to each other if they are mutually reachable. The result is a mesh of portal nodes that can be searched with a high-level pathfinder. For the high-level pathfinder, we can use a node-based approach instead of flow fields, e.g., the A* algorithm, to search the mesh. Finding the high-level path should usually be pretty fast, as it only depends on the number of portals on the grid.
- white == passable
- grey == portal tiles
- black == impassible
What's next?
The only major step left in the pathfinder integration is to include it in the actual game simulation, i.e., building it into map/terrain generation. This should be easier than the implementation of the pathfinder itself, but it will take some effort to get it right. If pathfinding becomes too tedious, we might switch things up and work on something else for a short while. In any case, you will find out what we decided to do in next month's update!
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
.
