pathing 7 - terrain analysis libraries
Historically, the BWTA library (for Brood War Terrain Analysis) was the solution. Here’s what I learned about the situation nowadays.
roll your own
Of the 13 bots whose source I had handy, these do not use BWTA but apparently roll their own map analysis: MaasCraft, Skynet, Tscmoo. In some cases it may be a vote of no confidence in the BWTA library; in some it may mean that that author wanted to do it on their own. UAlbertaBot uses BWTA for some tasks and its own map analysis for others, and likely some other bots do too.
Ratiotile has a sequence of 6 posts from 2012 analyzing region and choke detection in Skynet and BWTA and reimplements Skynet’s algorithm with tweaks.
BWTA2
The BWTA2 library in C++ is the maintained version of the abandoned original BWTA. I assume this is the version that BWMirror for Java “mirrors”.
I see complaints online that BWTA was slow and crashed on some maps. BWTA2 should at least reduce those problems.
It looks like BWTA2 does pathfinding using a navigation mesh, one of the fancy algorithms that I left for later consideration in this post. I’m thinking that I won’t return to the fancy algorithms because they’re not necessary for Starcraft. It’s easy to guess how a complex data structure leads to a slow and buggy map analysis.
BWEM
The BWEM C++ library (for Brood War Easy Map) by Igor Dimitrijevic is an alternative to BWTA. It claims to provide comparable information and to be more reliable and much faster. It also lets you send events to register that a map building or mineral patch has been removed, and updates its information to match.
I’m not aware of any bot that uses BWEM other than Igor Dimitrijevic’s own Stone and Iron, but I wouldn’t be surprised to find out that a few new bots do. BWEM 1.0 was released in September 2015, and BWEM 1.2 in February.
BWEM calculates ground distances and similar info in O(1) time using grids of data that are written by simple flood-fill algorithms. It’s similar to how Skynet does it (I haven’t looked into MaasCraft or Tscmoo). It makes sense that it should be fast and reliable.
For pathfinding specifically, BWEM returns a high-level path as a list of chokepoints to pass through. Paths are precomputed when the map is analyzed, so the operation is a lookup. If you want low-level pathfinding too, you need to do it another way.
BWEM knows about mineral patches which block the building of a base, usually a base on an island. Base::BlockingMinerals returns a list of blocking minerals for a given base, so you can mine them out first.
what to do?
Take advice about what library to use from people who have used them, not from me. But if I were evaluating them, I’d start with BWEM as the more modern choice.
Next: Really now, what is pathfinding?
Trackbacks
No Trackbacks
Comments
Igor Dimitrijevic on :
Nice serie you are writting BTW...
About paths, I think it is usefull to distinguish between the short ones and long ones. To simplify, let's say long paths involve the traversal of several choke points. Brood War's path finding does not handle well long paths, especially in the presence of blocking minerals or static buildings. This is exactly what BWEM's paths are for : they are choke points paths (high level paths) that can deal with long paths pretty well. For short paths though, there is little to gain using BWEM's paths and ground distances. The simple BWAPI::move function will do the job for such paths. I would add that for short paths especially, units often matter, so in this case you are more concerned with dynamic information than static paths. At least static paths alone are not sufficient. You already wrote lots of interesting things about this.
Jay Scott on :
Igor Dimitrijevic on :
Otherwise, what I usually do with BWAPI::move is calling it repeatedly: if Brood War's path finding fails at frame t, it may well succeed at frame t+n, because unit positions will be slightly different. Of course, this requires that you use dynamic algorithms, and that the units do move (at least yours). This way of spaming the basic Brood War move command to avoid the issues is used by human players BTW. It is highlighted in a video that Adam Heinermann has just posted in https://www.facebook.com/groups/bwapi/.
Jay Scott on :