-
A-Star Pathfinding
I'm writing some code for doing A* pathfinding. I plan on coding this in C, but first I'm going to have to sort out my linked list functions :/ What I have is coded in Blitz Basic (sorry), but hopefully it shouldnt be too hard to follow. The types are basically like structs and all variables are ints.
I have two problems. The first is with linking back through the steps on the path. Each step has a grid reference of its parent. If you look at the output image below there are a couple of instances where the path moves through squares that were determined as failed attempts. This only seems to occur when all adjacent tiles to the tile being checked are either blocked or already on the open list. The thing is however I look at the code I allways seem to get the impression that it should work. I must be wrong. Anyway If someone can point out what I can do to fix it, that would be very helpful. I'm pretty sure the bug is in the PathFind() function.
http://i92.photobucket.com/albums/l1...tarProblem.png
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 here. They offer a few alternatives, but these just improve the accuracy of determining the distance from one point to another. As you can see in the image above, my prog is not finding the shortest path and getting a more accurate distance measurement wouldent help things. If anyone has any ideas about how I could get the shortest path for this test data, without everything becoming ridiculously complicated it would be nice to know. Thanks.
[edit]Coloured comments[/edit]
-
Okay I figured out what was wrong. This:
Code:
If test\score < goodness
Was meant to be this:
Code:
If test\score > goodness
That took me ages to work out >_<