A Star movement test problem

BlitzMax Forums/BlitzMax Programming/A Star movement test problem

BugZilla
 #1
I am working on a turn based game using A Star to move on a grid. I got the A Star to work using a pathfinding library found here. It usually works great except when the path leads straight up, then the object stops at the first path node.

The source code is long here, but I was wondering if anyone could figure out the strange behavior:
Strict
Import "pathfinder.bmx"

Graphics 1280,1024

Global ship:TImage=LoadImage("ship1.png")
Global grass:TImage=LoadImage("grass.png")
Global rock:TImage=LoadImage("rock.png")
Global pathball:TImage=LoadImage("pathball.png")
Global rectangle:TImage=LoadImage("rectangle.png")
' ----------------------------  SET UP A STAR
Global Grid:Float[20, 20]
' THE TYPE TO HOLD THE PATHPOINTS
Global pathpoints:TList=CreateList()
Global path:Int[]
Global pathcount:Int=0  ' DENOTES WHERE WE CURRENTLY ARE ON THE PATH
Const TS = 80
Global fx, fy
Global my, mx
Local startx = 3, starty = 3,endx=1,endy=1
Local i
Global moveonpath=False
Global finishedmove=False
Global angle:Float=0
Global speed=0
Global dx:Float,dy:Float,shipx:Float,shipy:Float
'add obstacles to grid map
Grid[3,1]=1
grid[5,5]=1 
grid[5,4]=1
Grid[5,3]=1
Grid[10,10]=1
Grid[8,8]=1
Grid[8,10]=1
Grid[8,9]=1

TPathfinder.SetUp(Grid, 1, .03)
' --------------------------------------------------   MAIN PROGRAM LOOP
While Not KeyHit(key_escape)
	mx = MouseX() /TS
	my = MouseY() /TS
	mx=Max(mx,0); mx=Min(mx,19)
	my=Max(my,0); my=Min(my,19)
'----------------------------------------- LEFT MOUSE= START COORDINATES	
If MouseDown(1) Then
'reset path stuff
moveonpath=False
pathcount=0
ClearList(pathpoints)
'
If(Grid[mx,my]=0) Then
	startx=mx
	starty=my
	End If
	shipx=startx*TS
	shipy=starty*TS
End If	
' -----------------------------------------RIGHT MOUSE=END COORDINATES
If MouseDown(2)
pathcount=0
moveonpath=True
endx=mx
endy=my
dx=MouseX()
dy=MouseY()
speed=2
'COPY THE PATH ROUTE SO WE CAN DRAW IT LATER
	If TPathfinder.FindPath(startx, starty, endx,endy) Then
		path=TPathfinder.Route
	End If
'-------------------------- CONVERT THE PATH ARRAY INTO X AND Y COORDINATES
ClearList(pathpoints)
Local c=0
	For i=0 Until path.length Step 2
	Local ppoint:pathpoint
	ppoint=New pathpoint
	ppoint.px=path[i]*TS
	ppoint.py=path[i+1]*TS
	ppoint.count=c
	ListAddLast(pathpoints ,ppoint)
	c=c+1
	Next
	'we need to flip the list
	ReverseList(pathpoints)
'-----------------------------	
End If
'DRAW THE MAP
	For fy = 0 To 19
		For fx = 0 To 19
			If Grid[fx, fy]=0 Then
				DrawImage grass,fx * TS, fy * TS
			End If
			If Grid[fx, fy] >0 Then
				DrawImage rock,fx * TS, fy * TS
			End If
		Next
	Next
	'------------------------------- MOVE AND  DRAW PATH
	If moveonpath=True
	moveShip()
		For Local ppoint:pathpoint=EachIn pathpoints
		DrawImage pathball,ppoint.px,ppoint.py
		DrawRect ppoint.px,ppoint.py,5,5
		DrawText "Count="+ppoint.count,ppoint.px,ppoint.py+20
		Next	
	End If
	' DRAW MOUSEOVER RECTANGLE
	DrawImage rectangle,mx*TS,my*TS
'------------------------------------  DRAW THE SHIP
DrawImage ship,shipx,shipy
DrawRect shipx,shipy,5,5
DrawText pathcount+"/"+CountList(pathpoints),shipx,shipy-30

