Group Motion Planning
Author
Give me some links related to group motion planning.
Please tell how it is performed in such games like: StartCraft, WarCraft series, C&C series or AoE series.
Alright...
1) Please dont cross post. Post your topic in only one forum
2) Avoid very short posts, especially when you start the topic
3) Try doing the research on your own first. Tell us what you've found, we'll tell you if you missed anything important.
3) Especially avoid being authoritative. This is a discussion forum, people dont have to give you anything.
Author
I have read about classic A* algorithm (path finding on a field, represented with a regualr grid), also i have read about its modifications for group motion planning: LRA*, HRA*, WHRA*. But i haven't found any references about group motion planning on fields with no regular structure (grid, cells). Could you please give me some links referred to group motion planning or say how it is done in modern strategy games; e.g. C&C series, Warcraft series.
Every plane or space has a grid, it's called coordinates ;)
Depending on how exact you'd like it to have, you could just make yourself a grid on your map with bigger or smaller cells - that's how I'd try it at least.
Depending on how exact you'd like it to have, you could just make yourself a grid on your map with bigger or smaller cells - that's how I'd try it at least.
Quote:Original post by ZiCuer
But i haven't found any references about group motion planning on fields with no regular structure (grid, cells).
You would be (very) hard pressed to find a modern game that didn't discretise its pathfinding problem. For those games that are not played on an inherently discrete map, spatial decomposition is typically used to build a heirarchical navigation mesh. The degernate case (a one layer heirarchy) is easily achieved using the lowest level of decomposition (for example the leaves of a quad-tree).
Games that don't discretise the pathing space typically don't perform deliberative path planning. Rather, they use local behavioural methods, such as Steering Behaviours/Potential Fields/Reactive Behaviours.
The Game Programming Gems and Game AI Wisdom series of books have a variety of articles covering deployed (in published games) implementations of solutions to this problem.
Cheers,
Timkin
All the games you listed are played on a grid. You may not be able to see it, but it's certainly there.
The group motion planning is simple formation offsets. "I will arrive at destination + offsetvector". The offsets are either generated by hand or are calculated programmatically: fighters at front, ranged behind, etc.
But underlying everything is A* path-planning. You just have people path plan to an offset of the click point. If you want coherent movement between units with different move speeds you just slow everyone down to the speed of the slowest unit.
To achieve in-transit formation you pick a leader and have everyone maintain an offset from the leader. The complexity here is avoiding obstacles while maintaining formation. You can use steering / flocking behaviors for that but it remains a challenge fraught with edge cases.
-me
The group motion planning is simple formation offsets. "I will arrive at destination + offsetvector". The offsets are either generated by hand or are calculated programmatically: fighters at front, ranged behind, etc.
But underlying everything is A* path-planning. You just have people path plan to an offset of the click point. If you want coherent movement between units with different move speeds you just slow everyone down to the speed of the slowest unit.
To achieve in-transit formation you pick a leader and have everyone maintain an offset from the leader. The complexity here is avoiding obstacles while maintaining formation. You can use steering / flocking behaviors for that but it remains a challenge fraught with edge cases.
-me
i have a little problem using discrete maps for this kind of thing... say you move from cell (5, 5) to cell (5, 6). This is instant in computer time, but you need to animate the unit moving from the first cell to the second. So... when the unit is on its way in between the two cells (or nodes), which cell does it ACTUALLY occupy in the underlying data structure? doesnt this pose any other problems?
Quote:Original post by lemour9907
i have a little problem using discrete maps for this kind of thing... say you move from cell (5, 5) to cell (5, 6). This is instant in computer time, but you need to animate the unit moving from the first cell to the second. So... when the unit is on its way in between the two cells (or nodes), which cell does it ACTUALLY occupy in the underlying data structure? doesnt this pose any other problems?
Its as you wish. The most common case is occupy on arrival I guess, because you will often want to trigger some events when the unit arrives. This poses problem if you want coordinated pathfinding, but is (more of less easily) solved with a look-ahead.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
