astarlibrary - demo 5.bb

a_star_pathfinder A星路径寻找可以用来学习寻路的方法 可以用到很多地方 比如脱机的AI寻路就可以用到他

			For x = 1 To numberOfOpenListItems ;look for the item in the heap
			If openX(openList(x)) = a And openY(openList(x)) = b Then ;item found
				FCost(openList(x)) = Gcost(a,b) + HCost(openList(x)) ;change the F cost
				
				;See if changing the F score bubbles the item up from it's current location in the heap
				m = x
				While m <> 1 ;While item hasn't bubbled to the top (m=1)	
					;Check if child is < parent. If so, swap them.	
					If Fcost(openList(m)) < Fcost(openList(m/2)) Then
						temp = openList(m/2)
						openList(m/2) = openList(m)
						openList(m) = temp
						m = m/2
					Else
						Exit ;while/wend
					End If
				Wend 
				
				Exit ;for x = loop
			End If ;If openX(openList(x)) = a
			Next ;For x = 1 To numberOfOpenListItems

		End If ;If tempGcost < Gcost(a,b) Then			

	End If ;If not already on the open list				
	End If ;If corner = walkable
	End If ;If not occupied by a stopped unit
	End If ;If not an adjacent, temporarily unwalkable node
	End If ;If not a wall/obstacle cell.	
	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

;10.	Check to see if desired target has been found.
	If mode = normal  ;exit when target is added to open list.
		If whichList(targetX,targetY) = onOpenList Then path = found : Exit	
	Else If mode = randomMove 
		If Gcost(parentXval,parentYVal) > 20 + Rand(20)
			targetX = parentXval : targetY = parentYval 
			path = found : Exit		
		End If		
	End If		

	Forever ;repeat until path is found or deemed nonexistent
	
	
;11.	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

		;Record the path's cost. This is used by ClaimNodes().
		gPathCost = Gcost(targetX,targetY)

	End If ;If path = found Then 

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

;13.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 = stopped		
			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)	

		;If the pending collision is not head-on, repathing is optional. Check
		;to see if repathing produces a short enough path, and if so, use it.
		;Otherwise, tempStop.
		Else If gDiagonalBlockage = False					
			pathLength = unit\pathLength ;save current path stats
			pathLocation = unit\pathLocation ;save current path stats	
			currentPathBank = unit\pathBank ;save current path stats
			currentPathCost = RemainingPathCost(unit)	
			If unit\pathBank = unit\pathBank1 ;switch the pathBank
				unit\pathBank = unit\pathBank2
			Else
				unit\pathBank = unit\pathBank1
			End If
			unit\pathStatus = FindPath(unit.unit,unit\targetX,unit\targetY) ;check the path
			
			;Is resulting path nonexistent or too long? Then reset back to the
			;original path info saved above and tempStop. Otherwise, the path 
			;just generated will be used.
			If unit\pathStatus = nonexistent Or gPathCost > currentPathCost+35
				unit\pathLength = pathLength
				unit\pathLocation = pathLocation 	
				unit\pathBank = currentPathBank 
				unit\pathStatus = tempStopped									
			End If
			
		;If the pending collision is with a unit crossing diagonally right in
		;front of the unit, then tempStop.	This global variable is set by
		;the DetectCollision() function.	
		Else If gDiagonalBlockage = True	
			unit\pathStatus = tempStopped											
		End If
				
	End If
		
End Function

;This function calculates the remaining cost of the current path. This
;is used by the ClaimNodes() function to compare the unit's current
;path to a possible new path to determine which is better.
Function RemainingPathCost(unit.unit)
	lastX = Floor(unit\xLoc/tileSize)
	lastY = Floor(unit\yLoc/tileSize)
	For pathLocation = unit\pathLocation To unit\pathLength
		currentX = PeekShort (unit\pathBank,pathLocation*4)
		currentY = PeekShort (unit\pathBank,pathLocation*4+2)		
		If lastX<>currentX And lastY<>currentY 
			pathCost = pathCost+14 ;cost of going to diagonal squares	
		Else	
			pathCost = pathCost+10 ;cost of going to non-diagonal squares				
		End If
		lastX = currentX : lastY = currentY		
	Next
	Return pathCost
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)
	gDiagonalBlockage = False	
	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)	
					gDiagonalBlockage = True				
					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)