PDA

View Full Version : Dijkstra's Algorithm(help)



djoker
08-09-2007, 05:17 PM
hi ppl...
I need some help with an 3d pathfind with waypoints using Dijkstra's Algorithm, Any idea? Best Regards

Dan
08-09-2007, 06:49 PM
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.

djoker
08-09-2007, 06:58 PM
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

Dan
08-09-2007, 07:25 PM
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.

djoker
08-09-2007, 07:32 PM
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)

Dan
08-09-2007, 07:37 PM
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?

djoker
08-09-2007, 07:40 PM
outdoor fps game with objects in land

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

im creating the bad guys ai system

djoker
08-09-2007, 07:46 PM
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



Unit LEAF_Pathfinding;

Interface
Uses LEAF_System,LEAF_IO;

Type
LPath=Class
List:Array Of Integer;
Size:Word;
End;

PNode=^LNode; // Pointer to a node
LNode=Record
Name:String; //If Null then Name='NODE'+LStr(I)
Position:LVector;
NextNode:Array[0..3]Of Integer;
Distance:Array[0..3]Of Single;
//DIJKSTRAs ALGORITHM
VisitNumber:Integer; //What order was this node visited
CurrentDistance:Single; //What the current distance was at this point
TmpVar:Single; //Temporary area for storing distance data...
End;

LNodeList=Array Of LNode;

LPathfinder=Class
Protected
_NodeCount:Word;
_NodeList:LNodeList;

Public

Procedure Load(Source:LStream);
Procedure Save(Dest:LStream);

Procedure AddNode(Position:LVector);
Procedure RemoveNode(Id:Integer);
Function GetNode(Name:String):Integer;
Function GetNearNode(Pos:LVector):Integer;
Function GetNodeDistance(Node:Integer;Pos:LVector):Single;
Function GetPath(StartNode,EndNode:Word;Var Path:LPath):Boolean;


Property NodeCount:Word Read _NodeCount;
Property NodeList:LNodeList Read _NodeList;

End;

Implementation
Uses LEAF_Math;

// LPathfinder

Procedure LPathfinder.Load(Source: LStream);
Var
I,J:Integer;
S:String;
Begin
If Assigned(Source) Then
Begin
Source.Read(_NodeCount,SizeOf(_NodeCount));
SetLength(_NodeList,_NodeCount);
For I:=0 To Pred(_NodeCount) Do
Begin
Source.Read(_NodeList[I].Position,SizeOf(_NodeList [I].Position));
Source.Read(_NodeList[I].NextNode[0],SizeOf(Intege r)*4);
Source.Read(_NodeList[I].Distance[0],SizeOf(Single )*4);
For J:=0 To 3 Do
If _NodeList[I].NextNode[J]>=_NodeCount Then
Begin
RaiseError('AI.Pathfinding.Load(): Invalid node.');
Exit;
End;
Source.ReadString(S);
_NodeList[I].Name:=UpStr(S);
End;
End Else
Begin
SetLength(_NodeList,1);
For J:=0 To 3 Do
_NodeList[0].NextNode[J]:=-1;
End;
End;

Procedure LPathfinder.Save(Dest:LStream);
Var
I:Integer;
Begin
Dest.Write(_NodeCount,SizeOf(_NodeCount));
For I:=0 To Pred(_NodeCount) Do
Begin
Dest.Write(_NodeList[I].Position,SizeOf(_NodeList[ I].Position));
Dest.Write(_NodeList[I].NextNode[0],SizeOf(Integer )*4);
Dest.Write(_NodeList[I].Distance[0],SizeOf(Single) *4);
Dest.WriteString(_NodeList[I].Name);
End;
End;

Procedure LPathfinder.AddNode(Position:LVector);
Var
I:Integer;
Begin
SetLength(_NodeList,Succ(_NodeCount));
_NodeList[_NodeCount].Position:=Position;
_NodeList[_NodeCount].Name:='NODE'+LStr(Succ(_Node Count));
For I:=0 To 3 Do
Begin
_NodeList[_NodeCount].NextNode[I]:=-1;
_NodeList[_NodeCount].Distance[I]:=0;
End;
Inc(_NodeCount);

End;

Procedure LPathfinder.RemoveNode(Id:Integer);
Var
I,J:Integer;
Begin
For I:=0 To Pred(_NodeCount) Do
For J:=0 To 3 Do
If _NodeList[I].NextNode[J]=Id Then
_NodeList[I].NextNode[J]:=-1;

