Starcraft AI blog

For a view of the A* family today, I liked this site the best. Maybe I should have skipped the last two posts and pointed “go there!” But I don’t regret stopping at a couple points along the road to get an idea of the historical development.

Amit’s A* Pages

There’s more stuff here than ought to fit into one post, but I’ll keep to the highlights.

Practical techniques. Amit talks about different choices of heuristic, ways of adjusting the “actual” sunk cost g(x) and/or the heuristic future cost h(x) to get different behavior, and other little tricks. Worth reading, not worth repeating.

Implementation details. Amit has a long section on how to make A* efficient. For the priority queue at the heart of A*, he examines the tradeoffs of too many algorithms and then says that he’s never needed anything other than a binary heap. OK, done!

Various fancier data structures. This seems like a key section. If you represent a Starcraft map as a grid of tiles, then A* will have to do a ton of work to step over each tile that might be in a path. Amit offers these choices that seem relevant to Starcraft.

• visibility graph - draw polygons around obstacles and navigate from corner to corner
• navigation mesh - break walkable areas into convex polygons and navigate from edge to edge
• hierarchical representations - where each hierarchy level may be of a different type
• skip links - add extra graph edges to take long paths in one A* search step (cheap imitation hierarchical representation)

And there are choices about how to use each representation. It an important topic, but I don’t know enough to judge which ideas are worth going into in detail. I’ll come back to it when I’ve gotten further along.

Path recalculation when the map changes on you, ditto: I’ll revisit if necessary when I know more.

Islands. If the map has areas you can’t reach by walking but you may want to go to, you’d better mark them as only reachable by air. Do a preprocessing step, I guess, or at least cache the results. You don’t want to have to repeatedly search the whole map during the game to find out that you can’t walk there. That includes not only islands to expand to but cliffs you might want to drop on. Obvious, but I hadn’t thought of it.

Group movement more or less says “see flocking.” I’ll do flocking after potential fields, since they’re related. Is it Opprimobot that claims to use a flocking algorithm? Some bot does; I’ll check it out.

Coordinated movement, like moving in formation or moving through a narrow passage in order, earns a paragraph. It’s potentially interesting for Starcraft. If you want to do that coordination in top-down planning style, a better source is the article pair Coordinated Unit Movement and Implementing Coordinated Movement by Dave Pottinger on Gamasutra.

Tomorrow: Potential fields.