astarlibrary - demo 3 (4 way).bb

A*算法的演示程序

;A* Pathfinder (Version 1.83) by Patrick Lester. Used by permission.
;==================================================================
;Last updated 03/19/04

;This version of the A* pathfinder is modified to only allow 4 directional
;movement, which may be better suited for platform games.

;An article describing A* and this code in particular can be found at:
;http://www.policyalmanac.org/games/aStarTutorial.htm

;If you want to use this AStar Library, you may do so free of charge so 
;long as the author byline (above) is retained. Thank you to CaseyC 
;at the Blitz Forums for suggesting the use of binary heaps for the open 
;list. Email comments and questions to Patrick Lester at 
;[e-mail].

;Setup
;-----
;1. Include "includes/aStarLibrary.bb" at the top of your program.

;2. Create an array called walkability(x,y) that contains information
;	about the walkability of each square/tile on your map, with
;	0 = walkable (the default value) and 1 = unwalkable. The array
;	should range from (0,0) in the upper left hand corner to 
;	(mapWidth-1,mapHeight-1) in the bottom right hand corner.

;3. Adjust the following variables at the top of the .declareVariables
;	subroutine below. All three should be made global.
;	- tileSize = the width and height of your square tiles in pixels
;	- mapWidth = the width of your map in tiles = x value in
;		walkability array.
;	- mapHeight = the height of your map in tiles = y value in
;		walkability array.


;Calling the functions
;---------------------
;There are three main functions

;1.	FindPath(unit.unit,targetX,targetY)
;	- unit.unit = unit that is doing the pathfinding
;	- targetX,targetY = location of the target destination (pixel based coordinates)

;	The FindPath() function returns whether a path could be found (1) or
;	if it's nonexistent (2). If there is a path, it stores it in a bank
;	called unit\pathBank.

;2.   CheckPathStepAdvance(unit.unit)
;	This function updates the current path.

;3.	ReadPath(unit.unit)
; 	This function reads the path data generated by FindPath() and returns
;	the x and y coordinates of the next step on the path. They are stored
;	as xPath and yPath. These coordinates are pixel coordinates 
;	on the screen. See the function for more info.

;==========================================================
;DECLARE VARIABLES
.declareVariables

	;Adjust these variables to match your map dimensions (see "setup" above)
	Global tileSize = 50, mapWidth = 16, mapHeight = 12

	;Create needed arrays
	Dim walkability(mapWidth+1,mapHeight+1) ;array that holds wall/obstacle information	
	Dim openList(mapWidth*mapHeight+2) ;1 dimensional array holding ID# of open list items
	Dim whichList(mapWidth+1,mapHeight+1)  ;2 dimensional array used to record 
		;whether a cell is on the open list or on the closed list.
	Dim openX(mapWidth*mapHeight+2) ;1d array stores the x location of an item on the open list
	Dim openY(mapWidth*mapHeight+2) ;1d array stores the y location of an item on the open list
	Dim parentX(mapWidth+1,mapHeight+1) ;2d array to store parent of each cell (x)
	Dim parentY(mapWidth+1,mapHeight+1) ;2d array to store parent of each cell (y)
	Dim Fcost(mapWidth*mapHeight+2)	;1d array to store F cost of a cell on the open list
	Dim Gcost(mapWidth+1,mapHeight+1) 	;2d array to store G cost for each cell.
	Dim Hcost(mapWidth*mapHeight+2)	;1d array to store H cost of a cell on the open list		
	
	;Declare constants
	Global onClosedList = 10 ;openList variable	
	Const notfinished = 0, notStarted = 0, found = 1, nonexistent = 2; pathStatus constants 
	Const walkable = 0, unwalkable = 1; walkability array constants


;==========================================================
;FIND PATH: This function finds the path and saves it. Non-Blitz users please note,
;the first parameter is a pointer to a user-defined object called a unit, which contains all
;relevant info about the unit in question (its current location, speed, etc.). As an
;object-oriented data structure, types are similar to structs in C.
;	Please note that targetX and targetY are pixel-based coordinates relative to the
;upper left corner of the map, which is 0,0.
Function FindPath(unit.unit,targetX,targetY)

