home..

Optimized Enemy Pathfinding

Nathan Reilly / October 2025 (5215 Words, 29 Minutes)

blizzardgame

Overview

This page details how I created a performant enemy pathfinding system for a video game I’m currently developing.

Key Problem Variables:

Goals:

Generally, the behaviour of an enemy will be mostly focused on destroying the player’s base, rather than trying to kill the player themself. Thus, for players, I’ve currently settled with having the enemies periodically check if the player is closeby and within line of sight. If so, they attack the player (walking directly toward them to do so), and if not, they find something to destroy. Thus, as can be seen by the goals above, the pathfinding problem is focused on having enemies identify and navigate to player-built obstacles & structures.

Overall, the system would consist of two main subsystems: target selection and target navigation.

Target Selection

The first necessary subsystem is target selection. Target selection is the process by which the enemy chooses a target obstacle from all available options.

Problem Variables:

Goals:

Solution Exploration

Random Target

Initially, I had taken the obvious (and quite inefficient) approach of just having the enemy query all of the obstacles in the grid, and then pick the one with the smallest distance from the enemy’s position. I knew this was inefficient, so I tried an optimization:

I added flags to obstacles that distinguish what their general purpose is. For example, player-built obstacles (the ones that enemies target) have their own unique PlayerBuilt flag. This allows an efficient bitwise check to determine if an obstacle is a potential target. Then, I created a static helper class responsible for fetching a random obstacle of a given flag, which would be the enemy’s target. The retrieval of a random obstacle was optimized through caching. That is, a previous query would continue to be re-used to avoid having to re-query the grid at every retrieval. The cached query would be updated whenever the retrieved obstacle was null.

This worked efficiently in general. Not sure what the exact performance analysis is but I’m pretty sure it’s an amortized \(O(1)\), since most of the time the retrieved cached obstacle will not be null if there are many existing obstacles.

However, the major drawback was that target selection was completely random, which isn’t very fun. With this system, enemies could indifferently pick targets halfway across the map, or targets that have little to no value such as standalone walls.

If I instead had the helper class sort the targets by value or distance, then we degrade to \(O(n)\) anyways despite the caching. Thus, this was more of a placeholder implementation, and I needed a better solution.

Quadtrees

After doing some research on spatial queries (which involved a bit of LLM usage ofc), I was reminded of a data structure I’d learned about in class: Quadtrees.

Quadtrees are a type of Tree data structure where each internal node has exactly four children, each of which represent a subdivision of the node’s region in world-space. This subdivision allows for efficient (\(O(logn)\)) queries of elements given a specific subregion. This was perfect for my use case. Rather than querying all existing obstacles, I could instead use a Quadtree to only query a subset of obstacles that are nearby to the enemy, considerably narrowing down the possible targets.

Conveniently, there exists a Unity Package that natively implements Quadtrees: NativeQuadtree. I imported this package and implemented an ObstacleQuadTree class that wraps the underlying native implementation provided by this package. Then, I modified the obstacle grid system to allow initialization of an ObstacleQuadTree for each combination of flags.

Whenever an obstacle is added (removed) to the grid, a reference to it also gets added (removed) to any ObstacleQuadTree such that the ObstacleQuadTree’s flag filter contains its own. Thus, taking advantage of the PlayerBuilt flag, I now had a Quadtree that I could use to query player-built obstacles.

Now, efficient target selection was easy. The NativeQuadtree package conveniently allows querying either all obstacles within a given sub-region, or the nearest obstacles to a given position. Thus, I simply had the enemy query the \(k\) nearest obstacles to itself, and then it could choose the most optimal target within the query. For now, I had it choose the nearest one, as I still don’t have a system for player-built obstacle valuation. However, once that system is implemented, the enemy could consider both proximity and value in its choice.

However, although efficient, this implementation does not always provide the optimal target choice. For example, say a very high value target is the 6th nearest obstacle, yet the enemy only queries the 5 nearest. The enemy would ignore the very high value target despite it likely being a better choice. Thus, this system provides more of a heuristic for chosing targets for efficiency purposes. In the end, this may have been good enough.

Now, with efficient enough target selection, what remained was navigation. Given a target obstacle, how does the enemy get to it?

Target Navigation

