Page 1 of 2 12 LastLast
Results 1 to 10 of 20

Thread: Dijkstra's Algorithm(help)

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

  2. #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. #3

    Dijkstra's Algorithm(help)

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

  4. #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. #5

    Dijkstra's Algorithm(help)

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

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

  8. #8

    Dijkstra's Algorithm(help)

    Quote 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
      VisitNumber&#58;Integer; //What order was this node visited
      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 Load&#40;Source&#58;LStream&#41;;
       Procedure Save&#40;Dest&#58;LStream&#41;;
    
       Procedure AddNode&#40;Position&#58;LVector&#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;
    
    
       Property NodeCount&#58;Word Read _NodeCount;
       Property NodeList&#58;LNodeList Read _NodeList;
    
     End;
    
    Implementation
    Uses LEAF_Math;
    
    // LPathfinder
    
    Procedure LPathfinder.Load&#40;Source&#58; LStream&#41;;
    Var
     I,J&#58;Integer;
     S&#58;String;
    Begin
     If Assigned&#40;Source&#41; Then
     Begin
      Source.Read&#40;_NodeCount,SizeOf&#40;_NodeCount&#41;&#41;;
      SetLength&#40;_NodeList,_NodeCount&#41;;
      For I&#58;=0 To Pred&#40;_NodeCount&#41; Do
      Begin
       Source.Read&#40;_NodeList&#91;I&#93;.Position,SizeOf&#40;_NodeList&#91;I&#93;.Position&#41;&#41;;
       Source.Read&#40;_NodeList&#91;I&#93;.NextNode&#91;0&#93;,SizeOf&#40;Integer&#41;*4&#41;;
       Source.Read&#40;_NodeList&#91;I&#93;.Distance&#91;0&#93;,SizeOf&#40;Single&#41;*4&#41;;
       For J&#58;=0 To 3 Do
        If _NodeList&#91;I&#93;.NextNode&#91;J&#93;>=_NodeCount Then
        Begin
         RaiseError&#40;'AI.Pathfinding.Load&#40;&#41;&#58; Invalid node.'&#41;;
         Exit;
        End;
       Source.ReadString&#40;S&#41;;
       _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;
    
    Procedure LPathfinder.AddNode&#40;Position&#58;LVector&#41;;
    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.
    Never underestimate the power of Delphi.
    <br />There's those who play games,...and then there's who make games...

  9. #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. #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
    This is my game project - Top Down City:
    http://www.pascalgamedevelopment.com...y-Topic-Reboot

    My OpenAL audio wrapper with Intelligent Source Manager to use unlimited:
    http://www.pascalgamedevelopment.com...source+manager

Page 1 of 2 12 LastLast

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
  •