Sign in to follow this  
skow

Preferred method for pathing on tiled platform?

Recommended Posts

skow    248
Forgive this fairly basic question; I have primarily worked with greedy methods in the past for real-time decision making. For a simple platform made up of tiles (any where from 40,000 to 160,000), where tiles are categorized as “passable” or “avoidable”, what is the preferred method (to be done in real time) for calculating a set path? Is a simple A* method the way to go with such a large grid?

Share this post


Link to post
Share on other sites
Kaze    948
depends on how many traps there are (such as U shaped terrain),
you could simply have yor sprite try to move in the direction of its target and avoid obsicals in front of it and use A* it it gets stuck

Share this post


Link to post
Share on other sites
Timkin    864
Quote:
Original post by skow

Forgive this fairly basic question; I have primarily worked with greedy methods in the past for real-time decision making. For a simple platform made up of tiles (any where from 40,000 to 160,000), where tiles are categorized as “passable” or “avoidable”, what is the preferred method (to be done in real time) for calculating a set path? Is a simple A* method the way to go with such a large grid?


Basic A* on such a grid would be inefficient, since it performs computation at run time and so much could be precomputed to improve run time efficiency. My recommendation would be a heirarchical flood fill (such as Distance Transform on a quadtree decomposition of the platform tiling). This can be computed offline for static obstancles. If you have dynamic obstacles, still do the offline computation for static obstacles but include an obstacle avoidance behaviour computed in real time when an obstacle appears in an area that is deemed otherwise passable (this will require execution monitoring of the movement plan execution... this is fairly trivial to do).

Cheers,

Timkin

Share this post


Link to post
Share on other sites
JarmoKauko    122
Timkin,

You probably have explained the Distance Transform already a dozen times (I remember seeing some pseudo code here), but just to make sure: DT is computed for a selected goal node, right? In this case, for a selected node in a quadtree.. So are you suggesting precomputing Distance Transforms for all the quadtree nodes?

-Jarmo

Share this post


Link to post
Share on other sites
Timkin    864
Quote:
Original post by JarmoKauko
DT is computed for a selected goal node, right?


Yes.

Quote:

In this case, for a selected node in a quadtree.. So are you suggesting precomputing Distance Transforms for all the quadtree nodes?


No. Well, yes, but no. I'm suggesting a heirarchical approach to the floodfill that will limit the amount of space required to be filled to find a valid path, if it exists. I did start writing a more detailed explanation of my suggestion yesterday, but I don't have time to complete it just yet. Here is the gist of it...

Using a spatial decomposition enables you to compute the floodfill at increasing resolutions (stepping down the tree), with the scope of each fill restricted to just the region determined as needing a path crossing it at the previous level.

This can be sped up by further by utilising other techniques at more coarse resolutions, such as transition matrices (which can be precomputed offline for maps with static obstacles) to determine which quads (subtrees) are needed for a given path.

Does this make sense?

Share this post


Link to post
Share on other sites
JarmoKauko    122
Yes, but I'm still looking forward for the detailed explanation :) I'm not sure but it sounds like in some cases (e.g. in maze-like maps) a higher-level flood fill might not provide enough information to restrict the scope of a lower level flood fill.

-Jarmo

Share this post


Link to post
Share on other sites
Timkin    864
Since I don't have time to finish writing up my description, I'll provide some references for you to read over... these papers should be more than adequate for your needs. If there are any problems in deciphering them, just drop me a line...

Williams, M & Jones, D., "A Rapid Method For Path Planning In Three Dimensions...". Robotica v19, pp125-135, 2001.

Chen, D., Szczerba, R. & Uhran, J. Jnr., "A Framed-Quadtree Approach For Determining Euclidean Shortest Paths..." IEEE Trans. on Robotics and Automation. v13, n5. Oct 1997.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Steadtler    220
He might have run in the way of "File not available." for the first paper, and the "you need a subscription to access our content" for the IEEE one. And thats what college librairies are for...

I published a paper with IEEE, and now I have to pay to access my own research :P

Share this post


Link to post
Share on other sites
Timkin    864
Quote:
Original post by Steadtler
He might have run in the way of "File not available." for the first paper, and the "you need a subscription to access our content" for the IEEE one. And thats what college librairies are for...


Bugger... the first link worked fine for me when I posted it, but not any more... and the second link... well, that's what I get for posting from a box at work (where we have a subscription, so the IP is recognised).

Sorry about that guys... if you want a copy of either of these papers for research purposes, please let me know and I'll fascilitate it. I'll try and find a working link to the first paper.

Cheers,

Timkin

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this