3 registered members (Ayumi, Akow, AndrewAMD),
1,505
guests, and 9
spiders. |
Key:
Admin,
Global Mod,
Mod
|
|
|
Dijkstra and Wed paths
#211940
06/19/08 08:27
06/19/08 08:27
|
Joined: Jun 2005
Posts: 87 France
MadJack
OP
Junior Member
|
OP
Junior Member
Joined: Jun 2005
Posts: 87
France
|
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 : /***************************************************************************************
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...
|
|
|
Re: Dijkstra and Wed paths
[Re: NITRO777]
#212303
06/21/08 13:58
06/21/08 13:58
|
Joined: Jun 2005
Posts: 87 France
MadJack
OP
Junior Member
|
OP
Junior Member
Joined: Jun 2005
Posts: 87
France
|
I'll try to do my best To day, DJ algo using paths is working ! So, there is no doubt, I'll give you ASAP something to play with. BTW: sometimes a matrix is nothing more than two dimensional array you don't need to understand what is DJ algo to use it, at the end, we'll have some new path functions like this one : I am here, I want to go there, what is my next point ? I go on working...
|
|
|
Re: Dijkstra and Wed paths
[Re: MadJack]
#212309
06/21/08 14:34
06/21/08 14:34
|
Joined: Oct 2007
Posts: 5,210 İstanbul, Turkey
Quad
Senior Expert
|
Senior Expert
Joined: Oct 2007
Posts: 5,210
İstanbul, Turkey
|
this is gonna be awesome(t least for me) if system works fast.
3333333333
|
|
|
Re: Dijkstra and Wed paths
[Re: Quad]
#212316
06/21/08 15:14
06/21/08 15:14
|
Joined: Mar 2003
Posts: 3,010 analysis paralysis
NITRO777
Expert
|
Expert
Joined: Mar 2003
Posts: 3,010
analysis paralysis
|
I am here, I want to go there, what is my next point ? I am sure many people would want this kind of functionality, including myself. If it works good and is simple you could even get paid for it. I would pay for a simple functionality which could simply be dropped in a game with little complications.
|
|
|
Re: Dijkstra and Wed paths
[Re: NITRO777]
#213101
06/25/08 21:12
06/25/08 21:12
|
Joined: Jun 2005
Posts: 87 France
MadJack
OP
Junior Member
|
OP
Junior Member
Joined: Jun 2005
Posts: 87
France
|
Well, here is a beta demo (V 0.05): TestPath Just unzip TestPath in your work folder. Main file is DJ_Test.c I made this demo as simple as possible, but if you look at the level in wed, you can check that it is working. In this version, only one Entity can use the DJ functions for a given path. I have to work on memory management now (queues instead of arrays) but I am not sure to get it in Lite-C. It might be easier do make a DLL... Thanks for your encouragements If this work help you, it is free !
|
|
|
Re: Dijkstra and Wed paths
[Re: MadJack]
#213261
06/26/08 16:28
06/26/08 16:28
|
Joined: Mar 2003
Posts: 3,010 analysis paralysis
NITRO777
Expert
|
Expert
Joined: Mar 2003
Posts: 3,010
analysis paralysis
|
If this work help you, it is free ! Wow! That is unbelievable. Thank you very much! I dont know why more people are not excited about this code, probably they havent seen it yet. Maybe when you finish with it you should put it on "user contributions" or "Aum resources", just so your work doesnt just dissappear unnoticed.
|
|
|
Re: Dijkstra and Wed paths
[Re: NITRO777]
#215998
07/14/08 14:28
07/14/08 14:28
|
Joined: Mar 2003
Posts: 3,010 analysis paralysis
NITRO777
Expert
|
Expert
Joined: Mar 2003
Posts: 3,010
analysis paralysis
|
@MAdJack Where would you put a simple state chooser like:
If (state=hungry) PtDep =1; PtDest = 12; If (state=thirsty) PtDep =current; PtDest = 14; etc.
etc.
I am not so much concerned about how to write it as I am wondering WHERE in the code you could put it in order for the action to read it and the ai to go somewhere based on time or a particular state.
Any help appreciated
Last edited by TriNitroToluene; 07/14/08 14:30.
|
|
|
|