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

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]

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

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

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

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