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]