Hey, Does anyone have any good links to resources on RTA* or pseudo code for it. I have had a look around and have only been able to find a couple of uni lecture slides that don't explain much about the actual implementation. All I have been able to gather so far is that g(n) is calculated from the current node rather than the initial node for each member of the OPEN list. Anyone have any more info which might help me out? Thanks!

Now i'm also interested, i found this.

Linky

>This is odd, A* runs in real time.

I'll take a look at that paper.

Currently I have edited my A* implementation to recalculate the g(n) value with respect to the current node. And instead of the while() loop I just return the next best node to move to and request a further one once I am there. This seems to be working fine, though I get the occasional infinite loop - Hmm... backtracking...

Quote: >This is odd, A* runs in real time.

Yeh, you can get A* to run in real-time but A* calculates the full path from the start node to the end node in one go. In a dynamic environment this path may become blocked by another player or npc etc. Therefore you need an algorithm that can account for this. RTA* just gets the next best node and re-calculates the cost each time. So 'blockages' can be worked around. Though ofcourse this does mean that more work is done at each node.

If a path with A* becomes blocked you run A* again, just like you do with RTA*, but with A* you have to calculate the intire path again. My point is, calculating the intire path can be done in real time without using RTA*, that can produce suboptimal paths.

Quote: In a dynamic environment this path may become blocked by another player or npc etc. Therefore you need an algorithm that can account for this.

Well, you don't NEED one, but it one way to handle it. ;) Whether this is the right option for you depends on how often your paths are invalidated (and if this invalidation breaks connectivity - ie a local pathing solution won't work around it).

If your paths don't get invalidated frequently, you can just recognize that your path is blocked and repath with A* or any other such method. Or, instead, you can try to preform some sort of local movement around the obstacle (ie insert an intermediate point as your next waypoint, and path to it before resuming the normal path). Another solution, if the blockage is expected to be temporary, is to just wait for a few frames.

Sorry, didn't mean to detrail the RTA* conversation, just wanted to point out that there are a variety of options.

EDIT: One day I will get my quote tags right the first time; ah, that will be a glorious day.

Quote: If a path with A* becomes blocked you run A* again, just like you do with RTA*, but with A* you have to calculate the intire path again. My point is, calculating the intire path can be done in real time without using RTA*, that can produce suboptimal paths.

Depends upon the environment youre implementing it in I suppose. I'll stick with RTA* as paths are likely to become blocked often in the environment im using not to mention the size of it would make constant re-calculation using A* too inefficient. Also the goal node is re-calculated each frame depending upon the assessed needs of the NPC resulting in a different action being performed that may well mean it is changed often.

Quote:
Sorry, didn't mean to detrail the RTA* conversation, just wanted to point out that there are a variety of options.

No probs, given more time i'd like to have looked into more options including some Anytime path planning techniques too.

Thanks.

[Edited by - gazsux on May 16, 2005 5:22:46 PM]

Or you could just use D*...

Just how many nodes are we talking about?

Quote: Original post by xor
Just how many nodes are we talking about?

The actual number of nodes is probably less important than the algorithmic complexity of performing the search. A* is at best O(n*log(n)). If an obstacle invalidates a path at depth d', then there are at most b(d-d') nodes in the subtree below the invalidated branch that have become invalid (where b is the maximum branching factor in that subtree and d is the maximum depth of that subtree). You can work out the approximate time complexity of updating that subtree. There's also a slight time penalty for propogating the effects of the update back through the tree.

D* (Dynamic A*) is a good example of an algorithm that, if I recall correctly, restricts the update of the search tree to only the parts of the invalid subtree that can be reached from the current state and propogates the effective change in path cost to nodes affected by the invalidation of that path (that can be reached from the current state).

So, for example, you suddenly see ahead of you a door that is closed that you had assumed was open and through which your planned path lay. D* would be a good algorithm to use to update your search tree costs given this new information. If you're able to store your entire search tree discovered so far, then replanning is simply a matter of continuing the search from the current best node to the goal. If you cannot maintain your entire tree due to memory limitations, then you need to be a little creative about how and when you replan. That's a topic for a whole other thread though! ;)