The second necessary subsystem was target navigation. Target navigation is the process by which an enemy determines a path to the target, and then follows it.

Problem Variables:

Goals:

A*

The first solution I considered was implementing the A* pathfinding algorithm, using it to calculate the enemy’s path to the target. This algorithm is derived from the classic Djikstra’s algorithm that finds the shortest path to any node in a graph. A* improves upon Dijkstra’s in certain cases (such as 2D grids like ours) by using a heuristic to choose the best path to extend, rather than extending paths equally in all directions.

The issue with A* alone, however, is that it is a poor choice when there are many pathfinding agents. With just A*, I would need each enemy to independantly calculate its path to its target. Additionally, while moving along this path, they would potentially need to update it when the obstacle grid’s state changes. Thus, the performance demands would likely blow up with the arbitrarily high enemy count in my game.

Flow Fields

Though using A* alone to calculate pathing for each individual enemy was a naive solution, the algorithm itself could easily be leveraged for a more case-specific solution: Flow Fields.

Flow fields, sometimes called Dijkstra fields, are vector fields that assign a direction to each graph position that indicate where to walk next. On a 2D grid, these are created as follows:

  1. First, a specific cell, the target, is assigned a target distance value of 0. This represents the shortest travel distance needed to reach the target from that cell.
  2. Then, the distance value is propogated outward in the same manner as Dijkstra’s algorithm does its path searching. Consider a cell \(C_1\) and neighboring cell \(N_1\), and let \(D(C)\) denote the distance value of cell \(C\). When the propogation reaches \(C_1\), and if \(N_1\) is walkable, \(N_1\)’s target distance would be assigned the sum of \(C_1\)’s target distance and the distance from \(C_1\) to \(N_1\), i.e. \(D(N_1) := D(C_1) + 1\).
  3. Finally, when the propogation is finished (i.e. has covered the entire graph), a mapping is created that maps each cell to the most optimal neighbor cell to navigate to in order to reach the target. The optimal neighbor cell is set as the neighboring cell with the minimum target distance value.

This works well for a high enemy count use case because it maps any position on the grid to the optimal next navigation position. Thus, each enemy can use the same flow field, and as a result the pathfinding calculation is completely unaffected by the enemy count.

Once again, conveniently, someone had recently implemented compute shader -based flow fields for Unity! This was what I was planning on doing, as it seemed a similar problem to my temperature simulation (for which I also used compute shaders), yet this time I fortunately didn’t have to. The package is NativeFlowField.

Improved Target Selection

When looking through the NativeFlowField package, I noticed that it supported multiple targets. It did so by allowing you to specify the starting target distance grid, and thus I could assign different initial target distance values to cells, rather than only having the target cell start with 0. Because of the way that the flow field construction algorithm propogates distance outward from cells, this initial target distance value could act as a representation of the cell’s actual value. That is, any cell with a smaller initial target distance value would be prioritized, as it would be perceived as “closer” to the “target”.

This leads to a re-interpretation of the target distance value. Instead of being the distance to a single target, it more represents the effective value of travelling to a specific cell. This creates a direct relation between travel distance and value, where travel distance simply decreases the value of a path.

Now, with the flow field construction allowing for multiple targets, I could combine target selection and navigation into a single system! To do so, I simply added all possible targets into the flow field, with their initial target distance values corresponding to their actual value. With this, any enemy that queries the flow field for pathfinding would always make the optimal decision of which target to travel to, based on a combination of distance and value.

Additionally, I made a change to the NativeFlowField package (awaiting a PR merge right now…, 2025/10/26) that incorporates travel costs between neighboring cells into the flow field construction. This way, each obstacle, rather than being interpreted as an unwalkable cell that needs to be travelled around, is instead interpreted as a walkable cell that costs extra “distance”, or cost, to walk through. This cost would be proportional to the time it takes an enemy to destroy it.

Flow fields also provided high flexibility for future mechanics. For example, if some enemies can fly over obstacles, or destroy them quicker, then travel costs could be modified as needed. As another example, if I have enemies differ in which type of structures they value, I can calculate a separate flow field for different targeting styles by changing the assigned target values.

After implementing a small-scale version of this solution, it worked well, and it seems that this is the way to go for the overall target selection and navigation system.

