Navigation
by George Lancaster · in Torque Game Engine · 06/07/2004 (9:07 am) · 5 replies
What is the current navigation system. A*, Dijkstra, something else or none?
About the author
#2
A* is a good choice, but it burns too much cpu for my taste.
Thanx,
George
06/07/2004 (10:47 am)
Thats cool, I'll cook up a RLE Dijkstra system. Can't have my guys bumping into trees. =) It'll be similar to Red Dead's and/or Daredevil's nav and AI systems.A* is a good choice, but it burns too much cpu for my taste.
Thanx,
George
#3
06/07/2004 (11:39 am)
Just curious, what does the "RLE" stand for in your Dijkstra system? I am familiar with Dijkstra's pathing algorithm, but I have never seen it coupled with RLE.
#4
Anyway.. Yes, its A* based.
06/07/2004 (12:09 pm)
A* burns up CPU? compared to what? given that A* is used in nearly every pathing system ever produced.Anyway.. Yes, its A* based.
#5
Look up table:
*|0|1|2|3|4
---------
0|0|1|1|1|1
1|0|1|3|1|3
2|1|1|2|1|1
3|2|1|1|3|4
4|1|1|1|3|4
#1 So if you wanted to go from 0 node to the 4th node you would simply follow the chain.
#2 In the fouth column of row 1 it says to go to node 3
#3 In the fouth column of row 3 it contains the solution.
Because the table is cooked up before hand it simply shouldn't show up on the profiler. I found that A* with 20 or so guys on a PS2 would consume anywhere from 1 to 3 percent. (Node densities and lattice conductivity will be the variance in speed.)
What makes RLE so good is that its speedy and simple to debug. It also lends itself well to repeating number which the nav table has in spades.
A* is better at dynamic paths and far more documented than Dijksta. I didn't want to imply that A* sucks, its just I got the Dijkstra code ready to go and it would do a great job on what I am trying to create.
George
06/07/2004 (1:11 pm)
I know its often used, but A* is much slower than Dijksta. This is because of calculations for open and closed lists. Dijkstra on the other hand used a pre-calculated table hence its faster, but more memory intensive. (N squared) I used a Run Length Encode Dijkstra. This burns a little more cpu than the standard lookup table, but gives back 15 to 50x the memory. (Depends on interconductivity, densities of the nav lattice, and node ordering.)Look up table:
*|0|1|2|3|4
---------
0|0|1|1|1|1
1|0|1|3|1|3
2|1|1|2|1|1
3|2|1|1|3|4
4|1|1|1|3|4
#1 So if you wanted to go from 0 node to the 4th node you would simply follow the chain.
#2 In the fouth column of row 1 it says to go to node 3
#3 In the fouth column of row 3 it contains the solution.
Because the table is cooked up before hand it simply shouldn't show up on the profiler. I found that A* with 20 or so guys on a PS2 would consume anywhere from 1 to 3 percent. (Node densities and lattice conductivity will be the variance in speed.)
What makes RLE so good is that its speedy and simple to debug. It also lends itself well to repeating number which the nav table has in spades.
A* is better at dynamic paths and far more documented than Dijksta. I didn't want to imply that A* sucks, its just I got the Dijkstra code ready to go and it would do a great job on what I am trying to create.
George
Associate Kyle Carter