... but in many of those situations the current technique involves choosing one member of the group to act as a group leader... find the path for that leader and then work out how each group member can use the path to get to the goal (i.e., shortest path onto the leaders path). I agree though that this is not optimal, because you''d obviously like to be able to send members of a group all over a map, then have a single recall command that orders the group to converge on a single point.

Now consider if these groups were whole units of agents in themselves... you wouldn''t want to compute an individual path for each group and certainly not for each agent...

Timkin

quote: Original post by Timkin
Now consider if these groups were whole units of agents in themselves... you wouldn't want to compute an individual path for each group and certainly not for each agent...

It depends on the application (game). In some cases, like FSC for instance, a highly complex environment (think urban terrain with lots of buildings - each with lots of floors, rooms and stairwells, connecting tunnels - and a need to move a group from one intersection to another one across town) could make it necessary to calculate a path for each agent of a group in order to achieve the desired behavior. Especially, if the desired path was to have a quality of "stay out of the open" - thus meaning that the agents needed to navigate through and near buildings as much as possible.

Now I'm not saying that this example would be a "DTA Friendly" application of pathfinding, but I can think of others that would.

Eric


[edited by - Geta on April 16, 2003 9:23:03 AM]

That example definitely screams heirarchical planning , at least to me!

I''m going to have to burn a reminder into the back of my hand... each day I read GD and think, doh, I''m supposed to look through my boxes of papers for hard copies for Geta... and each night something at home distracts me from doing it...

I''ll TRY and remember tonight...

Timkin

quote: Original post by Timkin
That example definitely screams heirarchical planning , at least to me!

How does hierarchical planning help to solve the low-level planning requirement of moving agent by agent, from room to room in the buildings?

quote:
I''m going to have to burn a reminder into the back of my hand... each day I read GD and think, doh, I''m supposed to look through my boxes of papers for hard copies for Geta... and each night something at home distracts me from doing it...

I''ll TRY and remember tonight...

PS: Could you please check for hard copies of the papers you promised? Actually, I''m pretty sure my article proposal did not get accepted for GPG4 so there is no rush.

Thanks,

Eric

quote: Original post by Geta
How does hierarchical planning help to solve the low-level planning requirement of moving agent by agent, from room to room in the buildings?

A high level description of the environment (in terms of rooms, hallways, roads, etc.) can be quickly processed using the DTA. Each agent can then utilise this to formulate an abstract, individual plan. Paths through these regions can be worked out at a lower level utilising an appropriate algorithm. Where possible, low level paths can be shared between agents (for example, a path down a hallway, or a road).

quote: Original post by Geta
PS: Could you please check for hard copies of the papers you promised?

I am sorry for not getting them to you sooner. I have finally done a huge cleanout of my computer room today so I can now unpack the boxes that came from my Monash office tomorrow. I should then be able to get something to you shortly after.

As for the article not getting published... I still think it would be well worth the effort of investigating hybrid pathfinding algorithms and use of the DTA for heirarchical planning.

Regards,

Timkin

quote: Original post by Eelco
defining landmasses is the best way to go in this situation, im quite sure.

landmasses is not the right term though, cos it led you to believe it would cause trouble with trees enclosing an area. a better term for this would be just areas: each part of the map only reachable by itself.
to construct these area''s, add a member to your tile struct char area, and do a floodfill witch will fill all walkable tiles with a unique index. then keep searching the map for a spot thats not yet indexed by a floodfill and start a new floodfill from there, until youve covered all of the map.
then you can just check if the target and start have the same area index, and only if they do perform an a* search.

I was about to post this when I read Eelco''s reply. I believe he''s got the correct solution. This is something that should be repeated whenever a change in the land occurs, if a new tree grows for example. This way, all the complex calculations are pre-calculated for you, and you can avoid attempting to ever find a path from one place to another that is impossible. You will know this before ever calling the path finding algorithm. Therefore, your algorithm will always return a result, if it is called.

Jason Doucette - my online résumé page: www.jasondoucette.com
projects, real-time graphics, artificial intelligence, world records, wallpapers/desktops
"Great minds discuss ideas, average minds discuss events, small minds discuss people." - Admiral Hyman G. Rickover

quote: Original post by Timkin
If you had followed the link I posted above and looked at the Distance Transform Algorithm you would have realised (before dismissing it) that what you are suggesting is, infact, the DTA in a nutshell.

Aha.



Jason Doucette - my online résumé page: www.jasondoucette.com
projects, real-time graphics, artificial intelligence, world records, wallpapers/desktops
"Great minds discuss ideas, average minds discuss events, small minds discuss people." - Admiral Hyman G. Rickover

quote: Original post by Timkin
Original post by Geta
How does hierarchical planning help to solve the low-level planning requirement of moving agent by agent, from room to room in the buildings?


A high level description of the environment (in terms of rooms, hallways, roads, etc.) can be quickly processed using the DTA. Each agent can then utilise this to formulate an abstract, individual plan. Paths through these regions can be worked out at a lower level utilising an appropriate algorithm. Where possible, low level paths can be shared between agents (for example, a path down a hallway, or a road).

This description does not really convince me that the solution screams for a hierarchical planning solution. The problem is still with the low-level paths, and the higher level planning really does not address that.

Yes, I used a hierarchical solution in my implementation. The DTA would not have bought much (IMO) at that level over an A* simply because the A* was processing so few nodes at such a high level and the high level path was run only once per group.

Anyway, after I finish some other work shortly, I plan to build a test bed and produce some performance figures (A* vs. DTA) that might be worth discussing. Despite the appearance of no interest by publishers, I still think there an article of some use to game developers in all of this.

Eric