Accounting for an arbitrary-sized map

One key consideration with flow fields is scaling it to an arbitrarily large map. Since the map size is currently unknown, and likely going to be pseudo-infinite, I need to properly handle a few issues:

First, what happens if an enemy is too far from the player’s base to be realistically within the flow field? Second, how do I determine what sub-region to calculate the flow field over?

For the first issue, the solution I came up with (I remember coming up with this while on a run) was to simply have enemies outside of the flow field degrade back to the original target selection system (K nearest using a Quadtree), and then navigate directly toward the nearest player-built object until they are within range of a flow field. While they are using this simplified navigation logic, they will simply destroy anything that gets in the way along their path, ensuring they don’t get stuck. I implemented this solution, and it seems to work fine, so I’ll likely keep it as is.

For the second issue, I decided, as a temporary solution, to have the flow field be calculated over the smallest rectangular sub-region on the grid that contains all player-built buildings, with added padding. The padding (currently 25 cells) is present so that enemies can still navigate around environmental obstacles even if not within the minimal subregion. To keep track of the minimal subregion, I implemented the min-max heap from this paper to separately track the outer-most x and y coordinates of player-built buildings. This implementation worked well, but comes with some obvious drawbacks for scalability.

The minimal region approach breaks down once the player starts placing buildings far outside of their original “base”. This causes the flow field to be redundantly calculated over the large regions lying between “clumps” of buildings. To improve upon this in the future, I’ll need an approach that instead determines multiple smaller subregions that cover the grid more sparsely. E.g. if the player has two main bases, the improved system would provide something like the two minimal regions around each base, and then calculate flow fields for each region individually.

One approach I’ve thought about is leveraging a quadtree, and calculating flow fields separately over the regions of all lower-most nodes that have a player-built building within them. Once implemented, I’ll likely add it either to this journal entry or a new one detailing improvements.

Conclusion

In the end, the flow field approach worked generally well as a performant solution that satisfies all of the goals. In fact, this solution was much simpler to implement than I initially expected, and provides a lot of flexibility going forward. Check out this post for a small-scale demo of the system in action!

Resources

ROUGH

Below is the draft version of this journal entry, where I wrote stuff down as I worked through the problem. Less formalized, but goes into more detail.

Overview

I’m looking to create a performant enemy pathfinding system for a video game I’m currently developing.

Key Problem Variables:

Goals:

Rough Notes, working through it…

Target Selection

A target is an entity that the enemy will choose to navigate toward and attack. There are two main types of targets:

Deciding between the Player and a Structure

The enemy must first choose whether to target the player or a player-built obstacle (i.e. a Structure). This can depend on the enemy’s desired behaviour, although one strategy is to make the decision based on these steps:

  1. Check if the player is visible to the enemy and within some maximum player agro range.
    1. If so, choose the player as the target
  2. If not, choose a structure to target.

Choosing a Structure to target

When choosing a structure, this may also depend on enemy behaviour, but the general principles for the choice are as follows:

  1. The enemy will prefer nearby obstacles. A way to implement this is to simply query the nearest k player-built obstacles (using the PlayerBuilt obstacle flag ObstacleQuadtree).
  2. The enemy will prefer high-value obstacles, to avoid simply attacking low-value structures such as walls. A way to implement this is to choose one of the higher value targets within the k-nearest query results.

Pathfinding

When the enemy has a chosen target, the next challenge is for the enemy to pathfind to the target. The intended strategy here (not yet implemented) is as follows:

  1. The enemy can request an A* flow field to be built for this target which takes into account existing surrounding obstacles, assigning higher weights to them to reflect that they can be broken.
    1. Obstacle weights can be set proportional to how long it takes to destroy them, and maybe higher weights for natural objects vs player-built objects as the enemies to increase aggression toward the player in general.
    2. The A* flow field is built using a compute shader
  2. The enemy then uses this A* flow field for navigation. The A* flow field will be built and cached such that the furthest enemy from the target using it can always use it.
  3. As the enemy moves across the flow field, navigating toward the target, obstacle grid updates may trigger a flow field update. This will be seamless to the enemy, however.
  4. Once the enemy reaches the obstacle, or any obstacle on its path, it will change to an attack state to destroy that obstacle.
  5. Once the target obstacle is destroyed (for any reason, including the enemy itself destroying it), the enemy resets and chooses a new target.

