I didn't ask the number of nodes to question your sugestion timkin.
I asked it because i find it weird that A* isn't performing in real time.
I'm not trying to impose A* on you gazsux, you may give whatever importance you think it's adequate to your game to the path accuracy, and chosing RTA* is a valid choice, but just for the sake of argument, i think A* should run in real time, even with a slow machine(1Ghz), with a relatively high fps, and a small CPU time slice, it can pump out several paths for a reasonably sized map.

Well, cutting out the situations where your path is completely block, I think you can easily modify an ordinary A* generated path to accomodate for dynamic moving obstacles.

Your A* search should give you a path that is pretty much way-point based. So, the other thing you add to it is just slap on a potential field. The NPC is always strongly attracted to the next way-point it has to go to, but is repelled by any obstacle on the way. Thus, if there's a moving obstacle in your way, the attraction and repelling will slightly alter the path of the NPC to circle around the obstacle. I'm not saying that this will work all the time, but should work in many cases. A few heuristics may be required to make it work in more cases, but as I noted earlier, this should work AS LONG AS the obstacle doesn't block your general path, like an open door closing in front of you.

Quote: Original post by xor
I didn't ask the number of nodes to question your sugestion timkin.
I asked it because i find it weird that A* isn't performing in real time.
I'm not trying to impose A* on you gazsux, you may give whatever importance you think it's adequate to your game to the path accuracy, and chosing RTA* is a valid choice, but just for the sake of argument, i think A* should run in real time, even with a slow machine(1Ghz), with a relatively high fps, and a small CPU time slice, it can pump out several paths for a reasonably sized map.

What if you have 1000 units? Would you even then just use brute force and calculate A* for 1000 units every time they move from node to node? What if some path opens and closes periodically, like a constantly moving platform? A naive approach would go towards that path whenever it's open and as soon as it closes it would start going towards alternative route. And after a second it would again turn around and go towards the once-again open path. Thus it might never reach its goal.

Quote: What if you have 1000 units? Would you even then just use brute force and calculate A* for 1000 units every time they move from node to node? What if some path opens and closes periodically, like a constantly moving platform? A naive approach would go towards that path whenever it's open and as soon as it closes it would start going towards alternative route. And after a second it would again turn around and go towards the once-again open path. Thus it might never reach its goal.

Ok, first i don't know where did you get that number, 1000 units(?), i'm a bit outdated on the latest RTS games but from the ones i do remember none of them allowed the movement of 1000 units in a single frame, as a reference, on Warcraft III they allow 12 units to move per frame IIRC.

Second, i'm not trying to tell gazsux to use A* or not, i'm not saying i would use it or not, my only point in that quote is that A* should run in real time, i find it weird that it doesn't and wonder how many nodes we're talking about here so that A* is strained to such an extent.

Lastly, the problem you mentioned about the moving platform, the way you mentioned it, in this particular case, isn't a problem at all, we've only been talking about recalculating if a path gets blocked.
You could have used a different example though, a moving wall(or something) that would constantly block two paths, and those two paths would be the shortest paths for the unit to reach it's destiny, so it would never reach the end, but it'a be a bit pointless aswell, because A* and RTA* would both behave the same way.
Even the way you describe it, constant recalculations of the path for every node change, would produce the same results on both algorithms. That problem as more to do with the way the paths are updated then with the specific algorithm that's being used to get those paths.

So to conclude, i think your point is that RTA* is faster then A*, i agree. I just think A*, under reasonable ciscumstances, can perform in real time aswell with the added bonus of optimal paths.

Original post by xor

Quote: Ok, first i don't know where did you get that number, 1000 units(?), i'm a bit outdated on the latest RTS games but from the ones i do remember none of them allowed the movement of 1000 units in a single frame, as a reference, on Warcraft III they allow 12 units to move per frame IIRC.

What do you know, another thing Total Annihilation had back in 1997 that "modern" RTSs don't have: The ability to have hundreds of units moving onscreen at a time.

Anonymous Poster:
Your comment is unrelated to the quote itself.
The quote refers to the number of units that calculate a new path in a single frame, as when a group of units gets a move order.

Sure you can get hundreds even thousands of units moving around in a map at the same time, but they are fetching the next moves from a list of directions, that's not what the quote refers to.

Quote: Original post by xor
I didn't ask the number of nodes to question your sugestion timkin.

Yes, I know that you weren't talking to me when I replied to your question. However, I still felt that my answer was relevant to interject at that point... you have my apologies if you feel I diverted the thread away from your question and the direction you were taking it.

Timkin

Well I didn't say that I couldn't get A* to work in real-time, I said that I considered it to be too inefficient compared to RTA* as you mentioned in one of your posts. I wanted the solution to be quite flexible too, so that I can re-use the code for other future projects. I'll definitely look into D* though as I must admit to having never taken time out to read anything on it.

Cheers for the discussion guys!

I and some others are working on an open source remake of Total Annihilation (taspring.clan-sy.com) where we allow for 1000s of units and dynamic maps. We basically use a multileveled A* approach where we refine the path as we travels along it. I havent looked at RTA* very closely so I dont know how close it is to it.

But anyway the only slight delays we get is at the creation of the path where we have a delay of about 1ms for each unit pathing from one end of a medium map to the other (512*512 search squares). This can be noticable for >100 units starting to path at once so i hope to be able to reduce it further by introducing a caching system on the higher level paths. This should work since large groups of units starting pathing at once usually move along roughly the same path.

This approach cant give completly optimal paths but the error it create is usually not visible and and in some tests i did a few years ago it generally produced paths within 5% of the optimal value.

If you want to test it make sure to check out the latest CVS version since the pathfinding of the 0.41 version is horribly broken.