The best way to show the latest changes is through a video. The graphics are still placeholder but you can get an idea of what it will look like. My next step is to make it possible to move from floor to floor. Once that is in, it should feel like a real adventure rather than just a tech demo.
The aesthetics like text and menu animation are details that could have been ignored until later in the project, but it helps keep motivation up to see cool visual effects. When it’s just a slog of behind-the-scenes changes, it is easy to lose track of the excitement of the game. The visuals are also not nearly as complex as the tough stuff like AI and collision, so I can get some easy wins on those days when I just don’t feel like working.
I’ve worked on several new features over the last two weeks, including an upgrade system and a shopping menu. Nevertheless, as I build test maps I continue to find ways to tweak pathfinding so that the monsters behave intelligently, smoothly and aggressively.
One issue is the weight given to creature positions on the map. I give walls and trenches a weight of 9999 to ensure they are never a preferable part of the path. I also poll the creature positions to give creatures some weight–without this, the monsters don’t bother to move around one another, and it’s just not scary.
Fine-tuning of the weight added to squares occupied by creatures has paid off. Below are three examples of too little, too much, and just right. All three screens were taken at the same point after game start, and you can see how many more monsters can reach the player with the proper weight bias.
Weight 0 (no bias). The monsters form a line and get congested. Only 9 creatures have gotten in so far.
Monsters are shaded different colors to show their current movement mode:
Red: Full pathfinding (cannot see target)
Yellow: Uncrowding (cannot reach target and only has one direction to move)
Violet: Has line-of-sight to target and moves toward it Gauntlet-style
Blue: Adjacent to target (attacks repeatedly)
Black: Crowded, no movement options (stunned briefly)
Bias of 50. Still only 9 monsters make it into the hero's room. They take too many extra steps to avoid each other and zig-zag.Bias of 5. This is the best number I found--14 monsters have reached the hero in the same time. That's a 50% improvement.
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.
In Gauntlet, monsters simply move towards the player and get stuck behind walls.
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.
On game start, the main character broadcasts his path. Each monster hooks into it and takes the first step towards him.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.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:
The four moblins have found their path and are on the move.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.They've found the hero, ganked him, and assume their uncrowded formation.
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
