Starcraft AI blog

Christian McCrave, author of McRave, is writing a building placement library named BWEB. BWEB is C++ and depends on the BWEM map analysis library by Igor Dimitrijevic, and within those constraints should be easy to add to a Brood War bot. It’s currently in beta at version 0.8, finished enough to try out but not yet thoroughly tested.

The idea behind BWEB is to place buildings not one at a time like most bots, but in compact predefined “blocks” of several buildings of different sizes. A protoss block will include at least 1 space for a pylon plus possibly large spaces for gateways and other large buildings and medium spaces for buildings the size of a Citadel of Adun. From McRave Blocks v1.2 (mentioned in the code):

You can think of a block as a sort of macro for buildings. There are 2 ideas behind it: First, building placement can be compact. Bots that place buildings one at a time often leave space around each building for units to pass through, wasting room and filling up the main base. (ICEbot is a notorious example; its buildings tend to spill out of the main.) BWEB only has to leave space around each block. Second, the library itself can be faster, because it has to choose the locations of a small number of larger blocks rather than a large number of smaller buildings.

Here is the key part of the API, how to get a location for a building:

	// Returns the closest build position possible for a building designed for anything except defenses, with optional parameters of what tiles are used already and where you want to build closest to
	TilePosition getBuildPosition(UnitType, const set* = nullptr, TilePosition = Broodwar->self()->getStartLocation());

	// Returns the closest build position possible for a building designed for defenses, with optional parameters of what tiles are used already and where you want to build closest to
	TilePosition getDefBuildPosition(UnitType, const set* = nullptr, TilePosition = Broodwar->self()->getStartLocation());

	// Returns the closest build position possible, with optional parameters of what tiles are used already and where you want to build closest to
	TilePosition getAnyBuildPosition(UnitType, const set* = nullptr, TilePosition = Broodwar->self()->getStartLocation());

It’s simple enough; ask for a building location, get one. BWEB also has a method to fetch a wall to place in the natural choke, and various utility and debugging methods.

A comment in the code may be a to-do list:

	// Currently missing features:	
	// - Counting of how many of each type of block
	// - Defensive blocks - cannons/turrets
	// - Blocks for areas other than main
	// - Variations based on build order (bio build or mech build)
	// - Smooth density
	// - Optimize starting blocks

thoughts

Gaoyuan Chen’s grid of protoss buildings is similar in idea to BWEB’s blocks of buildings. Unlike BWEB, Gaoyuan Chen places medium buildings in large spaces (and it doesn’t seem to be a problem). In the picture, buildings off the grid are enemy proxies:

BWEB seems suitable for protoss and terran building placement. Zerg building placement has different requirements and doesn’t seem like a natural fit with the block technique. Sure enough, in the BWEB code I see plenty of special cases for terran and protoss, and no mention of zerg. Of course, terran and protoss benefit from compact building placement. Zerg has less space to place buildings, since they have to go on creep, but also has fewer buildings to place.

How does BWEB ensure that the mix of small, medium, and large building spaces fits the mix of buildings you will create? I got the impression that if, say, you want to (or later in the game end up wanting to) create many gateways (large) and fewer than usual tech buildings (mostly medium), then BWEB will pre-allocate blocks with more medium spaces than you finally use. That doesn’t sound like much of a problem, though.

It’s new software, and many features you might want are not there, at least not yet. You may want tech buildings in remote parts of your base so they are safer and harder to scout, and production buildings near the ramp. You can do that with the “build closest to here” feature, but you may have to take extra care to place pylons ahead of time. The wall feature is very limited so far. The game gives us many uses for complete or partial pylon walls and for supply depots as obstacles. There’s no apparent support for proxies or gas steals; you’ll have to use your own code. The same for spotting pylons or blocking the opponent’s natural with an incomplete engineering bay. And of course there are inherent limitations to the idea of predefined blocks of buildings. A predefined block is never quite optimized for the exact terrain and matchup and build order and so on.

Still, it seems fast and easy, and it’s an improvement over what most bots do today. It should be well worth trying out for a protoss or terran bot, especially if you already use BWEM.

Thanks to the author Christian McCrave for letting me know about it!