DrawText "LEFT CLICK TO PLACE START POINT, RIGHT CLICK TO PLACE END POINT",400,60
	Flip
	Cls
Wend
'-------------------------------------------------------------------   END MAIN LOOP
'
'-------------------------------------------   FUNCTIONS
'
'--------------------------------------------- GET DESTINATION FUNCTION
Function getDestination()
'get the pathpoint at the pathcount index
If(ListIsEmpty(pathpoints)=False)
Local p:pathpoint = pathpoint( pathpoints.ValueAtIndex( pathcount ) ) 
dx=p.px
dy=p.py
End If
'IF WE ARE AT THE AT THE NODE, INCREMENT THE PATHCOUNT
	If pointInRect(shipx,shipy,dx,dy,5,5)=1
	pathcount=pathcount+1
	End If
	
'IF WE ARE AT THE END OF THE PATH, RESET EVERYTHING
If pathcount=>CountList(pathpoints)
pathcount=0
ClearList(pathpoints)
moveonpath=False
End If
'====================================================
If pathcount=>CountList(pathpoints) Then pathcount=0
End Function
'-------------------------------------------------------------POINT IN RECT FUNCTION
Function pointInRect(sx,sy,rectx,recty,rectwidth,rectheight)
	Local inRect:Int=0
	If (sx=>rectx-rectwidth And sx=<rectx+rectwidth)
		If(sy=>recty-rectheight And sy=<sy+rectheight)
		inRect=1
		End If
	End If
	Return inRect
End Function
'===================================================     MOVE SHIP FUNCTION
Function moveShip()
getDestination()
angle=ATan2(dy-shipy,dx-shipx)
shipx=shipx+Cos(angle)*speed
shipy=shipy+Sin(angle)*speed
'
End Function
'
'-----------------------------------------------------   TYPES
Type pathpoint
Field px:Float
Field py:Float
Field count:Int
End Type


BugZilla
 #2
OK. Finally fixed the problem. The solution was to test for a collision between rectangles instead of just a point inside a rectangle (between the ship and the destination rectangle).

Here's the code, in case anyone wants to do something similar in the future.

Strict
Import "pathfinder.bmx"

Graphics 1280,1024

Global ship:TImage=LoadImage("ship1.png")
Global grass:TImage=LoadImage("grass.png")
Global rock:TImage=LoadImage("rock.png")
Global pathball:TImage = LoadImage("pathball.png")
Global rectangle:TImage=LoadImage("rectangle.png")
' ---------------------------- SET UP A STAR
Global Grid:Float[20, 20]
' THE TYPE TO HOLD THE PATHPOINTS
Global pathpoints:TList=CreateList()
Global path:Int[]
Global pathcount:Int=0 ' DENOTES WHERE WE CURRENTLY ARE ON THE PATH
Const TS = 80
Global fx, fy
Global my, mx
Local startx = 3, starty = 3,endx=1,endy=1
Local i
Global moveonpath=False
Global finishedmove=False
Global angle:Float=0
Global speed=0
Global dx:Float, dy:Float, shipx:Float, shipy:Float
'add obstacles to grid map
Grid[3,1]=1
grid[5,5]=1
grid[5,4]=1
Grid[5,3]=1
Grid[10,10]=1
Grid[8,8]=1
Grid[8,10]=1
Grid[8,9]=1

