astarlibrary - demo 5.bb

A*寻路算法

	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
						If x = Floor(unit\targetX/tileSize) And y=Floor(unit\targetY/tileSize)
							unit\targetX = gInt1*tileSize+.5*tileSize 
							unit\targetY = gInt2*tileSize+.5*tileSize 
						End If	
						Return succeeded ;1	
					End If
				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 Then Return True
	If island(x,y) <> island(Floor(unit\xLoc/tileSize),Floor(unit\yLoc/tileSize)) Then Return True		
	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
	Return True
End Function	

;This function is used by the FindPath() function to lay out
;'footprints' for other nearby units. A node within 1 node of
;the pathfinding unit that is occupied by another unit is
;treated as unwalkable. This function also lays out the
;current paths of any units within two units of the pathfinding
;unit. These nodes are then penalized within the FindPath() 
;function. This encourages paths that do not overlap those 
;of nearby units.
Function CreateFootPrints(unit.unit)
	tempUnwalkable = onClosedList-2
	penalized = onClosedList-3	
	unitX = Floor(unit\xLoc/tileSize) : unitY = Floor(unit\yLoc/tileSize)
	For a = unitX-2 To unitX+2
	For b = unitY-2 To unitY+2
		If a >= 0 And a < mapWidth And b>=0 And b < mapHeight
			If claimedNode(a,b) <> Null And claimedNode(a,b) <> unit
				otherUnit.unit = claimedNode(a,b)
				
				;Lay out penalized paths for units within 2 nodes of 
				;the pathfinding unit.
				For pathLocation = otherUnit\pathLocation-1 To otherUnit\pathLength
					If pathLocation>= 0	
						x = PeekShort (otherUnit\pathBank,pathLocation*4)	
						y = PeekShort (otherUnit\pathBank,pathLocation*4+2)		
						nearByPath(x,y) = penalized
					End If	
				Next
				
				;Designate nodes occupied by units within 1 node 
				;as temporarily unwalkable.
				If Abs(a-unitX) <= 1 And Abs(b-unitY) <= 1 
					tempUnwalkability(a,b) = tempUnwalkable
				End If	
				
			End If							
		End If
	Next
	Next	
End Function


;This function identifies nodes on the map that are not accessible from other areas
;of the map ("islands"). It assumes that the map does not change during the game.
;If so, this function must be called again. It is not a good idea to do this too often
;during the game, especially if it is a large map, because the function is a little slow.
;The island information is saved to an array called island(x,y).
Function IdentifyIslands()
	Dim island(mapWidth+1,mapHeight+1) 
	For startX = 0 To mapWidth-1
	For startY = 0 To mapHeight-1
		If walkability(startX,startY) = walkable And island(startX,startY) = 0	
			areaID =  areaID + 1		
			onClosedList = onClosedList+5 ;changing the values of onOpenList and onClosed list is faster than redimming whichList() array
			onOpenList = onClosedList-1
			openListItems = 1 : openList(1) = 1 : openX(1) = startX : openY(1) = startY
			Repeat
			parentXval = openX(openList(1)) : parentYVal = openY(openList(1))
			openList(1) = openList(openListItems) ;put last item in slot #1	
			openListItems = openListItems - 1 ;reduce number of open list items by 1
			whichList(parentXval,parentYVal) = onClosedList ;add cell to closed list
			island(parentXval,parentYVal) = areaID ;Assign item to areaID
			For b = parentYVal-1 To parentYVal+1
			For a = parentXval-1 To parentXval+1
				If a <> -1 And b <> -1 And a <> mapWidth And b <> mapHeight
				If whichList(a,b) <> onClosedList And whichList(a,b) <> onOpenList	
				If walkability(a,b) <> unwalkable ;not = walkable because could = occupied
				If (a=parentXVal Or b=parentYVal) ;If an orthogonal square of the right type(s)		
					squaresChecked = squaresChecked + 1
					m = openListItems+1 ;m = new item at end of heap					
					openList(m) = squaresChecked				
					openX(squaresChecked) = a : openY(squaresChecked) = b		
					openListItems = openListItems+1 ;add one to number of items on the open list
					whichList(a,b) = onOpenList
				End If ;If an orthogonal square of the right type(s)		
				End If ;If walkability(a,b) <> unwalkable
				End If ;If not on the open or closed lists
				End If ;If not off the map.
			Next
			Next
			Until openListItems = 0				
		End If	
	Next
	Next	
End Function


