Simple A* pathfinding alternative with interesting side-effects

A* pathfinding has become de facto standard for pathfinding in 2D games. However, it does place some constraints on your level design. While it works great in tile based games, I wanted to be able to place objects randomly at any pixel coordinate in the world. With a big map and many units it can get expensive to compute. In this case, developers usually just optimize their game loop, so that the algorithm doesn't get called for every render frame. Since my game is fast paced, I wanted AI to be really responsive to players moving around, so I searched for alternatives.

Another problem with A* pathfinding is that it's almost perfect. Enemies always take the optimal path and become too predictable. I wanted to have some randomness and surprise factor without having to complicate the AI code too much. I also wanted some enemies to be dumb and sometimes not "see" the way to get to the player immediately. But I didn't want them to become too dumb and get stuck on simple obstacles.

And then I discovered steering and obstacle avoidance. The algorithms are simpler, easier to implement and less expensive to compute. You can tweak many parameters to get different behaviors. With simple tweaks you can get the enemies to defend some areas, wait to attack until the player comes closer, act as a group, surround the player, etc. With a little bit of experimentation you can get some behaviors that seem very intelligent.

Since I'm making a game where the players usually have to line up with enemies to hit them, I decided to make that easier for players by having the enemies do the same whenever they can. When the enemy is far away, their priority is to line up with the player while coming close enough to land a hit:

The player can now just move to the right and not worry about having to line up themselves. Additionally, if the player has a ranged attack (throwing axe, shooting arrows, fireballs, etc.) he can simply start shooting and the enemy will make sure he gets in the path of the projectile before it arrives. This makes the combat feel fluid and easy to execute.

For most brawlers the approach above would be enough. Castle Crashers, Rampage Knights and similar games manage to get away with such simple AI because they made their levels with almost no obstacles in the middle of the screen. For my game, I wanted to have more interesting screens with more stuff in the middle: rocks, trees, bushes, pits, etc. on the outside and furniture inside buildings. So, AI needs to be smart about those.

Enter obstacles

Now, what happens when we have some obstacles in between. My approach was simply to allow the enemy to hit the obstacle and then figure out how to go around it:

How do you decide which way to go around? Remember, we are not trying to make the enemies perfect planners, so they can make mistakes. One approach is to simply check which path to go around the object would be shorter. This works fine, but I found out that simply choosing a random direction (UP or DOWN when the goblin hits the bush in the above image) works much better. When you have 4-5 enemies going after the same player, they would split and go around that tree using the upper or lower path. It makes behaviour for a group of enemies seem more natural.

What if the unit has two paths of which one is significantly longer than the other? Or what if one of the paths leads to a dead end? Without going back to full A* pathfinding, we can simply make the enemy figure out they took a wrong turn and reset their 'going around the obstacle' state. We can have a simple variable saying how long should avoiding an obstacle take and tweak that based on the level design and the behavior we want to get.

Protecting an area

Now, let's say you want the enemy to protect an area and wait for the player to come closer? We don't need to change any of the AI code at all, just wall off the relevant part of the level and make sure it's longer than the 'longest path to go around' variable from the main AI code I mentioned above.

The green line in the image above shows a long fence the enemies won't cross because the parameter for going around the obstacle is using a lower value than the green line's length. As the player comes closer to the bottom of the screen, the enemies start to have higher chance of coming out of their area to attack him.

This works pretty good in more complex screens. Having the enemies divided naturally by the level layout makes the game more enjoyable for the player as he can fight enemies in multiple stages.

In the image above you can see three disctinct areas for combat. The player is now in control and can decide on the tactics. Does he storm the enemy in the middle and then have two separate groups to fight. Or he would stay on top of the screen and allow all three of them to come closer so he can use combo to hit all of them with a single shot.

Having the enemy AI constrained by the level layout makes the combat much more tactical than your standard beat 'em up. Now you just need to create interesting level layouts to give enough options to the player.

Using steering to avoid erratic movement

Now, what's steering? Since we run the obstacle avoidance AI all the time, we want to make sure that the enemy movement feels natural. Going diagonally towards down-left and suddenly turning up would feel strange. So, when the player drastically changes his position, we try to rotate the enemy movement in 45 degree steps. This makes the enemies movement fluid and easier to track. Of course, if you hit an obstacle, you would do a 90 degree turn instead.

Sometimes you just want the unit to stop and go the other way. For example, if the tracked player is dead or escaped the room and the enemy starts tracking another player on the other side of the room. In these cases I allowed sudden turns because it feels ok in my game. But if you try it out and it feels wrong, you can smooth it out by steering in 45 degree steps every X milliseconds until you start going into the right direction. The exact value for X depends on the type of unit moving, so you should experiment until it feels good.

Group behavior for enemies

If you make the enemies treat each other as obstacles, you can get very interesting side effects. Most beat 'em up games allow enemies to walk through each other, but if you forbid that and use obstacle avoidance for AI, you can get cool group behaviors. For example, the enemies spontaneously form groups like in the image above without any changes to the base obstacle avoidance code presented so far.

Surrounding the player

In the images above, you can see three enemies approaching the player. As the first one starts to attack, the second one is avoiding the obstacle, i.e. avoiding the first attacker. As he gets close enough, he starts attacking too. In my game the weapon hit boxes are a little bit bigger vertically than the unit boxes, so you can attack an enemy if you're standing adjacent to them vertically as well. From the still screenshot it isn't obvious, but when you see it happening in real time it makes perfect sense.

After that, the third one comes and avoids the initial two attackers. While doing so, he gets past the player as well. Then he turns to face the player and starts attacking from the other side.

What's most interesting is that all of this happens automatically with the standard obstacle avoidance code. You don't have to program some special AI code for it.

Since Son of a Witch is a fun and cartoony game, I only used the simplest algorithms, but you can make it more sophisticated if you want to. I recommend checking out the red3d website for more behaviors like Seek and Flee, Pursue and Evade, Containment, Wall Following, Queuing (at a doorway), Flocking (combining: separation, alignment, cohesion), etc.

read more...   Tweet to @bigosaur Tweet Bigosaur, 2018-05-06