Lightning-fast A* implementation resource?
by Bjarne Grönnevik · in Technical Issues · 08/22/2005 (7:22 am) · 11 replies
Hi guys,
I made a small AI-Path manager in C++ for torque that practically removes the CPU usage associated with multiple AI:s trying to get around.
What it is:
It implements the A* algorithm and has the option of precompiling all the nodes in the net and storing the results to file.
The plus side:
- If the navigation nodes are pre-compiled, the "live" work is reduced to fetching an entry from a table.
- If using "live" pathfinding: it is still a lot faster than in having the pathfinder implemented in script ( A navigation net that took 15 minutes to calculate with the A* implementation in the "CTF Bots" resource took about 10 seconds to compile with this path manager ).
The minus side:
- When using the precompiled pathfinding, you will have trouble with a dynamic navigation net ( Like supporting un-locking a door, or blowing up a bridge ).
- The pre-compiled data may get big in huge navigation nets ( But I tried to save a minimal amount of data ).
Now I'm wondering if this is something that people would like to get their hands on as a resource?
I made a small AI-Path manager in C++ for torque that practically removes the CPU usage associated with multiple AI:s trying to get around.
What it is:
It implements the A* algorithm and has the option of precompiling all the nodes in the net and storing the results to file.
The plus side:
- If the navigation nodes are pre-compiled, the "live" work is reduced to fetching an entry from a table.
- If using "live" pathfinding: it is still a lot faster than in having the pathfinder implemented in script ( A navigation net that took 15 minutes to calculate with the A* implementation in the "CTF Bots" resource took about 10 seconds to compile with this path manager ).
The minus side:
- When using the precompiled pathfinding, you will have trouble with a dynamic navigation net ( Like supporting un-locking a door, or blowing up a bridge ).
- The pre-compiled data may get big in huge navigation nets ( But I tried to save a minimal amount of data ).
Now I'm wondering if this is something that people would like to get their hands on as a resource?
#2
Damn, that means I have to do stuff. Like work. Well well, I asked for it, didn't I? ;)
08/22/2005 (7:32 am)
Oh. Fast responce. :)Damn, that means I have to do stuff. Like work. Well well, I asked for it, didn't I? ;)
#4
08/23/2005 (7:10 am)
I'd love to see what you've done!
#5
B.T.W. Any tips on how to make sure the code parts dont get line breaks in them when you paste the code into the online form? ( Extra line breaks are inserted because the lines are broken in the textbox you write the resource in ).
08/23/2005 (10:21 am)
I uploaded it yesterday, havent been accepted yet.B.T.W. Any tips on how to make sure the code parts dont get line breaks in them when you paste the code into the online form? ( Extra line breaks are inserted because the lines are broken in the textbox you write the resource in ).
#6
You can link resources even if they haven't been accepted yet :) (if you go to My Account and grab the link)
08/23/2005 (10:24 am)
You could include a file with the code in external files so people could look at the resource and copy the code from the external files?You can link resources even if they haven't been accepted yet :) (if you go to My Account and grab the link)
#7
Here is its current state
( Any comments naturally welcome )
08/23/2005 (10:30 am)
Yes. I guess putting the files in files is a good idea ;)Here is its current state
( Any comments naturally welcome )
#9
08/23/2005 (10:59 am)
Hmmm... so I was actually in your book before? Are you spying on me? ;)
#10
08/24/2005 (12:17 am)
Thanks for posting this MUCH needed resource on AI pathfinding Bjarne.
#11
It lags when you look at them, but if you look away all is good :D
Having 100 BOTs is fine, but try not to place them in the same spot as I've done ;)
08/24/2005 (10:55 am)
I just updaded the resource with an example map using 72 nodes and 100 Torque Orcs.It lags when you look at them, but if you look away all is good :D
Having 100 BOTs is fine, but try not to place them in the same spot as I've done ;)
Torque Owner Chris Labombard
Premium Preferred
Honestly... of course we want this.