archive by month
Skip to content

shortest paths

Melee unit A is chasing enemy unit B. If they move at the same speed, when can A catch B? In principle, the answer is: When B reaches an edge and has to turn aside, allowing A to gain ground by taking a shorter path. An SCV B running loops around your base can be caught by a slow zergling A moving at the same speed if the zergling follows an inside track. If B is running across the map to safety among its friends, then as long as B takes the shortest path, A cannot catch up before B reaches its friends.

In practice, Stone’s SCV A can often catch a fleeing SCV B before B turns aside at an edge. And Steamhammer’s zerglings A can often catch Stone’s fleeing SCV B. And the same for many other bots, substituting other units A and B. The chasing unit A is using unit movement prediction to smooth its path, and is following a shorter path than the fleeing unit B. Starcraft’s native paths are not shortest paths (partly because units are often delayed near choke points or when passing an obstacle).

Does any bot implement good quality shortest paths for moving units B? It seems like a valuable skill. I don’t know of one, but I haven’t read most of the huge masses of code....

Trackbacks

No Trackbacks

Comments

Jay Scott on :

I recall that LetaBot uses path smoothing for mining, but Martin Rooijackers said it was expensive, so I think it is not used for other paths.

MicroDK on :

Locutus added pathing to moving units (not attack command) where he uses the next choke for pathing using the closest point on the choke to the final destination. I am mot sure this counts as shortest path. ;)

Jay Scott on :

I see that as a tweak to use BWEM a little more efficiently. Perhaps a flocking algorithm like OppromoBot’s does the job?

MicroDK on :

Is flocking shortest path? I dont know the algorithm of OpprimoBot but I would say flocking makes units spread out and align themselfs in the same direction. Not all units can take the shortest path then, since some units must walk on a path to the right or left of the unit mass center: https://gamedevelopment.tutsplus.com/tutorials/3-simple-rules-of-flocking-behaviors-alignment-cohesion-and-separation--gamedev-3444. But spreading out the units can have the benefit that the pack of units can catch a enemy scout or single unit since your units are taking different paths.

Arrak on :

I think that depends on how you define the best path for a group. If the initial group formation is like a "wall" (as opposed to "conga line"), and there are no chokepoints, per-unit paths such that the "last half" of a group quickly reaches a "goal zone" requires that group members avoid collision. If you then add the requirement that the group reconstructs and maintains a certain formation along the entire path in spite of all chokepoints, then flocking is pretty convenient.

nturley on :

Talking specifically about the pursuer/evader problem. I spent a bunch of time trying a creative solution which was to generate a voronoi diagram using the units and aim toward the midpoint of the voronoi edges. If the escape chokepoint is in an enemy voronoi region, then you are unlikely to be able to catch them before they escape. If you have multiple pursuers they will naturally swarm around the target because the voronoi midpoints will be distributed around the evaders.

It was a cool idea in theory, and in simple cases it worked fine. But barriers, concave regions, and large numbers of units made it messy. Someone smarter than me might be able to get it to work.

Add Comment

E-Mail addresses will not be displayed and will only be used for E-Mail notifications.

To prevent automated Bots from commentspamming, please enter the string you see in the image below in the appropriate input box. Your comment will only be submitted if the strings match. Please ensure that your browser supports and accepts cookies, or your comment cannot be verified correctly.
CAPTCHA

Form options

Submitted comments will be subject to moderation before being displayed.