astarlibrary - demo 3 (4 way).bb

A*算法的演示程序

	;If not a wall/obstacle square.
	If walkability(a,b) <> unwalkable 
	
	;If not already on the open list, add it to the open list.			
	If whichList(a,b) <> onOpenList	

		;Create a new open list item in the binary heap.
		newOpenListItemID = newOpenListItemID + 1; each new item has a unique ID #
		m = numberOfOpenListItems+1
		openList(m) = newOpenListItemID	 ;place the new open list item (actually, its ID#) at the bottom of the heap
		openX(newOpenListItemID) = a : openY(newOpenListItemID) = b ;record the x and y coordinates of the new item
			
		;Figure out its G, H and F costs and parent
		Gcost(a,b) = Gcost(parentXval,parentYVal)+10		
		Hcost(openList(m)) = 10*(Abs(a - targetx) + Abs(b - targety)) ; record the H cost of the new square
		Fcost(openList(m)) = Gcost(a,b) + Hcost(openList(m)) ;record the F cost of the new square
		parentX(a,b) = parentXval : parentY(a,b) = parentYVal	;record the parent of the new square	
		
		;Move the new open list item to the proper place in the binary heap.
		;Starting at the bottom, successively compare to parent items,
		;swapping as needed until the item finds its place in the heap
		;or bubbles all the way to the top (if it has the lowest F cost).
		While m <> 1 ;While item hasn't bubbled to the top (m=1)	
			;Check if child's F cost is < parent's F cost. 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
			End If
		Wend 
		numberOfOpenListItems = numberOfOpenListItems+1 ;add one to the number of items in the heap

		;Change whichList to show that the new item is on the open list.
		whichList(a,b) = onOpenList


;8.	If adjacent cell is already on the open list, check to see if this 
	;path to that cell from the starting location is a better one. 
	;If so, change the parent of the cell and its G and F costs.	
	Else; If whichList(a,b) = onOpenList
	
		;Figure out the G cost of this possible new path
		tempGcost = Gcost(parentXval,parentYVal)+10
		
		;If this path is shorter (G cost is lower) then change
		;the parent cell, G cost and F cost. 		
		If tempGcost < Gcost(a,b) Then 	;if G cost is less,
			parentX(a,b) = parentXval 	;change the square's parent
			parentY(a,b) = parentYVal
			Gcost(a,b) = tempGcost 	;change the G cost			

			;Because changing the G cost also changes the F cost, if
			;the item is on the open list we need to change the item's
			;recorded F cost and its position on the open list to make
			;sure that we maintain a properly ordered open list.
			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 not a wall/obstacle cell.	
	End If ;If not already on the closed list	
	End If ;If not off the map.	
	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


;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 (unit\xLoc = unit\xPath And unit\yLoc = unit\yPath) Or unit\pathLocation = 0
		If unit\pathLocation = unit\pathLength 
			unit\pathStatus = notstarted	
		Else 		
			unit\pathLocation = unit\pathLocation + 1
			ReadPath(unit) ;update xPath and yPath
		End If	
	End If	
End Function