Starcraft AI blog

Here is Steamhammer's new C++ MapPartitions class, which calculates ground connectivity. This is a donation to the community. Feel free to borrow it for your own bot, if you like. The download is a zip which contains 4 files: MapPartitions.cpp, MapPartitions.h, and 2 license files. The class contains some code derived from UAlbertaBot, so there is a UAlbertaBot license plus Steamhammer’s license. They are both MIT style licenses, which basically make no requirement beyond including the license file. (It’s irritating that the licensing considerations are as complex as the code, but that’s the world we live in.)

I’ll quote the comment describing it:

// Partition the map into connected walkable areas.
// The grain size is the walk tile, 8x8 pixels, the granularity the map provides.
// Unwalkable walk tiles are partition ID 0.
// Walkable partitions get partition IDs 1 and up.

// This class provides two features:
// 1. Walkability for all walk tiles, taking into account the immobile neutral
//    units at the start of the game.
// 2. Ground connectivity: What points are reachable by ground?

// If two walk tiles are in the same partition, it MIGHT be possible for a unit
// to walk between them. To know for sure, you have to find a path and verify
// that it is wide enough at every point for the unit to pass.
// If two walk tiles are not in the same partition, no unit can walk between them.

Concretely, the interface lets you directly test the walkability of a position, find the partition ID of a position, or check whether 2 positions are connected by ground. You can find out the total number of partitions (some maps have hundreds due to small holes), and you can draw partitions on the screen for debugging. There’s not that much to it.

A few notes:

• There is a separate initialize() method that is not called by the constructor. You have to call it yourself, in or after your main onStart(). Depending on your use case, this is sometimes necessary to avoid making BWAPI calls before BWAPI is initialized itself.
• Maps often have little side bits attached by a single walk tile. No unit is small enough to walk there, but this class doesn’t know it.
• The little side bits are not important, at least not in Steamhammer’s play. Units don’t want to go there.
• The class does not update when neutral units are destroyed, opening paths that used to be closed. But the walkability data structure is designed to be easy to update in that case.
• This version is slightly different from Steamhammer’s code. I changed the error handling so that I could remove one last dependency and make it completely standalone (except for BWAPI, of course). Only a handful of lines are different.

I’ve suggested before that authors should package up reusable code as libraries. BWEM, BWEB, and FAP are great examples. MapPartitions is more modest. When I’ve looked at breaking out Steamhammer code, until now I’ve always felt that the parts were too integrated with each other, with too many dependencies. MapPartitions is the first exception. I hope some people find it useful.