1. ## Dijkstra's Algorithm(help)

Originally Posted by Dan
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

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

2. ## Dijkstra's Algorithm(help)

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.

3. ## Dijkstra's Algorithm(help)

ok but i dont know how.
the LEAF path finding is not ok?

4. ## Dijkstra's Algorithm(help)

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.

5. ## Dijkstra's Algorithm(help)

Originally Posted by Dan
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

6. ## Dijkstra's Algorithm(help)

A very simple and stupid but working way would be to do that:
Code:
```procedure AddNode&#40;Vector&#58; TD3DXVector3&#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
NodeID &#58;= path.NodeCount;
NeighbourID &#58;= GetNearNode&#40;LVector&#40;Vector&#41;&#41;;
if NeighbourID = -1 then exit;
end;
...
//you put
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

7. ## Dijkstra's Algorithm(help)

for moment i see light on end of the tunnel

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
NodeID := NodeCount;
NeighbourID := GetNearNode(Position);
if NeighbourID = -1 then exit;

End;

but no no success ops:

8. ## Dijkstra's Algorithm(help)

dan see this plz

[pascal]

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
public
Graph : AIGraph;
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;
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[I].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));
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));
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;

For I := 1 To high(NodePath) do
begin
end;
result:=true;

End;

begin
//'##BD Add a node to the path finding system nodes list. 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;

[/pascal]

what is doing wrong :?

9. ## Dijkstra's Algorithm(help)

What is this? Another path finder? Looks messy...
What exactly does not work when you try to implement the LEAF's path finder?

10. ## Dijkstra's Algorithm(help)

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

Page 2 of 2 First 12

#### Posting Permissions

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