Sorry that it has been a couple of weeks since my last update…. I’ve been busy making some serious progress on game 2. I’ve been on a sprint to get some major things in place and I have achieved some pretty cool things. One of these things has been formulating a strategy for identifying what to shoot at.
In game 2, there will be the equivalent of the good old Blaster featured in Creeper World game 1. This unit just needs to shoot at the closest enemy Creeper in range. Of course it can’t shoot through solid terrain, so a line of sight (LOS) calculation also has to be done. So, from a Blaster’s perspective it needs to find the closest Creeper within its firing range that can be seen. To do this, a Blaster starts by inspecting the cells closest around it. Imagine the square made up of the 8 neighboring cells in an array. This square expands until Creeper is found. For any Creeper found, a LOS calculation is made. If the Blaster can see the Creeper, then that becomes the target. There is no reason to keep looking at further distances, since the Blaster wants to find the closest Creeper. Also note, that the expanding square doesn’t really remain a square for the entire search. For each cell being checked, the distance from the blaster is also checked. If the distance (actually the distance squared since I don’t want to do a square root calculation) exceeds the range of the Blaster, the cell isn’t checked.
But, what about the equivalent of the Mortar in game 1? Well, I call it the ‘Launcher’ in game 2. Keeping with game 1, it wants to shoot at the deepest/densest Creeper in range. In game 1, this meant searching in an expanding radius just like the Blaster does. But in this case the entire collection of cells in range have to be checked. As each is checked, the deepest Creeper yet seen is remembered. After all cells are checked, the Mortar from game 1 would have remembered where the deepest Creeper was and that becomes the target.
In game 2, the Launcher has an extra constraint. It wants to fire at the deepest Creeper in range, but it can’t fire it’s projectile (missile) straight at the target. Take the following image as an example:
Here you can see that a Launcher is in range of some of the oh-so-evil Creeper. But it is “around the corner” and doesn’t have a direct line of sight. Now, the Launcher’s firing solution has to be: “find the deepest Creeper in range for which there is a path and that path doesn’t at any point exceed the range of the Launcher”. It’s easy to see that there must be a path… imagine if the Creeper had been totally walled off. In this case it doesn’t matter if the Creeper is in linear range of the Launcher or not. No missile could reach the Creeper if there is no way in. But it is also important to realize that even if there is some path to the Creeper, this path can’t just wind around to the far reaches of the map. It would be unrealistic if the missile didn’t have a range, but the Launcher’s ability to target did.
To accomplish this firing solution, the Launcher searches outwards just like described above. As it expands its search radius, it doesn’t just remember the deepest Creeper it has seen. Instead, it remembers every cell that has Creeper in a sorted list. Once finished with the initial scan, the Launcher has an ordered list of all cells that contain Creeper. The item at the top of this list is the cell with the densest Creeper. For this item, the Launcher has to run a path finding algorithm to see if there is a path from the Creeper cell back to the Launcher. This path finding algorithm has a constraint that it can’t consider cells that fall outside of the range of the Launcher. If the path finding algorithm finds a path, then the Launcher has its target and can fire. If not, the next item in the list is inspected in the same way. Every cell that contains Creeper will in turn be inspected until a target is found, or there are no more possibilities.
The path finding algorithm is an AS3 optimized Vector.<int> A* algorithm. Actually its Dijkstra’s algorithm since I don’t use a heuristic because of another unit I have called “Micro-Rifts” that create “wormholes” on the map, but that’s fodder for another blog post…