Pathfinding on the RTS-SK!!
by RTS Kit Account · 02/07/2008 (6:04 pm) · 10 comments
I had this idea since a long time, but just recently -with a more concrete need-, is that I finally got avocated to work on pathfinding, more clearly on the port of the pathfinding part of the Tom Romanos and Gavin Bunney's immersive AI Engine (iAI) to the RTS-SK.
iAI is an excelent resource, and besides thank Gavin and Tom for such incredible work, I highly recommend it to anyone woking on AI and Torque. I also recommend the reading of the thread on the iAI engine. I have to thank everyone on that thread, involved on documentation and fixes for the proper use of Gavin's code. Some of the guys there, Thomas Huehn, opened my eyes about how easy it could be to use just the pathfinding part of the iAI engine. Thomas also did a fantastic mechanism to add a node using a grey scale bitmap to set the weight.
An image is better...
Now without more intruduction, lets talk about the port.
The core of the iAI pathfinding mechanism remains untouched. I also maintained the original filter/folder structure so would be easy to anyone intrested on continue the iAI integration to the RTS-SK.
The changes are on files where just little parts of the code where needed, or a lightwieght version of it would do a better job. Also some general modifications to the eninge are needed.
So, as the majority of the code on iAIAgent.cc/.h were not needed for the cause, I just lefted it out, integrating some of the fields and functions from that class to the RTSUnit.
Also I've included all the needed script functionality on the pathManager.cs file, forever defeating the historically hated comment:
// Clever pathfinding algorithms here! -- BJG
Sorry BJG, whoever you are! (Ben?) ;)
Plus some minor modifications on game.cs and player.cs
And thats all the porting work!
Doesnt look great?
I have writen an artcle on TDN with the description, some documentation, the download, and a step-by-step guide for a proper integration.
The pathfinding engine has some drawbacks, like a huge framerate drop when the node net is displayed (design/debug time anyway), also by default make no distinctions on the weight of each node (which isnt really a flaw), and the 45 degrees turning could result a little clumsy (the path smoothing maybe need some love for the RTS needs).
However, all in all the pathfinding is great, and the good design of the iAI engine, perfectly allows further improvements. The system is designed to work with diferent grids (node sub-networks). Also working on iAIPathNode::updateMoveModifier() would be easy to customize the node weight settings. And is really easy to test changes on the fly, ie. node grid size, paths, etc. To finish, the system has a good work on the engine console messages, so the feedback to the developer its great.
As a disclaimer, I have to say that I have little or no experience on AI, so any comments of mine on the subject, should be taked, at least, with care.
Some gridsize fun...
Ok, Ok, I'll shutup now, here is the TDN link: http://tdn.garagegames.com/wiki/RTS/iAIpathfinding
And here is the forum thread to discuss any issue: Pathfinding on the kit
iAI is an excelent resource, and besides thank Gavin and Tom for such incredible work, I highly recommend it to anyone woking on AI and Torque. I also recommend the reading of the thread on the iAI engine. I have to thank everyone on that thread, involved on documentation and fixes for the proper use of Gavin's code. Some of the guys there, Thomas Huehn, opened my eyes about how easy it could be to use just the pathfinding part of the iAI engine. Thomas also did a fantastic mechanism to add a node using a grey scale bitmap to set the weight.
An image is better...Now without more intruduction, lets talk about the port.
The core of the iAI pathfinding mechanism remains untouched. I also maintained the original filter/folder structure so would be easy to anyone intrested on continue the iAI integration to the RTS-SK.
The changes are on files where just little parts of the code where needed, or a lightwieght version of it would do a better job. Also some general modifications to the eninge are needed.
So, as the majority of the code on iAIAgent.cc/.h were not needed for the cause, I just lefted it out, integrating some of the fields and functions from that class to the RTSUnit.
Also I've included all the needed script functionality on the pathManager.cs file, forever defeating the historically hated comment:
// Clever pathfinding algorithms here! -- BJG
Sorry BJG, whoever you are! (Ben?) ;)
Plus some minor modifications on game.cs and player.cs
And thats all the porting work!
Doesnt look great?I have writen an artcle on TDN with the description, some documentation, the download, and a step-by-step guide for a proper integration.
The pathfinding engine has some drawbacks, like a huge framerate drop when the node net is displayed (design/debug time anyway), also by default make no distinctions on the weight of each node (which isnt really a flaw), and the 45 degrees turning could result a little clumsy (the path smoothing maybe need some love for the RTS needs).
However, all in all the pathfinding is great, and the good design of the iAI engine, perfectly allows further improvements. The system is designed to work with diferent grids (node sub-networks). Also working on iAIPathNode::updateMoveModifier() would be easy to customize the node weight settings. And is really easy to test changes on the fly, ie. node grid size, paths, etc. To finish, the system has a good work on the engine console messages, so the feedback to the developer its great.
As a disclaimer, I have to say that I have little or no experience on AI, so any comments of mine on the subject, should be taked, at least, with care.
Some gridsize fun...Ok, Ok, I'll shutup now, here is the TDN link: http://tdn.garagegames.com/wiki/RTS/iAIpathfinding
And here is the forum thread to discuss any issue: Pathfinding on the kit
#2
02/07/2008 (10:44 pm)
Excellent work as always! Just when I settled my mind on working on a simple FPS you do this! Ugh! :) 
#3
As always, any corrections to the TDN article are welcome (specially on my clumsy english :D )
02/08/2008 (2:26 pm)
Thanks guys :)As always, any corrections to the TDN article are welcome (specially on my clumsy english :D )
#4
Good work, but im not really sure this is quite fast enough, at least not in this form; when you for example tweak this a bit, so that units cant scale too steep slopes (which is probably one of the things you want to use this for) in such a way, that some areas (for example mountain tops) cant be reached, it seems to be very slow at calculating such a path does not exist. and this will affect the entire game i suppose as these will be calculated on the server. (or arent they)
you probably want to devide this into regions or do more of the calculations in the map reneration phase rather than ingame.
maybe its also an idea not to calculate a path for every unit in a selection, when it is proven not to be reachable at all.
03/08/2008 (7:11 am)
Hey there,Good work, but im not really sure this is quite fast enough, at least not in this form; when you for example tweak this a bit, so that units cant scale too steep slopes (which is probably one of the things you want to use this for) in such a way, that some areas (for example mountain tops) cant be reached, it seems to be very slow at calculating such a path does not exist. and this will affect the entire game i suppose as these will be calculated on the server. (or arent they)
you probably want to devide this into regions or do more of the calculations in the map reneration phase rather than ingame.
maybe its also an idea not to calculate a path for every unit in a selection, when it is proven not to be reachable at all.
#5
Afaik, the design also has a way to stop the process from start if the place is not reacheable, take a closer look, beacuse it sounds like its not working for you?
On the other matter, the system has the capability by design to use multiple regions, so you should have no problems there.
Its important to note. that this is not designed by me, its just a -rogue- port to the RTS-SK of an stablished resource. You are very welcome to implement and share any changes that you found usefull to rts needs!
03/08/2008 (11:36 am)
Well in fact this is just a starting point.Afaik, the design also has a way to stop the process from start if the place is not reacheable, take a closer look, beacuse it sounds like its not working for you?
On the other matter, the system has the capability by design to use multiple regions, so you should have no problems there.
Its important to note. that this is not designed by me, its just a -rogue- port to the RTS-SK of an stablished resource. You are very welcome to implement and share any changes that you found usefull to rts needs!
#6
i know the kit has the capability to stop when a point is not reachable; but before it states the point is unreachable, it tries a lot of routes (or all? im not sure). I made a simple change so that all the connected nodes get the same value in a memberfield i called mArea in the iAIPathGrid::createTerrainGrid method. which means it only has to check that variable in runtime to know wether we can skip the actual pathFinding. (im not sure you noticed; but if you would have a lot of units trying to reach an unreachable point the game freezes for a bit; and since this is serverside [i think] this could get pretty bad in multiplayer)
again, i didnt mean to get personal; great resource
03/08/2008 (12:34 pm)
hehe - i didnt mean to get personal there ;)i know the kit has the capability to stop when a point is not reachable; but before it states the point is unreachable, it tries a lot of routes (or all? im not sure). I made a simple change so that all the connected nodes get the same value in a memberfield i called mArea in the iAIPathGrid::createTerrainGrid method. which means it only has to check that variable in runtime to know wether we can skip the actual pathFinding. (im not sure you noticed; but if you would have a lot of units trying to reach an unreachable point the game freezes for a bit; and since this is serverside [i think] this could get pretty bad in multiplayer)
again, i didnt mean to get personal; great resource
#7
Really usefull info, however, as I didnt extensively tested this on the kit (didnt have time). What I was talking about on the "stop the process from start if the place is not reacheable" was just that, skip PF in case of unreachable place: I thought what you just did, was implemented by default, beacuse Gavin mentioned it on one of its .plans (in fact I'll check it out sometime soon [I hope], as maybe its there, but not working?).
Again Tjis,good job, and really useful info, any news on this dont doubt on post it :)
03/08/2008 (1:23 pm)
Oh, no, I didnt take it personal, just remarking the fact that this is not a resource designed specifically for the RTS-SK ;)Really usefull info, however, as I didnt extensively tested this on the kit (didnt have time). What I was talking about on the "stop the process from start if the place is not reacheable" was just that, skip PF in case of unreachable place: I thought what you just did, was implemented by default, beacuse Gavin mentioned it on one of its .plans (in fact I'll check it out sometime soon [I hope], as maybe its there, but not working?).
Again Tjis,good job, and really useful info, any news on this dont doubt on post it :)
#8
04/07/2008 (12:08 pm)
Great job to all involved! The RTS Kit is becoming more useful all the time! 
#9
I merged the CS code from World Dom mod into this updated player.cs and game.cs scripts.
Otherwise, everything was done as per the directions on TDN;
http://tdn.garagegames.com/wiki/RTS/iAIpathfinding
Everything compiled ok, but getting failures when I try to load the game now.
02/16/2010 (6:48 pm)
Trying to get this merged into the TGE 1.5.2 RTS Kit + World Domination Mod.I merged the CS code from World Dom mod into this updated player.cs and game.cs scripts.
Otherwise, everything was done as per the directions on TDN;
http://tdn.garagegames.com/wiki/RTS/iAIpathfinding
Everything compiled ok, but getting failures when I try to load the game now.
Compiling starter.RTS/server/scripts/resources/resourceGeneration.cs... Loading compiled script starter.RTS/server/scripts/resources/resourceGeneration.cs. Mapping string: MsgClientReady to index: 10 Mapping string: MsgMissionLoad to index: 11 *** LOADING MISSION: starter.RTS/data/missions/mission1.mis *** Stage 1 load *** Stage 2 load Executing starter.RTS/data/missions/mission1.mis. *** Mission loaded *** Sending mission load to client: starter.RTS/data/missions/mission1.mis Immersive AI :: Seek :: Building PathMap... Fatal: (c:\documents and settings\jyaskus\desktop\frts v2\engine\ts\tsmesh.cc @ 1908) TSMesh::castRay (1)
#10
However, it required some changes to player.cs as well ... which I posted on the forum under the following link;
http://www.torquepowered.com/community/forums/viewthread/71923
02/16/2010 (6:58 pm)
Got it working by applying to "stock" RTS Kit first ... then applying the World Domination mod files.However, it required some changes to player.cs as well ... which I posted on the forum under the following link;
http://www.torquepowered.com/community/forums/viewthread/71923
Torque 3D Owner James