Ooops
March 05, 2021, 06:16:02 AM

Author Topic: [bmx] Breadth-first pathfinder by Andres [ 1+ years ago ]  (Read 434 times)

Offline BlitzBot

[bmx] Breadth-first pathfinder by Andres [ 1+ years ago ]
« on: June 29, 2017, 12:28:42 AM »
Title : Breadth-first pathfinder
Author : Andres
Posted : 1+ years ago

Description : Here's an easy to use pathfinder, made it as portable as possible. Uses only 4 functions. Supports 2D and 3D maps (map's depth).
The pathmap is filled with flags like:
PATH_TOP, PATH_BOTTOM, PATH_LEFT, PATH_RIGHT, PATH_CEIL, PATH_FLOOR, PATH_ALL

As you can see it doesn't support just 1/0 maps, but also can handle walls (hope you understand what i mean :)

The path returned by FindPath() is a string (something like "11444422222222223331123") where 1 - north, 2 - south, 3 - west, 4 - east, 5 - up, 6 - down.



Functions:
Code: [Select]
CreatePathmap:TPathmap(width:Long, height:Long, depth:Long = 1)
PathmapSlot(this:TPathmap, flags:Int, x:Long, y:Long, z:Long = 0) ' Used to fill pathmap with information
FindPath:String(this:TPathmap, x1:Long, y1:Long, z1:Long, x2:Long, y2:Long, z2:Long) ' finds the path in a pathmap from position x1, y1, z1 to x2, y2, z2
FreePathmap(this:TPathmap)


Example:
Code: [Select]
SuperStrict

Graphics(800, 600)
SeedRnd(MilliSecs())

Global map_width:Int = 80
Global map_height:Int = 60

Include "pathfind.bmx"

' Create level
Global map:Int[map_width, map_height]
For Local y:Int = 0 To map_height -1
For Local x:Int = 0 To map_width - 1
If Rand(0, 5) < 2 Then map[x, y] = PATH_ALL
Next
Next

' Create pathmap
Global pathmap:TPathmap = CreatePathmap:TPathmap(map_width, map_height)
Global path:String = ""

' Copy level to pathmap
For Local y:Long = 0 To map_height -1
For Local x:Long = 0 To map_width - 1
PathmapSlot(pathmap, map[x, y], x, y)
Next
Next

While Not KeyHit(KEY_ESCAPE)
Cls()

' Draw level
For Local y:Int = 0 To map_height -1
For Local x:Int = 0 To map_width - 1
If CheckFlag(map[x, y], PATH_ALL)
SetColor(255, 0, 0)
Else
SetColor(255, 255, 255)
EndIf
DrawRect(x * 10, y * 10, 10, 10)
Next
Next

' 1 - north, 2 - south, 3 - west, 4 - east, 5 - up, 6 - down
path = FindPath(pathmap, map_width / 2, map_height / 2, 0, MouseX() / 10.0, MouseY() / 10.0, 0)

' Draw the PATH
If Len(path) > 0
SetColor(0, 0, 255)
Local x:Long = map_width / 2, y:Long = map_height / 2
For Local i:Int = 1 To Len(path)
Select Mid(path, i, 1)
Case "1"
y :- 1
Case "2"
y :+ 1
Case "3"
x :- 1
Case "4"
x :+ 1
End Select
DrawOval(x * 10, y * 10, 10, 10)
Next
EndIf

Flip()
Wend

FreePathmap(pathmap)


