Page 2 of 2 FirstFirst 12
Results 11 to 20 of 20

Thread: Dijkstra's Algorithm(help)

  1. #11

    Dijkstra's Algorithm(help)

    Quote 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
    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);
    Never underestimate the power of Delphi.
    <br />There's those who play games,...and then there's who make games...

  2. #12

    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. #13

    Dijkstra's Algorithm(help)

    ok but i dont know how.
    the LEAF path finding is not ok?
    Never underestimate the power of Delphi.
    <br />There's those who play games,...and then there's who make games...

  4. #14

    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. #15

    Dijkstra's Algorithm(help)

    Quote 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
    Never underestimate the power of Delphi.
    <br />There's those who play games,...and then there's who make games...

  6. #16

    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;;
      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

  7. #17

    Dijkstra's Algorithm(help)

    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 ops:

    dan thanks for your time
    Never underestimate the power of Delphi.
    <br />There's those who play games,...and then there's who make games...

  8. #18

    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
    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[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));
    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. 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 :?
    Never underestimate the power of Delphi.
    <br />There's those who play games,...and then there's who make games...

  9. #19

    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. #20

    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
    Never underestimate the power of Delphi.
    <br />There's those who play games,...and then there's who make games...

Page 2 of 2 FirstFirst 12

Bookmarks

Posting Permissions

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