Ooops
October 17, 2021, 06:38:51

### Author Topic: [bmx] General A* Pathfinder Import by Curtastic [ 1+ years ago ]  (Read 4181 times)

#### BlitzBot

• Jr. Member
•  • Posts: 1 ##### [bmx] General A* Pathfinder Import by Curtastic [ 1+ years ago ]
« on: June 29, 2017, 00:28:38 »
Title : General A* Pathfinder Import
Author : Curtastic
Posted : 1+ years ago

Description : This is a general pathfinder that works on a 2D grid where 1=wall and 0=walkable. Numbers between 0 and 1 are tiles that take longer than normal to cross.

You pass it a map[,] to set it up, and when you findpath it fills its route[] array.

Diagonal movement is optional.

[img]www.curtastic.com/pathfinder.html">
Example:
Code: [Select]
`'Click to make walls.'Rightclick to change starting point.'Mousewheel changes tile speeds.StrictImport "pathfinder.bmx"Graphics 800, 600Local Grid:Float[20, 20]Const TS = 29Local fx, fyLocal my, mxLocal startx = 1, starty = 1Local iLocal z, g:FloatMoveMouse 111, 111TPathfinder.SetUp(Grid, 1, .03)Repeat mx = MouseX() / TS my = MouseY() / TS mx=Max(mx,0); mx=Min(mx,19) my=Max(my,0); my=Min(my,19) If MouseDown(1) Then Grid[mx, my] = 1 If MouseHit(2) Then startx = mx starty = my EndIf 'use mousewheel to change tile speeds g = Grid[mx, my] + (MouseZ() - z) / 10.0 z = MouseZ() If g < 0 Then g = 0 If g > 1 Then g = 1 Grid[mx, my] = g 'Draw grid tiles For fy = 0 To 19 For fx = 0 To 19 If Grid[fx, fy] > 0 Then SetColor Grid[fx, fy] * 255, 0, 0 DrawRect fx * TS, fy * TS, TS, TS EndIf Next Next 'Draw grid lines SetColor 255, 255, 255 For fx = 0 To 20 DrawRect fx * TS, 0, 1, 20 * TS DrawRect 0, fx * TS, 20 * TS, 1 Next If TPathfinder.FindPath(startx, starty, mx, my) Then 'Draw path SetColor 0, 255, 0 For i = 0 Until TPathfinder.Route.length Step 2 DrawRect TPathfinder.Route[i] * TS + 5, TPathfinder.Route[i + 1] * TS + 5, 5, 5 Next EndIf DrawText TPathfinder.Paths, 0, 0 Flip Cls If KeyHit(key_escape) Then EndForever`