TPathfinder.SetUp(Grid, 1, .03)
' -------------------------------------------------- MAIN PROGRAM LOOP
While Not KeyHit(key_escape)
mx = MouseX() /TS
my = MouseY() /TS
mx=Max(mx,0); mx=Min(mx,19)
my=Max(my,0); my=Min(my,19)
'----------------------------------------- LEFT MOUSE= START COORDINATES
If MouseDown(1) Then
'reset path stuff
moveonpath=False
pathcount=0
ClearList(pathpoints)
'
If(Grid[mx,my]=0) Then
startx=mx
starty=my
End If
shipx = startx * TS
shipy = starty * TS
End If
' -----------------------------------------RIGHT MOUSE=END COORDINATES
If MouseDown(2)
endx = mx
endy=my
dx=MouseX()
dy=MouseY()
speed=2
'COPY THE PATH ROUTE SO WE CAN DRAW IT LATER
TPathfinder.SetUp(Grid, 1, .03)
If TPathfinder.FindPath(startx, starty, endx,endy) Then
path=TPathfinder.Route
End If
'--------------------------------------- CONVERT THE PATH ARRAY INTO X AND Y COORDINATES
pathcount = path.length - 1
dx = path[path.length - 1] * TS
dy = path[pathcount] * TS
'-----------------------------
End If
'----------------------------------- PRESS SPACE TO START MOVING
If KeyHit(KEY_SPACE)
moveonpath = True
End If
'DRAW THE MAP
For fy = 0 To 19
For fx = 0 To 19
If Grid[fx, fy]=0 Then
DrawImage grass,fx * TS, fy * TS
End If
If Grid[fx, fy] >0 Then
DrawImage rock,fx * TS, fy * TS
End If
Next
Next
'------------------------------------------------- MOVE AND DRAW PATH
If moveonpath = True Then moveShip()
For i = 0 Until path.length Step 2
DrawImage pathball, path[i] * TS, path[i + 1] * TS
DrawText "PX=" + i + " PY=" +( i + 1), path[i] * TS, path[i + 1] * TS
Next
' DRAW MOUSEOVER RECTANGLE
DrawImage rectangle,mx*TS,my*TS
'------------------------------------ DRAW THE SHIP
DrawImage ship, shipx, shipy
DrawRect shipx, shipy, 5, 5
' DIAGNOSTICS
DrawRect dx, dy, 10, 10
DrawText pathcount + "/" + CountList(pathpoints), shipx, shipy - 30
DrawText "DX=" + dx, 50, 20
DrawText "DY=" + dy, 50, 35
DrawText "ShipX=" + shipx, 50, 45
DrawText "ShipY=" + shipy, 50, 55
DrawText "Pathcount=" + pathcount, 50, 65
DrawText "Path length=" + CountList(pathpoints), 50, 75
DrawText "LEFT CLICK TO PLACE START POINT, RIGHT CLICK TO PLACE END POINT", 400, 60
Flip
Cls
Wend
'------------------------------------------------------------------- END MAIN LOOP
'
'------------------------------------------- FUNCTIONS
'
'------------------------------------------------------------------------------ GET DESTINATION FUNCTION
Function getDestination()
'get the pathpoint at the pathcount index
dx = path[pathcount - 1] * TS
dy = path[pathcount] * TS
'IF WE ARE AT THE AT THE NODE, INCREMENT THE PATHCOUNT
If RectCollision(shipx, shipy, dx, dy, 5, 5)
pathcount = pathcount - 2
End If
'IF WE ARE AT THE END OF THE PATH, RESET EVERYTHING
If pathcount <= 0
pathcount=0
moveonpath = False
End If
'====================================================
End Function
'----------------------------------------------------------------------------POINT IN RECT FUNCTION
Function pointInRect(sx,sy,rectx,recty,rectwidth,rectheight)
Local inRect:Int=0
If (sx=>rectx-rectwidth And sx=<rectx+rectwidth)
If(sy=>recty-rectheight And sy=<sy+rectheight)
inRect=1
End If
End If
Return inRect
End Function
'=================================================== MOVE SHIP FUNCTION
Function moveShip()
angle = ATan2(dy - shipy, dx - shipx)
shipx=shipx+Cos(angle)*speed
shipy=shipy+Sin(angle)*speed
getDestination()
End Function
'
Function Distance(Point1X, Point1Y, Point1Z, Point2X, Point2Y, Point2Z)
'calculate the x/y/z distances
Local dx = Point1X - Point2X
Local dy = Point1Y - Point2Y
Local dZ = Point1Z - Point2Z

'calculate exact distance
'Sqr() always returns an absolute value
Return Sqr( (dx^2) + (dy^2) + (dz^2) )
End Function

Function RectCollision(x1, y1, x2, y2, width, height)
If Abs(x1 - x2) < width:Int And Abs(y1 - y2) < height:Int Return True
Return False
End Function
'----------------------------------------------------- TYPES
Type pathpoint
Field px:Float
Field py:Float
Field count:Int
Field visited = False
End Type