Starcraft AI blog

This is an idea I came up with while working on building placement in the live Steamhammer. In that version I made the basic operation “can this building be put here?” faster by cleaning up redundant calculations. In the future I want Steamhammer to do complex building placement optimizations on the fly, requiring many steps, which means it will be useful to speed up each step even more. I haven’t implemented the idea, but it’s simple and seems broadly useful so I want to write it up for everybody.

Checking “can this building go here?” first of all means checking whether all the tiles the building will occupy are buildable and unobstructed. BWAPI can do this in one call. Steamhammer also checks certain adjacent tiles, and sometimes tiles adjacent to a neighboring building, to make sure there is free space and units can move around. The net effect is that certain rectangles of tiles are checked, one tile at a time: Is this one clear? The next one? The next one? There are a few extra checks like “is there pylon power?” but checking open space is the main part.

If you’re going to do a lot of building placements, as I am planning, then you can reduce the check of any one row or column of tiles to a single lookup in one of two simple precomputed data structures: How much room is clear to the right of/below this tile?

The algorithm is trivial. For example, to find out how many tiles are clear to the right of each tile on the map, start with a currentRoom counter set to 0, and scan each row of map cells from right to left. If a cell is open, increment currentRoom and store it; otherwise, reset the counter to 0 and store that. Done.

So if you want to place a 4x3 building with 1 tile space around it, you don’t have to check 6x5 = 30 tiles individually. You can check the 5 rows with 1 lookup each. Furthermore, if you’re going to compare different possible locations to choose the best, the minimum of those 5 values tells you how many tiles you can slide the building horizontally—you verify all those potential building placements with no further work. If you’re comparing many placements, you should easily earn back the investment of computing the extra data structure.

If you only want a fast first check for clear terrain, you can build the lookup table or tables once at the start of the game. If you want to take into account your own buildings and other stuff that you know about, you can build the table fresh when you need it, or you can update it incrementally as buildings come and go. The incremental algorithm is not hard. If you know the general area you want to build in, you can restrict the table to that area—for example, within the bounding box around the creep of a given base.

It’s simple and not entirely obvious, though I won’t be surprised if some bots already use the idea. I thought it would be useful to write up.