Dijkstra, A Star and Best First pathfinding solution (pre-comipled or real-time)
by Gabriel Notman · 08/23/2007 (4:41 pm) · 33 comments
Download Code File
Edit (April 08):
The updated version of this resource can be found here:
garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=14495
This is a path finding solution I developed last year as part of my studies.
The solution is based on placing marker objects as nodes within a specialized simgroup. The simgroup object is responsible for finding the path between two locations. It achieves this by searching for the nearest node with a direct LOS to both the start and target locations. It searches the graph and returns a list of object IDs as a space separated string. Using getPosition() on each of these objects (nodes) will give you the next target location to move to.
Features:
Adjacencies
Adjacency generation can either be done manually between two nodes, or for all the nodes using a built in function. The adjacency data takes several seconds to generate depending on the amount of nodes and the function. Functionality for saving and loading this data from a file is included. Additional nodes can also be added to the graph while preserving the existing adjacency data (see the documentation for the functions which facilitates this).
The adjacency functions are:
ALL: All nodes are set as adjacent.
NONE: No adjacencies are created.
LOS: All nodes with a direct line of sight are set as adjacent
DISTANCE: All nodes with a set distance are set as adjacent
HEURISTIC: Uses both LOS and DISTANCE to determine adjacency.
Path finding
Three separate algorithms have been implemented. Dijkstra, A star and Best first (greedy).
Features include the ability to pre-generate all the path data and save/load from a file. Has been tested doing real-time Dijkstra searching with 64 bots and uses about 1% of the time slice (using profiling).
Rendering
To facilitate development of the node graph, the adjacencies between the nodes are rendered. This is available while in the editor with at least one of the nodes selected. There are two render modes, one the adjacencies between the selected node and its adjacencies are drawn, and two where all adjacencies are rendered. When rendering all adjacencies, the last searched path is shown highlighted. See the documentation for further details on this.
An in editor screen shot here shows the path finding and adjacency data.
www.gabriel-notman.com/upload/screenshot.jpg @400k
Note that the this rendering process is based on OpenGL and will not work with TGEA, although modifying it for such should not be too difficult (it simply uses GL_LINES).
Issues:
The path finding is static, does not take into account dynamic objects such as enemies which the bot may wish to avoid.
The cost function is very simple, currently just the Euclidean distance.
The paths are not smoothed at all.
The included source has been tested with TGE 1.5.2,
I would appreciate any comments or feedback on this.
Edit (April 08):
The updated version of this resource can be found here:
garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=14495
This is a path finding solution I developed last year as part of my studies.
The solution is based on placing marker objects as nodes within a specialized simgroup. The simgroup object is responsible for finding the path between two locations. It achieves this by searching for the nearest node with a direct LOS to both the start and target locations. It searches the graph and returns a list of object IDs as a space separated string. Using getPosition() on each of these objects (nodes) will give you the next target location to move to.
Features:
Adjacencies
Adjacency generation can either be done manually between two nodes, or for all the nodes using a built in function. The adjacency data takes several seconds to generate depending on the amount of nodes and the function. Functionality for saving and loading this data from a file is included. Additional nodes can also be added to the graph while preserving the existing adjacency data (see the documentation for the functions which facilitates this).
The adjacency functions are:
ALL: All nodes are set as adjacent.
NONE: No adjacencies are created.
LOS: All nodes with a direct line of sight are set as adjacent
DISTANCE: All nodes with a set distance are set as adjacent
HEURISTIC: Uses both LOS and DISTANCE to determine adjacency.
Path finding
Three separate algorithms have been implemented. Dijkstra, A star and Best first (greedy).
Features include the ability to pre-generate all the path data and save/load from a file. Has been tested doing real-time Dijkstra searching with 64 bots and uses about 1% of the time slice (using profiling).
Rendering
To facilitate development of the node graph, the adjacencies between the nodes are rendered. This is available while in the editor with at least one of the nodes selected. There are two render modes, one the adjacencies between the selected node and its adjacencies are drawn, and two where all adjacencies are rendered. When rendering all adjacencies, the last searched path is shown highlighted. See the documentation for further details on this.
An in editor screen shot here shows the path finding and adjacency data.
www.gabriel-notman.com/upload/screenshot.jpg @400k
Note that the this rendering process is based on OpenGL and will not work with TGEA, although modifying it for such should not be too difficult (it simply uses GL_LINES).
Issues:
The path finding is static, does not take into account dynamic objects such as enemies which the bot may wish to avoid.
The cost function is very simple, currently just the Euclidean distance.
The paths are not smoothed at all.
The included source has been tested with TGE 1.5.2,
I would appreciate any comments or feedback on this.
About the author
#2
08/24/2007 (2:19 am)
This seems really cool and I will try this out in some days. Thanks for posting this as a resource!
#3
09/25/2007 (6:59 am)
Thank you, this was sorely needed.
#4
03/27/2008 (10:53 am)
Has anyone got this to work? I did everything accordingly with the code, etc, but my AIPathGroup is not created in the editor. When I click on it I get the window and enter a name but the group is not created.
#6
dLevel_01/server/scripts/game.cs (157): Unable to find function buildNodeGraph
....
03/27/2008 (11:52 am)
....dLevel_01/server/scripts/game.cs (157): Unable to find function buildNodeGraph
....
#7
...
pushDialog(): Invalid control: DemoEditorAlert
Mapping string: ToggleCamera to index: 3
creator/editor/EditorGui.cs (878): Unable to find object: '' attempting to call function 'open'
...
pushDialog(): Invalid control: DemoEditorAlert
Compiling creator/newObject.cs...
Loading compiled script creator/newObject.cs.
creator/newObject.cs (0): Unable to instantiate non-conobject class AIPathGroup.
creator/editor/EditorGui.cs (878): Unable to find object: '' attempting to call function 'open'
...
David
03/27/2008 (11:59 am)
Found more stuff in the console.log...
pushDialog(): Invalid control: DemoEditorAlert
Mapping string: ToggleCamera to index: 3
creator/editor/EditorGui.cs (878): Unable to find object: '' attempting to call function 'open'
...
pushDialog(): Invalid control: DemoEditorAlert
Compiling creator/newObject.cs...
Loading compiled script creator/newObject.cs.
creator/newObject.cs (0): Unable to instantiate non-conobject class AIPathGroup.
creator/editor/EditorGui.cs (878): Unable to find object: '' attempting to call function 'open'
...
David
#8
There are several possibilities here:
A. You have not included the the code files AIPathGroup (.h, .cc) into your project.
B. You have not recompiled since adding the files.
C. You are not using the new version of the executable (check the modification date).
Gabriel
03/27/2008 (12:06 pm)
It seems unable to create the AIPathGroup object.There are several possibilities here:
A. You have not included the the code files AIPathGroup (.h, .cc) into your project.
B. You have not recompiled since adding the files.
C. You are not using the new version of the executable (check the modification date).
Gabriel
#9
recompiled twice and went through the setup you wrote twice as well. I am using Torque 1.5.2.
I could try a clean 1.5.2 install to see what happens unless you think the problem is somewhere else.
David
03/27/2008 (12:25 pm)
I added the AIPathGroup and AIPathNode to my project, added the files *.txt adjustments, recompiled twice and went through the setup you wrote twice as well. I am using Torque 1.5.2.
I could try a clean 1.5.2 install to see what happens unless you think the problem is somewhere else.
David
#10
You definitely haven't added AIPathGroup properly because:
Make sure that you are running the same configuration build that you are compiling, so that you are not recompiling Debug but executing Release.
Gabriel
03/27/2008 (12:33 pm)
I tested it last week on a clean install of 1.5.2 and it worked fine.You definitely haven't added AIPathGroup properly because:
Quote:creator/newObject.cs (0): Unable to instantiate non-conobject class AIPathGroup.I stating that it does not know that type of object.
Make sure that you are running the same configuration build that you are compiling, so that you are not recompiling Debug but executing Release.
Gabriel
#11
The new version is awaiting approval.
Gabriel
03/27/2008 (12:34 pm)
I have just updated this resource BTW.The new version is awaiting approval.
Gabriel
#12
David
03/27/2008 (12:40 pm)
Do you mean aipathfinding.zip? I downloaded it but it's the same (dates, etc) as the one I downloaded earlier.David
#13
www.gabriel-notman.com/upload/PathFinding.zip
The changes will not affect the problem you are facing here though.
Gabriel
03/27/2008 (12:44 pm)
The new version can be found here:www.gabriel-notman.com/upload/PathFinding.zip
The changes will not affect the problem you are facing here though.
Gabriel
#15
Try deleting the executables in the example folder, and then rebuilding.
Also make sure the AIPath* files are added to the Torque Demo project in the solution.
Gabriel
03/27/2008 (12:57 pm)
Possibly I'm not sure. I haven't tried building Torque under Vista.Try deleting the executables in the example folder, and then rebuilding.
Also make sure the AIPath* files are added to the Torque Demo project in the solution.
Gabriel
#16
1) Installed the update on my XP computer, ran the AI mission and in editor mode I was able to see the blue lines that connected each path marker. Added several Korks, restarted the game and my bots were running around kina confused. (Did not have time to add new PathNodes).
2) installed the update on my Vista computer, ran the AI mission and in editor I added another PathNode. That worked but now I no links between any of the PathNodes. The blue lines are gone. I tried several things even moving the new PathNode directly under the one it was closest to but those things did not work. Restarted the game several times during this process. When I deleted the new PathNode I made, restarted the game, the blue lines came back.
David
03/28/2008 (10:51 am)
This is what I have come up with. 1) Installed the update on my XP computer, ran the AI mission and in editor mode I was able to see the blue lines that connected each path marker. Added several Korks, restarted the game and my bots were running around kina confused. (Did not have time to add new PathNodes).
2) installed the update on my Vista computer, ran the AI mission and in editor I added another PathNode. That worked but now I no links between any of the PathNodes. The blue lines are gone. I tried several things even moving the new PathNode directly under the one it was closest to but those things did not work. Restarted the game several times during this process. When I deleted the new PathNode I made, restarted the game, the blue lines came back.
David
#17
1) I have explained this on the new resource page which should be available soon. The additions I have made to AIPlayer.cs make Kork simply pick a random location to find a path and move to (it uses one of the nodes, but could use other coordinates), when it arrives it waits a second and then picks a new location to find a path to. It is not very intelligent behavior but it is simply to demonstrate the path finding.
2) How are you creating the new node? If you are creating it manually in the editor and then dragging it into the AIPathGroup, you are doing it incorrectly.
When you add nodes to the graph it automatically invalidates the existing adjacency data as the matrix size is no longer valid. You then have to rebuild it using the createAdjs(...) function. Alternatively you can use addObjectSafe(...) which will maintain the current adjacency data and create the new data for the node being added. See the word document in the zip for more information on these functions.
You will not see any connectivity (blue lines) if the adjacency data is invalid or not loaded correctly. You will see an error in the console if the data that is loaded does not match the graph.
If you are using the keybind to add new nodes (default 'x') it should be adding them correctly using these safe methods. Although you need to save the mission after adding any nodes (this saves the nodes to mission file and saves the adjacency data to a file too).
Hope this helps,
Gabriel
03/28/2008 (11:56 am)
I'm going to assume that you are using the new version of the resource.1) I have explained this on the new resource page which should be available soon. The additions I have made to AIPlayer.cs make Kork simply pick a random location to find a path and move to (it uses one of the nodes, but could use other coordinates), when it arrives it waits a second and then picks a new location to find a path to. It is not very intelligent behavior but it is simply to demonstrate the path finding.
2) How are you creating the new node? If you are creating it manually in the editor and then dragging it into the AIPathGroup, you are doing it incorrectly.
When you add nodes to the graph it automatically invalidates the existing adjacency data as the matrix size is no longer valid. You then have to rebuild it using the createAdjs(...) function. Alternatively you can use addObjectSafe(...) which will maintain the current adjacency data and create the new data for the node being added. See the word document in the zip for more information on these functions.
You will not see any connectivity (blue lines) if the adjacency data is invalid or not loaded correctly. You will see an error in the console if the data that is loaded does not match the graph.
If you are using the keybind to add new nodes (default 'x') it should be adding them correctly using these safe methods. Although you need to save the mission after adding any nodes (this saves the nodes to mission file and saves the adjacency data to a file too).
Hope this helps,
Gabriel
#18
Actually he runs back and forth on the top of the mountain. Anyways when do you think your new resource page will be up?
David
03/28/2008 (12:18 pm)
I am using the new version and everything is working now. I did the 'x' thing and sure enough there was the PathNode right under my feet. On the Vista computer I added several Korks and instead of using the Paths already setup he runs in a straight line to a far mountain and stops.Actually he runs back and forth on the top of the mountain. Anyways when do you think your new resource page will be up?
David
#19
Could you send me your console.log file and I will have a look for errors (you can look up my email on my profile).
Also try just with one bot to start with and see if he works fine.
Gabriel
03/28/2008 (12:36 pm)
I'm not sure when the resource will be approved.Could you send me your console.log file and I will have a look for errors (you can look up my email on my profile).
Also try just with one bot to start with and see if he works fine.
Gabriel
#20
04/05/2008 (8:03 pm)
I'm using Vista and this worked fine. I found it best to integrate the old CTF resource first (as seen in the screenshot) - give it a quick test to make sure it was working - and then install this resource and rebuild my engine.
Torque Owner James Thompson
Keiouu Studios