July 29, 2021, 09:45:50

### Author Topic: [bb] Pathfinding (Pre calculated 2D) by Matty [ 1+ years ago ]  (Read 767 times)

#### BlitzBot

• Jr. Member
• Posts: 1
##### [bb] Pathfinding (Pre calculated 2D) by Matty [ 1+ years ago ]
« on: June 29, 2017, 00:28:43 »
Title : Pathfinding (Pre calculated 2D)
Author : Matty
Posted : 1+ years ago

Description : Pathfinding routine I use in my games

Code :
Code: BlitzBasic
1. Const PathUp=1,PathDown=2,PathLeft=3,PathRight=4
2. ;Const MaxX=31,MaxZ=31
3. Global MaxX=7 ;horizontal number of grid squares (0-25) so 26 really
4. Global MaxZ=7 ;vertical number of grid squares (0-25)
5. Const MaxDepth=125 ;how deep to search, if a path to a point is longer than this then it won't find one....
6.
7. ;Be careful how high you set the MaxX,MaxZ as the pathfinding array is a 4 dimensional array
8. ;so doubling MaxX,MaxZ will multiply the size of the array by 16.  I really only need to use
9. ;3 bits per 'array slot' so a bank would be much more memory efficient (instead of the 32 bits used
10. ;here!)
11. ;
12. ;This is not the most memory efficient path finding method but for my game it works.  It would be suitable
13. ;for 2d games with small play areas and reasonably static environments...
14. ;
15. ;If you have only a small number of units that need to do pathfinding it can be used to calculate
16. ;paths in real time with a few adjustments.
17. ;
18. ;
19. ;This pathfinding method works better when the play area is full of obstacles.  The more open the
20. ;map the longer it will take to pre calculate the paths....Worst case scenario is a totally open
21. ;play area with no walls at all...
22. ;
23.
24. Graphics 800,600,32,2
25.
26. Dim MapArray(MaxX,MaxZ,1)
27. Dim PathfindingArray(MaxX,MaxZ,MaxX,MaxZ)
28. Dim PathArray(MaxX,MaxZ)
29. Dim PathTempArray(MaxX,MaxZ)
30. Dim PathToTake(MaxDepth,2)
31.
32. ;goto skiptohere ;uncomment this out if you wish to try pre calculating a path...you need to supply
33. ;your own map file (format described below) and may need to alter the MaxX,MaxZ values and perhaps MaxDepth above...current
34. ;value for MaxDepth should be suitable for Maps of size 25x25
35.
36.
37. ;Obviously you will use larger maps than the one shown here.
38.
39.
40. Data 1,1,1,1,1,1,1,1
41. Data 1,0,0,1,0,1,0,1
42. Data 1,0,0,0,0,1,0,1
43. Data 1,0,1,1,1,1,0,1
44. Data 1,0,0,0,0,0,0,1
45. Data 1,0,1,1,0,1,1,1
46. Data 1,0,1,0,0,0,0,1
47. Data 1,1,1,1,1,1,1,1
48.
49. For Z=0 To MaxZ
50. For X=0 To MaxX
51. Read MapArray(X,Z,0)
52. PathArray(x,z)=MapArray(x,z,0)
53.
54. Next
55. Next
56. CalculatePathFindingArray()
57. DisplayTestPathFinding()
58.
59. End
60. .skiptohere
61.
62. inmapfile=ReadFile("Your Map File Here")
63. If inmapfile=0 Then RuntimeError("You have to put a valid map file in for this to work")
64. ;
65. ;Map file should be generated in the following way:
66. ;outfile=writefile("Your Map File Here")
67. ;if outfile=0 then runtimeerror("Could not create map file for some reason...")
68. ;For x=0 to maxx
69. ;       for z=0 to maxz
70. ;       writebyte outfile,MapArray(x,z,0) ;MapArray(x,z,0)=0 for open grid square, MapArray(x,z,0)=1 for blocked grid square
71. ;
72. ;       next
73. ;next
74. ;closefile outfile
75.
76.
77. For x=0 To maxx
78.         For z=0 To maxz
79.                 MapArray(x,z,0)=ReadByte(inmapfile)
80.                 PathArray(x,z)=MapArray(x,z,0)
81.         Next
82. Next
83.
84.
85. CloseFile inmapfile
86.
87. CalculatePathFindingArray()
88.
89. outfile=WriteFile("your pre calculated path file name goes here")
90. If outfile=0 Then RuntimeError("something went wrong trying to write the path finding file to disk")
91. For Xi=0 To MaxX
92. For Zi=0 To MaxZ
93. For Xf=0 To MaxX
94. For Zf=0 To MaxZ
95. WriteByte outfile,PathFindingArray(xi,zi,xf,zf)
96. Next
97. Next
98. Next
99. Next
100.
101.
102. CloseFile outfile
103.
104.
105.
106. Function CalculatePathFindingArray(MapValue=0)
107.
108. starttime=MilliSecs()
109.
110.
111. For Xi=0 To MaxX
112.         For Zi=0 To MaxZ
113.                 For Xf=0 To MaxX
114.                         For Zf=0 To MaxZ
115.                                 If MapArray(Xi,Zi,0)=0 And MapArray(Xf,Zf,0)=0 Then
116.                                         PathFindingArray(Xi,Zi,Xf,Zf)=NewPathFind(Xi,Zi,Xf,Zf,MaxDepth)
117.
118.                                         If KeyDown(57) Then
119.                                                 Cls
120.                                                 Text 0,0,"Progress:Xi="+Xi+", Zi="+Zi+", Xf="+Xf+", Zf="+Zf
121.                                                 Flip
122.                                         EndIf
123.
124.                                         If MilliSecs()-calctime>5000 Then
125.                                                 calctime=MilliSecs()
126.                                                 Cls
127.                                                 Text 0,0,"Progress:"+100.0*Float(Xi*MaxX*MaxZ*MaxX+Zi*MaxX*MaxZ+Xf*MaxX+Zf)/Float(MaxX*MaxZ*MaxX*MaxZ)+"%"+", Map Number:"+Mapvalue
128.                                                 secondssofar=(MilliSecs()-starttime)/1000
129.                                                 mins=secondssofar/60
130.                                                 secs=secondssofar Mod 60
131.                                                 Text 0,15,"Time:"+mins+":"+secs
132.                                                 Flip
133.                                         EndIf
134.
135.                                         If KeyDown(1) Then End
136.                                 EndIf
137.                         Next
138.                 Next
139.         Next
140. Next
141.
142.
143. End Function
144.
145. Function NewPathFind(Column,Row,TargetColumn,TargetRow,Depth)
146. ;
147.
148. PathString\$="" ;no longer used anyway - it was originally used for storing a sequence of grid squares for another game
149.
150. Dim PathTempArray(MaxX,MaxZ) ;
151. Dim PathToTake(MaxDepth,2)
152.
153. If Depth>MaxDepth Then Depth=MaxDepth
154. If PathArray(Column,Row)<>0 Then Return 0 ;if the starting square is blocked then don't do any calculations
155.
156. If Column>=0 And Row>=0 And TargetColumn>=0 And TargetRow>=0 And Column<=MaxX And Row<=MaxZ And TargetColumn<=MaxX And TargetRow<=MaxZ Then
157. ;make sure that the starting square and finishing square is within the grid
158.
159.         MaxIndex=DepthSearch(Column,Row,TargetColumn,TargetRow,1,Depth) ;do a recursive search for the shortest route
160.         If MaxIndex>0 Then ;this little section no longer used, was used for another game...
161.
162.                 PathString\$=LSet(Str(PathToTake(1,1)),4)+LSet(Str(PathToTake(1,2)),4)
163. ;               For i=MaxIndex-1 To 1 Step -1
164. ;                       PathString\$=PathString\$+LSet(Str(PathToTake(i,1)),4)+LSet(Str(PathToTake(i,2)),4)
165. ;               Next
166.
167.         Else
168.                 PathString\$=""
169.         EndIf
170.
171. Else
172.
173.
174. EndIf
175. PathDirection=0
176. ;If PathToTake(1,1)<Column Then PathDirection=PathLeft
177. ;If PathToTake(1,1)>Column Then PathDirection=PathRight
178. ;If PathToTake(1,2)<Row Then PathDirection=PathUp
179. ;If PathToTake(1,2)>Row Then PathDirection=PathDown
180. ;return PathDirection
181.
182. Return PathToTake(1,0) ;PathToTake basically tells us which square to go to (up one or left one or right one or down one )
183.
184.
185. End Function
186.
187. Function DepthSearch(X,Y,TX,TY,N,Depth)
188. ;
189. ;I made this function quite some time ago that I no longer remember how it works...but it does
190. ;
191. ;
192. ;
193. ;
194.
195. If N>Depth Then Return 0 ;if we have searched too deep then return 0 - no path found
196.
197. PathTempArray(X,Y)=N ;assign the gridsquare we are searching a value indicating how many moves from our starting point we are (also equal to the depth of the search so far)
198.
199. If X=TX And Y=TY Then Return N ;if we are at our target square then exit and return the number of moves it took to get there
200.
201. AlreadyKnowTheWay=False ;this was a vain attempt at optimising the code, it doesn't work feel free to delete it...
202. ;If PathFindingArray(X,Y,TX,TY)<>0 Then AlreadyKnowTheWay=True
203.
204.
205. ;the next 4 if statements perform recursive searches in each of the 4 directions that movement is allowed in
206. ;if you had an 8 directional movement system for your AI units then you would need additional bits here...
207. ;the final value of MaxIndex1..MaxIndex4 tells us how many squares it took us to get to the target going in a certain direction from our current point...
208. ;
209.
210.
211. If X>0 And AlreadyKnowTheWay=False Then
212.
213.         If PathArray(X-1,Y)=0 And (PathTempArray(X-1,Y)=0 Or PathTempArray(X-1,Y)>N+1) Then MaxIndex1=DepthSearch(X-1,Y,TX,TY,N+1,Depth)
214.         ;above line checks if the square to our left is open (ie we can move there)
215.         ;it also checks (PathTempArray(X-1,Y)>N+1) if going to the square to our left would take less moves to get there in total then
216.         ;what previous searches have already calculated for that square...
217. EndIf
218. If Y>0  And AlreadyKnowTheWay=False Then
219.         If PathArray(X,Y-1)=0 And (PathTempArray(X,Y-1)=0 Or PathTempArray(X,Y-1)>N+1) Then MaxIndex2=DepthSearch(X,Y-1,TX,TY,N+1,Depth)
220. EndIf
221.
222. If X<MaxX And AlreadyKnowTheWay=False Then
223.         If PathArray(X+1,Y)=0 And (PathTempArray(X+1,Y)=0 Or PathTempArray(X+1,Y)>N+1) Then MaxIndex3=DepthSearch(X+1,Y,TX,TY,N+1,Depth)
224. EndIf
225.
226. If Y<MaxZ And AlreadyKnowTheWay=False Then
227.         If PathArray(X,Y+1)=0 And (PathTempArray(X,Y+1)=0 Or PathTempArray(X,Y+1)>N+1) Then MaxIndex4=DepthSearch(X,Y+1,TX,TY,N+1,Depth)
228. EndIf
229.
230.
231. If AlreadyKnowTheWay=False Then ;this will always be false, not really needed
232. MinIndex=MaxDepth+1
233.
234. If MaxIndex1<MinIndex And MaxIndex1<>0 Then MinIndex=MaxIndex1:PathToTake(N,0)=PathLeft:PathToTake(N,1)=X-1:PathToTake(N,2)=Y
235. If MaxIndex2<MinIndex And MaxIndex2<>0 Then MinIndex=MaxIndex2:PathToTake(N,0)=PathUp:PathToTake(N,1)=X:PathToTake(N,2)=Y-1
236. If MaxIndex3<MinIndex And MaxIndex3<>0 Then MinIndex=MaxIndex3:PathToTake(N,0)=PathRight:PathToTake(N,1)=X+1:PathToTake(N,2)=Y
237. If MaxIndex4<MinIndex And MaxIndex4<>0 Then MinIndex=MaxIndex4:PathToTake(N,0)=PathDown:PathToTake(N,1)=X:PathToTake(N,2)=Y+1
238. ;basically this compares each of the 4 directions initially chosen to get to our target point and
239. ;sets the "PathToTake" to be the one which was shortest.
240.
241.
242. If MinIndex=MaxDepth+1 Then
243.         Return 0
244. Else
245.         Return MinIndex
246. EndIf
247. Else
248. PathToTake(N,0)=PathFindingArray(X,Y,TX,TY)
249. Return 0
250.
251. EndIf
252.
253. End Function
254.
255.
256. Function DisplayTestPathFinding()
257.
258.
259.
260. xi=0
261. zi=maxz-1
262. Repeat
263. Cls
264. For x=0 To maxx
265. For z=0 To maxz
266. If maparray(x,z,0)=1 Then
267. Color 80,80,80
268. Rect x*10,z*10,10,10,1
269. EndIf
270. Next
271. Next
272.
273.
274. If MilliSecs()-its>1000 Or KeyHit(57)>0 Or maparray(xi,zi,0)=1 Or maparray(tx,tz,0)=1 Then
275. FlushKeys()
276. its=MilliSecs()
277. xi=xi-1
278. If xi<0 Then xi=maxx:zi=zi-1
279. If zi<0 Then zi=maxz
280. tx=Rand(0,maxx)
281. tz=Rand(0,maxz)
282. EndIf
283. If maparray(xi,zi,0)=0 And maparray(tx,tz,0)=0 Then
284. jits=0
285. nx=xi
286. nz=zi
287. Repeat
288. jits=jits+1
289. If jits=1 Then Color 255,0,255 Else Color 255,255,0
290. Rect 2+nx*10,2+nz*10,6,6,1
291.
292. Select pathfindingarray(nx,nz,tx,tz)
293.
294. Case pathup
295. nz=nz-1
296. Case pathdown
297. nz=nz+1
298. Case pathright
299. nx=nx+1
300. Case pathleft
301. nx=nx-1
302. Default
303. ;do nothing
304. End Select
305. Until jits>MaxDepth Or (nx=tx And nz=tz)
306. Color 0,255,0
307. Rect 2+tx*10,2+tz*10,6,6,1
308.
309. Else
310. its=its+1000
311. EndIf
312. Flip
313. Until KeyDown(1)>0
314.
315.
316. End Function
317.
318. Function readmapfile(filename\$)
319. infile=ReadFile(filename)
320. For x=0 To MaxX
321. For z=0 To MaxZ
322. ;MapArray(x,z,0);=Maze(x,sy-z)
323. maparray(x,z,0)=ReadByte(infile)
324. PathArray(x,z)=MapArray(x,z,0)
325. Next
326. Next
327. CloseFile infile
328.
329. End Function
330.
331. Function readpathfile(filename\$)
332. infile=ReadFile(filename)
333. For Xi=0 To MaxX
334. For Zi=0 To MaxZ
335. For Xf=0 To MaxX
336. For Zf=0 To MaxZ
337. PathFindingArray(xi,zi,xf,zf)=ReadByte(infile)
338. Next
339. Next
340. Next
341. Next
342.
343.
344. CloseFile infile
345. End Function