Strategy 2: This takes place whenever the enemy chooses to target a structure.

  1. The enemy requests a direction to move in. This direction is retrieved through an abstraction of a flow field.
    1. This flow field, rather than handling navigation to a single target, handles all of the targets. This works to prevent multiple flow fields generated, and also replaces target selection. Instead, each space on the grid has a weight represented by how much the enemy would want to make their way to it.
      1. Structures are thus weighted by something like: structure value - structure health, and all added as initial data to the flow field.
  2. The enemy moves in that direction.
  3. Once an enemy reaches an obstacle along its directed path, it will break that obstacle. State updates: The flow field is split into several chunks representing a smaller region of the area. When a chunk is updated, its flow field gets updated and then propagated outward into other chunks until the update’s effect is negligible in that chunk, and then propagation stops. This allows updates to only target specific areas.

Ok let’s try and implement this.

V1: No chunking, just generate a large flow field that’s big enough to cover the relevant area, add all obstacles to it.

Some other issues I’ve found:

Let’s make the changes intended though, I’ll worry about those bugs later.

A small problem

So while testing, I found a problem. If I had a player built obstacle behind non-player-built obstacles, the enemies would travel through the non-player-built obstacles (i.e. breaking them) rather than travelling around them, despite them having a significantly higher weight. Since these environmental obstacles had a higher weight, they should have been considered not worth it to break, and thus have been travelled around. ![[paths.png]] Turns out, this is due to the way the flow field is created, and it isn’t necessarily a flaw.

Essentially, the flow field algorithm works as follows:

  1. First, weights of all grid cells are taken as input. If a cell is walkable (i.e. nothing is there), then it’s weight is set to float.MinValue. If a cell is completely blocked, it’s weight is set to float.MaxValue. Otherwise, it has a weight between these two values, where a lower weight is a more preferred target.
  2. Then, the first compute shader calculated the integration field. This compute shader does a certain number of iterations over the entire grid (the default number is 100), where at each iteration:
    1. For each cell, its weight is re-calculated to be the minimum of its current weight and the weight of each of its neighbors (retrieved from the previous iteration/initial values) with the travel distance to each respective neighbor added to its weight. However, if its current weight is float.MinValue (i.e. walkable), it is instead the minimum of the neighbors only. And if its current weight is float.MaxValue (i.e. impassable), the neighbors are ignored and its weight stays as float.MaxValue.
      1. E.g. if a cell’s current weight is float.MinValue, and a neighboring cell has weight -50, then the cell’s current weight becomes -49, i.e. -50 + 1, since the distance to the neighbor is 1.
  3. Finally, the second compute shader calculates the actual flow field. This step is very simple, it assigns a coordinate to each cell representing the position of the neighbor with the smallest weight. This represents the ideal travel direction.
    1. E.g. if cell (0, 0) has neighbor weights: (0, 1): -5, (0, -1) 5, rest float.Maxvalue, then the ideal neighbor to travel to is (0, 1), and thus it is assigned that coordinate as its “next coordinate”.

This works well, but only if the only sort of obstacles are those that cannot be passed through. This is because that, when that is the case, the weights of any target other than the most valuable target can be ignored, as it is assumed that it costs nothing to travel through any target. So, the enemies only ever pathfind around impassable obstacles, i.e. those with their weights set to float.MaxValue. And this is only because the integration field computation treats them as a special case, not allowing cells with that weight to be any lower.

In my use-case, however, this property does not hold. Every target (i.e. obstacles) has a defined health, and enemies must inflict damage on these targets to break them and then travel through them. Thus, simply indicating that environmental obstacles have less value than player-built obstacles is not enough, because the enemies don’t know that it actually costs something to walk through them! Thus, enemies just treat them as if they’re not there.

Solution

The solution I came up with is this: Add a separate buffer (to be passed to the integration field shader) that represents the cost of travelling to a specific grid cell. The integration field shader will then add this cost to its final minimum value, therefore offsetting the benefit of travelling through the cell by the amount it costs to do so.

For example, if cell (0, 0) costs a weight of 5 to travel through, and its minimum neighbor has weight -10 with distance 1, then this cell’s weight will be assigned -10 + 1 + 5 = -4.

