pathing 1: intro
I don’t know much about pathfinding, so I decided to write about it.
I wrote earlier about threat-aware pathing, but I didn’t know how to implement it efficiently. Bots are real time and have a lot to think about, so faster is better.
I’ll write about classic A* pathing and its descendants, about potential fields, and about any other interesting ideas my shovel turns up (I’ve seen the corners of a couple other things that might be cool). I’ll look into the pathfinding features of libraries like BWEM. I hope to learn something about how it all works at the low level with BWAPI and how it might interact with Starcraft’s built-in pathfinding. In the end I’ll try to put pieces together to outline how to find paths in full generality, taking into account strategic and tactical goals, obstructions like terrain, destructible map objects, buildings and units, and fields of vision and fields of fire for both sides. I’ll try, but I don’t promise to succeed!
This should be old hat for old hands, but a lot of it is new to me. Maybe I’ll get some help in the comments.
Tomorrow: The classic A* algorithm.
Trackbacks
No Trackbacks
Comments
Johannes Holzfuß on :
I've been playing around with pathfinding in StarCraft a while ago (wrote a really crappy 4-pool boringbot -- sorry -- and then stopped, because I wasn't prepared for how much friggin' work writing a bot is), and I thought you might appreciate hearing what I came across.
First, there's a simple improvement to A* called Fringe Search. Another improvement to A* called Jump Point Search deals with redundant paths. There's also a wicked fast pathfinding method called "Jump Point Search+ with Goal Bounding", but you have to precalculate a lot of data for it to work. I implemented it, but it doesn't work well with destructible obstacles. Then there's a method called Subgoal Graphs that abstracts the tile grid into a higher-level graph. It was among the fastest pathfinders in a 2012 competition, but was a little less effective for StarCraft than for other games, because StarCraft has so many diagonal walls. I'd bet on this if I were to write a bot again, though.
There are a ton of other tricks to speed up A* (landmarks, etc.), but I guess this comment is getting long as is.
Hope this helps you in further research. :)
Jay Scott on :
Igor Dimitrijevic on :
Programmers wanting to quickly experiment with the basic paths provided can use the "pathExample" that comes with the library.
This function prints a paths between two random starting locations, and can be easily modified to test the functionnality.
The first screenshot on the site shows an exemple.