Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


what's starcraft2's pathfinding tech?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • This topic is locked This topic is locked
24 replies to this topic

#21 Emergent   Members   -  Reputation: 971

Like
0Likes
Like

Posted 03 March 2010 - 09:10 AM

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

Sponsor:

#22 remigius   Members   -  Reputation: 1172

Like
0Likes
Like

Posted 03 March 2010 - 10:17 AM

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]


Rim van Wersch [ MDXInfo ] [ XNAInfo ] [ YouTube ] - Do yourself a favor and bookmark this excellent free online D3D/shader book!

#23 Codeka   Members   -  Reputation: 1157

Like
0Likes
Like

Posted 03 March 2010 - 10:37 AM

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 :)

#24 xiongyouyi   Members   -  Reputation: 150

Like
0Likes
Like

Posted 18 April 2012 - 11:52 PM

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 Posted Image


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

#25 JTippetts   Moderators   -  Reputation: 8598

Like
0Likes
Like

Posted 18 April 2012 - 11:58 PM

Topic is 2 years old. Please don't necro. Start a new thread if you have a question.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS