October 28, 2020, 11:39:17 PM

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

Offline BlitzBot

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

Strict
Import "pathfinder.bmx"

Graphics 800, 600

Local Grid:Float[20, 20]
Const TS = 29
Local fx, fy
Local my, mx
Local startx = 1, starty = 1
Local i
Local z, g:Float

MoveMouse 111, 111

TPathfinder.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 End
Forever



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()[0]
  46.                 MapHeight = MapPassed.Dimensions()[1]
  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.                
  63.                 'If already on target.
  64.                 If StartX = EndX And StartY = EndY Then
  65.                         Route = New Int[2]
  66.                         Route[0] = StartX
  67.                         Route[1] = 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
  86.                 Local PHead:TPath
  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
  95.                 PHead = P
  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.
  241.                 P = PHead
  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


Comments :


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


Offline Gijsdemik

  • Jr. Member
  • **
  • Posts: 9
Re: [bmx] General A* Pathfinder Import by Curtastic [ 1+ years ago ]
« Reply #1 on: January 06, 2018, 09:46:41 AM »
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 ! :D

Offline RonTek

  • Sr. Member
  • ****
  • Posts: 357
Re: [bmx] General A* Pathfinder Import by Curtastic [ 1+ years ago ]
« Reply #2 on: January 06, 2018, 04:34:15 PM »
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.

Offline Gijsdemik

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

Offline Gijsdemik

  • Jr. Member
  • **
  • Posts: 9
Re: [bmx] General A* Pathfinder Import by Curtastic [ 1+ years ago ]
« Reply #4 on: April 25, 2018, 05:34:38 PM »
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.
So i uploaded a Demo video to youtube
>>>>>>>
&feature=youtu.be
<<<<<<<<<

I am verry happy that i found this path movement exmaple and code it helpt me alot as i am now one step in compliting my game!
Tnx!

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal