The navigator
The Navigator is the part of the AI that is responsible for pathfinding. Actually, his algorithm is fairly straightforward. Given an objective by the Manager, the Navigator determines the shortest path through a series of waypoints that are defined in the level file, then hands each waypoint in turn to the Driver.
A system to edit waypoints was already there in the editor; all I had to do was to allow for more than two connections to each waypoint. This leads to a graph of waypoints:
Each waypoint is a circle with a certain radius. Remember that I wrote that these circles were “no longer used in the current version, but I might start using them again in the future”? That turned out to be a good thought. The precise definition of the waypoint circle is this: from any point inside a waypoint circle, all points in the circles of connected waypoints are reachable with a straight line. A picture might help to make this clearer:
(If you spot any violations of this rule in the editor screenshot, please let me know. There is no automated check, because I was too lazy to do the math.) Why is this rule important? Well, when the Navigator determines that the cart is within a waypoint’s circle, he can tell the Driver to start heading for the next waypoint, because he is sure that it’s now in sight.
When asked to plot a course to an objective, the Navigator determines the closest waypoint (measured to the circle’s edge – this can be negative!) to the current position, and takes that as the start waypoint. He determines the end waypoint in the same way, using the position of the objective. Then he applies a standard A* (A-star) pathfinding algorithm, using the distance to the end waypoint as the heuristic.
Now one major rule of real-time game development on Android is: never, ever allocate memory while the game’s running. If you do, you might trigger the garbage collector, which might decide to free up some space, which will cause a noticable hiccup, sometimes as much as half a second. Hash maps? Stay away from them. String buffers? Pre-allocate a byte array that is sure to be large enough. Vectors? Array lists? Be sure to reserve as much as you’ll ever need, and you’d better know up front. Pre-allocate, pre-allocate, pre-allocate.
Anyway, the A* algorithm requires a priority queue implementation. There are several ways to implement a priority queue, but the binary heap is one of the few that allows us to pre-allocate without headaches. This is possible because this seemingly complex structure can be efficiently and easily represented by a simple array. Since the number of waypoints is known in advance, and the queue will never be larger than that, we simply allocate an array that’s large enough, and we’re done. There is just so much simple beauty and elegance in that data structure, that it makes me happy that I could put it in.
The A* algorithm also requires two sets of waypoints (the ‘open’ set and the ‘closed’ set), but we can simply store these as two boolean flags on the waypoints themselves. Parallel A* runs by different AIs will have to work on different sets of waypoints, but we can allocate those up front, so that’s no problem.
So, given our A* pathfinder, out pops the shortest route from the start waypoint to the end waypoint. Which waypoint to hand to the Driver? The start waypoint, right? Not necessarily. Recall that the start waypoint is the one closest to us, so according to the newly computed route, it might be the wrong way. We therefore hand to the Driver the last waypoint on the route that is still visible from our current position. So if we’re in a corridor, containing several waypoints to follow, we’ll immediately head for the last one, without bothering with the intermediate waypoints. If we go around the corner and the next waypoint becomes visible, that one immediately becomes the new target. Visibility checking is done by the Box2D physics engine, which is efficient native code, so it’s blazing fast.
So that’s it for the Navigator. It’s a good thing that I saved the Manager for last, because he’s still pretty simple-minded and not very effective. This is partly because he hardly communicates with those that he commands. It’s just too realistic! I guess that’s what you get for anthropomorphising your code …