If Id=Pred(_NodeCount) Then
Dec(_NodeCount)
Else
Begin
_NodeList[Id]:=_NodeList[Pred(_NodeCount)];
For I:=0 To Pred(_NodeCount) Do
For J:=0 To 3 Do
If _NodeList[I].NextNode[J]=Pred(_NodeCount) Then
_NodeList[I].NextNode[J]:=Id;
Dec(_NodeCount);
End;

End;

Function LPathfinder.GetNode(Name:String):Integer;
Var
I:Integer;
Begin
Name:=UpStr(Name);
Result:=-1;
For I:=0 To Pred(_NodeCount) Do
If _NodeList[I].Name=Name Then
Begin
Result:=I;
Break;
End;

End;

Function LPathfinder.GetNodeDistance(Node:Integer;Pos:LVect or):Single;
Begin
Result:=VectorLength(VectorSubtract(_NodeList[Node ].Position,Pos));
End;

Function LPathfinder.GetNearNode(Pos:LVector):Integer;
Var
I:Integer;
D,M:Single;
Begin
Result:=-1;
D:=99999;
For I:=0 To Pred(_NodeCount)Do
Begin
M:=Sqrt(Sqr(Pos.X-_NodeList[I].Position.x)+
Sqr(Pos.Y-_NodeList[I].Position.Y)+
Sqr(Pos.Z-_NodeList[I].Position.Z));
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;.VisitN umber>=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;.Current Distance=_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;.Ne xtNode&#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.

Dan
08-09-2007, 08:50 PM
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?

JernejL
08-09-2007, 09:21 PM
Check this out if you are into pathfinding, has a lot of code:

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

djoker
08-09-2007, 09:58 PM
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?
i:integer;
aPath:LPath;
begin
path.AddNode(D3DXVector3(0, 0, 0));
path.AddNode(D3DXVector3(10, 0, 0));
path.AddNode(D3DXVector3(20, 0, 0));
path.AddNode(D3DXVector3(30, 0, 0));
// path.AddNode(D3DXVector3(40, 0, 0));
// path.AddNode(D3DXVector3(50, 0, 0));


aPath:=LPath.Create;
found:=path.GetPath(1,3,apath);

Dan
08-09-2007, 10:08 PM
That topic doesn't actually touch the problem of node based path finding...
Although the concept is the same as 2d grid, they differ in implementation.
For node based path finding it's probably easiest to set up the nodes
yourself in the editor and get it to calculate all possible connections
(with ray tracing). After that it's all easy.

djoker
08-09-2007, 10:13 PM
ok but i dont know how.
the LEAF path finding is not ok?

Dan
08-09-2007, 10:14 PM
djoker
LEAF does not create connections between nodes automatically,
so you have to manually fill NextNode and Distance arrays for every
node that you create.

djoker
08-09-2007, 10:31 PM
djoker
LEAF does not create connections between nodes automatically,
so you have to manually fill NextNode and Distance arrays for every
node that you create.
yes yes
i thinking about that but this can be created by code

Dan
08-09-2007, 11:02 PM
A very simple and stupid but working way would be to do that:


procedure AddNode&#40;Vector&#58; TD3DXVector3&#41;;
procedure AddNeighbourNode&#40;CurNode, Neightbour&#58; integer&#41;;
var
i&#58; integer;
begin
for i &#58;= 0 to 3 do
if path.NodeList&#91;CurNode&#93;.NextNode&#91;i&#93; = -1 then
begin
path.NodeList&#91;CurNode&#93;.NextNode&#91;i&#93; &#58;= Neightbour;
path.NodeList&#91;CurNode&#93;.Distance&#91;i&#93; &#58;=
path.GetNodeDistance&#40;
Neightbour,
path.NodeList&#91;CurNode&#93;.Position
&#41;;
break;
end;
end;
var
NodeID&#58; integer;
NeighbourID&#58; integer;
begin
path.AddNode&#40;LVector&#40;Vector&#41;&#41;;
NodeID &#58;= path.NodeCount;
NeighbourID &#58;= GetNearNode&#40;LVector&#40;Vector&#41;&#41;;
if NeighbourID = -1 then exit;
AddNeighbourNode&#40;NodeID, NeighbourID&#41;;
AddNeighbourNode&#40;NeighbourID, NodeID&#41;;
end;
...
//So instead of path.AddNode&#40;D3DXVector3&#40;...&#41;&#41;;
//you put
AddNode&#40;D3DXVector3&#40;...&#41;&#41;;