Code :
Code: BlitzMax
1. '''''''''''''''''''''''''
2. 'A General A* Pathfinder'
3. 'Coded by Curtastic 2007'
4. 'Coded in Lightning IDE.'
5. '''''''''''''''''''''''''
6. SuperStrict
7.
8. Type TPathfinder Abstract
9.         '0=no diagonal movement.
10.         '1=diagonal movement and cutting corners allowed.
11.         '2=diagonal movement but no cutting corners.
12.         Global Diagonals:Int
13.
14.         'The higher this number, the more the path will randomly differ from what is optimum.
15.         Global Randomity:Float
16.
17.         'Map is a float. The closer to 1 the harder it is to move into this tile.
18.         'All values 1 or greater are considered walls.
19.         Global Map:Float[, ]
20.         Global MapWidth:Int
21.         Global MapHeight:Int
22.
23.         'The amount of steps in the route. (Read only)
24.         Global Paths:Int
25.
26.         'The resulting path is a 'resliced' route[].
27.         ' as [x0, y0, x1, y1, x2, y2, x3, y3, ..etc. .. xn,yn]
28.         ' The size of this array is paths*2.
29.         Global Route:Int[]
30.
31.         'The higher the BasicCost, the more accurate and slow pathfinding will be.
32.         Const BasicCost:Float = .17
33.
34.
35. 'Private:
36.         Global PathMap:TPath[, ]
37.         Const Root2:Float = 1.4142
38.
39.         Function SetUp(MapPassed:Float[,], Diag:Int=1, Random:Float=0)
40.                 Assert Random>0, "Randomity must be positive."
41.                 Assert Diag = 0 Or Diag = 1 Or Diag = 2, "Diagonals must be 0 or 1 or 2."
42.                 Assert MapPassed <> Null, "Map must not be null."
43.
44.                 Map = MapPassed
45.                 MapWidth = MapPassed.Dimensions()
46.                 MapHeight = MapPassed.Dimensions()
47.                 Diagonals = Diag
48.                 Randomity = Random
49.
50.         EndFunction
51.
52.         'Returns 1 if successful and 0 if unseccessful.
53.         'Fills the route[] array if successful.
54.         Function FindPath:Int(StartX:Int, StartY:Int, EndX:Int, EndY:Int)
55.
56.                 Assert Not(StartX < 0 Or StartY < 0 Or StartX >= MapWidth Or StartY >= MapHeight), ..
57.                  "Starting point out of bounds: " + StartX + "," + StartY
58.                 Assert Not(EndX < 0 Or EndY < 0 Or EndX >= MapWidth Or EndY >= MapHeight), ..
59.                  "End point out of bounds: " + EndX + "," + EndY
60.                 Assert Map <> Null, ..
61.                  "SetUp() must be called before FindPath"
62.
64.                 If StartX = EndX And StartY = EndY Then
65.                         Route = New Int
66.                         Route = StartX
67.                         Route = StartY
68.                         Paths = 1
69.                         Return 1
70.                 EndIf
71.
72.                 Paths = 0
73.
74.                 'If target is a wall.
75.                 If Map[EndX, EndY] >= 1 Then Return 0
76.
77.
78.                 Local P:TPath
79.                 Local P2:TPath
80.                 Local NewP:TPath
81.                 Local NewX:Int
82.                 Local NewY:Int
83.                 Local Dir:Int
84.                 Local DirMax:Int
85.                 Local Done:Int
87.                 Local MapHere:Float
88.                 Local DistX:Int
89.                 Local DistY:Int
90.
91.                 PathMap = New TPath[MapWidth, MapHeight]
92.
93.                 'Make first path node at start.
94.                 P = New TPath
96.                 P.X = StartX
97.                 P.Y = StartY
98.                 PathMap[StartX, StartY] = P
99.
100.                 If Diagonals Then
101.                         DirMax = 7
102.                 Else
103.                         DirMax = 3
104.                 EndIf
105.
106.
107.                 Repeat
108.
109.
110.                         For Dir = 0 To DirMax
111.
112.                                 'Move based on direction.
113.                                 Select Dir
114.                                         Case 0; NewX = P.X + 1; NewY = P.Y
115.                                         Case 1; NewX = P.X    ; NewY = P.Y + 1
116.                                         Case 2; NewX = P.X - 1; NewY = P.Y
117.                                         Case 3; NewX = P.X    ; NewY = P.Y - 1
118.                                         Case 4; NewX = P.X + 1; NewY = P.Y + 1
119.                                         Case 5; NewX = P.X - 1; NewY = P.Y + 1
120.                                         Case 6; NewX = P.X - 1; NewY = P.Y - 1
121.                                         Case 7; NewX = P.X + 1; NewY = P.Y - 1
122.                                 EndSelect
123.
124.                                 'Check if it is ok to make a new path node here.
125.                                 If NewX >= 0 And NewY >= 0 And NewX < MapWidth And NewY < MapHeight Then
126.                                         MapHere = Map[NewX, NewY]
127.                                         If MapHere < 1 Then
128.
129.                                                 'No cutting corners.
130.                                                 If Diagonals = 2 And Dir > 3 Then
131.                                                         If Map[NewX, P.Y] >= 1 Then Continue
132.                                                         If Map[P.X, NewY] >= 1 Then Continue
133.                                                 EndIf
134.
135.                                                 P2 = PathMap[NewX, NewY]
136.
137.                                                 'Check if there already is a path here.
138.                                                 If P2 = Null Then
139.
140.                                                         'DrawRect newx*29,newy*29,29,29
141.                                                         'Flip False
142.                                                         'If KeyHit(key_escape) Then End
143.
144.                                                         'Make new node.
145.                                                         NewP = New TPath
146.                                                         PathMap[NewX, NewY] = NewP
147.                                                         NewP.Parent = P
148.                                                         NewP.X = NewX
149.                                                         NewP.Y = NewY
150.
151.                                                         'Cost is slightly more for diagnols.
152.                                                         If Dir < 4 Then
153.                                                                 NewP.Cost = P.Cost + BasicCost + MapHere + Rnd(0, Randomity)
154.                                                         Else
155.                                                                 NewP.Cost = P.Cost + (BasicCost + MapHere + Rnd(0, Randomity)) * Root2
156.                                                         EndIf
157.
158.                                                         'Calculate distance from this node to target.
159.                                                         If Diagonals Then
160.                                                                 DistX = Abs(NewX - EndX)
161.                                                                 DistY = Abs(NewY - EndY)
162.                                                                 If DistX > DistY Then
163.                                                                         NewP.Dist = DistX - DistY + DistY * Root2
164.                                                                 Else
165.                                                                         NewP.Dist = DistY - DistX + DistX * Root2
166.                                                                 EndIf
167.                                                                 NewP.Dist :* .1
168.                                                         Else
169.                                                                 NewP.Dist = (Abs(NewX - EndX) + Abs(NewY - EndY)) / 8.0
170.                                                         EndIf
171.
172.                                                         'Insert node at appropriate spot in list.
173.                                                         P2 = P
174.                                                         Repeat
175.                                                                 If P2.After = Null Then
176.                                                                         P2.After = NewP
177.                                                                         Exit
178.                                                                 EndIf
179.                                                                 If P2.After.Dist + P2.After.Cost > NewP.Dist + NewP.Cost Then
180.                                                                         NewP.After = P2.After
181.                                                                         P2.After = NewP
182.                                                                         Exit
183.                                                                 EndIf
184.                                                                 P2 = P2.After
185.                                                         Forever
186.
187.                                                         'Check if found the end.
188.                                                         If NewX = EndX And NewY = EndY Then
189.                                                                 Done = 1
190.                                                                 Exit
191.                                                         EndIf
192.                                                 Else
193.                                                         'Overwrite existing path node if this way costs less.
194.                                                         If P2.Cost > P.Cost + BasicCost + MapHere * Root2 + Randomity Then
195.                                                                 P2.Parent = P
196.                                                                 'Cost is slightly more for diagnols.
197.                                                                 If Dir < 4 Then
198.                                                                         P2.Cost = P.Cost + BasicCost + MapHere + Rnd(0, Randomity)
199.                                                                 Else
200.                                                                         P2.Cost = P.Cost + (BasicCost + MapHere + Rnd(0, Randomity)) * Root2
201.                                                                 EndIf
202.                                                         EndIf
203.                                                 EndIf
204.                                         EndIf
205.                                 EndIf
206.                         Next
207.
208.                         If Done = 1 Then Exit
209.
210.                         P = P.After
211.                         If P = Null Then Exit
212.
213.                 Forever
214.
215.
216.                 If Done Then
217.                         'Count how many paths.
218.                         P2 = NewP
219.                         Repeat
220.                                 Paths:+ 1
221.                                 P2 = P2.Parent
222.                                 If P2 = Null Then Exit
223.                                 'If KeyDown(key_space) Then DebugStop
224.                         Forever
225.
226.                         'Make route from end to start.
227.                         Route = New Int[Paths * 2]
228.                         Local i:Int = 0
229.                         P2 = NewP
230.                         Repeat
231.                                 Route[i] = P2.X
232.                                 i:+ 1
233.                                 Route[i] = P2.Y
234.                                 i:+ 1
235.                                 P2 = P2.Parent
236.                                 If P2 = Null Then Exit
237.                         Forever
238.                 EndIf
239.
240.                 'Nullify parent pointers so mem will be deallocated.
242.                 Repeat
243.                         P.Parent = Null
244.                         P = P.After
245.                         If P = Null Then Exit
246.                 Forever
247.
248.                 Return Done
249.         EndFunction
250. EndType
251.
252.
253. 'Private
254. Type TPath
255.         Field X:Int
256.         Field Y:Int
257.         Field Parent:TPath
258.         Field Cost:Float
259.         Field Dist:Float
260.         Field After:TPath
261. EndType

