astarlibrary - demo 4b (time based).bb

A*寻路算法

	End If ;If not already on the closed list	
	End If ;If not off the map.	
	Next
	Next

;9.	If open list is empty then there is no path.	
	Else
		path = nonExistent : Exit
	End If

	;If target is added to open list then path has been found.
	If whichList(targetx,targety) = onOpenList Then path = found : Exit		

	Forever ;repeat until path is found or deemed nonexistent
	
	
;10.	Save the path if it exists. Copy it to a bank. 
	If path = found
		
		;a. Working backwards from the target to the starting location by checking
		;each cell's parent, figure out the length of the path.
		pathX = targetX : pathY = targetY	
		Repeat
			tempx = parentX(pathX,pathY)		
			pathY = parentY(pathX,pathY)
			pathX = tempx
			unit\pathLength = unit\pathLength + 1	
		Until pathX = startX And pathY = startY
	
		;b. Resize the data bank to the right size (leave room to store step 0,
		;which requires storing one more step than the length)
		ResizeBank unit\pathBank,(unit\pathLength+1)*4

		;c. Now copy the path information over to the databank. Since we are
		;working backwards from the target to the start location, we copy
		;the information to the data bank in reverse order. The result is
		;a properly ordered set of path data, from the first step to the
		;last.	
		pathX = targetX : pathY = targetY				
		cellPosition = unit\pathLength*4 ;start at the end	
		While Not (pathX = startX And pathY = startY)			
			PokeShort unit\pathBank,cellPosition,pathX ;store x value	
			PokeShort unit\pathBank,cellPosition+2,pathY ;store y value	
			cellPosition = cellPosition - 4 ;work backwards		
			tempx = parentX(pathX,pathY)		
			pathY = parentY(pathX,pathY)
			pathX = tempx
		Wend	
		PokeShort unit\pathBank,0,startX ;store starting x value	
		PokeShort unit\pathBank,2,startY ;store starting y value

	End If ;If path = found Then 

;11. Return info on whether a path has been found.
	Return path; Returns 1 if a path has been found, 2 if no path exists. 

;12.If there is no path to the selected target, set the pathfinder's
	;xPath and yPath equal to its current location and return that the
	;path is nonexistent.
	.noPath
	unit\xPath = startingX
	unit\yPath = startingY
	Return nonexistent

End Function
	

;==========================================================
;READ PATH DATA: These functions read the path data and convert
;it to screen pixel coordinates.
Function ReadPath(unit.unit)			
	unit\xPath = ReadPathX(unit.unit,unit\pathLocation)
	unit\yPath = ReadPathY(unit.unit,unit\pathLocation)
End Function

Function ReadPathX#(unit.unit,pathLocation)
	If pathLocation <= unit\pathLength
		x = PeekShort (unit\pathBank,pathLocation*4)
		Return tileSize*x + .5*tileSize ;align w/center of square	
	End If
End Function	

Function ReadPathY#(unit.unit,pathLocation)
	If pathLocation <= unit\pathLength
		y = PeekShort (unit\pathBank,pathLocation*4+2)
		Return tileSize*y + .5*tileSize ;align w/center of square		
	End If
End Function


;==========================================================
;COLLISION/NODE CLAIMING FUNCTIONS: These functions handle node claiming
;and collision detection (which occurs when a unit tries to claim a node that
;another unit has already claimed).

;This function checks whether the unit is close enough to the next
;path node to advance to the next one or, if it is the last path step,
;to stop.
Function CheckPathStepAdvance(unit.unit)	
	
	;If starting a new path ...
	If unit\pathLocation = 0			
		If unit\pathLength > 0 
			unit\pathLocation = unit\pathLocation+1
			ClaimNodes(unit.unit)
			ReadPath(unit) ;update xPath and yPath
		Else If unit\pathLength = 0			
			ReadPath(unit) ;update xPath and yPath
			If unit\xLoc = unit\xPath And unit\yLoc = unit\yPath
				unit\pathStatus = notstarted
				ClearNodes(unit.unit)							
			End If
		End If		
	
	;If reaching the next path node.		
	Else If unit\xLoc = unit\xPath And unit\yLoc = unit\yPath
		If unit\pathLocation = unit\pathLength 
			unit\pathStatus = notstarted
			ClearNodes(unit.unit)	
		Else
			unit\pathLocation = unit\pathLocation + 1
			ClaimNodes(unit.unit)
			ReadPath(unit) ;update xPath and yPath		
		End If	
	End If
			
End Function

;This function claims nodes for a unit. It is called by CheckPathStepAdvance().
Function ClaimNodes(unit.unit)
		
	;Clear previously claimed nodes and claim the node the unit is currently occupying.
	ClearNodes(unit.unit)
	
	;Check next path node for a collision.
	unit\unitCollidingWith.unit = DetectCollision(unit.unit)	
	
	;If no collision is detected, claim the node and figure out
	;the distance to the node.
	If unit\unitCollidingWith = Null		
		x2 = PeekShort (unit\pathBank,unit\pathLocation*4)
		y2 = PeekShort (unit\pathBank,unit\pathLocation*4+2)	
		claimedNode(x2,y2) = unit	
		ReadPath(unit.unit) ;update xPath/yPath			
		unit\distanceToNextNode = GetDistance#(unit\xLoc,unit\yLoc,unit\xPath,unit\yPath)	
	
	;Otherwise, if a collision has been detected ...
	Else		
		
		;If node is occupied by a unit not moving normally, repath.
		If unit\unitCollidingWith\pathStatus <> found			
			unit\pathStatus = FindPath(unit.unit,unit\targetX,unit\targetY)					

		;If there is a pending collision between the two units, repath.
		Else If UnitOnOtherUnitPath(unit.unit,unit\unitCollidingWith)
			unit\pathStatus = FindPath(unit.unit,unit\targetX,unit\targetY)	

		;Otherwise, just temporarily stop and wait for the other unit to pass by.	
		Else 				
			unit\pathStatus = tempStopped 									
		End If
				
	End If
		
