Path Finding Resource Update: Dijkstra, A Star and Best First pathfinding solution
by Gabriel Notman · 04/03/2008 (10:29 am) · 62 comments
Here is an update on the resource:
garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=13326
It has been updated so that it easy easier to integrate and use with the likes of the fps starter kit.
Also a few bugs were found in the original resource which have been fixed here.
It does use the Script Array resource by Daniel Neilsen.
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=4711
However this has been included already.
To use this resource in new missions, simply walk around the mission and press the drop node key (bound to 'x' by default). This will drop a node at your player's current position and start building the navigation graph, adjacency data and cost information. You must then save the mission before exiting. This will save the nodes as part of the mission, and will also save out the path data to file in the missions directory with the same name as the mission but with the added extension of '.dat'.
Once you have a navigation graph with at least two nodes, you can see a visual representation in the world editor. Simply open the editor and select one of the nodes. This will show a blue line connecting each of the nodes which are adjacent, or connected.
A modified version of the stronghold mission has been included with this resource (including the path data).
It will show up as 'AI Stronghold' in your missions list.
Here is a screen shot showing the navigation graph:
The AiPlayer script has been modified so that it will follow a path using this resource (if the navigation graph is available). Kork will simply pick a random location (it uses one of the graph's nodes as a target position, but it could use any coordinates), find a path to that location, and then head on his way. When he arrives he will wait one second and then repeat this process. This is not the most intelligent of behaviour, but it is there to simply demonstrate the path finding.
If you have the world editor open and one of the nodes selected, you will see the most recent found path drawn in green instead of the standard blue.
Unfortunately the graph data pushes this resource over the size limit.
You can download the resource here:
www.gabriel-notman.com/upload/PathFinding.zip
Known issues (April 12th 08):
1. Inefficient search of the start and end nodes. Currently it searches all the nodes in the graph to find the nearest nodes to both start and end positions. It uses a raycast to determine if it that node is reachable from either location. Initial testing on a ~100 node graph indicated this was taking up 90-95% of the time costs of the pathfinding. This cost will also increase with larger graphs (included demo graph has ~500 nodes). A potential fix is to add a maximum radius when searching for the start and end nodes, so reducing and limiting the raycast costs.
2. Possible bug with very short paths. If the closest node to both the start and end locations is the same, it may be added to the list twice.
3. Possible problem with very long paths. The full path is returned as a space separated list of node IDs in a single string. This has the potential to exceed the maximum string length, although I'm not sure what the limit is.
4. Nearest node may cause backtracking. When searching for a new path, it is possible that the AIPlayer will have to turn around and walk a few steps backwards. This is because the nearest node may be behind him. A possible solution will be to add an angular limit on the nodes to search for, so that the path only looks to use nodes in front of the AIPlayer, as starting nodes for the potential path.
I hope to work out these issues and update the resource soon.
garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=13326
It has been updated so that it easy easier to integrate and use with the likes of the fps starter kit.
Also a few bugs were found in the original resource which have been fixed here.
It does use the Script Array resource by Daniel Neilsen.
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=4711
However this has been included already.
To use this resource in new missions, simply walk around the mission and press the drop node key (bound to 'x' by default). This will drop a node at your player's current position and start building the navigation graph, adjacency data and cost information. You must then save the mission before exiting. This will save the nodes as part of the mission, and will also save out the path data to file in the missions directory with the same name as the mission but with the added extension of '.dat'.
Once you have a navigation graph with at least two nodes, you can see a visual representation in the world editor. Simply open the editor and select one of the nodes. This will show a blue line connecting each of the nodes which are adjacent, or connected.
A modified version of the stronghold mission has been included with this resource (including the path data).
It will show up as 'AI Stronghold' in your missions list.
Here is a screen shot showing the navigation graph:
The AiPlayer script has been modified so that it will follow a path using this resource (if the navigation graph is available). Kork will simply pick a random location (it uses one of the graph's nodes as a target position, but it could use any coordinates), find a path to that location, and then head on his way. When he arrives he will wait one second and then repeat this process. This is not the most intelligent of behaviour, but it is there to simply demonstrate the path finding.
If you have the world editor open and one of the nodes selected, you will see the most recent found path drawn in green instead of the standard blue.
Unfortunately the graph data pushes this resource over the size limit.
You can download the resource here:
www.gabriel-notman.com/upload/PathFinding.zip
Known issues (April 12th 08):
1. Inefficient search of the start and end nodes. Currently it searches all the nodes in the graph to find the nearest nodes to both start and end positions. It uses a raycast to determine if it that node is reachable from either location. Initial testing on a ~100 node graph indicated this was taking up 90-95% of the time costs of the pathfinding. This cost will also increase with larger graphs (included demo graph has ~500 nodes). A potential fix is to add a maximum radius when searching for the start and end nodes, so reducing and limiting the raycast costs.
2. Possible bug with very short paths. If the closest node to both the start and end locations is the same, it may be added to the list twice.
3. Possible problem with very long paths. The full path is returned as a space separated list of node IDs in a single string. This has the potential to exceed the maximum string length, although I'm not sure what the limit is.
4. Nearest node may cause backtracking. When searching for a new path, it is possible that the AIPlayer will have to turn around and walk a few steps backwards. This is because the nearest node may be behind him. A possible solution will be to add an angular limit on the nodes to search for, so that the path only looks to use nodes in front of the AIPlayer, as starting nodes for the potential path.
I hope to work out these issues and update the resource soon.
About the author
#62
08/11/2011 (8:57 am)
I've been meaning to post that, thank you!
Associate Steve Acaster
[YorkshireRifles]
//in renderline function if (_pathed) { //GFX->getDrawUtil()->drawLine(pos1,pos2,ColorI(0,255,0)); DebugDrawer *ddraw = DebugDrawer::get(); if ( ddraw ) { ddraw->drawLine( pos1, pos2, ColorI(0,255,0) ); } } else { //GFX->getDrawUtil()->drawLine(pos1,pos2,ColorI(0,0,255));//yorks DebugDrawer *ddraw = DebugDrawer::get(); if ( ddraw ) { ddraw->drawLine( pos1, pos2, ColorI(0,0,255) ); } }and the appropriate include:
This is Bryce's fix, not mine.