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?

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

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

Thanks Timkin, that was what i was looking for!

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

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?

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

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

Just curious... did these papers help in your understanding of a quadtree implemenation of the DT algorithm?

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