I made an an A* pathfinding algorithm for a competition entry awhile ago and I thought some people might find it useful since I haven't seen any other A* systems for DarkBASIC Classic. It would work good with an RTS or RPG game but it definitely needs some modification. I suggest using it in conjunction with the matrix select system by Kevin Picone at the Underware Design website
here. Just replace DestX=5 and DestZ=7 with DestX=MAtrixSelection_Xpos#(1) and DestZ=MAtrixSelection_Zpos#(1).
Edit: Look below for an edited version of the function. The DestX and Z in the new one have been changed to be input values for the function along with 2 new variables, MatrixTilesX and MatrixTilesZ. although the function doesnt require a matrix this specifies the width and height of your search area. I also forgot to note how important your closed list maximum value is because if the character isn't on an "island" you dont want it to appear as though the position you want to move to is inaccessible.
-The input value for the function is the object you are finding a path for
-To change the destination that an object is going for change the values DestX and DestZ in the function
-A value of 1 in the Grid array signifies that the sqaure is not walkable
-You can speed up the function by changing the way the arrays are setup and making them smaller but make sure they arent overloaded with data for the squares or the function will cut out automatically
-The second example in the file shows how to make a character that "learns" if the squares around it are walkable and remembers that
-The function doesn't require a matrix but it makes it easier
If you find any mistakes please tell me so i can edit the script in the download.
Edit2: Here is my sample of the pathfinding function that allows the use of fences along a node's edge. The fence sorrounds the wall in the center of the map. It isn't entirely complete as I have to make modifications to the grid array because it is 4 times larger in this function than in the function without fences and could bring down FPS for a large map.I just haven't found out how...
(It also lists all the variables and arrays and I'll be adding the rem statements and variable list to the download on this post.)
rem ******************************
rem A* Pathfinding Function
rem Fences Along Nodes (WIP)
rem
rem By Luke810
rem ******************************
` Setup
set display mode 1024,768,16
sync on
sync rate 60
hide mouse
autocam off
` Create Matrix
make matrix 1,180,180,9,9
` Create Waypoint Array
dim Waypoints(1,50,1)
dim NmbOfWaypoints(1)
dim Grid(21,21)
` Fill Grid Array
for x=7 to 13
Grid(x,10)=1
Grid(x,11)=1
Grid(x,9)=1
next x
` Create Wall Object
make object cube 2,20
color object 2,rgb(50,50,50)
position object 2,90,10,90
scale object 2,300,100,100
` Create Character Object
make object cube 1,20
color object 1,rgb(20,200,20)
position object 1,90,10,50
` Create Destination Object
make object cube 3,20
color object 3,rgb(200,20,20)
position object 3,90,10,130
` Position Camera
position camera 90,200,90
xrotate camera 90
` Calculate Path
Find_New_Path(1,5,7,10,10,50,120)
` Retrieve Waypoint Data
Waypoints=NmbOfWaypoints(1)
` Create Marker Flags
for x=1 to Waypoints
make object sphere x+3,10
position object x+3,Waypoints(1,x,0),10,Waypoints(1,x,1)
color object x+3,rgb(0,0,0)
next x
` Main Loop
do
set cursor 0,0
print " Waypoint Path:"
for x=1 to Waypoints
print " ",(Waypoints(1,x,0)/20)+1," ",(Waypoints(1,x,1)/20)+1
next x
print " Waypoints to Destination: ",waypoints-1
sync
` End Loop
loop
rem **********************
rem Pathfinding Function
rem **********************
function Find_New_Path(obj,DestX,DestZ,MatrixTilesX,MatrixTilesZ,Pathlength,MaxTiles)
` Create datalist arrays
Dim ClosedList(Pathlength,3)
Dim OpenList(MaxTiles,3)
Dim Fval(MaxTiles)
Dim Gval(MaxTiles)
Dim Hval(MaxTiles)
` Initialize Default F-Value
Fval(0)=100000
` Get Starting Position
StartX=((object position x(obj)/10)+1)
StartZ=((object position z(obj)/10)+1)
` Set Destination Position to Appropriate Center Sqaure...
DestX=DestX*2
DestZ=DestZ*2
` ...and the Grid Demensions
MatrixTilesX=(MatrixTilesX*2)+1
MatrixTilesZ=(MatrixTilesZ*2)+1
` Reset the Counter Values
Counter1=2
Counter2=1
` Set the Current Square to the Starting Square
CurrX=StartX
CurrZ=StartZ
` Reset the Finish Variable to Zero
Finish=0
` Set Second Fval so the Start Sqaure is Chosen as the First Sqaure
Fval(1)=99999
` Add the Starting Square to the Open List
OpenList(1,0)=CurrX
OpenList(1,1)=CurrZ
` Set the Gval for an Ddjacent Square Movement and a Diagonal Square Movement
G1=10
G2=14
` Begin the Loop Determining the Pathway
repeat
` Find Lowest F-Cost Square
for x=0 to Counter1-1
if Fval(x)<Fval(BestTile)
BestTile=x
endif
next z
` Add it to the Closed List
ClosedList(Counter2,0)=OpenList(BestTile,0)
ClosedList(Counter2,1)=OpenList(BestTile,1)
ClosedList(Counter2,2)=OpenList(BestTile,2)
ClosedList(Counter2,3)=OpenList(BestTile,3)
Fval(BestTile)=99999
inc Counter2
` Check for Array Overload(Means You Are On An Island Unless you Have Set This Too Low)
if Counter2>Pathlength then exitfunction
` Set Current Tile
CurrX=ClosedList(Counter2-1,0)
CurrZ=ClosedList(Counter2-1,1)
` Set Current Tile as Parent
ParentX=CurrX
ParentZ=CurrZ
` Add Adjacent Squares to Open List
for x=-2 to 2 step 2
for y=-2 to 2 step 2
` Reset some values
Run=1
Skip=0
Transferable=0
` Calculate the x and y Positions of the Tile
TileX=CurrX+x
TileY=CurrZ+y
` Check if This is the Destination Tile.
` If it sets finish to one so after it
` adds up the last few tiles then the function
` fills in the waypoint array.
if TileX=DestX and TileY=DestZ then Finish=1
` Check if Tile is Within Boundaries
if TileX>0 and TileX<MatrixTilesX and TileY>0 and TileY<MatrixTilesZ
` Check if the Sqaure is Walkable
if Grid(TileX,TileY)=0 and Grid(CurrX+(x/2),CurrZ+(y/2))=0
` Make sure its not Current Sqaure
if TileX<>CurrX or TileY<>CurrZ
` Check if the square is already on the closed list and if it is then Ignore it
for z=0 to Counter2-1
if ClosedList(z,0)=TileX and ClosedList(z,1)=TileY then Run=0
next z
` Set the f,g, and h values for the tile
if Run=1
` Check if it is already on the open list
for z=1 to Counter1
if OpenList(z,0)=TileX and OpenList(z,1)=TileY
Skip=1
Zval=z
endif
next z
` If it isnt on the open list just add it to the open list.
` If it is on the open list then check if the path to that square
` from the current square is faster than the old path to that square.
` If it is then change the h,g, and f values for that tile
if Skip=0
OpenList(Counter1,0)=TileX : OpenList(Counter1,1)=TileY
OpenList(Counter1,2)=ParentX : OpenList(Counter1,3)=ParentZ
ValX=abs(TileX-DestX)/2
ValZ=abs(TileY-DestZ)/2
Hval(Counter1)=(ValX+ValZ)*10
if y=0 or x=0 then Gval(Counter1)=Gval(BestTile)+G2 else Gval(Counter1)=Gval(BestTile)+G1
Fval(Counter1)=Hval(Counter1)+Gval(Counter1)
inc Counter1
else
if y=0 or x=0 then Gval=Gval(BestTile)+G2 else Gval=Gval(BestTile)+G1
if Gval<Gval(Zval)
OpenList(Zval,2)=ParentX : OpenList(Zval,3)=ParentZ
Gval(Zval)=Gval
Fval(Zval)=Gval+Hval(Zval)
endif
endif
endif
endif
endif
endif
next y
next x
rem Reset BestTile
BestTile=0
until Finish=1
` Reset some variables
Max_Waypoints=0
RndVar=1
` Add the first tiles to the array
` to get it started off
Waypoints(obj,0,0)=(DestX*10)-10
Waypoints(obj,0,1)=(DestZ*10)-10
Waypoints(obj,1,0)=ClosedList(Counter2-1,0)
Waypoints(obj,1,1)=ClosedList(Counter2-1,1)
NextX=ClosedList(Counter2-1,2)
NextZ=ClosedList(Counter2-1,3)
` Make sure the path isnt already finshed
if NextX=0 and NextZ=0 then Max_Waypoints=1
` If the path isnt finished than run this
if Max_Waypoints=0
` Add the rest of the path tiles to the array
repeat
inc RndVar
Waypoints(obj,RndVar,0)=NextX
Waypoints(obj,RndVar,1)=NextZ
for x=1 to Counter2-1
if ClosedList(x,0)=NextX and ClosedList(x,1)=NextZ
NextX=ClosedList(x,2)
NextZ=ClosedList(x,3)
endif
next x
until NextX=0 and NextZ=0
endif
` Convert the tile values of the array to
` actual (x,z) position in the world
for x=1 to RndVar
Waypoints(obj,x,0)=(Waypoints(obj,x,0)*10)-10
Waypoints(obj,x,1)=(Waypoints(obj,x,1)*10)-10
next x
` Set the Nmb of Waypoints
` ( For multiple units this
` array should be filled in
` as NmbOfWaypoints(obj) )
NmbOfWaypoints(1)=RndVar
` Undimension the arrays
UnDim ClosedList(PathLength,3)
UnDim OpenList(MaxTiles,3)
UnDim Fval(MaxTiles)
UnDim Gval(MaxTiles)
UnDim Hval(MaxTiles)
endfunction
remstart
VARIABLE DESCRIPTIONS
Find_New_Path(obj,DestX,DestZ,MatrixTilesX,MatrixTilesZ,Pathlength,MaxTiles)
obj= the object you want to find a path for
DestX= the x coordinate of the tile you want to get to
DestZ= the z coordinate of the tile you want to get to
MatrixTilesX= The number of tiles in your grid along the x axis+1
MatrixTilesZ= The number of tiles in your grid along the z axis+1
Pathlength= The maximum length of a path before it cuts out
MaxTiles= The maximum numbers of tile possible in the open sqaure
array. I suggest reading the site on A* pathfinding provided
in the forum to gain a better understanding of Open and Closed
lists.
TileX= Temporary values for adding tiles adjacent to the current tile to
the open list(The X coordingate of the temperary tile).
TileZ= Temporary values for adding tiles adjacent to the current tile to
the open list(The X coordingate of the temperary tile).
Counter1= # of items on Open List
Counter2= # of items on Closed List
RndVar= Temporary variable for keeping track of NmbOfWaypoints(object)
(inc command doesnt work with arrays and is faster than doing +1 fifty times
in most programming languages. I hope in Basic too :] )
Max_Waypoints= Changed too 1 if the number of waypoints in a path is the same as
the number of waypoints used to start off the loop that stores the waypoints to
the waypoint array (2 Waypoints).
BestTile= The best tile to choose as the next tile in the path when building the path.
NextX= Stores the X coordinate of the parent of the current tile when filling in the
waypoint array.
NextZ= Stores the Z coordinate of the parent of the current tile when filling in the
waypoint array.
ARRAY DESCRIPTIONS
OpenList(x,y)= The array with all the data for the tiles on the open list.
OpenList(x,0)= X coordinate of tile
OpenList(x,1)= Z coordinate of tile
OpenList(x,2)= X coordinate of parent tile
OpenList(x,3)= Z coordinate of parent tile
ClosedList(x,y)= The array with all the data for the tiles on the closed list.
ClosedList(x,0)= X coordinate of tile
ClosedList(x,1)= Z coordinate of tile
ClosedList(x,2)= X coordinate of parent tile
ClosedList(x,3)= Z coordinate of parent tile
Gval(x)= Distance from start point to this values respective square
Hval(x)= Heretic for the tile from the repesctive square
Fval(x)= Combination of H and G values
Waypoints(Object,PathLength,z)= The waypoint path for the appropriate object. It
goes in reverse order from destination to object starting at NmbOfWaypoints(object).
Waypoints(x,y,0)= X coordinate of waypoint
Waypoints(x,y,1)= Z coordinate of waypoint
- BE SURE TO CHANGE THE PATH LENGTH TO MATCH THE ONE SPECIFIED IN THE FUNCTION
- (If your object numbers start higher than zero I suggest giving them "ID"
numbers: Ex. 501=1 502=2 etc...)
NmbOfWaypoints(object)= The number of waypoints in that objects current path
- (If your object numbers start higher than zero I suggest giving them "ID"
numbers: Ex. 501=1 502=2 etc...)
remend