When I last wrote about Escape From Epstein Island, I had taken pains to combat an exploitable tactic, constant circle strafing, through changes to the design of the arenas. That was a nice first step, but it wasn’t enough. Currently the enemies all clump up in the middle. There are a few enemies that don’t do this, such as the IDF snipers, or the cabalists, but that’s because they are far range enemies who don’t need to get close to the player. If 95% of the enemies are in the middle, the player is incentivized to keep skirting around the edges, so the enemies needed to start spreading out and intercepting the player.
I decided to implement this behaviour starting with the riot police, who were already functional, albeit simple. All they do is move to the player and shoot at them if there is no cover in the way. Ideally, they’d pincer the player, as seen below.
My first idea was quite simple. If the problem is that the player is circle strafing, then the enemies should take into account the motion of the player, anticipate where they are going, and move there instead of directly to the player. Unfortunately, this isn’t actually what we want.
In the above screenshot what should happen is the enemies both coming around the corners and firing at the player at roughly the same time.
Yet when I move down into the obstacle the enemies “cleverly” move down themselves, anticipating my movement and trying to get ahead of it.
Here we have the same problem. The enemy below is about to round the corner on me. However, I then move upwards, and the pathfinding to intercept this movement takes the enemy back around to the other side of the cover, which ends up keeping me safe.
Do we want the enemies to move to where the player is going, do we want the enemies to move to the nearest spot where they can shoot the player, or do we want something in between? If it’s something in between, how do we weight these considerations? It’s hard to know exactly what behaviour we want out of these enemies, which makes it even more frustrating and difficult to program.
Yellow squares are for debugging. I’ll explain later.
I decided to strip away all the cover from the arena, and took away the riot police’s ability to shoot, so they simply follow the player around forever. After a while, I realized that what we want is the enemies to almost constantly hug the edges of the arena. I programmed them to think that the center is lava. Or more accurately, there is an increasingly powerful force that repulses them from the center the closer they get to it.
At this point the enemies would occasionally move towards the player in a beautiful arc avoiding the center, which allowed the player to move through the middle, while keeping the edges closed. But more often than not, they would clump together and we’d be back to square one. To improve their behaviour, I added an additional force that repels them away from each other, to the point where it ended up reminding me of Boids pathfinding.
While it wasn’t perfect, I was quite pleased with the result. The enemies were spreading out from each other, as well as the center, and I figured that if I could keep this phenomenon roughly in tact after adding back the obstacles, then we’d be in a great spot.
Spoiler warning: That didn’t happen.
And then they exploded.
One of the hardest problems with pathfinding is the transition from obstructed to non-obstructed pathing, and vice versa. Smoothly transitioning from one to the other is a challenge, especially after I added a bunch of conditions to their pathing, asking them to spread out and move away from the center. It’s possible that they got caught in a local maxima, where the force pushing them to the player was equaled by the force pushing them away from each other. Also, the pathing has its own bugs anyway.
Arrows crudely draw towards center. We want the enemies to maneuver themselves so that they face the enemy along the horizontal (in this case) orthogonal vectors.
I went back down to just one individual enemy, and tried a different tack. Circle strafing is by definition movement orthogonal to a vector that points towards the center of the arena. Therefore, we don’t need to know the movement of the player to pincer the player, just their position. We can cross the vector from the player to the center with a vector coming straight up from the floor to find these two directions. What’s more, we can then use the dot product of these two vectors with the player’s momentum, to potentially bias towards intercepting where they are going if we feel like it.
If you don’t know what Dot and Cross products are, you can watch this video, but essentially it doesn’t matter, because I ended up throwing this away when I realized that you don’t need to do any fancy math at all. The cross product works great when the player is near the middle of one of the four sides. If that’s the case, the enemies can move to some position along those lines. Unfortunately, this doesn’t work well when the player is in the corner, since any position away from the player along these vectors will quickly be out of bounds.
Yellow squares show the direction of the cross products. The enemies would move somewhere along those lines.
Instead, we want the enemies to pincer the player coming from vectors represented by the green squares.
The simpler solution is to use the angle from the player to the center to get the pincer vectors. So if the angle is between -30 and +30 degrees, or top middle, we approach from the left and right. If the player is in the corner, the angle will be between 30 and 60 degrees, then the player is in the top right corner, and the approach vectors are from the left and the bottom. And so on and so forth.
Things were looking great with obstacles added back in and just a single enemy, so I added a bunch of riot police back in there, and instantly observed the clumping behaviour again. This is when I realized that there was no easy way to spread the enemies out if they’re all moving towards the same distant goal. Basically, this approach doesn’t allow for that.
Even worse, they weren’t really keeping away from the middle, either, although that’s harder to show in screencaps. The main problem is that it’s not enough for the end result of the pathfinding to be in the right place. The entire pathfinding system, at least for this enemy, would need to be changed. If we want them to stay out of the middle of the arena, we need them to ignore the pathfinding routes that take them through the middle of the arena. It might be possible to modify the pathfinding code to take this into account, although debugging that sounds like a nightmare, but I think it’s time to call it quits and go with a totally different method.
Blue lines represent node links. A flanking enemy would need to stick to the outside paths.
There’s only so much group behaviour that you can get from enemies that aren’t being controlled as a group. Asking the enemies to spread out is one thing, but asking them to spread out intelligently while acting individually is next to impossible. There’s also a reason why so much of AI programming is combined with level designers leaving hints for the AI actors. I’ve already done this for the snipers, who have pre-laid spots which they fire from, and I’ve got some ideas for a modified version of that system here. I didn’t want to have to manually place hints around the arenas, but if I have to I have to.
I’m aware that this is something of an anticlimactic ending, as the problem is still unsolved, but sometimes there’s no way of knowing the right path without treading the wrong one. Also, I hadn’t updated the site in almost a week so I felt that I needed to write something. Back to work.