Code :
Code: BlitzMax
  1. Const FLAG1:Int = $01
  2. Const FLAG2:Int = $02
  3. Const FLAG4:Int = $04
  4. Const FLAG8:Int = $08
  5. Const FLAG16:Int = $10
  6. Const FLAG32:Int = $20
  7. Const FLAG64:Int = $40
  8. Const FLAG128:Int = $80
  9.  
  10. Function CheckFlag:Int(flags:Int, flag:Int)
  11.         If flags & flag Then Return True Else Return False
  12. End Function
  13.  
  14. Const PATH_TOP:Int = FLAG1
  15. Const PATH_BOTTOM:Int = FLAG2
  16. Const PATH_LEFT:Int = FLAG4
  17. Const PATH_RIGHT:Int = FLAG8
  18. Const PATH_CEIL:Int = FLAG16
  19. Const PATH_FLOOR:Int = FLAG32
  20. Const PATH_ALL:Int = FLAG64
  21.  
  22. ' List used for path find
  23. Global pathmap_path_list:TList = CreateList()
  24.  
  25. ' Pathmap type
  26. Type TPathmap
  27.         Field width:Long, height:Long, depth:Long
  28.        
  29.         Field map:TBank
  30. End Type
  31.  
  32. Type TPath
  33.         Field x:Long, y:Long, z:Long
  34.         Field path:String
  35. End Type
  36.  
  37. ' Create a new pathmap
  38. Function CreatePathmap:TPathmap(width:Long, height:Long, depth:Long = 1)
  39.         Local this:TPathmap = New TPathmap
  40.                 this.width = width
  41.                 this.height = height
  42.                 this.depth = depth
  43.                
  44.                 this.map = CreateBank(this.width * this.height * this.depth)
  45.                
  46.         Return this
  47. End Function
  48.  
  49. ' Insert flags to pathmap slot
  50. Function PathmapSlot(this:TPathmap, flags:Int, x:Long, y:Long, z:Long = 0)
  51.         Local offset:Long = (z * this.width * this.height) + (y * this.width) + x
  52.         PokeByte(this.map, offset, flags)
  53. End Function
  54.  
  55. ' Search for a path within pathmap; 1 - north, 2 - south, 3 - west, 4 - east, 5 - up, 6 - down
  56. Function FindPath:String(this:TPathmap, x1:Long, y1:Long, z1:Long, x2:Long, y2:Long, z2:Long)
  57.         Local offset:Long, offset_top:Long, offset_bottom:Long, offset_left:Long, offset_right:Long, offset_ceil:Long, offset_floor:Long
  58.        
  59.         Local temp_bank:TBank = CreateBank(BankSize(this.map))
  60.         CopyBank(this.map, 0, temp_bank, 0, BankSize(this.map))
  61.        
  62.         ClearList(pathmap_path_list)
  63.         Local that:TPath = New TPath
  64.                 that.x = x1
  65.                 that.y = y1
  66.                 that.z = z1
  67.                 that.path = ""
  68.                 ListAddFirst(pathmap_path_list, that)
  69.                 ListAddFirst(pathmap_path_list, that)
  70.        
  71.         For that:TPath = EachIn pathmap_path_list
  72.                 offset = (that.z * this.width * this.height) + (that.y * this.width) + that.x
  73.                
  74.                 ' TOP
  75.                 If that.y > 0
  76.                         offset_top = (that.z * this.width * this.height) + ((that.y - 1) * this.width) + that.x
  77.                         If Not CheckFlag(PeekByte(temp_bank, offset), PATH_TOP) And Not CheckFlag(PeekByte(temp_bank, offset_top), PATH_BOTTOM) And Not CheckFlag(PeekByte(temp_bank, offset_top), PATH_ALL)
  78.                                 Local pth:TPath = New TPath
  79.                                         pth.x = that.x
  80.                                         pth.y = that.y - 1
  81.                                         pth.z = that.z
  82.                                         pth.path = that.path + "1"
  83.                                         ListAddLast(pathmap_path_list, pth)
  84.                                         PokeByte(temp_bank, offset_top, PATH_ALL)
  85.                         EndIf
  86.                 EndIf
  87.                 ' LEFT
  88.                 If that.x > 0
  89.                         offset_left = (that.z * this.width * this.height) + (that.y * this.width) + that.x - 1
  90.                         If Not CheckFlag(PeekByte(temp_bank, offset), PATH_LEFT) And Not CheckFlag(PeekByte(temp_bank, offset_left), PATH_RIGHT) And Not CheckFlag(PeekByte(temp_bank, offset_left), PATH_ALL)
  91.                                 Local pth:TPath = New TPath
  92.                                         pth.x = that.x - 1
  93.                                         pth.y = that.y
  94.                                         pth.z = that.z
  95.                                         pth.path = that.path + "3"
  96.                                         ListAddLast(pathmap_path_list, pth)
  97.                                         PokeByte(temp_bank, offset_left, PATH_ALL)
  98.                         EndIf
  99.                 EndIf
  100.                 ' BOTTOM
  101.                 If that.y + 1 < this.height
  102.                         offset_bottom = (that.z * this.width * this.height) + ((that.y + 1) * this.width) + that.x
  103.                         If Not CheckFlag(PeekByte(temp_bank, offset), PATH_BOTTOM) And Not CheckFlag(PeekByte(temp_bank, offset_bottom), PATH_TOP) And Not CheckFlag(PeekByte(temp_bank, offset_bottom), PATH_ALL)
  104.                                 Local pth:TPath = New TPath
  105.                                         pth.x = that.x
  106.                                         pth.y = that.y + 1
  107.                                         pth.z = that.z
  108.                                         pth.path = that.path + "2"
  109.                                         ListAddLast(pathmap_path_list, pth)
  110.                                         PokeByte(temp_bank, offset_bottom, PATH_ALL)
  111.                         EndIf
  112.                 EndIf
  113.                 ' RIGHT
  114.                 If that.x + 1 < this.width
  115.                         offset_right = (that.z * this.width * this.height) + (that.y * this.width) + that.x + 1
  116.                         If Not CheckFlag(PeekByte(temp_bank, offset), PATH_RIGHT) And Not CheckFlag(PeekByte(temp_bank, offset_right), PATH_LEFT) And Not CheckFlag(PeekByte(temp_bank, offset_right), PATH_ALL)
  117.                                 Local pth:TPath = New TPath
  118.                                         pth.x = that.x + 1
  119.                                         pth.y = that.y
  120.                                         pth.z = that.z
  121.                                         pth.path = that.path + "4"
  122.                                         ListAddLast(pathmap_path_list, pth)
  123.                                         PokeByte(temp_bank, offset_right, PATH_ALL)
  124.                         EndIf
  125.                 EndIf
  126.                
  127.                 ' If the pathmap has 3 dimensions
  128.                 If this.depth > 1
  129.                         If that.z > 0
  130.                                 offset_ceil = ((that.z - 1) * this.width * this.height) + (that.y * this.width) + that.x
  131.                                 If Not CheckFlag(PeekByte(temp_bank, offset), PATH_CEIL) And Not CheckFlag(PeekByte(temp_bank, offset_ceil), PATH_FLOOR) And Not CheckFlag(PeekByte(temp_bank, offset_ceil), PATH_ALL)
  132.                                         Local pth:TPath = New TPath
  133.                                                 pth.x = that.x
  134.                                                 pth.y = that.y - 1
  135.                                                 pth.z = that.z
  136.                                                 pth.path = that.path + "5"
  137.                                                 ListAddLast(pathmap_path_list, pth)
  138.                                                 PokeByte(temp_bank, offset_ceil, PATH_ALL)
  139.                                 EndIf
  140.                         EndIf
  141.                         If that.z + 1< this.depth
  142.                                 offset_floor = ((that.z + 1) * this.width * this.height) + (that.y * this.width) + that.x
  143.                                 If Not CheckFlag(PeekByte(temp_bank, offset), PATH_FLOOR) And Not CheckFlag(PeekByte(temp_bank, offset_floor), PATH_CEIL) And Not CheckFlag(PeekByte(temp_bank, offset_floor), PATH_ALL)
  144.                                         Local pth:TPath = New TPath
  145.                                                 pth.x = that.x
  146.                                                 pth.y = that.y + 1
  147.                                                 pth.z = that.z
  148.                                                 pth.path = that.path + "6"
  149.                                                 ListAddLast(pathmap_path_list, pth)
  150.                                                 PokeByte(temp_bank, offset_floor, PATH_ALL)
  151.                                 EndIf
  152.                         EndIf
  153.                 EndIf
  154.                
  155.                 ' CORRECT PATH FOUND
  156.                 If that.x = x2 And that.y = y2 And that.z = z2
  157.                         Local path:String = that.path
  158.                         ClearList(pathmap_path_list)
  159.                         temp_bank = Null
  160.                         Return path
  161.                 EndIf
  162.                
  163.                 ' Return false if there is no solution
  164.                 If ListIsEmpty(pathmap_path_list) Then
  165.                         temp_bank = Null
  166.                         Return "[ERROR]"
  167.                 EndIf
  168.                                
  169.                 ' Remove the parent
  170.                 ListRemove(pathmap_path_list, that)
  171.                 that = Null
  172.         Next
  173.         Return "FAILED"
  174. End Function
  175.  
  176. ' Remove pathmap from memory
  177. Function FreePathmap(this:TPathmap)
  178.         this.map = Null
  179. End Function


Comments :


markcw(Posted 1+ years ago)

 That was cool, Andres.


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal