Posted By: MadJack
Dijkstra and Wed paths - 06/19/08 08:27
As I need it for my project, I am developping a pathfinder solution using the paths created and edited in WED.
This pathfinder will use DIJKSTRA algo.
The first step is to inialize a matrix with the nodes links and the distances.
Here is an example of code to do that :
Sorry, the page setup is almost lost between "code" tags...
More to come...
This pathfinder will use DIJKSTRA algo.
The first step is to inialize a matrix with the nodes links and the distances.
Here is an example of code to do that :
Code:
/*************************************************************************************** Basic Lite-C script for Pathfinding Will use DIJKSTRA Algo Nodes and edges are edited in WED using Path Objects (Add->Path and Vertex Move mode) Version 0.01 ****************************************************************************************/ #include <acknex.h> #include <default.c> int mat[1][1]; // Matrix where mat[i][j]>0 if there is a link between i and j // mat[i][j] = Distance between node number i and node number j int nbNodes; // How many nodes in the path ? /////////////////////////////////////////////////////////////////////// // An Entity is attached to a path, first we need to init the matrix // // Example : // // STRING* myPath = "path_000"; // ... // action myAction() // { // ... // initMat(me, myPath); // ... // } /////////////////////////////////////////////////////////////////////// function initMat(ENTITY* entPtr, STRING* entPath) { int i,j, numNextNode; int nodeOK=0, edgeOK=0, nbEdges=0; VECTOR posNode; // needed for path_getnode function var edgeSkill[3]; nbNodes = 0; nbNodes = path_set(entPtr, entPath); // path_set returns the number of nodes in the path (not in the manual !) realloc(mat, sizeof(int)*(nbNodes+1)*(nbNodes+1)); // (re)Set the matrix to the requested dimension for (i=1;i<=nbNodes; i++); // All unexplored nodes should be set to zero for (j=1;j<=nbNodes; j++); mat[i][j]=0; i=1; nodeOK = path_getnode (entPtr,i,posNode.x,NULL); // returns a positive value if node number i exist while(nodeOK>0) { j=1; edgeOK = path_getedge (entPtr,i,j,edgeSkill); // returns a positive value if edge number j exist // edgeSkill[0] = distance // edgeSkill[1] = edge weight // edgeSkill[1] = edge skill while(edgeOK>0) { nbEdges++; numNextNode = path_nextnode(entPtr, i, j); // edge number j exist, this function returns the number of the destination node mat[i][numNextNode]=(int)edgeSkill[0]; // distance is stored in mat[i][numNextNode] // You want to check each edge ? -> Uncomment next line : //printf("Mat[%1d][%2d] = %3d",i,numNextNode,mat[i][numNextNode]); j++; edgeOK = path_getedge (entPtr,i,j,edgeSkill); } i++; nodeOK = path_getnode (entPtr,i,posNode.x,NULL); } // You want to check number of edges ? -> Uncomment next line : // printf("Nb edges = %1d",nbEdges); } // NB : if you set a bi-directionnal sens between two points such as 1<->2, it will give 2 edges
Sorry, the page setup is almost lost between "code" tags...
More to come...