Here is the A* code. I think I documented it pretty well when I wrote it and I've been looking it over to refresh my memory. I used arrays for some of the variables only so they would be recognized within the function (global).
remstart
==============================================================
= Title : A* Pathfinding
= Author : No Time To Code
= Date : 6/2/09
= Version: 1.31 (No media required)
==============================================================
Comments Use A* algorithm to find to find path from start point to goal
Based on tutorial "A* Pathfinding for Beginners" by By Patrick Lester (Updated July 18, 2005)
http://www.policyalmanac.org/games/aStarTutorial.htm
Directions: Demo uses 10x10 grid based on DATA statement (0=open space, 1=Wall)
User can enter the starting node X and Z, the goal node X amd Z and whether diagonal movement is allowed
Once scene loads, hit SPACEBAR to start pathfinding
You can move the camera with the arrow keys
It will color nodes as it calculates the best route:
blue = node on closed list
green = node on open list
purple = node is part of best path
Note: There is no error checking to make sure the start and goal nodes the user enters are valid (i.e. between 1 - 10 and not on a wall node)
==============================================================
remend
rem =============================================================
rem = SET UP DISPLAY
rem =============================================================
autocam off
set display mode 800,600,32
sync on
sync rate 60
hide mouse
rem =============================================================
rem = MAIN
rem =============================================================
_main:
gosub _init
do
If search_stage(0) <> 0 then text 300,20,"SPACEBAR TO START SEARCH"
gosub _move_camera
`gosub _position_camera
`Get user input
If search_stage(0) = 0
gosub _get_input
Endif
`Start pathfinding when spacekey is pressed
If Spacekey()=1 and search_stage(0) = 1
search_stage(0) = 2 : `Actively pathfinding. Don't allow another search until this one is complete
node_current(0) = node_start(0) : node_current(1) = node_start(1) : `Define selected node
whichlist(node_current(0),node_current(1)) = 1 + wl : `Add current node to open list
Endif
`If search in progress go to pathfinding function
If search_stage(0) = 2 then Astar(NodesX,NodesZ,allow_diag,wl)
`If goal found go to function to display path
If goalfound(0) = True(0)
search_stage(0) = 3 : `Moving along path
display_path
search_stage(0) = 0 : `Ready for user input
goalfound(0) = False(0)
inc wl, 5 : `Increase values in which_list array so I don't have to zero them out
Endif
sync
loop
end
rem =============================================================
rem = SUBROUTINES - PROCEDURES
rem =============================================================
_init:
randomize timer()
basetime = timer()
movetime = basetime
gosub _create_arrays
gosub _environment_variables
gosub _create_textures
gosub _terrain
gosub _load_map
gosub _create_nodes
gosub _load_objects
gosub _position_camera
return
`---------------------------------------------------------------
_create_textures:
`Create and pull 2 images from bitmap
Create bitmap 1,64,64
Set current bitmap 1
ink RGB(0,0,0),RGB(0,255,255)
Box 0,0,64,64
get image 1,0,0,64,64 : `Get black image for matrix
ink RGB(255,255,255),RGB(0,0,0)
Set current bitmap 0
Delete bitmap 1
Return
`----------------------------------------------------------------
_terrain:
mat=1 : `Matrix number
matx#=(node_space+node_size)*NodesX
matz#=(node_space+node_size)*NodesZ
tilex=15
tilez=15
make matrix mat,matx#,matz#,tilex,tilez
Rem texture matrix
Prepare matrix texture 1,1,1,1
Set camera range 1,2900
return
`----------------------------------------------------------------
_environment_variables:
wl = 0 : `Variable for each loop. Will be increased by 5 each loop so I don;t have to zero out which_list array
`Spacing between nodes and size of nodes
node_space = 20
node_size = 20
search_stage(0) = 0 : `Start with getting user input
camx# = 205 : camy# = 200 : camz# =0 : `set camera position
return
`-------------------------------------------------------------------------
_create_arrays:
`Number of nodes in environment
NodesX = 10
NodesZ = 10
path_max = 100 : `Maximum node to be stored in path
Dim node(NodesX,NodesZ,1) : `10 cells across (X) and 10 cells down (Z), 0 = object number 1 - 100 in this example, 1 = Passible (0) or impassible (1),
Dim whichlist(NodesX,NodesZ) : `Keep track of which list a node is on. 0 = not on any list, 1 = open and 2 = closed
Dim node_start(1) : `0=X value of start node, 1=Z value of start node
Dim node_goal(1) : `0=X value of goal node, 1=Z value of goal node
Dim node_value(NodesX,NodesZ,4) : `0=Parent node X, 1=Parent node Z, 2= F value , 3=G value , 4=H value
Dim node_current(1) : `Current node X and Z
Dim lowF(2) : `Lowest lowest F value as for-next loops are running 0 = X, 1 =Z, 2 = F value of this node
Dim path(path_max,1) : `Stores found path. 0 = X value, 1 = Z value
Dim step_path(0) : `Hold number of step in found path
Dim goalfound(0) : `Value of 1 = True
Dim True(0) : True(0) = 1
Dim False(0) : False(0) = 0
Dim search_stage(0) : `What stage of search process is active 0 = Getting user input, 1 = Ready to search, 2 = Search in progress, 3 = Moving along path
Return
`----------------------------------------------------------------
_load_map:
`Load map data into array
Restore node_data
node = 1
For Z = 1 to NodesZ
For X = 1 to NodesX
Read d
node(X,Z,0) = node : `Assign object number
node(X,Z,1) = d : `Assign passible or unpassible value
inc node
Next X
Next Z
return
`-----------------------------------------------------------------
_create_nodes:
N = 1
For Z = 1 to NodesZ
For X = 1 to NodesX
`Make Objects
Select node(X,Z,1)
Case 0 : `Passable nodes
Make object plain N,10,10
Position Object N,50+X*node_space,1,matz#-Z*node_space
Color object N,rgb(0,0,0) : `Color node black so they start off as hidden
XRotate object N,90
Endcase
Case 1 : `Walls with gray color
Make object box N,node_size,node_size*2,node_size
Position Object N,50+X*node_space,node_size/2,matz#-Z*node_space
Color object N,rgb(128,128,128)
endcase
Endselect
inc N
Next X
Next Z
return
`-------------------------------------------------------------------------
`Create objects
_load_objects:
`Player object
Make object cylinder 500,node_size
Color object 500,Rgb(255,0,0)
`Goal object
Make object sphere 501,node_size
Color object 501,RGB(24,231,225)
return
Rem ****************MOUSE LOOK MODE******************************
_position_camera:
`Allow to move camera
OldCamAngleY# = CameraAngleY#
OldCamAngleX# = CameraAngleX#
CameraAngleY# = WrapValue(CameraAngleY#+MousemoveX()*0.2)
CameraAngleX# = WrapValue(CameraAngleX#+MousemoveY()*0.2)
Yrotate camera CurveAngle(CameraAngleY#,OldCamAngleY#,24)
Xrotate camera CurveAngle(CameraAngleX#,OldCamAngleX#,24)
Return
`----------------------------------------------------------------------
_move_camera:
rem ***************Move camera along X and Z axis
If Upkey()=1 then inc camz#,5
If Downkey()=1 then dec camz#,5
If Rightkey()=1 then inc camx#,5
If Leftkey()=1 then dec camx#,5
Position Camera camx#,camy#,camz#
return
`--------------------------------------------------------------------------
`Get user input for start and goal position
_get_input:
Set Camera View 0,0,1,1
Set cursor 0,10
Input "Enter X node for start ", temp
node_start(0) = temp
Input "Enter Z node for start ", temp
node_start(1) = temp
Input "Enter X node for goal ", temp
node_goal(0) = temp
Input "Enter Z node for goal ", temp
node_goal(1) = temp
Input "Allow diagonal movement (1 = Yes, 0 = No) ",allow_diag
search_stage(0) = 1 : `Ready for pathfinding mode
Set Camera View 0,0,800,600
`Reset all nodes to black
For Z = 1 to NodesZ
For X = 1 to NodesX
If node(X,Z,1) = 0 then color object node(X,Z,0),Rgb(0,0,0)
Next X
Next Z
`Position camera
POsition camera camx#,camy#,camz#
xrotate camera 45
`Position player and goal
Position object 500,object position x(node(node_start(0),node_start(1),0)),2+(object size(500)/2),object position z(node(node_start(0),node_start(1),0))
Position object 501,object position x(node(node_goal(0),node_goal(1),0)),2+(object size(501)/2),object position z(node(node_goal(0),node_goal(1),0))
return
rem =============================================================
rem = FUNCTIONS
rem =============================================================
`A* pathfinding function
function Astar(NodesX,NodesZ,allow_diag,wl)
lowF(2) = 99999 : `Will hold lowest F value after the following loop
`Look for lowest F cost square on open list
For Z = 1 to NodesZ
For X = 1 to NodesX
If whichlist(X,Z) = 1 + wl: `If cell X,Y is on open list
If node_value(X,Z,2) < lowF(2)
lowF(0) = X : lowF(1) = Z : `Make this the cell with the lowest F score
lowF(2) = node_value(X,Z,2)
endif
endif
Next X
Next Z
`Swich node with lowest F score to the closed list
whichlist(lowF(0),lowF(1)) = 2 + wl
`Make this node blue indicating it's closed
color object node(lowF(0),lowF(1),0),RGB(0,255,255)
`Make this node the current node
node_current(0) = lowF(0)
node_current(1) = lowF(1)
`If goal is on the closed list construct path
If lowF(0) = node_goal(0) and lowF(1) = node_goal(1)
path(1,0) = node_goal(0) : path(1,1) = node_goal(1) : `Set first step in path as goal
stp = 1
Repeat
stp = stp + 1
path(stp,0) = node_value(path(stp-1,0),path(stp-1,1),0) : `X value of parent of previous node on path
path(stp,1) = node_value(path(stp-1,0),path(stp-1,1),1) : `Z value of parent of previous node on path
Color object node(path(stp,0),path(stp,1),0),RGB(128,0,255) : `Make this node purple indicatig it's on the best path
Until path(stp,0) = node_start(0) and path(stp,1) = node_start(1) : `Current step on path is start node
goalfound(0) = 1
step_path(0) = stp : `Store number of steps in path
Exitfunction
Endif
`Look for all reachable squares adjacent to starting point
For Z = -1 to 1
For X = -1 to 1
If (allow_diag = False(0) and (X = 0 or Z = 0)) or allow_diag = True(0) :`If alloq_diag = False don't look at diagonal nodes
If node_current(0)+X > 0 and node_current(0)+X <= NodesX and node_current(1)+Z > 0 and node_current(1)+Z <= NodesZ : `Check that node is within bounds
If node(node_current(0)+X,node_current(1)+Z,1) = 0 and whichlist(node_current(0)+X,node_current(1)+Z) <> 2 + wl : `Walkable node and not on closed list
Select whichlist(node_current(0)+X,node_current(1)+Z)
nolist = wl
openlist = wl + 1
Case openlist : `Already on open list
If X = 0 or Z = 0 : `On same X or Z axis meaning directly above/below or left/right
G1 = 10
Else : `Cells is diagonal
G1 = 14
Endif
newG = G1 + node_value(node_current(0),node_current(1),3) : `G value of going through current node
If newG < node_value(node_current(0)+X,node_current(1)+Z,3) : `If this new G value is lower the the current G value of this node
node_value(node_current(0)+X,node_current(1)+Z,0) = node_current(0) : `Make current node the parent of this node X value
node_value(node_current(0)+X,node_current(1)+Z,1) = node_current(1) : `Make current node the parent of this node Z value
node_value(node_current(0)+X,node_current(1)+Z,3) = newG : `Change G value to this new lower value
F = newG + node_value(node_current(0)+X,node_current(1)+Z,4) : ``Recalculate F value
node_value(node_current(0)+X,node_current(1)+Z,2) = F : `Assign new F value
Endif
EndCase
Case Default : `Not on any list
whichlist(node_current(0)+X,node_current(1)+Z) = 1 + wl : `add to open list
color object node(node_current(0)+X,node_current(1)+Z,0),RGB(0,255,0) : `Make this node green indicatig it's on the open list
node_value(node_current(0)+X,node_current(1)+Z,0) = node_current(0) : `Make current node the parent of this node X value
node_value(node_current(0)+X,node_current(1)+Z,1) = node_current(1) : `Make current node the parent of this node Z value
`H score = 10*(abs(currentX-targetX) + abs(currentY-targetY))
H = 10*(abs(node_current(0)+X-node_goal(0)) + abs(node_current(1)+Z-node_goal(1)))
`G = the movement cost to move from the starting point A to a given square on the grid, following the path generated to get there
If X = 0 or Z = 0 : `On same X or Z axis meaning directly above/below or left/right
G = 10
Else : `Cells is diagonal
G = 14
Endif
`G is cost to move from current cell to this cell + G value of current cell
G = G + node_value(node_current(0),node_current(1),3)
`Get F score for this cell and store F,G and H in node_values(X,Y,2-4)
F = G + H
node_value(node_current(0)+X,node_current(1)+Z,2) = F
node_value(node_current(0)+X,node_current(1)+Z,3) = G
node_value(node_current(0)+X,node_current(1)+Z,4) = H
Endcase
Endselect
Endif
Endif
Endif
Next X
Next Z
Endfunction
`Function to display found path
Function display_path
mvdist# = 2 : `Distance object can move each repeat....until loop
For stp = step_path(0) to 1 Step -1
obj = node(path(stp,0),path(stp,1),0) : `Object number of node
`Get current location of mouse
X# = object position x(500) : Z# = object position z(500)
next_nodeX# = object position x(obj) : next_nodeZ# = object position z(obj)
`Move mouse to position of next node in path
repeat
If X# = next_nodeX#
`If already on same X axis, dont change X
Else
If X# < next_nodeX#
X# = X#+mvdist#
Else
X# = X#-mvdist#
Endif
Endif
If Z# = next_nodeZ#
`If already on same Z axis, dont change Z
Else
If Z# < next_nodeZ#
Z# = Z#+mvdist#
Else
Z# = Z#-mvdist#
Endif
Endif
Position object 500,X#,10,Z#
wait 2
until X# = next_nodeX# and Z# = next_nodeZ#
Next stp
Endfunction
rem =============================================================
rem = DATA STATEMENTS
rem =============================================================
node_data:
`Load map array
Data 0,0,0,0,0,0,0,0,0,0
Data 0,0,1,0,0,0,0,0,0,0
Data 0,0,1,0,1,1,0,0,0,0
Data 0,0,1,0,1,0,0,0,0,0
Data 0,0,0,0,1,0,0,0,0,0
Data 0,0,0,0,1,0,0,0,0,0
Data 0,0,1,1,1,0,0,0,0,0
Data 0,0,0,0,0,0,1,0,0,0
Data 0,0,0,0,1,1,1,0,0,0
Data 0,0,0,0,1,0,0,0,0,0