;This function chooses separate destinations for each member of
;of a group of selected units. When we choose a destination
;for the group, we don't want them to all try to go that exact
;location. Instead we want them to go to separate locations close 
;to that group target location.
;	If the units are all close enough together, the function merely
;returns that each unit should stay in the same place relative to one
;another. If the units are spread out, the function chooses a relative
;location for the unit.
Function ChooseGroupLocations()

	;Figure out the group center
	For unit.unit = Each unit
		If unit\selected = True
			totalX = totalX + unit\xLoc#
			totalY = totalY + unit\yLoc#	
			numberOfUnitsInGroup = numberOfUnitsInGroup+1
		End If	
	Next
	If numberOfUnitsInGroup = 0 Then Return
	groupCenterX# = totalX/numberOfUnitsInGroup
	groupCenterY# = totalY/numberOfUnitsInGroup	
	
	;Figure out if all of the units in the selected group are close enough to
	;each other to keep them more or less in the same locations relative
	;to one another.
	maxDistance = tileSize*Sqr(numberOfUnitsInGroup)	
	For unit.unit = Each unit
		If unit\selected = True
			unit\xDistanceFromGroupCenter# = unit\xLoc#-groupCenterX#
			unit\yDistanceFromGroupCenter# = unit\yLoc#-groupCenterY#
			If Abs(unit\xDistanceFromGroupCenter#) > maxDistance
				unitOutsideMaxDistance = True
			Else If Abs(unit\yDistanceFromGroupCenter#) > maxDistance
				unitOutsideMaxDistance = True			
			End If
		End If	
	Next
	
	;If they are all close enough together, we don't need to adjust their relative 
	;locations.
	If unitOutsideMaxDistance = False 
		;do nothing

	;If one or more group members is too far away, we need to generate a new
	;set of relative locations for the group members.
	Else If numberOfUnitsInGroup = 2

		For unit.unit = Each unit
			If unit\selected = True
				unit\actualAngleFromGroupCenter = 0			
				unit\assignedAngleFromGroupCenter = 0	
				unit\xDistanceFromGroupCenter# = Sgn(unit\xDistanceFromGroupCenter#)*tileSize/2
				unit\yDistanceFromGroupCenter# = Sgn(unit\yDistanceFromGroupCenter#)*tileSize/2	
			End If	
		Next	
				
	Else ;if 3+ units

		;Figure out the angles between each unit in the group and the group center.
		;Also, save unit type pointers to an array for sorting purposes	
		Dim gGroupUnit.unit(numberOfUnitsInGroup+1)			
		For unit.unit = Each unit
			If unit\selected = True
				x = x+1
				gGroupUnit.unit(x) = unit
				unit\actualAngleFromGroupCenter = GetAngle(groupCenterX#,groupCenterY#,unit\xLoc#,unit\yLoc#)		
			End If	
		Next	
		
		;Sort the units in the group according to their angle, from lowest to highest 
		topItemNotSorted = numberOfUnitsInGroup
		While topItemNotSorted <> 1
	
			;Find the highest value in the list
			highestValueItem = 1
			For sortItem = 1 To topItemNotSorted
				If gGroupUnit(sortItem)\actualAngleFromGroupCenter >= gGroupUnit(highestValueItem)\actualAngleFromGroupCenter 
					highestValueItem = sortItem
				End If
			Next
		
			;Now swap it with the highest item in the list
			temp.unit = gGroupUnit(topItemNotSorted)
			gGroupUnit(topItemNotSorted) = gGroupUnit(highestValueItem)
			gGroupUnit(highestValueItem) = temp
		
			topItemNotSorted = topItemNotSorted - 1			
		Wend
		
		;Now assign angles to each of the units in the group
		gGroupUnit(1)\assignedAngleFromGroupCenter = gGroupUnit(1)\actualAngleFromGroupCenter
		addAngle# = 360/numberOfUnitsInGroup		
		For x = 2 To numberOfUnitsInGroup
			gGroupUnit(x)\assignedAngleFromGroupCenter = gGroupUnit(x-1)\assignedAngleFromGroupCenter + addAngle
 			If gGroupUnit(x)\assignedAngleFromGroupCenter >= 360
				gGroupUnit(x)\assignedAngleFromGroupCenter = gGroupUnit(x)\assignedAngleFromGroupCenter-360
			End If
		Next
	
		;Now assign the xDistanceFromGroupCenter and yDistanceFromGroupCenter
		If numberOfUnitsInGroup <= 6
			radius# = Sqr(numberOfUnitsInGroup)*0.8*tileSize
			For unit.unit = Each unit
				If unit\selected = True
					unit\xDistanceFromGroupCenter# = radius*Cos(unit\assignedAngleFromGroupCenter)+(unit\ID Mod(2))
					unit\yDistanceFromGroupCenter# = -radius*Sin(unit\assignedAngleFromGroupCenter)	+(unit\ID Mod(2))	
				End If	
			Next	
		
		;If there are more than 6 units in the group, create two rings of units.
		Else
			innerRadius# = Sqr(numberOfUnitsInGroup/2)*0.8*tileSize
			outerRadius# = 2.5*Sqr(numberOfUnitsInGroup/2)*0.8*tileSize
			x = 0		
			For unit.unit = Each unit
				If unit\selected = True
					x = x+1
					If x Mod 2 = 0
						unit\xDistanceFromGroupCenter# = innerRadius*Cos(unit\assignedAngleFromGroupCenter)
						unit\yDistanceFromGroupCenter# = -innerRadius*Sin(unit\assignedAngleFromGroupCenter)		
					Else
						unit\xDistanceFromGroupCenter# = outerRadius*Cos(unit\assignedAngleFromGroupCenter)
						unit\yDistanceFromGroupCenter# = -outerRadius*Sin(unit\assignedAngleFromGroupCenter)					
					End If
				End If	
			Next					
		End If
			
	End If  ;If group\numberOfUnitsInGroup = 2

	;Now that the relative locations have been determined, we use this info
	;to generate the units' destination locations.
	For unit.unit = Each unit
		If unit\selected = True
			unit\targetX# = MouseX() + unit\xDistanceFromGroupCenter#
			unit\targetY# = MouseY() + unit\yDistanceFromGroupCenter#
			If unit\targetX < 0 Then unit\targetX = 0			
			If unit\targetX >= 800 Then unit\targetX = 799
			If unit\targetY < 0 Then unit\targetY = 0			
			If unit\targetY >= 600 Then unit\targetY = 599	
		End If	
	Next
		
End Function