Multiple Target Pathfinding – MagicalTimeBean

Proper enemy pathfinding AI is crucial to the game design. Prescribed routes were out of the question, since they could be blocked easily and the game wouldn’t be very difficult.

Tarchon uses two different types of movement AI:

Gauntlet style, or simple line-of-sight. If there is no obstacle between the monster and his prey, he’ll just move forward. This looks good in an open area, and doesn’t use much CPU. However, if there are walls between you and the monster, you’ll see the Gauntlet Effect: monsters crowding against the wall trying in vain to break through it.
Full pathing with the Djikstra algorithm. I can’t use the A* algorithm because monsters are going to path to the summoned creatures, hoping to kill them, as well as the main character. A* is much faster because it can favor the direction towards the target “as the crow flies” and be right most of the time, saving lots of CPU. Djikstra maps a path to every walkable square within a radius and takes a ton of CPU.

My first solution was to have each monster launch a pathfinder from its square, looking for any tasty targets in their aggro radius. Since the algorithm cost so much CPU, I set this to a range of about 4 squares in each direction.

This didn’t work out. There would be visible monsters just sitting there, not chasing after the player unless he got really close. Increasing the aggro range to 8 or 9 solved this, but at a tremendous CPU cost. It was bogging down my laptop to have even 20 monsters on the screen.

How Pathing Works

Imagine you are stuck in a labyrinth where the walls are blocks of equal size. At some point, a wizard is going to warp you to a random place in the labyrinth and unleash an undead man-bear on you. It’s vital that you find the shortest path back to the exit from wherever you find yourself. Fortunately, you have a piece of chalk with you.

You use the chalk to draw a 1 on the first tile next to the exit. This means there is1 step left until the exit. You then turn left and mark this tile with a 2, move forward and mark this tile with a 3, and so forth. When you reach a dead end, you backtrack until you find a tile that hasn’t been marked yet, and continue your path there. All you are doing is marking tiles with the value of the adjacent tile +1.

Pretty soon you’ll have marked every floor tile in the maze with a number. When you get teleported, you can see the numbers on all adjacent tiles, and move to the tile with the lower number. No guessing, just following the path you’ve already found.

Solution: Large Radius Pathing from Heroes, Line of Sight and Uncrowding

The shortest path from point A to point B is also the shortest path from point B to point A. So rather than have the monsters calculate their own paths, I have the player and summons calculate a large path using their position as the source. The monsters then request this path data from the gamestate, and can pick the closest target and move there. Because there are only 4 possible heroes on screen at once, this cuts down tremendously on CPU usage.

Gauntlet-style movement still has its place. When the monster has a line of sight to a target, he won’t even bother to use pathing anymore. This not only takes less CPU, but it looks better. Pathing in a large open space can be awkward because the monsters usually move in large horizontal and vertical paths, rather than zigzagging to close the distance to their target.

Another optimization is uncrowding. Before a monster even attempts to use pathing or line-of-sight movement, he checks to see if he can even move in any direction. If not, he gets stunned for 30 frames under the assumption that it’ll be a while before a path opens up. If there is only one direction to take, he will sometimes move in that direction, even if it is away from his target. This helps cut down on the “conga line” phenomenon at bottleneck points.

Pathing torture test: over 100 monsters

Special thanks to Gauntlet, Final Fantasy and Legend of Zelda for the placeholder sprites.

tarchon_pathing1 — On game start, the main character broadcasts his path. Each monster hooks into it and takes the first step towards him.

tarchon_pathing2 — More monsters have spawned and our hero's about to get mobbed. Notice the monsters at the top moved upward (out of the path) to reduce crowding.

tarchon_pathing3 — Over 100 monsters are on the map here. They've overwhelmed our hero.

You can see the uncrowding behavior in bottom right area of the final screen. Monsters have moved downward, away from the player, to rally and let the other monsters through.

Maze Solving

The monsters are pretty smart at this point. Check out how easily they solve this maze and overwhelm our hero:

maze1b — The four moblins have found their path and are on the move.

maze1c — The first two have taken a left turn at the fork because this is a shorter path. But the second two go straight, because there are already creatures using the shorter path. They are considering that a longer path because of the higher chance of being blocked by the first two creatures. With this system, the monsters can flank the hero.

maze1d — They've found the hero, ganked him, and assume their uncrowded formation.