End Function

;This function clears a unit's claimed nodes. This function is
;called principally by ClaimNodes() before new nodes are
;claimed. It is also called by CheckPathStepAdvance() when the 
;final path node is reached and by LaunchProgram() to initialize
;each unit's initial location.
Function ClearNodes(unit.unit)
	x = Floor(unit\xLoc/tileSize) : y = Floor(unit\yLoc/tileSize)
	For a = x-1 To x+1
	For b = y-1 To y+1
		If a>=0 And a<mapWidth And b>=0 And b<mapHeight
			If claimedNode(a,b) = unit Then claimedNode(a,b) = Null
		End If		
	Next
	Next
	claimedNode(x,y) = unit ;reclaim the one the unit is currently occupying.						
End Function

;This function checks to see if the next path step is free. 
;It is called from ClaimNodes() and by UpdatePath() when the
;unit is tempStopped.
Function DetectCollision.unit(unit.unit)
	x2 = PeekShort (unit\pathBank,unit\pathLocation*4)
	y2 = PeekShort (unit\pathBank,unit\pathLocation*4+2)			
	If claimedNode(x2,y2) = Null	
		x1 = Floor(unit\xLoc/tileSize)
		y1 = Floor(unit\yLoc/tileSize)	
		If x1<>x2 And y1<>y2 ;if next path step is diagonal
			If claimedNode(x1,y2) <> Null			
				If claimedNode(x1,y2) = claimedNode(x2,y1)	
					Return claimedNode(x1,y2)
				End If	
			End If								
		End If
	Else
		Return claimedNode(x2,y2)	
	End If	
End Function

;This function checks to see whether a unit is on another unit's 
;path. It is called by ClaimNodes().
Function UnitOnOtherUnitPath(unit.unit,otherUnit.unit)	
	unitX = Floor(unit\xLoc/tileSize)
	unitY = Floor(unit\yLoc/tileSize)		
	For pathLocation = otherUnit\pathLocation To otherUnit\pathLength		
		If unitX = PeekShort (otherUnit\pathBank,pathLocation*4)
			If unitY = PeekShort (otherUnit\pathBank,pathLocation*4+2)		
				Return True
			End If
		End If
		If pathLocation > otherUnit\pathLocation+1 Then Return
	Next
End Function 

;This function is used by the FindPath() function to 
;check whether the given target location is walkable.
;If not, it finds a new, nearby target location that is
;walkable. The new coordinates are written to the
;gInt1 and gInt2 global variables.
Function CheckRedirect(unit.unit, x,y)
	If NodeOccupied(unit.unit,x,y) = True
		For radius = 1 To 10
			For option = 1 To 4
				If option = 1 
					gInt1 = x : gInt2 = y-radius
				Else If option = 2 
					gInt1 = x : gInt2 = y+radius
				Else If option = 3 
					gInt1 = x-radius : gInt2 = y
				Else If option = 4 
					gInt1 = x+radius : gInt2 = y	
				End If			
				If gInt1 >= 0 And gInt1 < mapWidth And gInt2 >= 0 And gInt2 < mapHeight
					If NodeOccupied(unit.unit,gInt1,gInt2) = False Then Return succeeded ;1	
				End If
			Next
		Next
		Return failed ;unable to find redirect (returns -1).	
	End If
End Function

;This function is used by the CheckRedirect() function to 
;determine whether a given node is walkable for a given unit.
Function NodeOccupied(unit.unit,x,y)
	If walkability(x,y) <> unwalkable
		If claimedNode(x,y) = Null Or claimedNode(x,y) = unit ;node is free
			Return False
		Else ;there is another unit there
			If claimedNode(x,y)\pathStatus = found ;but if it is moving ...
				If claimedNode(x,y)<>unit\unitCollidingWith ;and unit is not colliding with it
				 	Return False
				End If
			End If	
		End If
	End If
	Return True
End Function


;This function is used by the FindPath() function to lay out
;'footprints' for other units within 1 node. FindPath() treats
;these nodes as unwalkable. 
Function CreateFootPrints(unit.unit)
	tempUnwalkable = onClosedList - 2
	unitX = Floor(unit\xLoc/tileSize) : unitY = Floor(unit\yLoc/tileSize)
	For a = unitX-1 To unitX+1
	For b = unitY-1 To unitY+1
		If a >= 0 And a < mapWidth And b>=0 And b < mapHeight
			If claimedNode(a,b) <> Null And claimedNode(a,b) <> unit
				tempUnwalkability(a,b) = tempUnwalkable
			End If			
		End If
	Next
	Next	
End Function