there might be errors in the code cause I was just typing straight it.
but you can probably see the logic, even though it is probably the worst
implementation possible :D

djoker
09-09-2007, 07:52 AM
for moment i see light on end of the tunnel

Procedure LPathfinder.AddNodeEx(Position:TD3DVector);
procedure AddNeighbourNode(CurNode, Neightbour: integer);
var
i: integer;
begin
for i := 0 to 3 do
if NodeList[CurNode].NextNode[i] = -1 then
begin
NodeList[CurNode].NextNode[i] := Neightbour;
NodeList[CurNode].Distance[i] :=GetNodeDistance(Neightbour,NodeList[CurNode].Position);
break;
end;
end;
var
NodeID: integer;
NeighbourID: integer;
begin
AddNode(Position);
NodeID := NodeCount;
NeighbourID := GetNearNode(Position);
if NeighbourID = -1 then exit;
AddNeighbourNode(NodeID, NeighbourID);
AddNeighbourNode(NeighbourID, NodeID);


End;


but no no success :oops:

dan thanks for your time

djoker
09-09-2007, 01:14 PM
dan see this plz




TAINodes =record
NodePosition : D3DVECTOR;
NodeAround:array of Integer;
NodeAroundNum : Integer;
NodeAroundCnt:integer;
// Flags : Integer;
NodeDistance:array of Single;
End;

AIGraph=record
Node:array of TAINodes;
NumNode : Integer;
End;

TDXPathFind=class
private
ResearchRadius, MaxChangeAltitude:single;
public
Graph : AIGraph;
procedure AddNode(Position : D3DVECTOR);
procedure CreateAIGraph;
Function FindPath(StartPos ,EndPos : D3DVECTOR; var StorePath : TDXPath) : Boolean;
procedure Render;
constructor create;
end;



Function VModulus(V : D3DVECTOR) : Single;
begin
//result:= D3DXVec3Length(V);
with v do Result:= Sqrt(x*x + y*y + z*z);

End;
Function VSubtract(V1: D3DVECTOR; V2 : D3DVECTOR) : D3DVECTOR;
begin
result.x:= v1.x - v2.x;
result.y:= v1.y - v2.y;
result.z:= v1.z - v2.z;



End;

constructor TDXPathFind.create;
begin
// setlength( Node,1);
MaxChangeAltitude := 50;
ResearchRadius := 600;
Graph.NumNode:=0;

end;

procedure TDXPathFind.CreateAIGraph;

// '##BD Links the nodes each others in order to speed up the path finding. Note : You must call this method before using any path finding method.
var
i , Node :integer;
Distance : Single;
Changed:boolean;
begin
For I := 1 To succ(Graph.NumNode) do
begin
setlength(Graph.Node.NodeDistance,0);
setlength(Graph.Node[I].NodeAround,0);
For Node := 1 To succ(Graph.NumNode) do
begin
If Node <> I Then
begin

Distance := VModulus(VSubtract(Graph.Node[I].NodePosition, Graph.Node[Node].NodePosition));
If Distance < ResearchRadius Then
begin
{ If (Collsion(Graph.Node[I].NodePosition, Graph.Node[Node].NodePosition) = False)
And (Graph.Node[I].NodePosition.y - Graph.Node[Node].NodePosition.y < MaxChangeAltitude)
then
begin
}
With Graph.Node[I] do
begin
// Distance:=20;
setlength(NodeAround,length(NodeAround) + 1);
setlength(NodeDistance,length(NodeDistance) + 1);
NodeAroundNum := NodeAroundNum + 1;
NodeAround[high(NodeAround)] := Node;
NodeDistance[high(NodeDistance)] := Distance;
End;// With
end;

// end;
End;
end ;//for Node
end;//for I
//'Let a place to the end and start point
// setlength(Graph.Node,high(Graph.Node) + 3);
setlength(Graph.Node,succ(Graph.NumNode + 2));
End;

Function TDXPathFind.FindPath(StartPos ,EndPos : D3DVECTOR; var StorePath : TDXPath) : Boolean;
// Function TDXPathFind.FindPath(StartPos ,EndPos : D3DVECTOR) : Boolean;
// '##BD Find a path from the start vector to the end vector. Returns True if a path has been found, False else.
// '##PD StartPos Start vector in the 3d world
// '##PD EndPos End vector in the 3d world
// '##PD Path Path in what the found path will be stored.
var
inode,StartNode,
EndNode : Integer;
Score:array of Single;
Distance,BestScore : Single;
node,Index,s,i : Integer;
BestNode,N : Integer;
NodePath:array of integer;
Changed:boolean;
trys:integer;
begin
result:=false;
setlength(Score,succ(Graph.NumNode) + 2);

