Pathfinding

BlitzMax Forums/BlitzMax Beginners Area/Pathfinding

Sanctus (Posted 2006) [#1]

Well I tryed a search but that didn't help me... In blitz3d there was the A* sistem for pathfinding but now in blitzmax I dont know any so I was wondering if any of you guys know a way how I could do pathfinding in Bmax... A dwl link would be nice

Dreamora (Posted 2006) [#2]

There is one. Check out the german bb boards (http://www.blitzforum.de) in the BlitzMax codearchiv section to find it :-)

Sanctus (Posted 2006) [#3]

Thats in german... I don't understand anything Anyway I was hoping for a pathfinding for dummyes cuz its preety hard for me...(I mearly done it in blitz3D...the 2D version f it)

Dreamora (Posted 2006) [#4]

Yes its in german ... but remember, we are reading the english boards as well although we are german speaking :) After all not that hard to understand if you understand the basic concepts behind A* which I assume you do. (if not google for A* and you will find many many A* for dummies pages as you are looking for) gamasutra.org and gamedev.net are normally the place to start searching

Sanctus (Posted 2006) [#5]

Thx Oh and I'm from Romania and I speek romanian,english and a bit of french :P absolultey no german(maybe just ja nein und dakesheun... did I spell ok?)

Oddball (Posted 2006) [#6]

There's an A* example in the BlitzMax sample folder, and an A* example on the BlitWiki. [a http://www.blitzwiki.org/index.php/Category:AStar_Pathfinding_%28Module%29]Astar pathfinding module[/a]

deps (Posted 2006) [#7]

This is a nice A* tutorial: http://www.policyalmanac.org/games/aStarTutorial.htm

Jesse (Posted 2006) [#8]

His source code is still in the blitzcoders webpage: http://www.blitzcoder.com/cgi-bin/showcase/showcase_showentry.pl?id=turtle177604062002002208&comments=no It is in blitzplus but easy to convert. I converted the chaser demo to BlitzMax: name astarlib.bmx 'A* Pathfinder (Version 1:82) by Patrick Lester: Used by permission: ' '================================================================== 'Last updated 03/15/04 'converted to BlitzMAx By Jesse Perez on June 15,2006 'An article describing A* And this code in particular can be found at; 'http;//www:policyalmanac:org/games/aStarTutorial:htm 'If you want To use this AStar Library, you may do so free of charge so 'Long as the author byline (above) is retained: Thank you To CaseyC 'at the Blitz Forums For suggesting the use of binary heaps For the open 'list: Email comments And questions To Patrick Lester at 'pwlester@policyalmanac:org: 'Setup '----- '1: Include "includes/aStarLibrary:bb" at the top of your program: '2: Create an array called map(x,y) that contains information ' about the map of each square/tile on your map, with ' 0 = walkable (the Default value) And 1 = unwalkable: The array ' should range from (0,0) in the Upper Left hand corner To ' (mapWidth-1,mapHeight-1) in the bottom Right hand corner: '3: Adjust the following variables at the top of the :declareVariables ' subroutine below: All three should be made global: ' - tileSize = the width And height of your square tiles in pixels ' - mapWidth = the width of your map in tiles = x value in ' map array: ' - mapHeight = the height of your map in tiles = y value in ' map array: 'Calling the functions '--------------------- 'There are three main functions '1: FindPath(unit:unit,targetX,targetY) ' - unit:unit = unit that is doing the pathfinding ' - targetX,targetY = location of the target destination (pixel based coordinates) ' The FindPath() Function returns whether a path could be found (1) Or ' If it's nonexistent (2): If there is a path, it stores it in a bank ' called unit.pathBank: '2: CheckPathStepAdvance(unit:unit) ' This Function updates the current path: '3: ReadPath(unit:unit) ' This Function reads the path data generated by FindPath() And returns ' the x And y coordinates of the Next Step on the path: They are stored ' as xPath And yPath: These coordinates are pixel coordinates ' on the screen: See the Function For more info: '========================================================== Const notfinished = 0, notStarted = 0, found = 1, nonexistent = 2' pathStatus constants Const walkable = 0, unwalkable = 1' map array constants Type Tnode Field x#,y# End Type Type Tunit Field ID, xLoc#, yLoc#, speed#, sprite:timage, targetX, targetY, target:Tunit Field pathAI, pathStatus, pathLength, pathLocation, pathBank:tbank, xPath, yPath End Type Type Tastar Field tileSize Field mapWidth Field mapHeight Field map[][] 'array that holds wall/obstacle information Field openlist[] '1 dimensional array holding ID# of open list items Field WhichList[][] '2 dimensional array used To record Field openX[] '1d array stores the x locations of an item on the open list Field openY[] '1d array stores the y location of an item on the open list Field parentX[][] '2d array To store parent of each cell (x) Field parentY[][] '2d array To store parent of each cell (y) Field Fcost[] '1d array To store F cost of a cell on the open list Field Gcost[][] '2d array To store G cost For each cell: Field Hcost[] '1d array To store H cost of a cell on the open list Global onClosedlist = 10 Function create:Tastar(tilesize,mapwidth,mapheight,map[][]) Local astar:tastar = New Tastar astar.tileSize = tilesize astar.mapWidth = mapwidth astar.mapHeight = mapheight astar.map = map ' array that holds wall/obstacle information astar.openlist = astar.openlist[..mapWidth*mapHeight+2] ' 1 dimensional array holding ID# of open list items Local z astar.whichList = astar.whichList[..mapWidth+1] ' array to record whether a cell is on the opelist or on the closed list: For z= 0 To mapWidth ; astar.whichList[z]=astar.whichList[z][..mapHeight+1];Next astar.openX=astar.openX[..mapwidth*mapHeight+2] ' 1d array stores the x locations of an item on the open list astar.openY=astar.openY[..mapWidth*mapHeight+2] ' 1d array stores the y location of an item on the open list astar.parentX=astar.parentX[..mapWidth+1] ' 2d array To store parent of each cell (x) For z = 0 To mapWidth ; astar.parentX[z]=astar.parentX[z][..MapHeight+1];Next astar.ParentY = astar.parenty[..MapWidth+1] ' 2d array To store parent of each cell (y) For z = 0 To mapWidth; astar.parentY[z]=astar.parentY[z][..mapHeight+1];Next astar.Fcost=astar.Fcost[..mapWidth*mapheight+2] ' 1d array To store F cost of a cell on the open list astar.Gcost = astar.Gcost[..mapWidth+1] ' 2d array To store G cost For each cell: For z = 0 To mapWidth; astar.Gcost[z] = astar.Gcost[z][..mapHeight+1];Next astar.Hcost = astar.Hcost[..mapWidth*mapHeight+2] ' 1d array To store H cost of a cell on the open list astar.onClosedlist = 10 Return astar End Function '========================================================== 'FIND PATH; This Function finds the path And saves it: Non-Blitz users please note, 'the first parameter is a pointer To a user-defined Object called a unit, which contains all 'relevant info about the unit in question (its current location, speed, etc:): As an 'Object-oriented data structure, types are similar To structs in C: ' Please note that targetX And targetY are pixel-based coordinates relative To the 'Upper Left corner of the map, which is 0,0: Method FindPath(unit:Tunit,targetX,targetY) '1: Convert location data (in pixels) To coordinates in the map array: Local startX = Floor(unit.xLoc/tileSize) ; Local startY = Floor(unit.yLoc/tileSize) targetX = Floor(targetX/tileSize) ; targetY = Floor(targetY/tileSize) Local newOpenListItemID Local addedGcost Local path,temp '2: Quick Path Checks; Under the some circumstances no path needs To 'be generated ::: 'If starting location And target are in the same location::: If startX = targetX And startY = targetY And unit.pathLocation > 0 Then Return found If startX = targetX And startY = targetY And unit.pathLocation = 0 Then Return nonexistent 'If target square is unwalkable, Return that it's a nonexistent path: If map[targetX][targetY] = unwalkable Then unit.xPath = startX unit.yPath = startY Return nonexistent EndIf '3: Reset some variables that need To be cleared If onClosedList > 100 'occasionally redim whichList 'Dim whichList(mapWidth,mapHeight) onClosedList = 10 For Local w = 0 To mapHeight-1 For Local z =0 To mapWidth-1; whichList[z][w]=0;Next Next End If onClosedList = onClosedList+2 'changing the values of onOpenList And onClosed list is faster than redimming whichList() array Local onOpenList = onClosedList-1 unit.pathLength = notstarted 'i:e, = 0 unit.pathLocation = notstarted 'i:e, = 0 Gcost[startX][startY] = 0 'reset starting square's G value to 0 '4: Add the starting location To the open list of squares To be checked: Local numberOfOpenListItems = 1 openList[1] = 1 'assign it as the top (And currently only) item in the open list, which is maintained as a binary heap (explained below) openX[1] = startX ; openY[1] = startY '5: Do the following Until a path is found Or deemed nonexistent: Repeat '6: If the open list is Not empty, take the first cell off of the list: 'This is the lowest F cost cell on the open list: If numberOfOpenListItems <> 0 Then 'Pop the first item off the open list: Local parentXval = openX[openList[1]] ;Local parentYVal = openY[openList[1]] 'record cell coordinates of the item whichList[parentXval][parentYVal] = onClosedList 'add the item To the closed list 'Open List = Binary Heap; Delete this item from the open list, which 'is maintained as a binary heap: For more information on binary heaps, see; 'http;//www:policyalmanac:org/games/binaryHeaps:htm numberOfOpenListItems = numberOfOpenListItems - 1 'reduce number of open list items by 1 openList[1] = openList[numberOfOpenListItems+1] 'move the last item in the heap up To slot #1 Local v = 1 Repeat 'Repeat the following Until the New item in slot #1 sinks To its proper spot in the heap: Local u = v If 2*u+1 <= numberOfOpenListItems 'If both children exist 'Check If the F cost of the parent is greater than each child: 'Select the lowest of the two children: If Fcost[openList[u]] >= Fcost[openList[2*u]] Then v = 2*u If Fcost[openList[v]] >= Fcost[openList[2*u+1]] Then v = 2*u+1 Else If 2*u <= numberOfOpenListItems 'If only child #1 exists 'Check If the F cost of the parent is greater than child #1 If Fcost[openList[u]] >= Fcost[openList[2*u]] Then v = 2*u End If End If If u<>v 'If parent's F is > one of its children, swap them temp = openList[u] openList[u] = openList[v] openList[v] = temp Else Exit 'otherwise, Exit loop End If Forever '7: Check the adjacent squares: (Its "children" -- these path children 'are similar, conceptually, To the binary heap children mentioned 'above, but don't confuse them: They are different: Path children 'are portrayed in Demo 1 with grey pointers pointing toward 'their parents:) Add these adjacent child squares To the open list 'For later consideration If appropriate (see various If statements 'below): For Local b = parentYVal-1 To parentYVal+1 For Local a = parentXval-1 To parentXval+1 'If Not off the map (do this first To avoid array out-of-bounds errors) If a <> -1 And b <> -1 And a <> mapWidth And b <> mapHeight 'If Not already on the closed list (items on the closed list have 'already been considered And can now be ignored): If whichList[a][b] <> onClosedList 'If Not a wall/obstacle square: If map[a][b] <> unwalkable 'Don't cut across corners (this is optional) Local corner = walkable If a = parentXVal-1 If b = parentYVal-1 If map[parentXval-1][parentYval] = unwalkable Or map[parentXval][parentYval-1] = unwalkable Then corner = unwalkable Else If b = parentYVal+1 If map[parentXval][parentYval+1] = unwalkable Or map[parentXval-1][parentYval] = unwalkable Then corner = unwalkable End If Else If a = parentXVal+1 If b = parentYVal-1 If map[parentXval][parentYval-1] = unwalkable Or map[parentXval+1][parentYval] = unwalkable Then corner = unwalkable Else If b = parentYVal+1 If map[parentXval+1][parentYval] = unwalkable Or map[parentXval][parentYval+1] = unwalkable Then corner = unwalkable End If End If If corner = walkable 'If Not already on the open list, add it To the open list: Local m If whichList[a][b] <> onOpenList 'Create a New open list item in the binary heap: newOpenListItemID = newOpenListItemID + 1' each New item has a unique ID # m = numberOfOpenListItems+1 openList[m] = newOpenListItemID 'place the New open list item (actually, its ID#) at the bottom of the heap openX[newOpenListItemID] = a ; openY[newOpenListItemID] = b 'record the x And y coordinates of the New item 'Figure out its G cost If Abs(a-parentXval) = 1 And Abs(b-parentYVal) = 1 Then addedGCost = 14 'cost of going To diagonal squares Else addedGCost = 10 'cost of going To non-diagonal squares End If Gcost[a][b] = Gcost[parentXval][parentYVal]+addedGCost 'Figure out its H And F costs And parent Hcost[openList[m]] = 10*(Abs(a - targetx) + Abs(b - targety)) ' record the H cost of the New square Fcost[openList[m]] = Gcost[a][b] + Hcost[openList[m]] 'record the F cost of the New square parentX[a][b] = parentXval ; parentY[a][b] = parentYVal 'record the parent of the New square 'Move the New open list item To the proper place in the binary heap: 'Starting at the bottom, successively compare To parent items, 'swapping as needed Until the item finds its place in the heap 'Or bubbles all the way To the top (If it has the lowest F cost): While m <> 1 'While item hasn't bubbled to the top (m=1) 'Check If child's F cost is < parent's F cost: If so, swap them: If Fcost[openList[m]] <= Fcost[openList[m/2]] Then temp = openList[m/2] openList[m/2] = openList[m] openList[m] = temp m = m/2 Else Exit End If Wend numberOfOpenListItems = numberOfOpenListItems+1 'add one To the number of items in the heap 'Change whichList To show that the New item is on the open list: whichList[a][b] = onOpenList '8: If adjacent cell is already on the open list, check To see If this 'path To that cell from the starting location is a better one: 'If so, change the parent of the cell And its G And F costs: Else' If whichList(a,b) = onOpenList 'Figure out the G cost of this possible New path If Abs(a-parentXval) = 1 And Abs(b-parentYVal) = 1 Then addedGCost = 14'cost of going To diagonal tiles Else addedGCost = 10 'cost of going To non-diagonal tiles End If Local tempGcost = Gcost[parentXval][parentYVal]+addedGCost 'If this path is shorter (G cost is Lower) Then change 'the parent cell, G cost And F cost: If tempGcost < Gcost[a][b] Then 'If G cost is less, parentX[a][b] = parentXval 'change the square's parent parentY[a][b] = parentYVal Gcost[a][b] = tempGcost 'change the G cost 'Because changing the G cost also changes the F cost, If 'the item is on the open list we need To change the item's 'recorded F cost And its position on the open list To make 'sure that we maintain a properly ordered open list: For Local x = 1 To numberOfOpenListItems 'look For the item in the heap If openX[openList[x]] = a And openY[openList[x]] = b Then 'item found FCost[openList[x]] = Gcost[a][b] + HCost[openList[x]] 'change the F cost 'See If changing the F score bubbles the item up from it's current location in the heap m = x While m <> 1 'While item hasn't bubbled to the top (m=1) 'Check If child is < parent: If so, swap them: If Fcost[openList[m]] < Fcost[openList[m/2]] Then temp = openList[m/2] openList[m/2] = openList[m] openList[m] = temp m = m/2 Else Exit 'While/Wend End If Wend Exit 'For x = loop End If 'If openX(openList(x)) = a Next 'For x = 1 To numberOfOpenListItems End If 'If tempGcost < Gcost(a,b) Then End If 'If Not already on the open list End If 'If corner = walkable End If 'If Not a wall/obstacle cell: End If 'If Not already on the closed list End If 'If Not off the map: Next Next '9: If open list is empty Then there is no path: Else path = nonExistent ; Exit End If 'If target is added To open list Then path has been found: If whichList[targetx][targety] = onOpenList Then path = found ; Exit Forever 'Repeat Until path is found Or deemed nonexistent '10: Save the path If it exists: Copy it To a bank: Local tempx If path = found 'a: Working backwards from the target To the starting location by checking 'each cell's parent, figure out the length of the path: Local pathX = targetX ; Local pathY = targetY Repeat tempx = parentX[pathX][pathY] pathY = parentY[pathX][pathY] pathX = tempx unit.pathLength = unit.pathLength + 1 Until pathX = startX And pathY = startY 'b: Resize the data bank To the Right size (leave room To store Step 0, 'which requires storing one more Step than the length) ResizeBank unit.pathBank,(unit.pathLength+1)*4 'c: Now copy the path information over To the databank: Since we are 'working backwards from the target To the start location, we copy 'the information To the data bank in reverse order: The result is 'a properly ordered set of path data, from the first Step To the 'last: pathX = targetX ; pathY = targetY Local cellPosition = unit.pathLength*4 'start at the End While Not (pathX = startX And pathY = startY) PokeShort unit.pathBank,cellPosition,pathX 'store x value PokeShort unit.pathBank,cellPosition+2,pathY 'store y value cellPosition = cellPosition - 4 'work backwards tempx = parentX[pathX][pathY] pathY = parentY[pathX][pathY] pathX = tempx Wend PokeShort unit.pathBank,0,startX 'store starting x value PokeShort unit.pathBank,2,startY 'store starting y value End If 'If path = found Then '11: Return info on whether a path has been found: Return path' Returns 1 If a path has been found, 2 If no path exists: '12:If there is no path To the selected target, set the pathfinder's 'xPath And yPath equal To its current location And Return that the 'path is nonexistent: End Method '========================================================== 'READ PATH DATA; These functions read the path data And convert 'it To screen pixel coordinates: Function ReadPath(unit:Tunit) unit.xPath = ReadPathX(unit,unit.pathLocation) unit.yPath = ReadPathY(unit,unit.pathLocation) End Function Function ReadPathX#(unit:Tunit,pathLocation) If pathLocation <= unit.pathLength Local x =PeekShort (unit.pathBank,pathLocation*4) Return tileSize*x + .5*tileSize 'align w/center of square End If End Function Function ReadPathY#(unit:Tunit,pathLocation) If pathLocation <= unit.pathLength Local y = PeekShort (unit.pathBank,pathLocation*4+2) Return tileSize*y + .5*tileSize 'align w/center of square End If End Function 'This Function checks whether the unit is close enough To the Next 'path node To advance To the Next one Or, If it is the last path Step, 'To stop: Method CheckPathStepAdvance(unit:Tunit) If (unit.xLoc = unit.xPath And unit.yLoc = unit.yPath) Or unit.pathLocation = 0 If unit.pathLocation = unit.pathLength unit.pathStatus = notstarted Else unit.pathLocation = unit.pathLocation + 1 ReadPath(unit) 'update xPath And yPath End If End If End Method End Type you can test it with this: name chasergame.bmx Strict Include "astarlib.bmx" Const USERCONTROLLED = 1 Const CHASE = 2 Const TILESIZE = 50 Const MAPWIDTH = 32 Const MAPHEIGHT= 24 Type Tgame Field cursor:timage Field grid:timage Field redBlock:timage Field wallBlock:timage Field smiley:timage Field chaser:timage Field Drawing, Erasing, Started Field unit:Tunit Field Astar:Tastar Field map[][] Global unitList:Tlist Function create:tgame() Local game:tgame = New Tgame If Not GraphicsModeExists(1024,768) RuntimeError "Sorry, this program won't work with your graphics card." Graphics 1024,768,1 ; SetMaskColor 255,255,255 ; HideMouse() game.cursor = LoadImage("graphics/red_pointer.bmp",MASKEDIMAGE) game.grid = LoadImage("graphics/grid.bmp",MASKEDIMAGE) game.redBlock = LoadImage("graphics/end.bmp") 'target location game.wallBlock = LoadImage("graphics/wall.bmp") 'wall game.smiley = LoadImage("graphics/smiley.bmp",MASKEDIMAGE) MidHandleImage game.smiley game.chaser = LoadImage("graphics/ghost.bmp",MASKEDIMAGE) MidHandleImage game.chaser SetBlend(ALPHABLEND) Local tempunit:tunit game.map=game.map[..mapwidth+1] For Local z = 0 To mapwidth game.map[z]=game.map[z][..mapHeight] Next game.Astar = Tastar.Create(TILESIZE,MAPWIDTH,MAPHEIGHT,game.map) For Local x = 1 To 3 'Create And initialize 3 units game.unit = New Tunit ; game.unit.ID = x If Not game.UnitList Then game.unitList = CreateList() game.unit.pathBank = CreateBank(1) 'data bank that unit's path data is stored in game.unitList.addlast(game.unit) If x = 1 'smily game.unit.xLoc = 125 game.unit.yLoc = 325 game.unit.speed = 5.3 game.unit.pathAI = userControlled game.unit.sprite = game.smiley ; tempunit = game.unit Else 'If x = 2 'chaser game.unit.xLoc = 625+Rand(250) game.unit.yLoc = 50+Rand(500) game.unit.speed = 3 game.unit.target = tempunit game.unit.pathAI = chase game.unit.sprite = game.chaser 'First unit End If Next Return game End Function Method RunProgram()'Main program loop While Not KeyHit(KEY_ESCAPE) ; UserInput() MoveUnits() RenderScreen() Wend End Method Method UserInput()'This Function handles most user mouse And keyboard Input If Started = False 'If in map edit mode If (Not MouseDown(1)) Then Drawing = False; Erasing = False If MouseDown(1) 'Edit map by drawing Or erasing walls If map[MouseX()/tileSize][MouseY()/tileSize] = walkable And Erasing = False 'Draw walls map[MouseX()/tileSize][MouseY()/tileSize] = unwalkable Drawing = True End If If map[MouseX()/tileSize][MouseY()/tileSize] = unwalkable And Drawing = False 'Erase walls map[MouseX()/tileSize][MouseY()/tileSize] = walkable Erasing = True End If Else If KeyHit(KEY_ENTER) Or MouseHit(2) Then 'Activate smiley sprite If Return/enter Or Right mouse button is hit Started = True End If Else 'If in game/pathfinding mode Then reenter map edit mode by pressing enter/Return key. This stops the units. If KeyHit(KEY_ENTER) Started = False ; FlushMouse() For unit = EachIn unitList unit.pathStatus = Not started Next EndIf End If End Method Method RenderScreen() 'This Function draws stuff on the screen. Cls For Local x = 0 To mapwidth-1 'Draw the walls And the grid For Local y = 0 To mapheight-1 If map[x][y] = unwalkable Then DrawImage wallBlock,x*tilesize,y*tilesize DrawImage grid,x*tileSize,y*tileSize Next Next For Local r:tunit = EachIn unitList DrawImage r.sprite,r.xLoc,r.yLoc Next DrawImage cursor,MouseX(),MouseY() 'Draw the mouse Flip End Method Method MoveUnits() 'This Function performs pathfinding And moves the units. If Started = True For unit = EachIn unitList UpdatePath(unit) If unit.pathStatus = found Then MoveUnit(unit) ; Next EndIf End Method Method UpdatePath(unit:Tunit) 'This Function checks For path updates And calls the FindPath() Function when needed. If unit.pathAI = userControlled 'If the unit is the smiley, trigger New paths using the mouse If MouseHit(1) Or MouseHit(2) unit.pathStatus = astar.FindPath(unit,MouseX(),MouseY()) Else If unit.pathAI = chase 'Step Until it reaches the smiley. If smiley And chaser aren't at same loc. on screen And no active path, find a New path. If Not (unit.xLoc = unit.target.xLoc And unit.yLoc = unit.target.yLoc) 'If not generating pad, generate one. Update it when 'the chaser reaches its third Step on path. If unit.pathStatus <> found Or unit.pathlocation = 3 unit.pathStatus = astar.FindPath(unit,unit.target.xLoc,unit.target.yLoc) End If End If End If End Method Method MoveUnit(unit:Tunit)'This Function moves the sprites around on the screen. astar.CheckPathStepAdvance(unit) 'Check For pathStep advances. Local xVector# = unit.xPath-unit.xLoc Local yVector# = unit.yPath-unit.yLoc Local angle# = ATan2(yVector#,xVector#) Local xSpeed# = Cos(angle)*unit.speed Local ySpeed# = Sin(angle)*unit.speed If Abs(unit.xLoc - unit.xPath) < Abs(xSpeed) unit.xLoc = unit.xPath Else unit.xLoc = unit.xLoc + xSpeed If Abs(unit.yLoc - unit.yPath) < Abs(ySpeed) unit.yLoc = unit.yPath Else unit.yLoc = unit.yLoc + ySpeed End Method End Type SeedRnd MilliSecs() Local game:tgame = Tgame.create() game.RunProgram() End create a folder, put both files in there and copy the graphics folder from the tutorial samples in to your new folder and try. EDITED: sorry guys I uploaded the wrong files. It should be ok now ;).

Sanctus (Posted 2006) [#9]

Thx a lot jesse :D:D *hug*

Jesse (Posted 2006) [#10]

SORRY! Sanctus, I fixed the chasser game file . it works now.