Control the Iron!
Where is the API documentation?
The whole documentation of the BWEM library is located in its headers source files.
A good place to start with is src/bwem.h
Every single function and type is documented in details.
You don't need to read the whole API documentation though.
The library provides concret and expected abstractions such as areas and choke points.
You may want to read first the files src/examples.h and src/examples.cpp, which provide runable examples of how you can use the library and access the features.
How mature is the library?
I consider it quite mature, in terms of both functionality and robustness.
The API is stable now.
The functionality should not evolve much, since the library provides all you need to access the Areas, ChokePoints, Bases, Tiles and MiniTiles in an easy and efficient way.
The library has been tested on most of the official maps of StarCraft and BroodWar, with satisfying results.
Stone, the first bot based on the library, demonstrated both its functionality and its robustness.
Iron, currently under development, is based on the library too.
How fast is it?
On my computer, which runs at 2.5 GHz, the whole analysis takes 100 ms for typical maps used in StarCraft AI competitions.
It takes 500 ms to analyse one of the biggest map: Frozen Sea.scx.
As a consequence, you should be able to run in debug mode in a decent way.
Most of the functionality is provided with a time complexity of O(1). This includes path and ground distance requests.
How robust is it?
The library has been tested on many maps, including special ones like Crystallis.scm.
If you do encounter some maps yielding unacceptable results, or even a crash, please let me know!
Is it easy to use?
I think so, but that's obviously subjective.
Here is a snippet, taken from the file examples.cpp that comes with the library:
for (const Area & area : theMap.Areas())
for (const Base & base : area.Bases())
Position(base.Location() + UnitType(Terran_Command_Center).tileSize()),
vector<Ressource *> AssignedRessources(base.Minerals().begin(), base.Minerals().end());
AssignedRessources.insert(AssignedRessources.end(), base.Geysers().begin(), base.Geysers().end());
for (const Ressource * r : AssignedRessources)
Broodwar->drawLineMap(base.Center(), r->Pos(), MapDrawer::Color::assignedRessources);
The extract shows how to iterate through the Areas, the Bases, and their assigned Ressources.
Do not hesitate to read more of examples.cpp!
MapDrawer is a helper class that is provided together with the library. It can be used to print information about the map onto the game screen.
Another helper class, MapPrinter, can be used to print information about the map into a file.
Both are highly customizable and proved to be useful for debug purposes.
By the way, they have been used to produce the screenshots in this site.
Safety is another aspect of the ease of use.
BWEM provides safety through its use of modern C++ style.
An exemple is type safety. Programming an AI for Starcraft requires dealing with three kinds of positions.
In my experience, this is the source of a huge number of bugs.
In order to avoid the possibility of errors, BWEM's API uses the template TPosition and its specializations
(Position, WalkPosition, TilePosition)
provided by the BWAPI library, whenever possible.
Also, make sure to read the getting started page.
How does it work?
The analysis follows the steps:
Altitudes are computed for each MiniTile.
The Areas are computed by considering the miniTiles successively in descending order of their altitude.
The library also provides automatic recalculation of paths and ground distances (in the case blocking Minerals being destroyed for example).
Each of them either:
- involves the creation of a new Area.
- is added to some existing neighbouring Area.
- makes two neighbouring Areas merge together.
The ChokePoints are deduced.
Some statistics and measures like paths and ground distances are calculated.
The Bases are created at relevant locations.
When this occurs, only a small part of the analysis is processed again.
What are altitudes?
The altitude is the distance from the nearest non walkable MiniTile, except those which are part of small enough zones (lakes).
Altitudes play an important role in the analysis process.
Besides that, altitudes can be very useful in implementing various algorithms.
Suppose, for example, you have your air unit somewhere in some area, being attacked by ground units.
You want it to reach the nearest non walkable zone, to escape from the pursuers.
Knowing the altitude for each MiniTile, you can use this very simple greedy algorithm: among the 8 directions,
always choose the one for which the altitude of the neighbouring MiniTile is the lowest. This way you get the shortest path in O(1).
Conversely it is just as easy to reach highest altitudes, though there may be local optima.
Is the code simple?
Clearly, it is not trivial!
The algorithms used are, however, quite simples. Most of them are derived from dijkstra and breadth-first search algorithms.
Moreover the whole analysis is divided into sequential and well separated processes so that it is easy to reason about.
What if I'm not satisfied with the results of the analysis?
Areas, ChokePoints, Base placement are automatically computed by the BWEM library.
You may not agree with all the results, for all the maps.
Fortunatly, most of the algorithms used by the analysis are parametrised and it is fairly easy to modify these parameters.
More information about that in bwem.h.
As discussed in Is the code simple?, the algorithms themselves are not that complex.
You might want to modify them so that they fit your needs.
So may I modify the code to fit my needs?
Usually, when you use a library, you don't want to modify it, as it may be hard work and error prone.
Moreover, this removes the possibility of using next versions of the library easily.
The case of the BWEM library is particular, however:
- it doesn't aim at evolving much, as it is quite mature and stable now.
- some users are not involved in a long-term project, especially those willing to compete in StarCraft AI competitions for one year only.
So if you really need to change some of the code to fit your particular needs, feel free!
Is the library extensible?
Appart from willing to modify some part of the code, you may want to add your own, related features.
For simple cases, you will simply write functions that work on Areas, ChokePoints or Bases.
But what if you want, saying, Areas to contain more information?
As you don't want to modify the library, you will have to define some AreaExtension class.
Then, you usually will want to be able to:
access the Area from its corresponding AreaExtension → you can use either Area::Id() or Areas addresses.
access the AreaExtension from its corresponding Area → you can use Area::Ext() and Area::SetExt().
More generally, BWEM's main classes inherit from UserData, which provides the Ext() / SetExt() methods.
You can use them to extend theses classes.
It is neither an easy nor a safe way, but it is fearly feasible.
By the way, Stone demonstrates this technique. It uses 4 extension types: VArea, VChokePoint, VBase and VMap.
You can look at the source code for more details.
Are the paths optimal?
The BWEM library provides paths made of ChokePoints. They are intented to be shortest, ground, paths.
The suggested paths, if not optimal, are still very good paths.
Looking at the first screenshot in the home page you may notice that the printed path connects the middle of the ChokePoints.
Of course, in the general case the shortest path do NOT go through the exact middle of the ChokePoints.
That the printed path connects middles is just a visual choice. It doesn't mean you should do the same. In a real case where you
have to move a unit frame by frame, you would order it to move to the middle of next ChokePoint that is far enough (saying 10 tiles).
This way, the unit will go through the ChokePoints of the path in a smart way.
Stone demonstrates this technique. If you are interested, download its source code and look at the file walking.cpp.
Can I use the library together with other libraries?
Of course you can.
The BWEM library is a light-weight library with namespaces and minimal dependancies. It is not likely to interfere with other libraries.
For example, you can include the BWEM library even if you already uses the BWTA2 library.
This way wou can access to specific features from each library.
Control the Iron!