Filax(Posted 1+ years ago)

Great do you think that possible to get the same way but in 3D ?

Andy_A(Posted 1+ years ago)

<div class="quote"> Great do you think that possible to get the same way but in 3D ? </div>+1

#### Gijsdemik

• Jr. Member
•  • Posts: 12 ##### Re: [bmx] General A* Pathfinder Import by Curtastic [ 1+ years ago ]
« Reply #1 on: January 06, 2018, 09:46:41 »
Who Cool,
Ive been looking for something like this for a long time.
i am not yet a great coder and i needed this for movement in my game.
After blitz its site went down i was afraid i had to do all this alone
The demo is good to understand thanks for this code share ! #### RonTek ##### Re: [bmx] General A* Pathfinder Import by Curtastic [ 1+ years ago ]
« Reply #2 on: January 06, 2018, 16:34:15 »
Hi Gijsdemik,

I don't know about your requirements, but having checked this and if you're working on a grid base system, the output below is not considered a valid entry: maybe you can try and find other blitzmax codes here or disregard this if it works for you.

#### Gijsdemik

• Jr. Member
•  • Posts: 12 ##### Re: [bmx] General A* Pathfinder Import by Curtastic [ 1+ years ago ]
« Reply #3 on: April 19, 2018, 08:59:41 »
He
No its oke like this, its perfect for my game #### Gijsdemik

• Jr. Member
•  • Posts: 12 ##### Re: [bmx] General A* Pathfinder Import by Curtastic [ 1+ years ago ]
« Reply #4 on: April 25, 2018, 17:34:38 »
Hi!

As i noted it was fine for my game.
And i got the whole movement working for my game.

I tought is was cool to show how i used it and what my game is going to be.