A Star movement test problem
BlitzMax Forums/BlitzMax Programming/A Star movement test problem
| ||
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 |
| ||
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 |