Code:
Graphics 640, 480, 32, 2
Global font = LoadFont(arial, 10)
SetFont font
;------------Globals----------------;
Const x_cells=20
Const y_cells=16
Const all_cells = x_cells * y_cells
Const PATH_MAX=100
Dim grid(all_cells)
Type open
Field grid_pos
Field parent
Field score
End Type
Type closed
Field grid_pos
Field parent
Field score
End Type
Dim path(PATH_MAX)
;------------Init Grid--------------;
For i = 0 To all_cells-1
Read grid(i)
Next
DrawGrid()
PathFind(141, 147)
DrawPath()
WaitKey
;-----------------------------------------------------------------------------------------------;
;***************************** PATH FINDING FUNCTIONS ******************************************;
;-----------------------------------------------------------------------------------------------;
Function PathFind(orig, dest)
;CREATE START POINT
this.open = New open
this\grid_pos = orig
this\parent=-1
this\score=0
Repeat
;FIND LOWEST SCORE
lowest.open = First open
For this.open = Each open
If this\score < lowest\score Then lowest = this
Next
;IF TARGET REACHED
If lowest\grid_pos = dest
GetPath(lowest.open)
Return True
EndIf
;CHECK EACH ADJACENT SQUARE TO TILE
For y=-x_cells To x_cells Step x_cells
For x=-1 To 1
pos = lowest\grid_pos+x+y
If(PathIsValid(lowest.open, x, y, pos)=True)
;GET MOVE COST TO ADJACENT TILE
If(y <> 0 And x <> 0)
move_cost = grid(pos)+(grid(pos)/2)
Else
move_cost = grid(pos)
EndIf
;GUESS MOVE COST FROM TILE TO TARGET
;need a better method
dx=Abs((dest Mod x_cells)-(pos Mod x_cells))
dy=Abs((dest / x_cells)-(pos / x_cells))
distance = (dx+dy)*10
goodness = distance + move_cost
;CHECK IF DESTINATION IS ON OPEN LIST
check=0
For test.open = Each open
If test <> lowest
If test\grid_pos = pos
If test\score < goodness
check =1
Exit
Else
Delete test.open
EndIf
EndIf
EndIf
Next
If check = 0
;ADD MOVE TO OPEN LIST
create.open = New open
create\parent = lowest\grid_pos
create\grid_pos = pos
create\score = goodness
EndIf
;DEBUG TEXT - DEMO STUFF-------------------------------------------------,
Color 200, 0, 0 ;
Text(((pos Mod x_cells)*32)+22, ((pos / x_cells)*32)+2, move_cost) ;
Color 0, 200, 0 ;
Text(((pos Mod x_cells)*32)+18, ((pos / x_cells)*32)+23, distance) ;
Color 0, 0, 200 ;
Text(((pos Mod x_cells)*32)+2, ((pos / x_cells)*32)+23, create\score) ;
Delay(50) ;
;------------------------------------------------------------------------'
EndIf
Next
Next
;MOVE CURRENT TILE FROM OPEN LIST TO CLOSED LIST
cl.closed = New closed
cl\grid_pos = lowest\grid_pos
cl\parent = lowest\parent
cl\parent = lowest\parent
cl\score = lowest\score
Delete lowest.open
Forever
End Function
;-----------------------------------------------------;
Function GetPath(lowest.open)
waypoint = lowest\parent
count = 0
While waypoint <> -1
For c.closed = Each closed
If c\grid_pos = waypoint Then Exit
Next
path(count)=c\grid_pos
waypoint=c\parent
count=count+1
Wend
End Function
;-----------------------------------------------------;
Function PathIsValid(this.open, x, y, pos)
If x=0 And y=0 Then Return False
If pos < 0 Or pos >= all_cells Then Return False
If this\grid_pos Mod x_cells = 0 And pos Mod x_cells = x_cells-1 Then Return False
If this\grid_pos Mod x_cells = x_cells-1 And pos Mod x_cells = 0 Then Return False
If(PathIsBlocked(pos)=True) Then Return False
For cl.closed = Each closed
If cl\grid_pos = pos Return False
Next
Return True
End Function
;--------OBSTRUCTING TILE REFERENCES GO IN HERE-------;
Function PathIsBlocked(pos)
If grid(pos) = -1 Return True
Return False
End Function
;-----------------------------------------------------------------------------------------------;
;***************************** DEMO FUNCTIONS **************************************************;
;-----------------------------------------------------------------------------------------------;
Function DrawGrid()
For x=0 To 640 Step 32
For y=0 To 480 Step 32
Color 255, 255, 255
Line x, 0, x, 480
Line 0, y, 640, y
tile=grid(((y/32)*x_cells)+(x/32))
If tile = -1
Color 80, 80, 80
Rect x, y, 32, 32, 1
Else If tile = -2
Color 120, 30, 30
Rect x, y, 32, 32, 1
Else If tile = -3
Color 30, 120, 30
Rect x, y, 32, 32, 1
Else
Text x+3, y+2, tile
EndIf
Next
Next
End Function
Function DrawPath()
While path(i) <> 0
Color 200,200, 50
Oval (path(i) Mod x_cells)*32+12, (path(i) / x_cells)*32+12, 8, 8, 1
Color 20,20, 100
Text (path(i) Mod x_cells)*32+14, (path(i) / x_cells)*32+11, i
i=i+1
Wend
End Function
;-----------------------------------------------------------------------------------------------;
;***********************************************************************************************;
;-----------------------------------------------------------------------------------------------;
Data 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, -1, -1, -1, -1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, -1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, -1, 10, -1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, -2, 10, -1, -1, -1, 10, -3, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, -1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, -1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, -1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, -1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, -1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, -1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, -1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
The second problem I have is with the heuristics. At the moment I am using a very simple method to guess the move cost to the destination. Basically just the x distance+ y distance. I have been working off the A* tutorials