Off the beaten path
In my last project I adopted a simple pathfinding approach. If you clicked on any portion of the walkable surface, the algorithm would simply determine the horizontal/vertical goal, scan for collision-free gaps, and build a queue of steps for the character to take. It wasn't elegant or profound but it worked.

This time around I can't afford such an inefficient strategy, since the circumstances are far more complex. There's sprawling terrain, characters which pursue each other, dead-end paths, and so on. So just how do I account for all this?

Trial and error
I grabbed my notepad and started scribbling down scenarios. First I tried a "shrinking box" approach, where I extended a logical rectangle between two points, checked for collisions, and recursively divided that box in half to determine viable paths. No dice. Then I explored the idea of defining waypoints all over the terrain. It was a step forward, but "bad" paths were occasionally chosen and I didn't relish the idea of manually plotting countless waypoints.

Online searches led me to a tried-and-true pathfinding algorithm called A* ("A-star"). Unfortunately the first few articles I found were completely over my head. Then, like an angel appearing in the midst of blinding Silverlight, I found this brilliant A* tutorial by Patrick Lester. He disassembled a complex algorithm into its distinct parts, described each piece in digestible English, and demonstrated the concepts with illustrations and source code.

Adopting A*
If you've had a look at the article linked above, it all sounds great in theory. But could all this voodoo actually be applied in practice? The short answer is a resounding yes!

The key to a successful implementation of A* is to translate an area to two dimensions. No problem in my case since the game is a two-dimensional scroller. To give some visual context to this, take a look at Figure 1 to the right (ignore the cheesy graphics, they're only placeholders). We've got the player character (top right), an enemy (top left), a few Charlie Brown trees and an odd shape in the middle. I've defined the tree trunks and the odd shape as "collidable" objects by wrapping each of them in custom ContentControl called ZoneCollisionArea.

Now take a look at Figure 2. Once the terrain is loaded I scan the canvas in fixed-size segments. If a segment overlaps any collidable object it is flagged as off-limits (the shaded blocks). I've rendered the segments as rectangles for illustration purposes only; the actual implementation is only a logical grid. You wouldn't want to add those visual segments (and thereby punish your framerate) when the underlying workhorse is a two-dimension array of enum values. In this case there are only two TerrainType values, walkable and non-walkable, but there's nothing stopping me from adding more types with various "costs". It's already built into the AI. The enemy would automatically choose the lower cost of "easy" terrain over, say, trudging through a swamp.

And finally, figure 3 demonstrates that the algorithm successfully accounts for the collidable segments and finds an intelligent path for the enemy (from green block to red block). The best part is, when using a binary heap as described in Lester's article, it is extremely fast. I've had five enemies simultaneously chase me around the map without any perceivable hiccups, and that's before implementing any sort of multithreading.

Best of all, if I stagger the timer intervals associated with each enemy instance, they update their paths at different times and avoid overlapping in many cases. Sometimes it even gives the impression that they're intelligently flanking the player or anticipating his next move.