;1.	Convert location data (in pixels) to coordinates in the walkability array.
	startX = Floor(unit\xLoc/tileSize) : startY = Floor(unit\yLoc/tileSize)	
	targetX = Floor(targetX/tileSize) : targetY = Floor(targetY/tileSize)

;2.	Quick Path Checks: Under the some circumstances no path needs to
	;be generated ...

	;If starting location and target are in the same location...
	If startX = targetX And startY = targetY And unit\pathLocation > 0 Then Return found
	If startX = targetX And startY = targetY And unit\pathLocation = 0 Then Return nonexistent

	;If target square is unwalkable, return that it's a nonexistent path.
	If walkability(targetX,targetY) = unwalkable Then Goto noPath

;3.	Reset some variables that need to be cleared
	If onClosedList > 1000000 ;occasionally redim whichList
		Dim whichList(mapWidth,mapHeight) : onClosedList = 10
	End If	
	onClosedList = onClosedList+2 ;changing the values of onOpenList and onClosed list is faster than redimming whichList() array
	onOpenList = onClosedList-1
	unit\pathLength = notstarted ;i.e, = 0
	unit\pathLocation = notstarted ;i.e, = 0
	Gcost(startX,startY) = 0 ;reset starting square's G value to 0

;4.	Add the starting location to the open list of squares to be checked.
	numberOfOpenListItems = 1
	openList(1) = 1 ;assign it as the top (and currently only) item in the open list, which is maintained as a binary heap (explained below)
	openX(1) = startX : openY(1) = startY


;5.	Do the following until a path is found or deemed nonexistent.
	Repeat

	
;6.	If the open list is not empty, take the first cell off of the list.
	;This is the lowest F cost cell on the open list.
	If numberOfOpenListItems <> 0 Then

	;Pop the first item off the open list.
	parentXval = openX(openList(1)) : parentYVal = openY(openList(1)) ;record cell coordinates of the item
	whichList(parentXval,parentYVal) = onClosedList ;add the item to the closed list

	;Open List = Binary Heap: Delete this item from the open list, which
	;is maintained as a binary heap. For more information on binary heaps, see:
	;http://www.policyalmanac.org/games/binaryHeaps.htm
	numberOfOpenListItems = numberOfOpenListItems - 1 ;reduce number of open list items by 1	
	openList(1) = openList(numberOfOpenListItems+1) ;move the last item in the heap up to slot #1
	v = 1	
	Repeat ;Repeat the following until the new item in slot #1 sinks to its proper spot in the heap.
		u = v	
		If 2*u+1 <= numberOfOpenListItems ;if both children exist
		 	;Check if the F cost of the parent is greater than each child.
			;Select the lowest of the two children.	
			If Fcost(openList(u)) >= Fcost(openList(2*u)) Then v = 2*u
			If Fcost(openList(v)) >= Fcost(openList(2*u+1)) Then v = 2*u+1		
		Else
			If 2*u <= numberOfOpenListItems ;if only child #1 exists
			 	;Check if the F cost of the parent is greater than child #1	
				If Fcost(openList(u)) >= Fcost(openList(2*u)) Then v = 2*u
			End If	
		End If
		If u<>v ;if parent's F is > one of its children, swap them
			temp = openList(u)
			openList(u) = openList(v)
			openList(v) = temp				
		Else
			Exit ;otherwise, exit loop
		End If	
	Forever

	
;7.	Check the adjacent squares. (Its "children" -- these path children
	;are similar, conceptually, to the binary heap children mentioned
	;above, but don't confuse them. They are different. Path children
	;are portrayed in Demo 1 with grey pointers pointing toward
	;their parents.) Add these adjacent child squares to the open list
	;for later consideration if appropriate (see various if statements
	;below).
	For direction = 1 To 4
	
	If direction = 1 
		a = parentXVal : b = parentYVal-1
	Else If direction = 2 
		a = parentXVal-1 : b = parentYVal
	Else If direction = 3 
		a = parentXVal+1 : b = parentYVal
	Else If direction = 4 
		a = parentXVal : b = parentYVal+1
	End If		

	;If not off the map (do this first to avoid array out-of-bounds errors)
	If a <> -1 And b <> -1 And a <> mapWidth And b <> mapHeight

	;If not already on the closed list (items on the closed list have
	;already been considered and can now be ignored).			
	If whichList(a,b) <> onClosedList