what's starcraft2's pathfinding tech?

ccanan · 2012-04-19T05:58:03

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

Artificial Intelligence Programming

Started by ccanan March 02, 2010 09:39 AM

23 comments, last by JTippetts 12 years ago

Emergent

982

March 03, 2010 03:10 PM

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

remigius

1,173

March 03, 2010 04:17 PM

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!

Codeka

1,239

March 03, 2010 04:37 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 :)

War Worlds • Journal

xiongyouyi

150

April 19, 2012 05:52 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