October 2009 – MagicalTimeBean

Multiple Target Pathfinding

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.

Development status

Here’s a quick list of what’s been done so far. It is a condensation of my task log and time tracker text file, leaving out all the bugfixes and just listing new features added.

Week of 9/12-9/19:

basic floor drawing
basic editor features (tile and collision map)
main character movement & attacking
animated tiles

Week of 9/20-9/27:

basic creature movement & attacking (line of sight only)
projectile attack that fires at closest target
monster spawners
archer summon
triggers and gates system
simple hud showing HP and summons

Week of 9/28-10/4:

place monster spawners in editor
place gates and triggers in editor
floor data stored and loaded in xml
tank summon
bomber summon

Week of 10/5-10/12:

basic sound effects system
creature AI: pathfinding (slow but works)

Week of 10/13-10-20:

pathfinding optimized
set player start position in floor data

The pathfinding is the big challenge so far with this project. I knew it was going to be the hardest engineering aspect, with the content design being the biggest overall challenge. I’m kind of intimidated by the prospect of tuning damage levels and finding ways to make each stage interesting given the game mechanics. Nevertheless, taking it one step at a time, it’ll get done.

As for what’s next, I don’t keep a huge checklist of subprojects, because I find it too daunting to see ahead of time the hundreds of microfeatures the game needs. My task list tends to be about six items or less, and only items that can be worked on within a week are added.

My next tasks involve:

Creating a few basic monster types (e.g. fast, medium, slow)
Building some test maps with various mazes and situations
Text dialog overlay and menu system

Introduction to the project

I’m making a 16-bit style dungeon crawler similar to Gauntlet or Legend of Zelda. It features summable allies to give it kind of a tower defense twist. Basically, you have to traverse a dungeon and destroy hordes of monsters, but their numbers are too great to take on alone.

All the summons stay in the same position once placed, and can be killed by enemies just like you can. They do things like fire arrows, throw firebombs, and tank damage. Strategic placement of the summons is key to getting through the game.

There will be an upgrade mechanic to boost your allies’ powers, such as attack rate, damage, and special effects like piercing and AOE. I’m also planning a spell system where each summon has an ultimate attack that consumes a potion but devastates the enemy.

Basically, this is the type of game I dreamed of making when I was a kid.

This blog has been started.

Someone at IndieCade proclaimed that it is never too early to show your game project. My project is definitely in its early stages, but I figure it won’t hurt to show it in development.

For now it only has placeholder graphics and basic game mechanics. My next post will have a screenshot or two and a description of the game.