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: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(Integer)*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(_NodeCount));
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:LVector):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:=M;
Result:=I;
End;
End;
End;
Function LPathfinder.GetPath(StartNode,EndNode:Word;Var Path:LPath):Boolean;
Var
// Any variables required
I,J,K:Word;
CurrentVisitNumber:Word; //Which visit the current node will be
CurrNode:Word; //Which node we are scanning...
LowestNodeFound:Word; //For when we are searching for the lowest temporary value
LowestValFound:Single; //For above variable
StartTime:Cardinal;
Begin
Path.Size:=2;
SetLength(Path.List,2);
If StartNode=EndNode Then //we're already there...
Begin
Path.List[0]:=StartNode;
Path.List[1]:=EndNode;
Result:=True;
{$IFDEF PROFILE}Profiler.EndProfile;{$ENDIF}
Exit;
End;
//Setup all the data we need
For I:=0 To Pred(_NodeCount) Do
Begin
_NodeList[I].VisitNumber:=-1; //Not visited
_NodeList[I].CurrentDistance:=-1; //Unknown distance
_NodeList[I].TmpVar:=99999; //A high number that can easily be beaten
End;
//Set the first variable
_NodeList[StartNode].VisitNumber:=1;
CurrentVisitNumber:=1; //Initialise
CurrNode:=StartNode;
_NodeList[StartNode].CurrentDistance:=0;
_NodeList[StartNode].TmpVar:=0;
LowestNodeFound:=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:=0 To 3 Do
If (_NodeList[CurrNode].NextNode[J]<1>=0)Then //Only if there is a node in this direction
If (_NodeList[_NodeList[CurrNode].NextNode[J]].VisitNumber>=0)Then //Only if we visited this node...
If (_NodeList[CurrNode].CurrentDistance-_NodeList[_NodeList[CurrNode].NextNode[J]].CurrentDistance=_NodeList[CurrNode].Distance[J]) Then //NextNode(0) is part of the route home
Begin
Inc(Path.Size);
SetLength(Path.List,Path.Size);
Path.List[Pred(Path.Size)]:=_NodeList[CurrNode].NextNode[J];
CurrNode:=_NodeList[CurrNode].NextNode[J];
Break;
End;
Until False;
//Reverse the path list
For I:=0 To Pred(Path.Size Div 2) Do
Begin
J:=Path.Size-Succ(I);
K:=Path.List[I];
Path.List[I]:=Path.List[J];
Path.List[J]:=K;
End;
Result:=True;
{$IFDEF PROFILE}Profiler.EndProfile;{$ENDIF}
End;
End.
Reply With Quote
Bookmarks