pathfinding – MagicalTimeBean

Debug Visualizations & Tile Blending

With each project, I put a bit more time into debugging visualizations. I just try to look for things I spend time debugging a lot (where I step through code) and making sure there’s a quick way to show how things are working.

The most basic is the hitbox visualization, which shows world geometry (walls are red, trenches are yellow) as well as actor hitboxes. The monster hitboxes change color when their AI switches from pathfinding to Gauntlet movement (when they are in line of sight).

This is where you can see a few different layers of the pathfinding AI. The blue blob following the summoner is the vision radius. When monsters step on it, they switch from using pathfinding to directly walking towards the player. The numbers in the top right of each tile are the step values for the path map. They actually represent how many tiles away the target is, in this case the summoner. The numbers in the bottom right of the blue blob are the priority levels for the vision. Because summons also broadcast pathing and vision fields, each tile needs to have a specific target based on distance.

Finally we have the targeting radius. This is built just like the radius above, but it’s not obstructed by trenches. It’s used for the archer to pick targets. In the previous Soulcaster games, NPCs would fire off “line of sight” tracers to find targets. Because of how expensive these were for the CPU, they would have to be restricted to intervals of once or twice per second. This just made the AI slightly less responsive. This system is instantly responsive and by my guess, uses about 10% of the CPU power.

Not a debugging feature, but it’s something I just finished today and think is pretty cool. Since the levels are generated from basic elements, I have to teach the computer to do all the nice tile blending I did by hand in the previous games. It’s a fun challenge. This test just shows 16 different blend tiles which use the cardinal directions. To get rid of the divots in the corners of solid walls, I’ll need to add support for all 8 adjacent tiles. This can be used all over the place, for both natural and artificial architecture.

Pathfinding Exhibition

I’ve gotten things to a state where it’s good enough that I want to show it off. This video shows all the features I’ve put in place, and what happens when they’re removed. It’s kind of like that elementary school science experiment where you bake several batches of cookies and leave out a different ingredient each time, to see the results.

The pathfinding AI is a collection of features:

Gauntlet Movement: Monsters move towards the summoner. They will slide along walls with diagonal movement, but can’t navigate around corners and will get stuck easily.
Sidestepping: Even without any maze solving code, the Gauntlet movement can be improved a bit. When monsters sense that they have been blockaded for about one second, they randomly try moving in a diagonal towards the summoner, which helps them get around walls.
Raw Pathfinding: A maze solving algorithm points the monsters towards the closest viable path to the summoner. If the monster has a direct, visible path to the summoner, it switches back to Gauntlet movement, because that tends to be faster than using the path. Notice how the rats on the right side get stuck because they get to the doorway at precisely the same time. I call this the Three Stooges Effect, and I came up with a pretty cool solution for it:
Traffic Fields: A traffic director data type watches the monster movement, and adds vectors to each floor tile. If a monster tries to walk on a tile that has a vector pointing in the opposite direction, it gets blockaded just like a wall. This way, whoever gets there first sets up the flow of traffic for that particular tile. Each vector times out after a second or so of inactivity, which lets the patiently waiting rats through. Look at the rats on the right now–they are behaving so orderly! Even though both rats reach the doorway at the same time, the top one got evaluated first, got its movement vector placed there, and successfully repelled the lower rat (and all his friends). The visualization lets you see the tile vectors as arrows.
Creature Weight: The numbers you see on each tile in the Traffic Field visualization are the “weights” of each tile. These are used in the maze solving algorithm. They actually represent the number of steps it takes to get to that particular tile from the point of origin: in this case, the summoner. The fastest route is easily generated by starting at the monster’s location, and just picking the lowest number from the eight available directions. With creature weight taken into account, any tile occupied by a creature gets its weight bumped up by a couple points, or 5 points if the creature is blockaded. Notice how the rats don’t all take the same path: once a few have started using a particular route, the weight to cross it is now larger than another route. Not only does this decrease the time it takes for a large crowd to solve the maze, but it also has the great side effect of flanking.
Uncrowding: This last one is subtle, but makes a difference. When a monster has been blocked for more than a couple full seconds, it picks a random direction to move which is roughly in the opposite direction they were originally trying to go. This breaks up congestion and slightly improves the maze solving time.

At this point, the pathfinding AI is good enough to leave alone for a while. I just wanted to get it to a point where the monsters don’t get stuck, and you won’t be able to cheese them (at least not easily).

Pathfinding AI Improved

So many rats, it's almost unbelievable — So many rats, it’s almost unbelievable

Pathfinding on the pixel level works great now.

As you can see in the above screenshot, the rats will find their way to you really fast. It’s so much better than the tile based pathing that it’ll take some rebalancing. If an interior room full of fast moving monsters suddenly gets opened, they’ll swarm you really fast if they have a path to you. One archer or knight is not going to be able to take them out. AOE attacks from the bomber will be a bit more effective though, and maybe even necessary if you face something like the above scenario.

A new dimension in balancing will also be the monster AI. The red rats above are using omniscient pathing, meaning they have a psychic awareness of the summoner’s location, and will find the fastest route there. This type of behavior might need to be used sparingly, because it’ll get overwhelming. A lot of lower level mobs will wander aimlessly, use Gauntlet style movement, or need vision to be aggroed. Boss creatures can also affect the AI of the lower level mobs, for example granting them awareness of the player’s position.

Off The Grid: Research Complete

After a quick rewrite of the collision detection system, and a couple extra AI systems that aid in pathfinding (more on that in a future post), I’ve got the monsters working just how I need them to. Even with a super fast spawn rate, they don’t overlap, and if they get deadlocked trying to get into a doorway from opposite directions, they will back off after a moment and retry.

With omniscient pathing turned on, the rats are completely unstoppable.

This is with pathfinding disabled, and AI set to move Gauntlet style (always towards the player).