Ooops
November 28, 2020, 02:36:49 PM

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

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
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. :P


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