• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
ccanan

what's starcraft2's pathfinding tech?

24 posts in this topic

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]
0

Share this post


Link to post
Share on other sites
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?
0

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.
0

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.

0

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...
0

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.
0

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?
0

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]
0

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?

0

Share this post


Link to post
Share on other sites
Quote:
Original post by Emergent
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.
I can think of a few ways to do it. One could be that all units that have line-of-sight to each other define a single "flock" and each "flock" generates their own path. Another one would be that when two or more units are touching (or close enough) they define a flock. When creating the path, any units within x units of the nearest flock will first move to join the flock before following the path as well.

It's certainly not easy, and they seem to have done a fantastic job. The bit right at the end of the video where the zerg swarm the enemy base, destroying it in seconds is awesome.
0

Share this post


Link to post
Share on other sites
Quote:
Original post by Kaze
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?

You didn't... but the OP did. That's what this thread is about. Your comment about re-pathing around people in the way was not correct in the arena of SC2.
0

Share this post


Link to post
Share on other sites
Quote:
Original post by CodekaI can think of a few ways to do it. One could be that all units that have line-of-sight to each other define a single "flock" and each "flock" generates their own path.

Ack! You do NOT want to do a ton of LOS checks just to see if a group is together. That would almost be worse than running A* for all the members.

0

Share this post


Link to post
Share on other sites
Quote:
Original post by InnocuousFox
Ack! You do NOT want to do a ton of LOS checks just to see if a group is together. That would almost be worse than running A* for all the members.


That might depend though on what you're already doing. If you have a LOS manager that is already maintaining a database of LOS statuses between the whole n^2 worth of units then this would be "free". A typicaly LOS manager amoritizes LOS checks over frames so you do no more than X per frame at the cost of some per-frame accuracy (so maybe a latency of up to ~250ms for the accuracy of a given LOS status). There are many other reasons you want LOS between units (though typically not between allies). It's very likely that they have this system in place; we certainly had one on every RTS or FPS game I've ever worked on.

However, LOS does seem like a strange way to go about group determination in an RTS. You already have various meta-data available. For instance groups can simply be determined by what units were selected together when an order was given. It would be informative to experiment to see what happens if you have 2 groups of zerglings and order them separately to attack a given unit. Do both groups flock together or flock independently?

-me
0

Share this post


Link to post
Share on other sites
Quote:
Original post by InnocuousFox
Quote:
Original post by CodekaI can think of a few ways to do it. One could be that all units that have line-of-sight to each other define a single "flock" and each "flock" generates their own path.

Ack! You do NOT want to do a ton of LOS checks just to see if a group is together. That would almost be worse than running A* for all the members.
Well, that's why I also thought of the "touching" algorithm, which certainly seems more likely.
0

Share this post


Link to post
Share on other sites

This actually looks similar to something I've been doing with particles. It's pretty easy and efficient to set up mutual seperation based on some sphere, which would translate well to seperating units based on their bounding sphere.

If you look to the video to around 4:50, you'll see that incoming units just move to the target location, while pushing away anyone within their 'bounding sphere'. If you just enforce this seperation constraint for all units, it would work out like this. The pushees also seem to slide aside rather than really walk, so it really looks similar to a cheap particle seperation simulation.

It's still awesome to apply this to RTS units, but it would be less mathy than suggested.
0

Share this post


Link to post
Share on other sites
AIGameDev.com sent out this snippet yesterday to advertise their Game AI Conference in Paris later this year:
Quote:
Recently, two videos have surfaced with demos of what I'd call "modern"
pathfinding in a RTS. Basically, technology that goes beyond just using A*
to plan shortest paths for each unit. In this case, SC2 stands for both
StarCraft 2 and Supreme Commander 2! Here are the videos:

FlowField Pathfinding in Supreme Commander 2
http://j.mp/8X2fBA (GameTrailers.com)
350+ Unit Zergling Swarm in StarCraft 2: Pathfinding Demo
http://j.mp/cvaKSK (YouTube.com)


The general concensus here is that A* is still used of course; in the
StarCraft 2 you'll see the group of zergling split into two around a large
obstacle, which is a sign that there are at least two shortest path
searches: one for each side. What's interesting there's a fluid-looking
simulation in there also, so the first units that arrive at the target get
pushed outwards by the latter units. It could be done using reactive
avoidance behaviors, but I'd be a little surprised as I've never seen it
look this good! A global fluid-like solver would probably help with
performance over many local avoidance queries.

Supreme Commander 2 actually mentions that their work is based on the
Continuum Crowds paper by the University of Washington.

Continuum Crowds: Project Page
http://grail.cs.washington.edu/projects/crowd-flows/


This kind of technology definitely uses a global fluid-like solver to help
units deal with dynamic obstacles better. The implementation seems very
robust, in particular when the two groups move through each other and one
is sent new orders half way through. It'd be interesting to see how
StarCraft 2 deals with those situations of having two moving groups heading
towards each other, or checking if indeed flow lanes are formed around
large obstacles.
Apparently these two videos are making the rounds [wink]
0

