home | features | getting started | FAQ | Stone | Iron | download | help | about

# FAQ

- How mature is the library?
- How fast is it?
- How robust is it?
- Is it easy to use?
- How does it work?
- What are altitudes?
- Is the code simple?
- What if I'm not satisfied with the results of the analysis?
- So may I modify the code to fit my needs?
- Is the library extensible?
- Are the paths optimal?

## 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?

The analysis:

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.

The services:

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())
            {
                if (MapDrawer::showBases)
                    Broodwar->drawBoxMap(Position(base.Location()),
                                         Position(base.Location() + UnitType(Terran_Command_Center).tileSize()),
                                         MapDrawer::Color::bases);

                if (MapDrawer::showAssignedRessources)
                {
                    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.
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.

The library also provides automatic recalculation of paths and ground distances (in the case blocking Minerals being destroyed for example).
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.

home | features | getting started | FAQ | Stone | Iron | download | help | about