EEI – Teamwork Makes the Pathfinding Dream Work

In the last article, I realized that my original idea for implementing the pincering/flanking behaviour was a dead end. No problem, I thought, as the path forward was obvious and the solution would be implemented within a matter of days. What followed was the most frustrating two weeks of my entire programming career. At least the technical challenge was eventually hurdled.

Early into this rut I realized that I needed to start taking some screenshots of the debugging, because this would probably be interesting content. Let’s start with the screencap below, which illustrates the first failed strategy to get the police to space themselves out. The green diamonds mark a subset of all the tiles that are not in the center. The idea was to have the entities pathfind around only using these tiles. This idea failed for a number of reasons.

As I detailed in the last article, my original idea started by calculating the two vectors orthogonal to the vector from the player character to the center. Imagine yourself as the avatar looking directly towards the center of the arena (or directly away) and holding your arms straight out to the sides. These two vectors are easily found using the cross product of the vector towards the center, and the imaginary vector running from the camera and into the scene.

Unfortunately, we can’t just have our enemies pathfind to some spots at some distance from the player, because traditional pathfinding exists to find the shortest path, which is a straight line. This leaves us with the same gameplay problem that arises from the enemies pathfinding directly at the player, albeit not as pronounced. The player can still just circle around the enemies for days, especially when cover is involved.

What we want is the enemies to take the circular paths outlined here.

This was quickly evident in playtesting, and it’s obvious when you think about it. In the above example, all the player needs to do to avoid the enemy on the right is to circle around the edge of the arena. They’ll always be safe behind cover. Remember, the game has a massive problem where we want to force the player back into the center. If anything, we want to bias the enemies towards giving the player space in the center and taking away the edges, so this solution is a dead end. Any pathfinding solution that tries to find an end spot near the player runs into this problem. We need to bias the enemies to stick near the edges along their entire path.

Part of what made this so challenging is that it wasn’t perfectly clear to me the exact, precise movement I wanted from the individual enemies until I started screencapping them in various positions relative to the player character and manually drawing arrows. If the player is in the absolute dead center, as shown above, the enemies collapsing towards the player is fairly obvious and easy to program. But if the player is anywhere else it becomes far more difficult.

I looked at the above and below images for a while and tried to make sense of them. It looks kind of like the enemies are supposed to move in a circle relative to the center of the arena, but that isn’t the case for the two enemies in the top left and bottom right quadrants. Should the logic therefore be focused on attracting the enemies to the edge then? How do we go about achieving this?

Before I get to the solution, let me dazzle you with beautiful debugging art.

Above we see a ring of red debugging squares surrounding the center of the arena, at a distance equal to the distance from the player to the center. As the player gets closer to the center, the ring shrinks.

Despite the arena’s world position being dead center of the scene, the center of the arena wasn’t actually dead center in the arena. That was the source of a number of extremely frustrating bugs before I figured that out, then a few bugs after, when I accidentally used two subtly differing center positions.

Near dead center.

Anyway, as the player moves from the center, the ring grows.

The ring represents the path we want our enemies to take. That part is actually quite simple, and it took me longer than I care to admit to figure that out. In my defense, I was dealing with a number of other bugs, and the square nature of the arena squashes out a lot of these paths.

There’s no way of explaining this next part if you don’t understand cross and dot products, so here’s a refresher.

Remember when I talked about imagining that you were the player, looking towards the center and sticking your arms out? The way we calculate that mathematically is through cross products. Think of it as a way of getting perpendicular vectors. 

Cross products are a bit like square roots. Every square root gives you two results, a positive and negative number, and you need to figure out which one is correct. Likewise, every cross product gives you two results, depending on the order of operations. You have to figure out which result is correct, and it’s easy to mess something up somewhere. That’s why the diamond colours are flipped in the two images sandwiching this paragraph.

Our beloved ZOGbots need to move perpendicular to the vector facing center, and also towards the player. This is visually represented in the below screenshot, where the purple diamonds represent the intended movement vector of the enemy.

EDIT: Massively simplified this explanation. Essentially one of the two valid vectors perpendicular to the center will have a positive dot product with the vector straight to the player. Once identified, simply move in that direction, as illustrated by the purple line above. 

The yellow diamond represents the rough goal destination, currently outside the arena. The green square is the nearest valid tile.

Since my pathfinding implementation doesn’t work on direction, but rather destination, we calculate some point a fair ways from the entity. Then we work back towards the center until we have found a valid, traversable tile.

This works technically, but unfortunately for gameplay purposes it’s not that simple. If we implement this naive solution, then the enemies display two unfavourable traits. First, they clump up together, which makes it extremely difficult to even see where they are. Secondly, they can still be defeated by brainless circle strafing, since they don’t peel off and try getting ahead of the player.

Red area visualizes area where enemies can choose either path, depending on circumstances.

The solution to this is fairly obvious. In layman’s terms, if the enemy is already close to the player, then they behave normally. However, if they are in an area where either path around the arena is roughly of equal length, then they take two things into consideration. First, they look at the position of all the other enemies, counting up the ones that are along either path to the player, and try to even up both sides. Secondly, they bias towards getting on the path that the player is moving along, to get out in front of the player.

Calculating this lead to one of the most annoying bugs I have ever dealt with. I kept having enemies getting stuck. They would move correctly for a while, then erroneously move back and forth in a small area. 

This is shown by the blue line, which I was calculating for another reason entirely, but which shows the flipped movement of this enemy.

Eventually I realized that there was a problem with the way that the enemies tried to fill each “side” of the circle leading to the player.

The way this should be calculated is by getting the cross product of the vector from the player to the center, flipping this if the dot product between that and the vector from the enemy to the center is negative. Then getting the vectors from the other enemies towards the center, and checking if the dot product of that with the cross product from the pc to the center is positive. If it is, then we’re moving along the same side of the path.

I understand that you’re probably confused by that explanation. Just understand that we’re counting how many of each enemy are on each side of an imaginary line from the pc through the center of the arena.

The actual movement of the enemy is blended between perfectly perpendicular movement around the center of the arena, and movement directly towards the player character. As the pc gets closer to the center, we bias more towards direct movement, and vice versa. This gets stored in another vector, which I was using in the original version of the code to check for the above calculation. The idea is that we count the enemies based on whether or not they are in that path of movement.

Exaggerated (and bad) picture of problem.

Unfortunately, this leads to some nasty false positives, where we start seeing other enemies “in our path,” when they are actually on the opposite side of the pc. This bug was particularly annoying, since it disappeared unless conditions were just right, and the behaviour was proper most of the time.

Before I go, I have to whine about two other bugs.

Can you figure out why the above if statement always evaluates as true? It should be pretty easy, since the dot product of two normalized vectors – and both vectors are normalized – can’t possibly exceed 1. The correct code is seen below.

Why did this bug take me so long to track down? Well because it works half the time, and this particular part of the code ran intermittently. Also, the ****ing IDE blocked the value from me, and I didn’t think I’d make such a stupid mistake.

Then there was this line of code, previously incorrect, which lead to the enemies erroneously counting themselves in the peeling off code, which, you guessed it, lead to correct behaviour the vast majority of the time, and head scratching behaviour every now and then. 

Then there was another whole set of bugs related to the way I do pathing, where the enemies would path to the edges of the nearest cover regardless of whether that made any sense or not.

Finally, I haven’t actually solved all the bugs. If you look around the fifteen second mark in the video, you’ll see two cops getting stuck for a few seconds. I have no idea why.  

I entirely agree with this comment from Dutchy.

But it’s over for now.