Brood War API – The Comprehensive Guide (of time and space)

Index for the Comprehensive Guide posts

As I mentioned before, I plan to write a complete goddamn book about BWAPI. I plan to publish the drafts of the chapters from that book. The blog will not contain everything from the planned full book, and I will interject stupid shit my observations, feelings, and stuff I feel like here and there. This also serves as a fact check staging ground, and I encourage you to poke holes, proofread, and provide constructive criticism to everything I publish about the topic.

With that, let’s jump into the first topic, which is time and space. Most of this stuff is already mentioned in this blog, but in scattered tidbits, not in a structured way. So with that, here is a preview of one of the chapters.

(Chapter) An inside look into StarCraft

To understand how and why our bots do the things they do – and usually not the things we want – it is useful to know the inner workings of the game engine. Since StarCraft is not open source, the tool I’m using this is the OpenBW project’s core engine, which is described as:

“The core engine is able to simulate Brood War, including the original features, bugs, and pathfinding quirks.”

I will provide code samples for everything I’ll describe, but those can be safely skipped for the most part. I aim to describe the inner workings in plain text. After all, if you want to look at the source, you can just do that without reading this chapter.

The beginning of time – how StarCraft manages it

The first thing I’d like to describe is how the game handles time itself. You might have guessed, that despite being called a real-time strategy, it is indeed broken down to discrete units of time. The smallest unit of those is called a frame. This is the atomic unit for game logic, nothing that happens in the game can take less than one frame. The game engine is capable of different speeds, that can be set via BWAPI. Here is a chart of common in-game speed settings. (Human matches are almost always played on Fastest)

Game speed settingMilliseconds per frameFrame per second (FPS)
Slowest1675.99
Slower1119.01
Slow8312.05
Normal6714.93
Fast5617.86
Faster4820.83
Fastest4223.81

Bot games are usually played on faster speeds – BWAPI enables you to speed the game up, the only constraint is the processing power of the computer. Some leagues use headless mode where there is no graphical output during play to resolve matches even faster.

What can happen during one frame? The answer is not much. Most actions take more than one frame to execute. There are a few examples that can be measured on a per-frame basis (by no means comprehensive):

  • Hit point regeneration, either the natural rate for Zerg units, or healing done by a Medic.
  • Protoss shield regeneration
  • Energy regeneration
  • Resolving damage

It is important to note that frames only apply to game-logic actions, not everything. If a frame is not executed fully, the graphics are still updated, and the poll for user input still continues. This is something we probably don’t have to concern ourselves with.

Frame skipping

By default, StarCraft only uses the frame skip functionality for processing replays, executing a number of game frames before drawing one of them. BWAPI has a functionality to set this explicitly (setFrameSkip).

..and space – spatial measurements

There are three distinct units of space that the game works with. It is worth noting that in the underlying StarCraft code the granularity is much finer. You might have seen the fp8 variable type in the code examples, this means a fixed point (binary) variable with 8 points of precision. This is used for calculating movement, hit chance, among other things. It is important to note, that StarCraft is entirely grid-based. The buildings and terrain doodads can appear three dimensional, but they are isometrically drawn 2D sprites. This can cause some interesting effects, and trick the eye into thinking that some units can/can’t fit in places, while the opposite is true.

But let’s talk about the spatial units that are visible to the end user (the player or the bot author)

The first is Positions, which is equivalent to a pixel. Every unit in the game has a bounding rectangle. In the Appendix, I included a chart with all unit sizes in the game. Hero units have the same sizes as their regular counterparts, except for Infested Kerrigan. Burrowed units have the same size as when they are unburrowed.

The sizes of the rectangles do not change when the unit sprites align differently. A long but narrow unit, like a Protoss Reaver, occupies a 32×32 pixel sized rectangle, no matter which way it appears to be facing (Another examples are Ghosts and Ultralisks). Collisions are checked on the pixel level, and units can stack infinitely, but generally the game code aims to avoid that. One famous example for stacking is the worker drill.

