Pathfinding using waypoints help

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