Hi Ross - I use waypoints in my game and have a simple program I run outside of the actual game to pre calculate the pathfinding solution so that in the game the units only need to specify their starting and target positions and they are given the 'next node' to move to on their way to their target.
However the same system could be used in real time. (with some modifications)
Here is a cutdown version of what I use, hopefully it is helpful. The IsInLOS function will need to be changed if you are doing a 3d world, as it is currently for a 2d environment.
;;
;Path Node Pre Calculator Waypoints Etc
;
;Read In Node File
;
;
;Go Through Each Node And Create List Of Visible Nodes From Each Node (connect them)
;
;Go Through Each Node and calc path to each other node storing the id num of the next node to get there
;
;
;
Type nodeobject
Field id
Field x
Field y
End Type
Dim NodeVisArray(255,255)
infile=ReadFile("pathnodes.txt")
While Not(Eof(infile))
node.nodeobject=New nodeobject
node\id=ReadByte(infile)
node\x=ReadShort(infile)
node\y=ReadShort(infile)
Wend
CloseFile infile
Dim NodePathArray(255,255)
Dim NodeSearchedArray(255)
Dim BestNodePath(255)
Dim MapArray(3200,2400) ;This is used for a 2d world to get the Line of Sight ->Change Function IsInLOS for 3d environments.
DoStuff() ;precalculate the pathfinding data
End
Function CalcNodePaths()
For Node.NodeObject=Each NodeObject
For OtherNode.NodeObject=Each NodeObject
Distance=0
For i=0 To 255
NodeSearchedArray(i)=255
BestNodePath(i)=0
Next
LeastDistance=255
If Handle(node)<>Handle(othernode) Then
If NodeVisArray(Node\ID,OtherNode\ID)=1 Then
NodePathArray(Node\ID,OtherNode\ID)=OtherNode\ID
Else
NextNodeToDestination(Node.NodeObject,OtherNode.NodeObject,0)
If LeastDistance<255 Then
NodePathArray(Node\ID,OtherNode\ID)=BestNodePath(1)
EndIf
EndIf
EndIf
Next
Next
End Function
Function WriteNodePathArray(Filename$)
outfile=WriteFile(filename$)
For i=0 To 255
For j=0 To 255
WriteByte outfile,NodePathArray(i,j)
Next
Next
CloseFile outfile
End Function
Global LeastDistance
Function NextNodeToDestination(CurrentNode.NodeObject,FinalNode.NodeObject,NodeCount)
NodeSearchedArray(CurrentNode\ID)=NodeCount
If NodeCount>=255 Then Return 255
If Handle(CurrentNode)=Handle(FinalNode) Then Return NodeCount
For OtherNode.NodeObject=Each NodeObject
If Handle(CurrentNode)<>Handle(OtherNode) Then
If NodeVisArray(OtherNode\ID,CurrentNode\ID)=1 Then
If NodeCount<NodeSearchedArray(OtherNode\ID) Then
NodeDist=NextNodeToDestination(OtherNode.NodeObject,FinalNode.NodeObject,NodeCount+1)
If NodeDist<LeastDistance Then
LeastDistance=NodeDist
BestNodePath(NodeCount)=CurrentNode\ID
EndIf
EndIf
Else
EndIf
EndIf
Next
Return 255
End Function
Function CalcNodesVisibleToNode()
For Node.NodeObject=Each NodeObject
For OtherNode.NodeObject=Each NodeObject
If IsInLos(Node.NodeObject,OtherNode\X,OtherNode\Y)=True Then NodeVisarray(Node\ID,OtherNode\ID)=1 Else NodeVisarray(Node\ID,OtherNode\ID)=0
Next
Next
End Function
Function IsInLOS(Node.NodeObject,X,Y)
If Node.NodeObject<>Null Then
StartX#=X
StartY#=Y
FinalX#=Node\X
FinalY#=Node\Y
Dist#=Sqr((FinalX-StartX)^2+(FinalY-StartY)^2)
If Dist=0 Then Return True
If Dist>0 Then
dx#=(FinalX-StartX)/Dist
dy#=(FinalY-StartY)/Dist
Repeat
StartX=StartX+dx
StartY=StartY+dy
If StartX>=0 And StartY>=0 And StartX<=3199 And StartY<=2399 Then
If MapArray(StartX,StartY)=0 Then HitWall=True
Else
HitWall=True
EndIf
Until HitWall=True Or (Abs(StartX-FinalX)<2.0 And Abs(StartY-FinalY)<2.0)
If HitWall=True Then Return False Else Return True
EndIf
EndIf
End Function
Function DoStuff()
CalcNodesVisibleToNode()
CalcNodePaths()
WriteNodePathArray("PreCalculatedPaths.txt")
End Function