iOS Development Optimizations Part 4 – Pathfinding

Closed

Tower Defense and Hero Defense are actually quite different in terms of pathfinding. For Hero Defense, we had to statically create a nav-mesh at design time, and all of our entities – player and foe alike – navigated it using A* at both the high level and the local level. Since we had so many separate entities moving to so many different targets, the mesh needed to be able to reach the entire map, and the entities would have to calculate their exact path on the fly.

For Tower Defense though, the possible paths are constantly – and drastically changed. Players create mazes using their buildings, cutting off certain openings and creating intricate side lanes. The nav mesh was useless, and A* was pretty much in its worst case scenario. The one advantage we did have was that every moving entity on the screen was heading towards the same destination – the resource the player is trying to protect!

Very helpful, thanks...

The best solution we found is also the simplest. We flood-fill out from the resource building to every square on the map it can reach. The maps are reasonably sized – roughly 20×40 squares – so flood filling the entire thing takes a fraction of a frame. If we had to do this for every enemy, or for many resource buildings, it would add up and cause a significant penalty. However, one flood fill will find the optimal path for any entity on the screen, no matter where it is! We also only need to update this when a tower is built. Ok, that’s a bit of a lie, because there’s one painful situation exposed here.

All paths lead to the roman looking building

Players can create mazes as long as they want in our game – but at all times, the enemies must be able to reach their target. We simply don’t let them place towers where they would permanently block all paths. This means that whenever a player drags a tower out, we need to recalculate the paths for every square they drag the tower over, so we can give feedback when the path is blocked.

Now that's just not fair...

Still, since each flood fill takes less than a frame, and checking for a blocking build is easy (does each entity have a path to the goal or not?), this painful situation is… tolerable. I had intended to implement a predictive solver for the background thread, which would monitor the user’s drag motion and attempt to pre-solve for squares it might end up in. Fortunately, play testing revealed this wasn’t necessary, as the delay was unnoticeable. Concrete data to the rescue again!

This entry is filed under Gaming, NicholasMTElliott.com, Programming, Prophetic Sky. And tagged with , , , , , , , , , . You can follow any responses to this entry through RSS 2.0. Both comments and pings are currently closed.

Comments are currently closed.