paper on dropship paths
I looked through the CoG 2020 accepted papers and noted a couple that relate to Starcraft. One is Combining Influence Maps with Heuristic Search for Executing Sneak-Attacks in RTS Games by Lucas Critch and David Churchill.
This looks like a student Lucas Critch with advisor Dave Churchill. Including the advisor’s name on a student’s paper as second author is an academic convention, and does not give away how much work the advisor may have contributed to it; it may be a substantial effort not much less than the student’s, but it is often “OK, that’s good enough, you can add my name.” The advisor is generally better known than the student, which may draw attention to the paper and its first author. Alternatively, the advisor’s name may overshadow the student who is soon forgotten. I’m not sure which effect is bigger.
As usual, the title is bigger than the content. The paper is actually about how to route a dropship across the map so that the enemy is less likely to catch it along the way, so that the drop is not intercepted and comes as a surprise. It proposes to use the A* algorithm to find the dropship path, and assigns a higher cost to tiles which the enemy is thought to be more likely to see or shoot at; A* will find the lowest-cost path, trading off distance versus risk of being caught.
The paper proposes three influence maps to add up to figure the costs: An enemy vision map based on known or remembered enemy units and their vision range, to avoid being seen; an enemy damage map based on units that can shoot at the dropship, to avoid being shot down (if you are going to be seen, at least be seen by something that can’t kill you); and a weaker map of shortest paths between various bases, which the enemy is likely to be moving along. This figure from the paper shows a sample path:
The path looks fairly reasonable, except that the dropship should follow more diagonals and not exact horizontals and verticals. The paper says nothing about replanning the path when new information is discovered. Trying the system out in real games is future work, not yet done. Theoretically, the shorter safe paths might lead to faster drops which do more damage.
This is early stage work and not impressive so far. But I think it is a good reminder for bot authors: Most bots do not worry much about what the enemy sees, and pay attention mostly to what the enemy does. Finding good transport paths in real time is an important basic skill that bots will eventually have to master. The reaver-dropping protoss bots especially may want to think about that; aiming for the enemy army and aiming for the enemy base and workers call for different approaches.
Although a more important basic skill, that many bots also lack, is recognizing the danger and reacting properly when they do spot a transport moving across the map. Most bots are incurious and it never occurs to them that perhaps a drop is incoming, and perhaps defenders should be moved into position to intercept.
Trackbacks
No Trackbacks
Comments
Dan on :
Here is PurpleWave's parameterizable pathfinder, which can be configured to factor in enemy vision and attack range as costs. It powers all of PW's non-direct movement: kiting, scouting, shuttle/reaver usage, and just moving around map obstacles. It's designed to be used for drop harassment, though presently isn't.
It's proven very useful but isn't a panacaea. The cost functions are hard to tune. And it's easy to construct a cost function which violates A* heuristic admissibility. The paths are fairly unstable with respect to changing game conditions; enemies don't just stand in place while you path around them. Because I pathfind at 32px resolution, the kiting paths aren't as efficient at opening gaps as Locutus/Iron/Bereaver/Skynet which use continuous angle math. One of the most common ways for PW to lose these days especially in PvP is due to stilted retreats due to imperfect retreat angles combined with the aforementioned instability.
I believe these issues can all be tuned away but that's a far cry from actually doing it. But the parameterizable pathfinder is a powerful tool and a lot of what bots do to *avoid* implementing one are low-ceiling workarounds.
Pathfind parameterizer: https://github.com/dgant/PurpleWave/blob/master/src/Information/Geography/Pathfinding/PathfindProfile.scala
Pathfinding:
https://github.com/dgant/PurpleWave/blob/master/src/Information/Geography/Pathfinding/TilePathfinder.scala
Jay Scott on :
Though simply redoing your path when new info comes in is not very different.
Bruce on :
I've also added a generic pathfinder, but am only using it for some very specific things right now (like scout movement). I need to make some performance improvements before using it more, or at least properly handle the case where the path to the goal is blocked so it doesn't visit almost every tile on the map.
Jay Scott on :
Bring transport along with the army to a place that’s close by air to an enemy base. Then you can choose: Pick up and safely drop a short distance away, or if you notice the enemy is prepared for that, then forget your transports because their units are out of position for a straight ground attack.