Comments :

Damien Sturdy(Posted 1+ years ago)

Blooming excelent I'm going to test this against my own code later- probrably converting this to work in simple 3D environments along the way- i recon this will beat mine since it *only* takes 5-10 minutes to calc against my 30-60. Very good work!

CS_TBL(Posted 1+ years ago)

I took the opportunity to clean-up this code, but after deleting overhead/unimportant functions and commented/unimportant code I finally found out the idea behind this pathfinding. The idea is funny, but unsuitable for a game in which the map may change (think Warcraft etc.).Is it true that for every start and end it finds a complete path but only stores the first step? Is it possible to get the *complete* path somehow? I wish to get rid of the precalc idea and just have a function which returns a bank with coordinates upon a simple sx,sy,dx,dy,depth request.coord-bank would be:step 1: (short)x (short)ystep 2: (short)x (short)ystep 3: (short)x (short)ystep 4: (short)x (short)ystep 5: (short)x (short)yetc.So, 4 bytes per step, leading to a max of 600 bytes for a search-depth of 150 ..In the best case I want everything local, with zero globals, consts or dims.

Matty(Posted 1+ years ago)

Hi CS_TBL:Yes it does only store the first step.  I use it in my Gauntlet remake in partnership with a second simple pathfindingtechnique of moving to the right/left around an obstacle if it meets something 'dynamic' so that when it gets to a different square all it has to do is look up 'where should I go next from here'.In a previous game which I did not finish I used a piece of code which formed the basis of this where it calculatesdynamic paths, as you suggest, storing the entire path.  It worked fine but I doubted whether it would be fast enoughto use in real time for the number of AI units I have in my Gauntlet clone so changed it to this.  For a smaller numberof AI units it can be used in realtime and store the complete path for that AI unit very easily.  If you look in the function "NewPathFind" at the bit where I commented out "PathString" - that was left over code from myearlier version.  It would be very easy to replace "PathString\$" with a bank.  Also, the "PathArray" could be modified so thatit stores both which squares are blocked by 'terrain' and which squares are blocked by other AI units so that a simplecall to NewPathFind(...) would return a bank handle to the unit which needs to find a path.

SimplePortal 2.3.6 © 2008-2014, SimplePortal