"AI AI Three" by Troy H. Cheek on Aug 24, 2009
As I mentioned before, I'm working on a Lua-based computer-controlled opponent (aka Skirmish AI) for the RTS game XTA on the Spring Engine. Last week, I talked about general economy and scouting. This week, I want to talk about pathfinding.
Pathfinding is hard.
There, I said it.
In a nutshell, pathfinding is finding a path from one point to another. That sounds simple, but it's actually pretty complicated. In XTA, most vehicles can't drive under water or over mountains. Kbots (aka walkers) can handle almost any mountain but are again stimied by water. Hovercrafter can handle water just fine, but only if there's a gentle slope of a beach so they can reach it, while they hate mountains or even just bumpy ground. Airplanes can go anywhere, but they are the weakest builders and pretty easy to swat out of the air once you realize the need. In other words, most units can't reach every point on a map from any other point on a map. This is bad if, for example, you want to build something with a construction vehicle but you don't know if a construction vehicle can reach the build site.
So far, my Skirmish AI has dealt with this problem by ignoring it. It only tries to build or attack on dry land and generally tries to build close to existing structures, so it hasn't yet run into the problem of, say, sending a walker to an island halfway across the map. However, my scouting, building, and attack routines would be quite a bit more efficient if they knew the boundaries of what was available to them.
In fact, one of the items I've been building can be built both on land and under water. The air repair pad does exactly what it says on the tin. Damaged aircraft retreat to the nearest one for repairs. It's actually preferable to build these under water because it hides the planes from casual observation. Most land and air units can't attack or even see units under water. The problem is that some land units can build the repair pad, so if I'm not careful, the AI can issue an underwater build order to a land unit. If the build site is close to a beach and the unit's reach is long enough, the build proceeds as normal. If not, the unit flounders around for a while, finally gives up, the AI realizes that it still needs a repair pad, and the same build order is issued again.
This would be less of a problem if my Skirmish AI was a little smarter about issuing build orders. My Central Build AI does an excellent job of issuing the correct build orders to the correct builders, but it's more a helper utility than an actual Artificial Intelligence. It depends on the Natural Stupidity of the player to make sure funky orders aren't issued or, if issued, aren't repeated. While my success with Central Build inspired me to start the Skirmish AI, I haven't integrated the former into the latter. It seems a bit like overkill at this point. Rather than issue the build command to a single builder and order other nearby builders to assist it, I found that I could simply issue the build command to all the builders capable of building it and tell all the others to just assist any project at or near that location. Much simpler. Much less code. Much less hassle.
It works just fine, unless one or more of the builders which can build the requested structure can't reach it. They just kind of mill around uselessly until the engine finally realizes that they're stuck. This wastes valuable build time that could be used on the next project.
Incidentally, this was originally the approach I tried with Central Build AI. A heretofor unknown bug in the Spring Engine caused it to crash occasionally when using this approach, so I had to try another approach. Technically, it wasn't the approach that caused the crash, but the fact that I was using the wrong parameters, but that should have caused a simple error message and not crashed the engine or, in one case, Windows. The developers have since fixed it, so I tried using the approach again. It works pretty well, except in cases where the builder can't reach the location, which brings us back to pathfinding.
The Spring Engine handles pathfinding on its own after a fashion. If the unit can get there from here, it will. Eventually, it will throw up a "can't reach destination" error if it can't. The path might not always be optimal, and it's recalculated on the fly as the unit moves, so it takes up a bit of processing power. I'm told that this is why the engine slows down when there are a lot of units in play. It's not the units themselves or displaying them, it's moving them.
The Spring Engine has some Lua call-ins about pathfinding, but the one that seems most useful (Spring.RequestPath) returns some kind of UserData Object which isn't well documented. At least, it's not documented clearly enough for my muddled brain. The only useful data I've gotten out of the pathfinder call-ins is getting the path of a given unit after it's already been given an order to move, which kind of defeats the purpose. However, there doesn't appear to be a "you can't get there from here" function.
There is some kind of path map displayed by Spring when you hit F2, showing green for areas the selected unit can reach, but I'm not sure if that's something in the map files or something generated by Spring itself. In either case, I don't know how to read it, so it's not much use to me.
I could in theory write my own pathfinding routine. Many years ago, I came across a program listing which described a pretty nifty way to generate (or traverse) a maze. I've since rewritten this program for every language I've learned. It's also good for paint fill or any other purpose where you want to hit every contiguous point in a defined area. I suppose that I could start at the designated start point and work outwards, checking each point around to make sure that a tank (or similiar vehicle) could fit there. I could be reasonably sure that any point so located would be reachable from any other point. This would be computationally expensive, so I wouldn't want to do it often, but I might have to or it won't take into account weapon damage to the terrain or blockages caused by recently built structures.
The simplest way to generate path information on the fly is simply to draw an imaginary line between the origin and the destination, then check a few points along that line to see if each point is passable. This has the disadvantage of returning a false negative if there is an obstacle or water along the shortest path even if there is plenty of flat ground on either side. Of course, you can throw in some wiggle room on either side of said path, but again we're wandering over into computational expensive land.
I also really need to figure out the best way to see if a particular point is passable by a particular vehicle. Currently, I'm telling Spring to test building a particular structure about the same size as the mobile unit at the point in question. If Spring could build at that location, I assume a vehicle could pass. There's probably a better way. There are several "Ground Informations" call-ins which I have yet to decipher. I expect that one of these might be useful.
More later.