Now, if (0, 0) is part of a direct path to a high value target, it won’t necessarily be travelled through, as cells around it may have less travel cost and thus have a lower effective weight.

Now, instead of assigning an extremely high weight to environmental obstacles, they simply have the same weight as walkable cells. Instead, they have a higher travel cost value, which makes them effectively less desirable walkable cells.

Results

This worked! Implementing the new buffer as described changed the enemies behavior to the following:

This was super useful as well, and I felt it could be applied to a bunch of other scenarios (e.g. more difficult terrain), so I added a PR for this feature to the original repo!

Nevermind…

The next day, I did some more testing and found an issue: Enemies would sometimes stop just before they reach their targeted structure. Turns out, this was an issue with my implementation of travel costs. This was kind of embarassing, since I needed to close my PR temporarily to fix this. Thankfully, it hadn’t been merged yet (as I’m writing this, still hasn’t lol. Not sure how active the guy is…)

The issue with my implementation was that the travel cost would end up being added to its cell’s final cost multiple times, not just once, which was intended.

The point of adding the travel cost to the cell itself, as opposed to only adding it to the neighbor cost calculation (which would have nearly the same effect), is that the flow field calculation directly adjacent to the high-cost cell would be incorrect. This is because if the travel cost is only added to the neighbors, then it is only reflected in the neighbors, and thus to the neighbors themselves, their own lowest-weighted neighbor would actually be the high-cost cell. Thus, enemies standing next to it would ignore its cost and likely attempt to travel through it, which is incorrect.

I anticipated this problem and thus decided to instead add it directly to the cell. The problem with this that I didn’t see (which now seems obvious) is that the travel cost would get added at every integration step, without taking into account the fact that it may have been added in a previous step.

Consider cell \(C\) with some non-zero travel cost \(T\) and non-zero value \(V\), and its neighbor cell \(N\) that has no cost or value.

On the first step, \(C\)’s weight is set to \(V + T\), and \(N\) keeps a float.MaxValue weight.

On the second step, however, \(C\)’s weight then changes to \(V+T+T\), which is already incorrect (it should either be \(V+T\), or lower if there are better targets around). On the same step, \(N\) receives a weight of \(V+T+1\), adding \(1\) to \(C\)’s previous weight.

On the third (and subsequent steps), \(C\) continues to receive a weight of \((V+T+1)+1+T\), which is the weight of \(N\) plus one, plus the travel cost. This is because, now, \(N\) has a smaller weight than \(C\) itself, so \(C\)’s final weight is now the result of adding the distance (one) and the travel cost (\(T\)) to \(N\)’s weight instead.

Thus, in the end, \(N\) keeps its correct weight, but \(C\) does not, remaining always \(T+1\) larger than its neighbor. As a result, enemies will never choose to travel into \(C\) (that is, attempting to destroy the structure at that cell), which makes them a complete non-threat. Not ideal for an enemy.

Solution… Again

The simple solution is to actually revert back to the idea of only adding the travel cost to the neighbors, and in addition forcing the flow field calculation step to also include the travel cost. This way, both the integration step and the flow field calculation correctly incorporate travel costs without adding the cost to any cell at all. This avoids compounding the travel cost several times in quite a simple way, and is undoubtedly the better solution.

For example, in the above case, \(C\)’s weight would always just be calculated as \(V\), and remain that way unless a better target is close enough. However, \(N\)’s weight (assuming \(C\) is its minimum weighted neighbor) is calculated as \(V+T+1\). As you can see, only a cell’s neighbor “knows” about its travel cost.

This is also more accurate to what a travel cost of a cell actually represents. That is, the cost of travelling from a neighboring cell into that cell.

Finally, when determining in which direction to travel to while at cell \(N\), the flow field will add \(C\)’s travel cost to its final weight, avoiding the issue of underestimating a cell that has a travel cost, which would cause enemies to always try to walk through them if they are adjacent.

Testing a few times with this solution again, the issue is gone. Hopefully this is the last oversight related to the flow field calculation.

Player Aggression

There are certain cases where the enemy may re-target to the player even if its current target is a structure. Some examples may be:

Resources (that I’ve looked at)