Graph.Node[Graph.NumNode +1].NodePosition := StartPos;
Graph.Node[Graph.NumNode +2].NodePosition := EndPos;


For I := Graph.NumNode + 1 To Graph.NumNode + 2 do
begin
setlength(graph.Node[i].NodeDistance,0);
setlength(graph.Node[i].NodeAround,0);

For Node := 1 To Graph.NumNode do
begin
If Node <> I Then
begin
Distance := VModulus(VSubtract(Graph.Node[I].NodePosition, Graph.Node[Node].NodePosition));
// showmessage(floattostr(Distance));
If Distance < ResearchRadius Then
begin

{ If (Collsion(Graph.Node[i].NodePosition, Graph.Node[node].NodePosition) = false) then
begin
}
With Graph.Node[I] do
begin


setlength(NodeAround ,succ(high(NodeAround) + 2));
setlength(NodeDistance,succ(high(NodeDistance) + 2));

setlength(Graph.Node[Node].NodeAround ,pred(Graph.Node[Node].NodeAroundNum+1));
setlength(Graph.Node[Node].NodeDistance,pred(Graph.Node[Node].NodeAroundNum+1));


Graph.Node[Node].NodeAround[high(Graph.Node[Node].NodeAround)] := I;
Graph.Node[Node].NodeDistance[high(Graph.Node[Node].NodeDistance)] := Distance;

NodeAround[high(NodeAround)] := Node;
NodeDistance[high(NodeDistance)] := Distance;


End;
End;
// End;
end;
end;
end;



//' Voodoo VB Path finding algorithm.
Score[Graph.NumNode + 2] := 1;


//'Create a node map from the end node

Changed := False;
repeat

For I := 1 To Graph.NumNode + 2 do
begin
With Graph.Node[I] do
begin
If Score[I] <> 0 Then
begin
For N := 1 To high(NodeAround) do
begin
ProcessMessages;
If (Score[I] + NodeDistance[N] < Score[NodeAround[N]])
Or (Score[NodeAround[N]] = 0) Then
begin;
Score[NodeAround[N]] := Score[I] + NodeDistance[N];
Changed := True;
End;
end;
End;
End;

end;

Changed := False;

Until Changed = False;


// //Now search the path
S := Graph.NumNode +1 ;
repeat

BestNode := -1;
BestScore := 10000000;// 'let's take a impossible number

For I := 1 To high(Graph.Node[S].NodeAround) do
begin
Index := Graph.Node[S].NodeAround[I];
If (Score[Index] < BestScore) And (Score[Index] <> 0) Then
begin
BestScore := Score[Index];
BestNode := Index;
End;
end;
ProcessMessages;
If BestNode = -1 Then
begin
showmessage ('No found in searching');
exit;
End;
setlength(NodePath,high(NodePath) + 2);
NodePath[high(NodePath)] := BestNode;
If BestNode = Graph.NumNode + 2 Then break;
S := BestNode;

until false;
//end;


StorePath.AddPathNode(Graph.Node[Graph.NumNode + 1].NodePosition);
For I := 1 To high(NodePath) do
begin
StorePath.AddPathNode(Graph.Node[NodePath[I]].NodePosition);
end;
StorePath.AddPathNode(Graph.Node[Graph.NumNode + 2].NodePosition);
result:=true;

End;


procedure TDXPathFind.AddNode(Position : D3DVECTOR);
begin
//'##BD Add a node to the path finding system nodes list. [i]Note : When all the nodes are added, you have to call the AICreateGraph function.
// '##PD Position Position in the 3d world of the new node.
Graph.NumNode := Graph.NumNode + 1;
setlength(Graph.Node,Graph.NumNode+2);
Graph.Node[Graph.NumNode].NodePosition := Position

End;



what is doing wrong :?

Dan
09-09-2007, 04:02 PM
What is this? Another path finder? Looks messy...
What exactly does not work when you try to implement the LEAF's path finder?

djoker
09-09-2007, 05:00 PM
is from open source truvision3d engine
i convert the code from vb 2 delphi




What exactly does not work when you try to implement the LEAF's path finder?
dont find the path :S