Share this post


Link to post
Share on other sites
Quote:
Original post by remigius
If you look to the video to around 4:50, you'll see that incoming units just move to the target location, while pushing away anyone within their 'bounding sphere'. If you just enforce this seperation constraint for all units, it would work out like this. The pushees also seem to slide aside rather than really walk, so it really looks similar to a cheap particle seperation simulation.

I agree... but the reason I think it is more than simply that is the individual units don't START straight at the target. They compress towards a stream as if they are waiting their turn slightly. That's why I believe they are also trying to get near the "main path".
0

Share this post


Link to post
Share on other sites
Quote:
Original post by swiftcoder
AIGameDev.com sent out this snippet yesterday [...]:
Quote:
[...]
The general concensus here is that A* is still used of course; in the
StarCraft 2 you'll see the group of zergling split into two around a large
obstacle, which is a sign that there are at least two shortest path
searches: one for each side.
[...]


It's not obvious to me that this implies that A* is done twice. It could simply be that the repulsion terms in the flocking push some agents onto the other path. It's these kind of issues that, again, make me interested in how much deliberative planning is done vs. reactive stuff.
0

Share this post


Link to post
Share on other sites
Quote:
Original post by InnocuousFox
I agree. If they are only generally trying to stay near the path, but are being pushed by their fellows, splitting around obstacles (including ravines) is no big deal.


...if the obstacles (and so, path differences) are small.

Let me give an example of where this fails though (I think Codeka already gets what I mean, but I suppose a picture never hurts:


....
...........X..
.....................
......... ....
.... ..
.... ...
..OO | O... ...
.OOO | OO.... ...
| OO............
.........


Here I assume a 4-connected map, with
'.' = passable tile
'[space]' = obstructed tile
'|' = also an obstructed tile; I want to highlight these; I'm calling them the "ravine."
'O' = agent
'X' = goal

Now suppose we select all agents across the ravine and tell them to go to the goal, X. You see the problem with generating a single path, and the motivation for the conversation Codeka and I were having...
0

Share this post


Link to post
Share on other sites
Quote:
Original post by InnocuousFox
...the reason I think it is more than simply that is the individual units don't START straight at the target. They compress towards a stream as if they are waiting their turn slightly. That's why I believe they are also trying to get near the "main path".


Ah right, I completely missed your earlier post somehow. I guess it comes down to this seperation and the attraction to the A* path then indeed. Seems like excellent stuff for a demo, but I guess I'll wrap up my other bazillion ones first [smile]
0

Share this post


Link to post
Share on other sites
Quote:
Original post by Emergent

....
...........X..
.....................
......... ....
.... ..
.... ...
..OO | O... ...
.OOO | OO.... ...
| OO............
.........
Yeah, this is what I was thinking of. The problem is basically how do you define those two separate groups.

Just thinking about it a bit more, I think the "line-of-sight" idea is actually the best. Now, when I say "line-of-sight" I don't actually mean your traditional line-of-sight (where A can "see" B), though, I just mean that if you moved in a straight line from A to B there's no obstacles. All units that are such defined are in a flock and can move together.

If you use a navmesh as your navigation data structure, then it's actually trivial: you just define "line-of-sight" as everything in the same polygon of the navmesh - that's basically O(1). You might have extra logic to handle adjacent polygons, perhaps.

So in the example above, the two groups would obviously be in separate polygons, so they get two separate paths. But each unit in the group would then just using a "follow path" algorithm to stay near the path, but away from it's fellows.

Navmeshes are cool :)
0

Share this post


Link to post
Share on other sites
[quote name='Codeka' timestamp='1267634228' post='4612998'][indent]Quote: [i]Original post by Emergent[/i]


....

...........X..

.....................

......... ....

.... ..

.... ...

..OO | O... ...

.OOO | OO.... ...

| OO............

.........

[/indent]
Yeah, this is what I was thinking of. The problem is basically how do you define those two separate groups.

Just thinking about it a bit more, I think the "line-of-sight" idea is actually the best. Now, when I say "line-of-sight" I don't actually mean your traditional line-of-sight (where A can "see" B), though, I just mean that if you moved in a straight line from A to B there's no obstacles. All units that are such defined are in a flock and can move together.

If you use a navmesh as your navigation data structure, then it's actually trivial: you just define "line-of-sight" as everything in the same polygon of the navmesh - that's basically O(1). You might have extra logic to handle adjacent polygons, perhaps.

So in the example above, the two groups would obviously be in separate polygons, so they get two separate paths. But each unit in the group would then just using a "follow path" algorithm to stay near the path, but away from it's fellows.

Navmeshes are cool [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]
[/quote]

If I use grid astar, how to implement the separate groups?
0

Share this post


Link to post
Share on other sites
Guest
This topic is now closed to further replies.
Sign in to follow this  
Followers 0