This is for
tier 1!
I neaded some pathfinding for the enemys in my raycaster and found
pedrolbs great code in the codebase.
I simply added a more dynamic twist and movement code.
And making it simplier to be added to your own projects.
The only thing i didt change more then adding first nodes x/y cord is the great search routine.
I made this as an learning experience and that i neaded a good pathfinding for my raycaster.
There is alot of room for improvements to get it faster but its pretty fast already.
If you think i messed it up to much so can you find the original here !
http://www.thegamecreators.com/?m=codebase_view&i=b496ae7bec039ca2806967d3443fd672
Initiate_Pathfinder:
// This is simply the size of the grid map the pathfinder should search
#Constant PathFinder_Width 24
#Constant PathFinder_Height 14
//astar arrays , types and globals ------------------------------
//node type to populate cells
Type AstarNode
H as Integer //distance to end
G as Integer //distance from start
ParentX as Integer //coord x of parent cell
ParentY as Integer //coord y of parent cell
EndType
//matrix of nodes to help calculate path
Dim PathFinder_Node[PathFinder_Width,PathFinder_Height] As AstarNode
//List type to populate cells
Type AstarList
Open as Integer // open list of cells
Closed as Integer //closed list of cells
EndType
//an array for the open/closed list of cells
Dim PathFinder_List[1000,1] As AstarList
//these two vectors define offset of search patterns
//directions are respectively null,N,W,S,E,NE,SE,SW,NW
Dim PathFinder_Vector_X [8] as Integer = [0,0,1,0,-1,1,1,-1,-1]
Dim PathFinder_Vector_Y [8] as Integer = [0,-1,0,1,0,-1,1,1,-1]
// This stores the first nodes x/y coords in the found path
global PathFinder_First_X , PathFinder_First_Y
// A string that stores the found path
Global PathFinder_Path$=""
// This node matrix stores the sprite id on that tile when you place an solid object here.
// The pathfinder treats all numbers higher then 0 as an solid object. ( None walkable )
// Very usefull if you want to be able to fast and easy remove or add objects that are solid.
Dim PathFinder_Solid[PathFinder_Width,PathFinder_Height]
// AGK Pathfinder uses an grid where each tile is in this scale
// Simply so if your game uses tiles in the size 16 change this to 16
#Constant PathFinder_Scale 32
Return
Function PathFinder_Search(sX, sY, eX, eY, Diag, MaxSteps)
// Parameters
// sX - x coord of origin cell
// sY - y coord of origin cell
// eX - x coord of destination cell
// eY - y coord of destination cell
// Diag
// 0 - No diagonals
// 1 - Allow diagonals without cutting corners
// 2 - Allow all diagonals
// MaxSteps - max number of steps you allow the function to run
//
// This function is counting on the existence of 3 globals
// PathFinder_Width - integer - size x of the map
// PathFinder_Height - integer - size y of the map
// PathFinder_Solid[PathFinder_Width,PathFinder_Height] - integers - matrix holding collision info
//This var will define how many directions we will be searching from each parent cell
Dirs=4
//if diagonals are allowed we update the amount of directions to search
If Diag>0 then Dirs=8
//these two vars a and b will help search the open list for the next node
a=0
b=0
//will help to check if there are any more path possibilities
CountOpenCells=0
//these four vars will help find the way back
//from end cell to start cell
CamX=-1
CamY=-1
CamXaux = -1
CamYaux = -1
//this var will hold the path returned by the function
FoundPath$=""
//will help to check if we reached the end of the path search
TerminationFlag = 0
//x coord of point being examined starts being the x of the starting point
Px=sX
//y coord of point being examined starts being the y of the starting point
Py=sY
//step counter
StepCounter=0
//node holding our currently examined parent cell
P as AstarNode
//node holding the cells examined around the parent cell
NewP as AstarNode
//and here we say there is one element in the open list
OpenCounter=1
//here we say there are zero elements in the closed list
ClosedCounter=0
//this tells the function we are currently using element 0 of the open list
OpenCurrent = 0
//dont search if start equals end
If sX=eX and sY=eY then FoundPath$="already at target"
//dont search if end is a wall
If FoundPath$="" and PathFinder_Solid[eX,eY]>0 then FoundPath$="impossible path"
If FoundPath$="" and PathFinder_Solid[sX,sY]>0 then FoundPath$="impossible path"
//if we passed the first checks we are ready for the actual search
If FoundPath$=""
//this will initialize MapCalc to -1 in all four values of each node
P.G=-1
P.H=-1
P.ParentX=-1
P.ParentY=-1
For i = 0 to PathFinder_Width
For j = 0 to PathFinder_Height
PathFinder_Node[i,j] = P
Next j
Next i
//here we define the starting cell as the first
//element of the open list
PathFinder_List[0,0].Open=sX
PathFinder_List[0,1].Open=sY
//these four lines define the node of the starting cell
P.G=0
P.H=10*(Abs(Px-eX)+Abs(Py-eY))
P.ParentX = 666
P.ParentY = 666
//and this one puts the node in the starting coords
PathFinder_Node[sX,sY]=P
//lets start the search
Do
//increment step counter
StepCounter = StepCounter + 1
//iterator for direction offsets
For i = 1 to Dirs
//first we acquire the coords of the cell to be examined
NewPx = Px + PathFinder_Vector_X [i]
NewPy = Py + PathFinder_Vector_Y [i]
//we start assuming its walkable
Walkable = 1
//then we will define it as not walkable if...
//if the coordinates are off the grid
If NewPx<0 or NewPx>PathFinder_Width or NewPy<0 or NewPy>PathFinder_Height then Walkable = 0
If Walkable = 1
//if there is a wall at this new cell
If PathFinder_Solid[NewPx,NewPy]>0 then Walkable = 0
//if this is a diagonal direction but we cant cut corners and we would have to
If NewPy + 1 <= PathFinder_Height and NewPx - 1 >= 0
If Diag = 1 and i=5 and (PathFinder_Solid[NewPx,NewPy+1]>0 Or PathFinder_Solid[NewPx-1,NewPy]>0) then Walkable = 0
EndIf
If NewPy - 1 >= 0 and NewPx - 1 >= 0
If Diag = 1 and i=6 and (PathFinder_Solid[NewPx,NewPy-1]>0 Or PathFinder_Solid[NewPx-1,NewPy]>0) then Walkable = 0
EndIf
If NewPy - 1 >= 0 and NewPx + 1 <= PathFinder_Width
If Diag = 1 and i=7 and (PathFinder_Solid[NewPx,NewPy-1]>0 Or PathFinder_Solid[NewPx+1,NewPy]>0) then Walkable = 0
EndIf
If NewPy + 1 <= PathFinder_Height and NewPx + 1 <= PathFinder_Width
If Diag = 1 and i=8 and (PathFinder_Solid[NewPx,NewPy+1]>0 Or PathFinder_Solid[NewPx+1,NewPy]>0) then Walkable = 0
EndIf
//if the cell is already in the closed list
for j=0 to ClosedCounter -1
if PathFinder_List[j,0].Closed = NewPx and PathFinder_List[j,1].Closed = NewPy then Walkable = 0
next j
EndIf
//if none of the previous checks was positive then the cell is walkable for sure
If Walkable = 1
//so we define the node values that will occupy it
NewP.ParentX = Px
NewP.ParentY = Py
// the following penalizes a diagonal movement
If i <= 4
NewP.G=P.G+10
Else
NewP.G=P.G+14
EndIf
NewP.H=10*(Abs(NewPx-eX)+Abs(NewPy-eY))
//lets check if the cell is already in the open list
OpenExists = -1
for j=0 to OpenCounter -1
if PathFinder_List[j,0].Open = NewPx and PathFinder_List[j,1].Open = NewPy then OpenExists = j
next j
if OpenExists = -1
//if it is not then we give it the values of the new node
//and we put the cell in the open list also incrementing the open list counter
PathFinder_List[OpenCounter,0].Open = NewPx
PathFinder_List[OpenCounter,1].Open = NewPy
OpenCounter = OpenCounter + 1
PathFinder_Node[NewPx,NewPy] = NewP
//if by any chance we spotted the end cell lets raise a termination flag
If NewPx=eX and NewPy=eY then TerminationFlag=1
else
//if the cell is already in the open list we check to
//see if this new way of reaching it is better tahn the one
//previously found
if PathFinder_Node[NewPx,NewPy].G > NewP.G then PathFinder_Node[NewPx,NewPy] = NewP
endif
//finished dealing with this walkable cell
EndIf
//lets go and check the next neighbour of our current cell
Next i
//at this point we checked every possible neighbour of the currently examined cell
//if the termination flag was raised
//we build the path string and exit the function
If TerminationFlag=1
//we start at the end cell
FoundPath$=str(eX)+","+str(eY)
CamX=eX
CamY=eY
//we will repeat the following steps until we reach the starting node
repeat
FoundPath$=FoundPath$+","
CamXaux = CamX
CamYaux = CamY
PathFinder_First_X=CamXaux
PathFinder_First_Y=CamYaux
//we make CamX and CamY point to the parent cell of the current cell
CamX=PathFinder_Node[CamXaux,CamYaux].ParentX
CamY=PathFinder_Node[CamXaux,CamYaux].ParentY
//and we put those coords in the path string
FoundPath$=FoundPath$+str(CamX)+","+str(CamY)
until CamX=sX and CamY=sY
//and we exit the do loop cycle to exit the function
exit
EndIf
//if we went over the step limit we issue an error and leave the function
If StepCounter>=MaxSteps
FoundPath$="step limit exceeded"
Exit
EndIf
//this invalidates the element of the open list we were examining
PathFinder_List[OpenCurrent,0].Open = -1
PathFinder_List[OpenCurrent,1].Open = -1
//this adds that element to the closed list and increments the closed list counter
PathFinder_List[ClosedCounter,0].Closed = Px
PathFinder_List[ClosedCounter,1].Closed = Py
ClosedCounter = ClosedCounter + 1
//here starts the process that will find the best
//possible candidate to become the next current cell to be examined
//initialize the comparison values to high values
MinimoF = 999999
MinimoH = 999999
//initialize the counter of valid elements in the open list
CountOpenCells=0
for i = 0 to OpenCounter - 1
//will only check the element if its valid
If PathFinder_List[i,0].Open > -1
//increments the counter of valid elements
CountOpenCells=CountOpenCells+1
//retrieves the coords of the open list element
a = PathFinder_List[i,0].Open
b = PathFinder_List[i,1].Open
//now we check the values of these coordinates
AuxValue = PathFinder_Node[a,b].G + PathFinder_Node[a,b].H
AuxValue2 = PathFinder_Node[a,b].H
//and we compare them to the best we found so far
If AuxValue <= MinimoF and AuxValue2 < MinimoH
//if they are better we prepare the cell to be examined next
MinimoF = AuxValue
MinimoH = AuxValue2
OpenCurrent = i
Px = a
Py = b
P = PathFinder_Node[a,b]
endif
endif
next i
//if there are no valid elements in the open list we have no path to
//help us reach the end cell
if CountOpenCells = 0
FoundPath$="no path to target"
exit
endif
// now that we have a new cell to examine we go back to
// start checking its neighbours
Loop
EndIf
EndFunction FoundPath$
This is still work in progress.
Iam doing this for fun and often dont have a clue wath iam doing
But strangely enough so does it work.
The sample file is extremely simple and should be easy to understand?
I will make the code cleaner and better later on.
i simply wanted to make an sample that whas easy to use for newcomers to agk.
Sometimes do you have an great idea for an game that neads pathfinding but dont know how to get it in to the game.
This should help?
