Thread: 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.

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]