Jump to content
  • Advertisement
Sign in to follow this  
ccanan

what's starcraft2's pathfinding tech?

This topic is 2377 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

">check this what's the tech? it looks really amazing. I just find this which looks amazing too: supreme commander2's flow field. are they the same? thx in advance! (Mod note: edited and linked obnoxiously long urls so that people could actually use a resolution of less than 4000 pixels wide to read this thread.) [Edited by - InnocuousFox on March 2, 2010 3:40:37 PM]

Share this post


Link to post
Share on other sites
Advertisement
Doesn't look like 'path-finding' is the amazing part there. You are probably referencing the flocking behavior of the zerglings? What part are you impressed by?

Share this post


Link to post
Share on other sites
Quote:
Original post by choffstein
What part are you impressed by?
In am mostly impressed by the way they navigate choke-points.

In the original StarCraft, it could take ages to successfully navigate a group of only 10-20 units through a narrow entrance, and here several hundred seem to squeeze through all right.

The flow-field stuff is even more impressive.

Share this post


Link to post
Share on other sites
Quote:
Original post by swiftcoder
Quote:
Original post by choffstein
What part are you impressed by?
In am mostly impressed by the way they navigate choke-points.

In the original StarCraft, it could take ages to successfully navigate a group of only 10-20 units through a narrow entrance, and here several hundred seem to squeeze through all right.


The big problem with the path finding in starcraft is that the A* only takes into account the terrain and building, if it runs into other units and can't slide past them it will repath a alternate route. This works fine for a small number of units but if you try to navigate a large number of units through a narrow passage inevitably a few will run into the units ahead of them and find another path, this usually means trying to go backwards though the passage. At this point they will run into the units going in the right direction and return to their original path but all the units they hit will now do a U-turn and pretty soon your entire army is just spinning in circles.

Share this post


Link to post
Share on other sites
Quote:
Original post by swiftcoder
Quote:
Original post by choffstein
What part are you impressed by?
In am mostly impressed by the way they navigate choke-points.

In the original StarCraft, it could take ages to successfully navigate a group of only 10-20 units through a narrow entrance, and here several hundred seem to squeeze through all right.

The flow-field stuff is even more impressive.


Didn't even notice it, and didn't look at the second video! That is pretty impressive stuff. My untrained eye still spots flocking behavior though...

Share this post


Link to post
Share on other sites
Starcraft's queuing really is pretty impressive; usually, even with Reynolds-style queuing, you end up with at least some slowdown/bottleneck effect.

The other thing I wonder is how precisely the flocking in Starcraft2 ties in to the path planner, and how it's decided how many paths to plan (and to what extent they trade off between computing policies and computing paths, and how much they do at runtime vs in map preprocessing). Plus, are they even using square tiles under-the-hood (I'd guess so, but you never know...)

The flocking I see in Supreme Commander 2, since it's demonstrated on an open field, isn't much different from things even I have done. But I probably have the same questions about the division between planning and flocking for that game too.

Share this post


Link to post
Share on other sites
My guess is that there is one main A* path for the group. Then each unit applies a combined vector of attraction to that path and separation from their buddies.

@Kaze: In SC2, units will push through their buddies rather than repath around. You sure you aren't talking about the old one?

Share this post


Link to post
Share on other sites
Quote:
Original post by InnocuousFox
My guess is that there is one main A* path for the group. Then each unit applies a combined vector of attraction to that path and separation from their buddies.


That's what I figure whatever they do must reduce to most of the time, but you can imagine situations where this would fail, so I'm guessing they must actually be doing something a little more robust. For instance, suppose you have a group of units selected across a ravine, and units on the different sides must follow very different paths to reach the same goal; something must be done to deal with cases like this.

[EDIT 1: One hypothetical solution: Maintain a "performance measure" for the flock -- e.g., maximum distance to centroid, or variance -- and run a simple clustering algorithm on the flock to split it when it drops below some threshold; then replan for each flock. Even this could fail in some situations though; e.g. closely-spaced hallways.]

[EDIT 2: There are also various ways you can imagine building a wavefront-style algorithm to start from all of your units (and perhaps also the goal, in a bidirectional fashion) to compute feasible, probably-near-optimal paths; you do run into the problem of merging wavefronts, but maybe that's not so bad...]

[Edited by - Emergent on March 2, 2010 4:56:04 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by InnocuousFox
@Kaze: In SC2, units will push through their buddies rather than repath around. You sure you aren't talking about the old one?


When did I mention SC2?

Share this post


Link to post
Share on other sites

This topic is 2377 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Guest
This topic is now closed to further replies.
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!