A-Star Pathfinding

This is a discussion on A-Star Pathfinding within the General AI Programming forums, part of the Cprogramming.com and AIHorizon.com's Artificial Intelligence Boards category; I'm writing some code for doing A* pathfinding. I plan on coding this in C, but first I'm going to ...

  1. #1
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218

    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]
    Last edited by mike_g; 08-05-2007 at 11:00 AM.

  2. #2
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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 >_<

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pathfinding question
    By h3ro in forum General AI Programming
    Replies: 13
    Last Post: 05-15-2008, 10:29 AM
  2. star wars vs star trek
    By psychopath in forum A Brief History of Cprogramming.com
    Replies: 28
    Last Post: 06-14-2005, 10:28 PM
  3. AI (Pathfinding)
    By jdinger in forum Game Programming
    Replies: 7
    Last Post: 04-16-2003, 10:20 AM
  4. AI (pathfinding) tutorial
    By dirkduck in forum Game Programming
    Replies: 3
    Last Post: 02-09-2002, 11:04 AM
  5. Star Wars or Star Trek
    By Garfield in forum A Brief History of Cprogramming.com
    Replies: 32
    Last Post: 09-28-2001, 08:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21