December 03, 2020, 08:15:19 PM

Author Topic: [bmx] A* (astar) routine by coffeedotbean [ 11 months ago ]  (Read 789 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
Title : A* (astar) routine
Author : coffeedotbean
Posted : 11 months ago

Description : BlitzMax port of Patrick Lester's "A* Pathfinding for Beginners" <a href="http://www.policyalmanac.org/games/aStarTutorial.htm" target="_blank">http://www.policyalmanac.org/games/aStarTutorial.htm[/url]

Code :
Code: BlitzMax
  1. '===========================================================================================================================
  2. '===========================================================================================================================
  3. ' CREDITS
  4. ' =======
  5. ' BlitzMax port of Patrick Lester's "A* Pathfinding for Beginners" http://www.policyalmanac.org/games/aStarTutorial.htm
  6. ' Conversion by 'CoffeeDotBean' http://www.blitzbasic.com/Account/showuser.php?id=584 (June 26 2016)
  7. '
  8. '
  9. ' HOW TO USE
  10. ' ==========
  11. '1. Include this file (.bmx) at the top of your program.
  12. '
  13. '2. Create a NEW TPath_Astar:Object. e.g myPath:TPath_Astar = New TPath_Astar; myPath is your hook going forward.
  14. '
  15. '3. Call Prepare() Method and pass in the required information.
  16. '      Arr[,]             = 2d Int Array containing your Map data, does not need to be specially formatted.
  17. '      UnWalkableValues[] = Int Array containing Values that the Search will consider as Walls & impassable terrain.
  18. '      StartX/Y           = Start Grid ref.
  19. '      TargetX/Y          = Target Grid ref.
  20. '
  21. '4. Call Search() Method to look for a Path, call PathFound() to know if a path was found
  22. '      EightWay           = If False diaganls will be ignored.
  23. '      CutCorners         = (only applicanle with Eightway=True), Cut diagonaly through corners.
  24. '
  25. '5. Return A found Path, all Methods will return (-1) if no path is avaliable
  26. '      GetPathInt()       = Return Int Array with directions (Start ==> Target) 1,2,3,4,5,6,7,8 (1=up, 2=up&right, 3=right, 4=down&right etc..).
  27. '      GetPathStr()       = Return String Array with compass directions (Start ==> Target) N,NE,E,SE,S,SW,W,NW.
  28. '      GetPathRef()       = Return Int Array with Array grid references (probably not useful).
  29. '
  30. '
  31. ' OTHER METHODS
  32. ' =============
  33. '*. PathFound()           = Return True if a path was found after calling Search() Method.
  34. '*. PathClear()           = Flag the path as not found (does not nullify any other data).
  35. '*. GetPathLength()       = Return Length of the path as steps (tiles) between Start and Target along the path.
  36. '*. GetPathDistance()     = Return Distance between Start and Target in Pixels along the path.
  37. '===========================================================================================================================
  38. '===========================================================================================================================
  39.  
  40. Type TPath_Astar
  41.         Const NOTFINISHED:Int = 0
  42.         Const NOTSTARTED:Int = 0
  43.         Const FOUND:Int = 1
  44.         Const NONEXISTENT:Int = 2
  45.         Const WALKABLE:Int = 0
  46.         Const UNWALKABLE:Int = 1
  47.         Const ONCLOSEDLIST:Int = 2
  48.         Const ONOPENLIST:Int = 1
  49.         Field MapWidth:Int
  50.         Field MapHeight:Int
  51.         Field Walkability:Int[,]
  52.         Field OpenList:Int[]
  53.         Field WhichList:Int[,]
  54.         Field OpenX:Int[]
  55.         Field OpenY:Int[]
  56.         Field ParentX:Int[,]
  57.         Field ParentY:Int[,]
  58.         Field FCost:Int[]
  59.         Field GCost:Int[,]
  60.         Field HCost:Int[]
  61.         Field StartX:Int
  62.         Field StartY:Int
  63.         Field TargetX:Int
  64.         Field TargetY:Int
  65.         Field NumberOfOpenListItems:Int
  66.         Field NewOpenListItemID:Int
  67.         Field Path:Int
  68.         Field Steps:TList
  69.        
  70.         rem
  71.         bbdoc:  Flag path as not exisiting
  72.         end rem
  73.         Method Clear:Int()
  74.                 Path = NONEXISTENT
  75.         End Method
  76.        
  77.         rem
  78.         bbdoc:  Search for a path, EightWay=False means no diagonals, CutCorners only applicable with diagonals (Eightway)
  79.         end rem
  80.         Method Search:Int(EightWay:Int = True, CutCorners:Int = False)
  81.                 NumberOfOpenListItems = 1
  82.                 OpenList[1] = 1
  83.                 OpenX[1] = StartX
  84.                 OpenY[1] = StartY
  85.                
  86.                 Repeat
  87. '6 ------------------------------------------------------------------- 
  88.                         If NumberOfOpenListItems <> 0
  89.                                 Local ParentXval:Int = OpenX[OpenList[1]]
  90.                                 Local ParentYval:Int = OpenY[OpenList[1]]
  91.                                 WhichList[ParentXval, ParentYval] = ONCLOSEDLIST
  92.                                 NumberOfOpenListItems:-1
  93.                                 OpenList[1] = OpenList[NumberOfOpenListItems + 1]
  94.                                 Local v:Int = 1
  95.                                 Repeat
  96.                                         Local u:Int = v
  97.                                         If 2 * u + 1 <= NumberOfOpenListItems
  98.                                                 If FCost[OpenList[u]] >= FCost[OpenList[2 * u]] Then v = 2 * u
  99.                                                 If FCost[OpenList[v]] >= FCost[OpenList[2 * u + 1]] Then v = 2 * u + 1
  100.                                         Else
  101.                                                 If 2 * u <= NumberOfOpenListItems
  102.                                                         If FCost[OpenList[u]] >= FCost[OpenList[2 * u]] Then v = 2 * u
  103.                                                 End If 
  104.                                         End If
  105.                                         If u <> v
  106.                                                 Local temp:Int = OpenList[u]
  107.                                                 OpenList[u] = OpenList[v]
  108.                                                 OpenList[v] = temp
  109.                                         Else
  110.                                                 Exit
  111.                                         End If
  112.                                 Forever
  113. ' 7 -------------------------------------------------------------------
  114.                                 For Local b:Int = ParentYval - 1 To ParentYval + 1             
  115.                                 For Local a:Int = ParentXval - 1 To ParentXval + 1
  116.                                         If Not EightWay
  117.                                                 If a = ParentXval + 1 And b = ParentYval + 1 Then Continue
  118.                                                 If a = ParentXval - 1 And b = ParentYval - 1 Then Continue
  119.                                                 If a = ParentXval + 1 And b = ParentYval - 1 Then Continue
  120.                                                 If a = ParentXval - 1 And b = ParentYval + 1 Then Continue
  121.                                         EndIf
  122.                                        
  123.                                         If a <> - 1 And b <> - 1 And a <> MapWidth And b <> MapHeight
  124.                                                 If whichList[a, b] <> ONCLOSEDLIST
  125.                                                         If walkability[a, b] <> unwalkable
  126.                                                                
  127.                                                                 Local Corner:Int = WALKABLE
  128.                                                                 If CutCorners = False
  129.                                                                         If a = ParentXval - 1
  130.                                                                                 If b = ParentYval - 1
  131.                                                                                         If Walkability[ParentXval - 1, ParentYval] = UNWALKABLE Or Walkability[ParentXval, ParentYval - 1] = UNWALKABLE Then Corner = UNWALKABLE
  132.                                                                                 Else If b = ParentYval + 1
  133.                                                                                         If Walkability[ParentXval, ParentYval + 1] = UNWALKABLE Or Walkability[ParentXval - 1, ParentYval] = UNWALKABLE Then Corner = UNWALKABLE
  134.                                                                                 End If
  135.                                                                         Else If a = ParentXval + 1
  136.                                                                                 If b = ParentYval - 1
  137.                                                                                         If Walkability[ParentXval, ParentYval - 1] = UNWALKABLE Or Walkability[ParentXval + 1, ParentYval] = UNWALKABLE Then Corner = UNWALKABLE
  138.                                                                                 Else If b = ParentYval + 1
  139.                                                                                         If Walkability[ParentXval + 1, ParentYval] = UNWALKABLE Or Walkability[ParentXval, ParentYval + 1] = UNWALKABLE Then Corner = UNWALKABLE
  140.                                                                                 End If
  141.                                                                         End If
  142.                                                                 EndIf
  143.                                                                
  144.                                                                 If Corner = WALKABLE
  145.                                                                         If whichList[a, b] <> ONOPENLIST
  146.                                                                                 NewOpenListItemID:+1
  147.                                                                                 Local m:Int = NumberOfOpenListItems + 1
  148.                                                                                 OpenList[m] = NewOpenListItemID
  149.                                                                                 OpenX[NewOpenListItemID] = a
  150.                                                                                 openY[NewOpenListItemID] = b
  151.                                                                                
  152.                                                                                 If Abs(a - ParentXval) = 1 And Abs(b - ParentYval) = 1
  153.                                                                                         Gcost[a, b] = Gcost[ParentXval, ParentYval] + 14
  154.                                                                                 Else   
  155.                                                                                         Gcost[a, b] = Gcost[ParentXval, ParentYval] + 10
  156.                                                                                 End If
  157.                                                                
  158.                                                                                 HCost[OpenList[m]] = EstimateHcost(a, b)
  159.                                                                                 FCost[OpenList[m]] = GCost[a, b] + HCost[openList[m]]
  160.                                                                                 ParentX[a, b] = ParentXval
  161.                                                                                 ParentY[a, b] = ParentYval
  162.                
  163.                                                                                 While m <> 1
  164.                                                                                         If FCost[openList[m]] <= FCost[OpenList[m / 2]]
  165.                                                                                                 Local temp:Int = OpenList[m / 2]
  166.                                                                                                 OpenList[m / 2] = OpenList[m]
  167.                                                                                                 OpenList[m] = temp
  168.                                                                                                 m = m / 2
  169.                                                                                         Else
  170.                                                                                                 Exit
  171.                                                                                         End If
  172.                                                                                 Wend
  173.                                                                                 NumberOfOpenListItems:+1
  174.                                                                                 WhichList[a, b] = ONOPENLIST
  175. ' 8 -------------------------------------------------------------------                                                                        
  176.                                                                         Else 'whichList[a, b] <> ONOPENLIST
  177.                                                                                 Local tempGcost:Int
  178.                                                                                 If Abs(a - ParentXval) = 1 And Abs(b - ParentYval) = 1
  179.                                                                                         tempGcost = Gcost[ParentXval, ParentYval] + 14
  180.                                                                                 Else   
  181.                                                                                         tempGcost = Gcost[ParentXval, ParentYval] + 10
  182.                                                                                 End If
  183.                                                                                 If tempGcost < GCost[a, b]
  184.                                                                                         ParentX[a, b] = ParentXval
  185.                                                                                         ParentY[a, b] = ParentYval
  186.                                                                                         GCost[a, b] = tempGcost
  187.                                                                                
  188.                                                                                         For Local x:Int = 1 To NumberOfOpenListItems
  189.                                                                                                 If OpenX[OpenList[x]] = a And OpenY[OpenList[x]] = b
  190.                                                                                                         FCost[OpenList[x]] = Gcost[a, b] + HCost[OpenList[x]]
  191.                                                                                                         Local m:Int = x
  192.                                                                                                         While m <> 1
  193.                                                                                                                 If FCost[OpenList[m]] < FCost[OpenList[m / 2]] Then
  194.                                                                                                                         Local temp:Int = OpenList[m / 2]
  195.                                                                                                                         OpenList[m / 2] = openList[m]
  196.                                                                                                                         OpenList[m] = temp
  197.                                                                                                                         m = m/2
  198.                                                                                                                 Else
  199.                                                                                                                         Exit 'while/wend
  200.                                                                                                                 End If
  201.                                                                                                         Wend
  202.                                                                                                         Exit 'for x = loop
  203.                                                                                                 End If 'If openX(openList(x)) = a
  204.                                                                                         Next 'For x = 1 To numberOfOpenListItems       
  205.                                                                                 End If 'If tempGcost < Gcost(a,b)              
  206.                                                                         End If ' If not already on the open list
  207.                                                                 End If ' If corner = walkable
  208.                                                         End If ' If not a wall/obstacle cell
  209.                                                 End If 'If not already on the closed list
  210.                                         End If 'If not off the map.
  211.                                 Next
  212.                                 Next
  213. ' 9 -------------------------------------------------------------------                        
  214.                         Else  'NumberOfOpenListItems / If open list is empty then there is no path.
  215.                                 Path = NONEXISTENT
  216.                                 Exit
  217.                         EndIf 'NumberOfOpenListItems
  218.                        
  219.                         If WhichList[TargetX, TargetY] = ONOPENLIST
  220.                                 Path = FOUND
  221.                                 Exit
  222.                         EndIf
  223.  
  224.                 Forever
  225. ' 10 -------------------------------------------------------------------                       
  226.                 If Path = FOUND
  227.                         Local pathX:Int = TargetX
  228.                         Local pathY:Int = TargetY
  229.                         Steps.AddFirst(String(pathX + (pathY * MapWidth)))
  230.                         Repeat
  231.                                 Local tempx:Int = ParentX[pathX, pathY]
  232.                                 pathY = ParentY[pathX, pathY]
  233.                                 pathX = tempx
  234.                                 Steps.AddFirst(String(pathX + (pathY * MapWidth)))
  235.                         Until pathX = StartX And pathY = StartY
  236.                 End If
  237.                
  238.         End Method
  239.        
  240.         rem
  241.         bbdoc:  Prepare to do a search, ALWAYS call before calling Search() Method
  242.         end rem
  243.         Method Prepare:Int(Arr:Int[,], UnWalkableValues:Int[], StartX:Int, StartY:Int, TargetX:Int, TargetY:Int)
  244.                 'Store start and target locations
  245.                 Self.StartX = StartX
  246.                 Self.StartY = StartY
  247.                 Self.TargetX = TargetX
  248.                 Self.TargetY = TargetY
  249.                 'Initalise arrays
  250.                 MapWidth = arr.Dimensions()[0]
  251.                 MapHeight = arr.Dimensions()[1]
  252.                 Walkability = New Int[MapWidth, MapHeight]
  253.                 WhichList = New Int[MapWidth, MapHeight]
  254.                 ParentX = New Int[MapWidth, MapHeight]
  255.                 ParentY = New Int[MapWidth, MapHeight]
  256.                 GCost = New Int[MapWidth, MapHeight]
  257.                 OpenList = New Int[MapWidth * MapHeight + 2]
  258.                 OpenX = New Int[MapWidth * MapHeight + 2]
  259.                 OpenY = New Int[MapWidth * MapHeight + 2]
  260.                 FCost = New Int[MapWidth * MapHeight + 2]
  261.                 HCost = New Int[MapWidth * MapHeight + 2]
  262.                 'Reset Fields
  263.                 NumberOfOpenListItems = 0
  264.                 NewOpenListItemID = 0
  265.                 Steps = New TList
  266.                 'Make array to check walkable squares
  267.                 For Local x:Int = 0 Until MapWidth
  268.                         For Local y:Int = 0 Until MapHeight
  269.                                         For Local a:Int = 0 Until UnWalkableValues.Length
  270.                                                 If Arr[x, y] = UnWalkableValues[a] Then Walkability[x, y] = UNWALKABLE
  271.                                         Next
  272.                         Next
  273.                 Next   
  274.         End Method
  275.  
  276.         rem
  277.         bbdoc:  Return Estimated cost (H)euristic (used in search Method), three methods available, default is Manhatten
  278.         end rem
  279.         Method EstimateHcost:Int(a:Int, b:Int, Formula:Int = 0)
  280.                 Local h:Int    
  281.                 Select Formula
  282.                         Case 0 'Manhattan (dx+dy) (DEFAULT)    
  283.                                 h = 10 * (Abs(a - TargetX) + Abs(b - TargetY))
  284.                         Case 1 'Diagonal Shortcut Estimation Method (NOT USED BY DEFAULT)
  285.                                 Local xDistance:Int = Abs(a - TargetX)
  286.                                 Local yDistance:Int = Abs(b - TargetY)
  287.                                 If xDistance > yDistance Then
  288.                                         h = 14 * yDistance + 10 * (xDistance - yDistance)
  289.                                 Else
  290.                                         h = 14 * xDistance + 10 * (yDistance - xDistance)
  291.                                 End If
  292.                         Case 2 'Max(dx,dy) (NOT USED BY DEFAULT)
  293.                                 Local xDistance:Int = Abs(a - TargetX)
  294.                                 Local yDistance:Int = Abs(b - TargetY)
  295.                                 If xDistance > yDistance Then
  296.                                         H = 10*xDistance
  297.                                 Else
  298.                                         H = 10*yDistance
  299.                                 End If
  300.                 End Select                     
  301.                 Return h
  302.         End Method
  303.        
  304.         rem
  305.         bbdoc:  DEBUG - draw path results (wouldn't typicaly use this, but useful for testing/debugging)
  306.         end rem
  307.         Method Render:Int(TileSize:Int, JustShowPath:Int = True)
  308.                 If Path <> FOUND Return 0
  309.                
  310.                 If Not JustShowPath
  311.                         'List type, green=openlist, red=closedlist
  312.                         For Local x:Int = 0 Until MapWidth
  313.                                 For Local y:Int = 0 Until MapHeight
  314.                                         If WhichList[x, y] = ONOPENLIST
  315.                                                 SetColor 106, 193, 1
  316.                                         ElseIf WhichList[x, y] = ONCLOSEDLIST
  317.                                                 SetColor 195, 15, 1
  318.                                         Else
  319.                                                 Continue
  320.                                         EndIf
  321.                                         If (x = StartX And y = StartY) Or (x = TargetX And y = TargetY)
  322.                                                 SetColor 42, 155, 196
  323.                                                 DrawRect((x * TileSize), (y * TileSize), TileSize, TileSize)
  324.                                         Else
  325.                                                 DrawRect((x * TileSize), (y * TileSize), TileSize, TileSize)
  326.                                         End If
  327.                                        
  328.                                 Next
  329.                         Next
  330.                        
  331.                         'Parent pointers
  332.                         SetColor 0, 0, 0
  333.                         For Local x:Int = 0 Until MapWidth
  334.                                 For Local y:Int = 0 Until MapHeight
  335.                                         If WhichList[x, y] = 0 Continue
  336.                                         If x = StartX And y = StartY Continue
  337.                                         Local index:Int = (x + (y * MapWidth))
  338.                                         Local val:Int = (ParentX[x, y] + (ParentY[x, y] * MapWidth))
  339.                                         Local angle:Int
  340.                                         Select val - index
  341.                                                 Case 1 ;angle = 90
  342.                                                 Case - 1;angle = 270
  343.                                                 Case MapWidth;angle = 180
  344.                                                 Case - MapWidth;angle = 0
  345.                                                 Case MapWidth + 1;angle = 135
  346.                                                 Case MapWidth - 1;angle = 225
  347.                                                 Case - MapWidth - 1;angle = 315
  348.                                                 Case - MapWidth + 1;angle = 45
  349.                                         End Select
  350.                                         DrawOval(((x + 0.5) * TileSize) - ((TileSize / 5) / 2),  ..
  351.                                         ((y + 0.5) * TileSize) - ((TileSize / 5) / 2),  ..
  352.                                         (TileSize / 5), (TileSize / 5))
  353.                                         DrawLine((x + 0.5) * TileSize, (y + 0.5) * TileSize,  ..
  354.                                         ((x + 0.5) * TileSize) + (Sin(180 - angle) * (TileSize / 3)),  ..
  355.                                         ((y + 0.5) * TileSize) + (Cos(180-angle) * (TileSize/3)))
  356.                                 Next
  357.                         Next
  358.                        
  359.                         'Costs
  360.                         SetColor 0, 0, 0
  361.                         For Local x:Int = 0 Until MapWidth
  362.                                 For Local y:Int = 0 Until MapHeight
  363.                                         If WhichList[x, y] = 0 Continue
  364.                                         If x = StartX And y = StartY Continue
  365.                                         DrawText(GCost[x, y] + EstimateHcost(x, y), (x * TileSize) + 2, (y * TileSize) + 2)
  366.                                         DrawText(GCost[x, y], (x * TileSize) + 2, ((y + 1) * TileSize) - TextHeight(""))
  367.                                         DrawText(EstimateHcost(x, y), ((x + 1) * TileSize) - TextWidth(String EstimateHcost(x, y)) - 4, ((y + 1) * TileSize) - TextHeight(""))
  368.                                 Next
  369.                         Next
  370.                         SetColor 255, 255, 255
  371.                 EndIf
  372.                
  373.                 'Path
  374.                 If Path <> FOUND Then Return 0
  375.                 Local b:Int[] = GetPathRef()
  376.                 For Local x:Int = 0 Until MapWidth
  377.                         For Local y:Int = 0 Until MapHeight
  378.                                 For Local a:Int = 0 Until b.Length
  379.                                         If b[a] = (x + (y * MapWidth))
  380.                                                 DrawOval(((x + 0.5) * TileSize)-(TileSize / 8), ((y + 0.5) * TileSize)-(TileSize / 8), (TileSize / 4), (TileSize / 4))
  381.                                         Local angle:Int
  382.                                         Local lineLen:Int = TileSize
  383.                                         If a = b.Length - 1 Continue
  384.                                         Select b[a + 1] - b[a]
  385.                                                 Case 1 ;angle = 90
  386.                                                 Case - 1;angle = 270
  387.                                                 Case MapWidth;angle = 180
  388.                                                 Case - MapWidth;angle = 0
  389.                                                 Case MapWidth + 1;angle = 135 ; lineLen:+(TileSize / 3)
  390.                                                 Case MapWidth - 1;angle = 225 ; lineLen:+(TileSize / 3)
  391.                                                 Case - MapWidth - 1;angle = 315; lineLen:+(TileSize / 3)
  392.                                                 Case - MapWidth + 1;angle = 45 ; lineLen:+(TileSize / 3)
  393.                                         End Select
  394.                                         DrawLine((x + 0.5) * TileSize, (y + 0.5) * TileSize,  ..
  395.                                         ((x + 0.5) * TileSize) + (Sin(180 - angle) * (lineLen)),  ..
  396.                                         ((y + 0.5) * TileSize) + (Cos(180 - angle) * (lineLen)))
  397.                                         EndIf
  398.                                 Next
  399.                         Next
  400.                 Next
  401.         End Method
  402.        
  403.         rem
  404.         bbdoc:  Return a FOUND path as INT[] Array (Start --> Target) representing directions CLOCKWISE; (1)=up, (2)=up&right, (3)=right, (4)=down&right .. etc ..
  405.         end rem
  406.         Method GetPathInt:Int[] ()
  407.                 If Path <> FOUND Return[- 1]
  408.                 Local b:Int[Steps.Count() - 1]
  409.                 For Local i:Int = 0 Until b.Length
  410.                         Local a:Int = Int(String Steps.ValueAtIndex(i))
  411.                         Local c:Int = Int(String Steps.ValueAtIndex(i + 1))
  412.                         Select a - c
  413.                                 Case 1 ;b[i] = 7
  414.                                 Case - 1;b[i] = 3
  415.                                 Case MapWidth;b[i] = 1
  416.                                 Case - MapWidth;b[i] = 5
  417.                                 Case MapWidth + 1;b[i] = 8
  418.                                 Case MapWidth - 1;b[i] = 2
  419.                                 Case - MapWidth - 1; b[i] = 4
  420.                                 Case - MapWidth + 1;b[i] = 6
  421.                         End Select
  422.                 Next
  423.                 Return b
  424.         End Method
  425.        
  426.         rem
  427.         bbdoc:  Return a FOUND path as STRING[] Array (Start --> Target) representing compass directions CLOCKWISE; "N", "NE", "E", "SE", "S", "SW", "W", "NW"
  428.         end rem
  429.         Method GetPathStr:String[] ()
  430.                 If Path <> FOUND Return["NO PATH"]
  431.                 Local a:Int[] = GetPathInt()
  432.                 Local b:String[a.Length]
  433.                 For Local i:Int = 0 Until a.Length
  434.                         Select a[i]
  435.                                 Case 1;b[i] = "N"
  436.                                 Case 2;b[i] = "NE"
  437.                                 Case 3;b[i] = "E"
  438.                                 Case 4;b[i] = "SE"
  439.                                 Case 5;b[i] = "S"
  440.                                 Case 6;b[i] = "SW"
  441.                                 Case 7;b[i] = "W"
  442.                                 Case 8;b[i] = "NW"
  443.                         End Select
  444.                 Next
  445.                 Return b
  446.         End Method
  447.        
  448.         rem
  449.         bbdoc:  Return a FOUND path as Array (x,y) Tile reference values (probably not that useful)
  450.         end rem
  451.         Method GetPathRef:Int[] ()
  452.                 If Path <> FOUND Return[- 1]
  453.                 Local b:Int[GetPathInt().Length + 1]
  454.                 Local pathX:Int = TargetX
  455.                 Local pathY:Int = TargetY
  456.                 Local i:Int = b.Length - 1
  457.                 b[i] = (TargetX + (TargetY * MapWidth)) ; i:-1
  458.                 Repeat
  459.                         Local tempx:Int = ParentX[pathX, pathY]
  460.                         pathY = ParentY[pathX, pathY]
  461.                         pathX = tempx
  462.                         b[i] = (pathX + (pathY * MapWidth))
  463.                         i:-1
  464.                 Until pathX = StartX And pathY = StartY
  465.                 Return b
  466.         End Method
  467.        
  468.         rem
  469.         bbdoc:  Return how many steps are in the FOUND path
  470.         end rem
  471.         Method GetPathLength:Int()
  472.                 If Path <> FOUND Return - 1
  473.                 Return Steps.Count()
  474.         End Method
  475.        
  476.         rem
  477.         bbdoc:  Return the length (in pixels) of the FOUND path (going through the center of each tile)
  478.         end rem
  479.         Method GetPathDistance:Int(DiagonalCost:Int = 14, VertHorzCost:Int = 10)
  480.                 If Path <> FOUND Return - 1
  481.                 Local a:Int[] = GetPathInt()
  482.                 Local cost:Int
  483.                 For Local i:Int = 0 Until a.Length
  484.                         Select a[i]
  485.                                 Case 1;cost:+VertHorzCost
  486.                                 Case 2;cost:+DiagonalCost
  487.                                 Case 3;cost:+VertHorzCost
  488.                                 Case 4;cost:+DiagonalCost
  489.                                 Case 5;cost:+VertHorzCost
  490.                                 Case 6;cost:+DiagonalCost
  491.                                 Case 7;cost:+VertHorzCost
  492.                                 Case 8;cost:+DiagonalCost
  493.                         End Select
  494.                 Next
  495.                 Return cost
  496.         End Method
  497.        
  498.         rem
  499.         bbdoc:  Return True if a path has been found after the last Search() call
  500.         end rem
  501.         Method PathFound:Int()
  502.                 If Path = FOUND Then Return 1
  503.         End Method
  504.        
  505. End Type


Comments :


coffeedotbean(Posted 11 months ago)

 Download this and a demo.bmx from my google drive <a href="https://drive.google.com/open?id=0B1jBbicq8v_dWk5FRVlWWVZnRFE" target="_blank">https://drive.google.com/open?id=0B1jBbicq8v_dWk5FRVlWWVZnRFE[/url]


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal