December 03, 2020, 07:43:55 PM

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

#### 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()
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.
208.         Restore level
209.         For y = 0 To mapheight
210.         For x = 0 To mapwidth
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

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.