The next spatial unit on the scale is the WalkPosition. It is a 8×8 pixel rectangle. This is used for walkability calculations.

Here is an article mentioning this, from one of the original StarCraft authors. I’d like to borrow this picture, illustrating the discrepancy between the isometrically drawn sprites, and actual walkable positions:

Annotated StarCraft screen captured show tile edges

The biggest spatial unit is the TilePosition, which is a 32×32 pixel square. This is used for placing buildings mostly, and you can easily observe this, when placing down one, it conforms to a grid.

There is another unit called a Region. It is used internally by StarCraft, it contains a group of tiles with similar properties, and creates a node for pathfinding. More on that in the BWAPI chapters.

Terrain and the effects thereof

Units can occupy multiple tiles, but when considering which one they exactly stand on, this code piece below is executed. The parameters passed to the function (x and y position) are the center of the unit.

size_t tile_index(xy pos) const {
size_t ux = (size_t)pos.x / 32;
size_t uy = (size_t)pos.y / 32;
if (ux >= game_st.map_tile_width || uy >= game_st.map_tile_height) error("attempt to get tile index for invalid position %d %d", pos.x, pos.y);
return uy * game_st.map_tile_width + ux;
}

The unit’s x and y position (pixel) is divided by 32, changing the granularity of the calculations to tilepositions. Tiles are stored in an array, and we get back an index inside that array. This is the tile that is considered when checking if the unit is in cover or not. Cover works the following way: By default, every ranged attack has an 1/256 miss chance. If the target is considered to be on a piece of terrain that is marked as cover, an additional 119/256 is added to that, so attacks will miss almost half the time. What missing means will be explained in the units and attacks section. The same extra miss chance is also applies if the target unit is on higher ground than the attacking unit.

There are three height levels in the game engine, but BWAPI can return six distinct values. According to the BWAPI documentation, those can be:

0: Low ground
1: Low ground doodad
2: High ground
3: High ground doodad
4: Very high ground
5: Very high ground doodad

And the appropriate code piece is this:

    int get_ground_height_at(xy pos) const {
      size_t index = tile_index(pos);
      tile_id tile_id = game_st.gfx_tiles.at(index);
      size_t megatile_index = game_st.cv5.at(tile_id.group_index()).mega_tile_index[tile_id.subtile_index()];
      size_t ux = pos.x;
      size_t uy = pos.y;
      int flags = game_st.vf4.at(megatile_index).flags[uy / 8 % 4 * 4 + ux / 8 % 4];
      if (flags & vf4_entry::flag_high) return 2;
      if (flags & vf4_entry::flag_middle) return 1;
      return 0;
  }

So behind the scenes, the cover terrain is just another height level (In this list, doodad effectively means cover). With multiple height level difference, the miss chance is not cumulative, just applied once.

Ramps

Ramps don’t have any special rules, although it may seem otherwise. They are composed of multiple tiles, and the height difference rules apply normally. Some mapmakers “hack” together multiple ramp segments, and they might have different terrain properties – a ramp that appears uphill can be actually downhill.

Additional tile properties

Terrain tiles have some additional properties, which are:

  • Buildability: Can any building be placed here?
  • Walkability: Pretty self-explanatory. Can land units walk over this tile? As mentioned, actually calculated on the WalkPosition level. A partially walkable tile is unbuildable. Fun fact: there was a BWAPI bug related to this.
  • An explored and a visible flag: Explored is where the tile is not under the “black” fog of war, visible is when you have active vision on the given tile. Invisibility and detection is handled on the unit level, and tiles don’t affect that.
  • Having creep and power, for Zerg and Protoss units.

The end

And that’s all I have for this episode. I’m working on multiple chapters at the same time, and everything is subject to change, always, nothing is certain, existence is pain. I’m curious to hear your thoughts, and if you can spot a factual error, you get 1 whole good boy point!

Thanks for reading! If you don’t want to miss any updates, consider subsciribing to the mailing list, or following me on social media – Facebook and Twitter!

Leave a Reply