December 03, 2020, 07:43:55 PM

Author Topic: [bb] A Star Pathfinding by Pakz [ 1+ years ago ]  (Read 553 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bb] A Star Pathfinding by Pakz [ 1+ years ago ]
« on: June 29, 2017, 12:28:40 AM »
Title : A Star Pathfinding
Author : Pakz
Posted : 1+ years ago

Description : I had bought the book ai for game developers and there was a chapter about pathfinding in it. I programmed a blitz basic version.

The program has a maze where every second a new path is calculated. Hold escape key to exit.

edit : I shortened the code.


Code :
Code: BlitzBasic
  1. Graphics 640,480,32,2
  2. SetBuffer BackBuffer()
  3. Global sx,sy,ex,ey
  4. Global mapwidth = 39
  5. Global mapheight = 29
  6. Global cellwidth = 16
  7. Global cellheight = 16
  8. Dim map(mapwidth,mapheight)
  9. Type ol
  10.         Field x,y,f,g,h,px,py
  11. End Type
  12. Type cl
  13.         Field x,y,f,g,h,px,py
  14. End Type
  15. Type path
  16.         Field x,y
  17. End Type
  18. SeedRnd MilliSecs()
  19. readmap()
  20.  
  21. While KeyDown(1) = False
  22.         Cls
  23.         setcoordinates()
  24.         drawmap()
  25.         tim = MilliSecs()
  26.         findpath()
  27.         tim = MilliSecs()-tim
  28.         drawpath()
  29.         Color 0,0,0
  30.         Rect 0,0,GraphicsWidth(),12,True
  31.         Color 255,0,0
  32.         Text 0,0,"time taken "+tim
  33.         Flip
  34.         Delay 1000
  35. Wend
  36. End
  37.  
  38. Function findpath()
  39.         ; Remove old pathfinding data
  40.         Delete Each ol
  41.         Delete Each cl
  42.         Delete Each path
  43.         ; Move the start position onto the open list
  44.         d.ol = New ol
  45.         dx = sx
  46.         dy = sy
  47.         Local exitloop = False
  48.         Local tx,ty,tf,tg,th,tpx,tpy,newx,newy,lowestf
  49.         While exitloop = False
  50.                 ; If the open list is empty then exit loop (path not found)
  51.                 If openlistisempty() = True Then exitloop = True
  52.                 ; Get the position from the open list with the lowest f value
  53.                 lowestf = 100000
  54.                 For e.ol = Each ol
  55.                         If ef < lowestf Then
  56.                                 lowestf = ef
  57.                                 tx = ex
  58.                                 ty = ey
  59.                                 tf = ef
  60.                                 tg = eg
  61.                                 th = eh
  62.                                 tpx = epx
  63.                                 tpy = epy
  64.                         End If
  65.                 Next
  66.                 ; If the current position is the end position then path is found
  67.                 If tx = ex And ty = ey Then
  68.                         exitloop = True
  69.                         f.cl = New cl
  70.                         fx = tx
  71.                         fy = ty
  72.                         ff = tf
  73.                         fg = tf
  74.                         fh = th
  75.                         fpx = tpx
  76.                         fpy = tpy
  77.                         findpathback()
  78.                         Else
  79.                         ; Move the current position to the closed list
  80.                         g.cl = New cl
  81.                         gx = tx
  82.                         gy = ty
  83.                         gf = tf
  84.                         gg = tg
  85.                         gh = th
  86.                         gpx = tpx
  87.                         gpy = tpy
  88.                         ; Remove the current position from the open list
  89.                         removefromopenlist(tx,ty)
  90.                         ; Get the eight positions from around the current position
  91.                         ; and move them to the open list
  92.                         ;
  93.                         For y=-1 To 1
  94.                         For x=-1 To 1
  95.                         newx = tx + x
  96.                         newy = ty + y
  97.                         If newx > -1 And newy > -1 And newx < mapwidth+1 And newy < mapheight+1
  98.                         If isonopenlist(newx,newy) = False Then
  99.                         If isonclosedlist(newx,newy) = False Then
  100.                         If map(newx,newy) = 0 Then
  101.                                 h.ol = New ol
  102.                                 hx = newx
  103.                                 hy = newy
  104.                                 hg = tg + 1
  105.                                 hh = distance(newx,newy,ex,ey)
  106.                                 hf = hg+hh
  107.                                 hpx = tx
  108.                                 hpy = ty
  109.                         End If
  110.                         End If
  111.                         End If
  112.                         End If
  113.                         Next
  114.                         Next
  115.                        
  116.                 End If
  117.         Wend
  118. End Function
  119.  
  120. Function findpathback()
  121.         Local exitloop = False
  122.         x = ex
  123.         y = ey
  124.         While exitloop = False
  125.                 For this.cl = Each cl
  126.                         If x = thisx And y = thisy Then
  127.                                 x = thispx
  128.                                 y = thispy
  129.                                 that.path = New path
  130.                                 thatx = x
  131.                                 thaty = y
  132.                         End If
  133.                 Next
  134.                 If x = sx And y = sy Then exitloop = True
  135.         Wend
  136. End Function
  137.  
  138. Function drawpath()
  139.         Color 255,255,0
  140.         For this.path = Each path
  141.                 Oval thisx*cellwidth+4,thisy*cellheight+4,8,8,True
  142.         Next
  143. End Function
  144.  
  145. Function openlistisempty()
  146.         Local count = 0
  147.         For this.ol = Each ol
  148.                 count = count + 1
  149.                 If count > 0 Then Return False
  150.         Next
  151.         If count = 0 Then Return True
  152. End Function
  153.  
  154. Function isonclosedlist(x,y)
  155.         For this.cl = Each cl
  156.                 If thisx = x And thisy = y Then Return True
  157.         Next
  158.         Return False
  159. End Function
  160.  
  161. Function isonopenlist(x,y)
  162.         For this.ol = Each ol
  163.                 If thisx = x And thisy = y Then Return True
  164.         Next
  165.         Return False
  166. End Function
  167.  
  168. Function removefromopenlist(x,y)
  169.         For this.ol = Each ol
  170.                 If thisx = x And thisy = y Then
  171.                         Delete this
  172.                         Return
  173.                 End If
  174.         Next
  175. End Function
  176.  
  177. Function setcoordinates()
  178.         Local exitloop = False
  179.         While exitloop = False
  180.                 sx = Rand(mapwidth)
  181.                 sy = Rand(mapheight)
  182.                 ex = Rand(mapwidth)
  183.                 ey = Rand(mapheight)
  184.                 If map(sx,sy) = 0 And map(ex,ey) = 0 Then
  185.                         If sx<>ex And sy<>ey Then
  186.                                 exitloop = True
  187.                         End If
  188.                 End If
  189.         Wend
  190. End Function
  191.  
  192. Function drawmap()
  193.         Color 0,0,255
  194.         For y = 0 To mapheight
  195.         For x = 0 To mapwidth
  196.                 If map(x,y) = 1 Then
  197.                         Rect x*cellwidth,y*cellheight,cellwidth,cellheight,True
  198.                 End If
  199.         Next
  200.         Next
  201.         Color 0,255,0
  202.         Oval sx*cellwidth+8,sy*cellheight+8,8,8,True
  203.         Color 255,0,0
  204.         Oval ex*cellwidth+8,ey*cellheight+8,8,8,True
  205. End Function
  206.  
  207. Function readmap()
  208.         Restore level
  209.         For y = 0 To mapheight
  210.         For x = 0 To mapwidth
  211.                 Read a
  212.                 map(x,y) = a
  213.         Next
  214.         Next
  215. End Function
  216.  
  217. Function distance(x1,y1,x2,y2)
  218.         Return Sqr( ( x1 - x2 ) * ( x1 - x2 ) + ( y1 - y2 ) * ( y1 - y2 ) )
  219. End Function
  220.  
  221. .level
  222. Data 0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0
  223. Data 0,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,0
  224. Data 0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0
  225. Data 0,1,1,1,1,1,0,1,0,1,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0
  226. Data 0,1,0,0,0,1,0,1,0,1,0,1,1,1,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0
  227. Data 0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,0,1,0,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0
  228. Data 0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0
  229. Data 0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0
  230. Data 0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0
  231. Data 0,1,0,1,0,1,0,1,0,0,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0
  232. Data 0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,1,0,1,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0
  233. Data 0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,0,1,0,1,0,0,1,0,1,0,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0
  234. Data 0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0
  235. Data 0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0
  236. Data 0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0
  237. Data 1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1
  238. Data 0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0
  239. Data 0,0,0,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0
  240. Data 0,0,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0
  241. Data 0,0,0,1,0,1,1,1,0,1,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0
  242. Data 0,0,0,1,0,1,0,1,0,1,0,0,0,1,1,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0
  243. Data 0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0
  244. Data 0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0
  245. Data 0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0
  246. Data 0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0
  247. Data 0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0
  248. Data 0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,1,0,1,0,0,1,0,1,0,0
  249. Data 0,0,0,1,0,1,0,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,1,0,1,0,0,1,0,1,0,0
  250. Data 0,0,0,1,0,1,1,1,1,1,0,1,0,1,1,1,1,0,1,0,1,1,1,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,0
  251. Data 0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,0


Comments :


virtlands(Posted 1+ years ago)

 I do like this a lot.....


Guy Fawkes(Posted 1+ years ago)

 PACMAN REMAKE TIME! =D


virtlands(Posted 1+ years ago)

 I agree, Pakz should do a Pak-Man.  


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal