1. ## Dijkstra's Algorithm(help)

hi ppl...
I need some help with an 3d pathfind with waypoints using Dijkstra's Algorithm, Any idea? Best Regards

2. ## Dijkstra's Algorithm(help)

Dijkstra's Algorithm is the same as A* only without heuristics.
What exactly do you need help with? there is a lot of general information
on the net.

3. ## Dijkstra's Algorithm(help)

Originally Posted by Dan
Dijkstra's Algorithm is the same as A* only without heuristics.
What exactly do you need help with? there is a lot of general information
on the net.
all the help ...

i dont now how to start...
my idea is put same 3d points(waypoints ) and then search the closest point to the player and
create a path.
i read same texts on the net but i never cam with the idea.
maybe im to dumb

4. ## Dijkstra's Algorithm(help)

I would suggesst to use A* algorithm.
In the net you can find examples for a 2D grid, but it really doesn't matter
what kind of grid or way point system you use.
http://www.policyalmanac.org/games/aStarTutorial.htm
Try this article, I think it quite clearly explains the basics of
path finding on 2D grid. Once you understand how it works
you can start to implement path finding for waypoint system.

5. ## Dijkstra's Algorithm(help)

Originally Posted by Dan
I would suggesst to use A* algorithm.
In the net you can find examples for a 2D grid, but it really doesn't matter
what kind of grid or way point system you use.
http://www.policyalmanac.org/games/aStarTutorial.htm
Try this article, I think it quite clearly explains the basics of
path finding on 2D grid. Once you understand how it works
you can start to implement path finding for waypoint system.

i have 2d pathfinder sources.. ans i try to put in my 3d game but no success
all 2d path have array 's(grids)

6. ## Dijkstra's Algorithm(help)

The way point system is not so much different from a grid system.
Every node simply needs to store the pointers to all the neighbour nodes.
And what kind of game exactly are you making?

7. ## Dijkstra's Algorithm(help)

outdoor fps game with objects in land

http://www.pascalgamedevelopment.com...pic.php?t=4756

im creating the bad guys ai system

8. ## Dijkstra's Algorithm(help)

Originally Posted by Dan
The way point system is not so much different from a grid system.
Every node simply needs to store the pointers to all the neighbour nodes.
And what kind of game exactly are you making?
dan see this plz

http://leafproject.com.sapo.pt/leaf.html

the unit LEAF_Pathfinding is that i want but thin unit dont work

