Tarchon is now SOULCASTER

Tarchon is a good working title, but I knew it was never going to cut it as a release title. The main reason is the ambiguity. As a 10-year-old in an arcade, on my last quarter of the day, there are two machines I haven’t tried: TARCHON and DUNGEON DESTRUCTION SPIRIT MASTERS. With DDSM, I know what I am getting. It’s reliable. Very likely there will be wizards and swords. Then there is TARCHON… what is this one? Is it sci-fi? Is it going to be one of those puzzle games where it takes four quarters just to understand the rules? The other game promises instant action. I’ll go with that.

A four word title would have been too much, especially when I make the sequel (DUNGEON DESTRUCTION SPIRIT MASTERS II: SWORD ALLIANCE OF THE ANCIENTS). I struggled with 2-word titles for a while. After calling a council of a couple close friends, we landed on Soulcaster. James gets credit for this one, plus a McDonald’s gift certificate. See how handsomely I reward my consultants?

Anyway, I spent some time in Paint.NET earlier this week and came up with a logo. It seems to be a bit too jagged and horror-looking, but it’s in the right direction and the final game will probably have something like this.


New Mechanics: Dialog box, merchant, upgrades, drop items

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.

It’s really coming together.

More pathfinding and AI

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.
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 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.
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.

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:
  1. 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.
  2. 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.
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.