Code:
```Unit LEAF_Pathfinding;

Interface
Uses LEAF_System,LEAF_IO;

Type
LPath=Class
List&#58;Array Of Integer;
Size&#58;Word;
End;

PNode=^LNode; // Pointer to a node
LNode=Record
Name&#58;String; //If Null then Name='NODE'+LStr&#40;I&#41;
Position&#58;LVector;
NextNode&#58;Array&#91;0..3&#93;Of Integer;
Distance&#58;Array&#91;0..3&#93;Of Single;
//DIJKSTRAs ALGORITHM
CurrentDistance&#58;Single; //What the current distance was at this point
TmpVar&#58;Single; //Temporary area for storing distance data...
End;

LNodeList=Array Of LNode;

LPathfinder=Class
Protected
_NodeCount&#58;Word;
_NodeList&#58;LNodeList;

Public

Procedure Save&#40;Dest&#58;LStream&#41;;

Procedure RemoveNode&#40;Id&#58;Integer&#41;;
Function GetNode&#40;Name&#58;String&#41;&#58;Integer;
Function GetNearNode&#40;Pos&#58;LVector&#41;&#58;Integer;
Function GetNodeDistance&#40;Node&#58;Integer;Pos&#58;LVector&#41;&#58;Single;
Function GetPath&#40;StartNode,EndNode&#58;Word;Var Path&#58;LPath&#41;&#58;Boolean;

End;

Implementation
Uses LEAF_Math;

// LPathfinder

Var
I,J&#58;Integer;
S&#58;String;
Begin
If Assigned&#40;Source&#41; Then
Begin
SetLength&#40;_NodeList,_NodeCount&#41;;
For I&#58;=0 To Pred&#40;_NodeCount&#41; Do
Begin
For J&#58;=0 To 3 Do
If _NodeList&#91;I&#93;.NextNode&#91;J&#93;>=_NodeCount Then
Begin
Exit;
End;
_NodeList&#91;I&#93;.Name&#58;=UpStr&#40;S&#41;;
End;
End Else
Begin
SetLength&#40;_NodeList,1&#41;;
For J&#58;=0 To 3 Do
_NodeList&#91;0&#93;.NextNode&#91;J&#93;&#58;=-1;
End;
End;

Procedure LPathfinder.Save&#40;Dest&#58;LStream&#41;;
Var
I&#58;Integer;
Begin
Dest.Write&#40;_NodeCount,SizeOf&#40;_NodeCount&#41;&#41;;
For I&#58;=0 To Pred&#40;_NodeCount&#41; Do
Begin
Dest.Write&#40;_NodeList&#91;I&#93;.Position,SizeOf&#40;_NodeList&#91;I&#93;.Position&#41;&#41;;
Dest.Write&#40;_NodeList&#91;I&#93;.NextNode&#91;0&#93;,SizeOf&#40;Integer&#41;*4&#41;;
Dest.Write&#40;_NodeList&#91;I&#93;.Distance&#91;0&#93;,SizeOf&#40;Single&#41;*4&#41;;
Dest.WriteString&#40;_NodeList&#91;I&#93;.Name&#41;;
End;
End;

Var
I&#58;Integer;
Begin
SetLength&#40;_NodeList,Succ&#40;_NodeCount&#41;&#41;;
_NodeList&#91;_NodeCount&#93;.Position&#58;=Position;
_NodeList&#91;_NodeCount&#93;.Name&#58;='NODE'+LStr&#40;Succ&#40;_NodeCount&#41;&#41;;
For I&#58;=0 To 3 Do
Begin
_NodeList&#91;_NodeCount&#93;.NextNode&#91;I&#93;&#58;=-1;
_NodeList&#91;_NodeCount&#93;.Distance&#91;I&#93;&#58;=0;
End;
Inc&#40;_NodeCount&#41;;

End;

Procedure LPathfinder.RemoveNode&#40;Id&#58;Integer&#41;;
Var
I,J&#58;Integer;
Begin
For I&#58;=0 To Pred&#40;_NodeCount&#41; Do
For J&#58;=0 To 3 Do
If _NodeList&#91;I&#93;.NextNode&#91;J&#93;=Id Then
_NodeList&#91;I&#93;.NextNode&#91;J&#93;&#58;=-1;

If Id=Pred&#40;_NodeCount&#41; Then
Dec&#40;_NodeCount&#41;
Else
Begin
_NodeList&#91;Id&#93;&#58;=_NodeList&#91;Pred&#40;_NodeCount&#41;&#93;;
For I&#58;=0 To Pred&#40;_NodeCount&#41; Do
For J&#58;=0 To 3 Do
If _NodeList&#91;I&#93;.NextNode&#91;J&#93;=Pred&#40;_NodeCount&#41; Then
_NodeList&#91;I&#93;.NextNode&#91;J&#93;&#58;=Id;
Dec&#40;_NodeCount&#41;;
End;

End;

Function LPathfinder.GetNode&#40;Name&#58;String&#41;&#58;Integer;
Var
I&#58;Integer;
Begin
Name&#58;=UpStr&#40;Name&#41;;
Result&#58;=-1;
For I&#58;=0 To Pred&#40;_NodeCount&#41; Do
If _NodeList&#91;I&#93;.Name=Name Then
Begin
Result&#58;=I;
Break;
End;

End;

Function LPathfinder.GetNodeDistance&#40;Node&#58;Integer;Pos&#58;LVector&#41;&#58;Single;
Begin
Result&#58;=VectorLength&#40;VectorSubtract&#40;_NodeList&#91;Node&#93;.Position,Pos&#41;&#41;;
End;

Function LPathfinder.GetNearNode&#40;Pos&#58;LVector&#41;&#58;Integer;
Var
I&#58;Integer;
D,M&#58;Single;
Begin
Result&#58;=-1;
D&#58;=99999;
For I&#58;=0 To Pred&#40;_NodeCount&#41;Do
Begin
M&#58;=Sqrt&#40;Sqr&#40;Pos.X-_NodeList&#91;I&#93;.Position.x&#41;+
Sqr&#40;Pos.Y-_NodeList&#91;I&#93;.Position.Y&#41;+
Sqr&#40;Pos.Z-_NodeList&#91;I&#93;.Position.Z&#41;&#41;;
If M<D Then
Begin
D&#58;=M;
Result&#58;=I;
End;
End;

End;

Function LPathfinder.GetPath&#40;StartNode,EndNode&#58;Word;Var Path&#58;LPath&#41;&#58;Boolean;
Var
// Any variables required
I,J,K&#58;Word;
CurrentVisitNumber&#58;Word; //Which visit the current node will be
CurrNode&#58;Word; //Which node we are scanning...
LowestNodeFound&#58;Word; //For when we are searching for the lowest temporary value
LowestValFound&#58;Single; //For above variable
StartTime&#58;Cardinal;
Begin
Path.Size&#58;=2;
SetLength&#40;Path.List,2&#41;;
If StartNode=EndNode Then //we're already there...
Begin
Path.List&#91;0&#93;&#58;=StartNode;
Path.List&#91;1&#93;&#58;=EndNode;
Result&#58;=True;
&#123;\$IFDEF PROFILE&#125;Profiler.EndProfile;&#123;\$ENDIF&#125;
Exit;
End;

//Setup all the data we need
For I&#58;=0 To Pred&#40;_NodeCount&#41; Do
Begin
_NodeList&#91;I&#93;.VisitNumber&#58;=-1; //Not visited
_NodeList&#91;I&#93;.CurrentDistance&#58;=-1; //Unknown distance
_NodeList&#91;I&#93;.TmpVar&#58;=99999; //A high number that can easily be beaten
End;

//Set the first variable
_NodeList&#91;StartNode&#93;.VisitNumber&#58;=1;
CurrentVisitNumber&#58;=1; //Initialise
CurrNode&#58;=StartNode;
_NodeList&#91;StartNode&#93;.CurrentDistance&#58;=0;
_NodeList&#91;StartNode&#93;.TmpVar&#58;=0;

LowestNodeFound&#58;=0;
Repeat
//Go to each node that the current one touches
//and make it's temporary variable = source distance + weight of the arc
For J&#58;=0 To 3 Do
If &#40;_NodeList&#91;CurrNode&#93;.NextNode&#91;J&#93;<1>=0&#41;Then //Only if there is a node in this direction
If &#40;_NodeList&#91;_NodeList&#91;CurrNode&#93;.NextNode&#91;J&#93;&#93;.VisitNumber>=0&#41;Then //Only if we visited this node...
If &#40;_NodeList&#91;CurrNode&#93;.CurrentDistance-_NodeList&#91;_NodeList&#91;CurrNode&#93;.NextNode&#91;J&#93;&#93;.CurrentDistance=_NodeList&#91;CurrNode&#93;.Distance&#91;J&#93;&#41; Then //NextNode&#40;0&#41; is part of the route home
Begin
Inc&#40;Path.Size&#41;;
SetLength&#40;Path.List,Path.Size&#41;;
Path.List&#91;Pred&#40;Path.Size&#41;&#93;&#58;=_NodeList&#91;CurrNode&#93;.NextNode&#91;J&#93;;
CurrNode&#58;=_NodeList&#91;CurrNode&#93;.NextNode&#91;J&#93;;
Break;
End;

Until False;

//Reverse the path list
For I&#58;=0 To Pred&#40;Path.Size Div 2&#41; Do
Begin
J&#58;=Path.Size-Succ&#40;I&#41;;
K&#58;=Path.List&#91;I&#93;;
Path.List&#91;I&#93;&#58;=Path.List&#91;J&#93;;
Path.List&#91;J&#93;&#58;=K;
End;

Result&#58;=True;
&#123;\$IFDEF PROFILE&#125;Profiler.EndProfile;&#123;\$ENDIF&#125;
End;

End.```

9. ## Dijkstra's Algorithm(help)

The problem is most likely not in the LEAF path finding, but in your implementation, can you show the code of how you implement it?

10. ## Dijkstra's Algorithm(help)

Check this out if you are into pathfinding, has a lot of code:

http://www.pascalgamedevelopment.com...?t=910&start=0

Page 1 of 2 12 Last

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•