Author Topic: A-Star Pathfinding [BB2D]  (Read 3703 times)

0 Members and 1 Guest are viewing this topic.

Offline mike_g

  • Amiga 1200
  • ****
  • Posts: 435
  • Karma: 34
    • View Profile
A-Star Pathfinding [BB2D]
« on: August 05, 2007 »
I don't know if there would be any use for this kind of thing in a demo, but heres a set of pathfinding functions I have been working on:
Code: [Select]
Graphics 640, 480, 32, 2
Global font = LoadFont(arial, 10)
SetFont font

;------------Globals----------------;
Const x_cells=20
Const y_cells=16
Const all_cells = x_cells * y_cells
Const PATH_MAX=100
Dim grid(all_cells)

Type open
    Field grid_pos
Field parent
Field score
Field move_cost
End Type

Type closed
    Field grid_pos
Field parent
Field score
Field move_cost
End Type

Dim path(PATH_MAX)
;------------Init Grid--------------;
For i = 0 To all_cells-1
    Read grid(i)
Next

DrawGrid()
PathFind(141, 186)
DrawPath()
WaitKey

;-----------------------------------------------------------------------------------------------;
;***************************** PATH FINDING FUNCTIONS ******************************************;
;-----------------------------------------------------------------------------------------------;
Function PathFind(orig, dest)

;CREATE START POINT
this.open = New open
this\grid_pos = orig
this\parent=-1
this\score=0
this\move_cost=0

Repeat
;FIND LOWEST SCORE
lowest.open = First open
For this.open = Each open
If this\score < lowest\score Then lowest = this
Next
 
;IF TARGET REACHED
If lowest\grid_pos = dest
GetPath(lowest.open)
Return True
EndIf

;CHECK EACH ADJACENT SQUARE TO TILE
For y=-x_cells To x_cells Step x_cells
    For x=-1 To 1
    new_pos = lowest\grid_pos+x+y
If(PathIsValid(lowest\grid_pos, x, y, new_pos)=True)

;GET MOVE COST TO ADJACENT TILE
If(y <> 0 And x <> 0)
move_cost = grid(new_pos)+(grid(new_pos)*0.4)
Else
move_cost = grid(new_pos)
EndIf

;GUESS MOVE COST FROM TILE TO TARGET
;need a better method
dx#=Abs((dest Mod x_cells)-(new_pos Mod x_cells)-1)
dy#=Abs((dest / x_cells)-(new_pos / x_cells))
distance = Sqr((dx*dx)+(dy*dy))*10

goodness = distance + move_cost +lowest\move_cost

;CHECK IF DESTINATION IS ON OPEN LIST
check=0
For test.open = Each open
If test\grid_pos = new_pos
If test\score < goodness
check =1
Else
Delete test.open
EndIf
Exit
EndIf
Next
;IF NOT ADD TO OPEN LIST
If check = 0
create.open = New open
create\parent = lowest\grid_pos
create\move_cost = lowest\move_cost + move_cost
create\grid_pos = new_pos
create\score = goodness
EndIf

;DEBUG TEXT - DEMO STUFF-------------------------------------------------,
Color 200, 0, 0 ;
Text(((new_pos Mod x_cells)*32)+22, ((new_pos / x_cells)*32)+2, move_cost)
Color 0, 200, 0
Text(((new_pos Mod x_cells)*32)+18, ((new_pos / x_cells)*32)+23, distance)
Color 0, 0, 200
If check = 0
Text(((new_pos Mod x_cells)*32)+2, ((new_pos / x_cells)*32)+23, create\score)
EndIf
Delay(50) ;
;------------------------------------------------------------------------'
EndIf
Next
Next

;MOVE CURRENT TILE FROM OPEN LIST TO CLOSED LIST
cl.closed = New closed
cl\grid_pos = lowest\grid_pos
cl\parent = lowest\parent
cl\score = lowest\score 
Delete lowest.open

Forever
End Function
;-----------------------------------------------------;
Function GetPath(lowest.open)
waypoint = lowest\parent
count = 0
While waypoint <> -1
For c.closed = Each closed
If c\grid_pos = waypoint Then Exit
Next
path(count)=c\grid_pos
waypoint=c\parent
count=count+1
Wend
End Function
;-----------------------------------------------------;
Function PathIsValid(this_pos, x, y, pos)
If x=0 And y=0 Then Return False
If pos < 0 Or pos >= all_cells Then Return False
If this_pos Mod x_cells = 0 And pos Mod x_cells = x_cells-1 Then Return False
If this_pos Mod x_cells = x_cells-1 And pos Mod x_cells = 0 Then Return False
If(PathIsBlocked(pos)=True) Then Return False
For cl.closed = Each closed
If cl\grid_pos = pos Return False
Next
Return True
End Function

;--------OBSTRUCTING TILE REFERENCES GO IN HERE-------;
Function PathIsBlocked(pos)
    If grid(pos) = -1 Return True
Return False
End Function

;-----------------------------------------------------------------------------------------------;
;***************************** DEMO FUNCTIONS **************************************************;
;-----------------------------------------------------------------------------------------------;
Function DrawGrid()
For x=0 To 640 Step 32
    For y=0 To 480 Step 32
    Color 255, 255, 255
Line x, 0, x, 480
    Line 0, y, 640, y
   
tile=grid(((y/32)*x_cells)+(x/32))
    If tile = -1
Color 80, 80, 80
Rect x, y, 32, 32, 1
    Else If tile = -2
Color 120, 30, 30
Rect x, y, 32, 32, 1
    Else If tile = -3
Color 30, 120, 30
Rect x, y, 32, 32, 1
    Else
    Text x+3, y+2, tile
    EndIf
Next
Next 
End Function

Function DrawPath()
While path(i) <> 0
Color 200,200, 50
Oval (path(i) Mod x_cells)*32+12, (path(i) / x_cells)*32+12, 8, 8, 1
Color 20,20, 100
Text (path(i) Mod x_cells)*32+14, (path(i) / x_cells)*32+11, i
i=i+1
Wend
End Function
;-----------------------------------------------------------------------------------------------;
;***********************************************************************************************;
;-----------------------------------------------------------------------------------------------;

Data 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, -1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, -2, 10, 10, -1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, -1, -1, -1, -1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, -3, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Data 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
I should be converting this C once I got my code for linked lists sorted out.
« Last Edit: June 16, 2008 by mike_g »

Offline Jim

  • Founder Member
  • DBF Aficionado
  • ********
  • Posts: 5301
  • Karma: 402
    • View Profile
Re: A-Star Pathfinding [BB2D]
« Reply #1 on: August 06, 2007 »
Thanks mike_g, that's a good demo. K+
For those who don't know, the A* algorithm forms the basis of many games' AI routines.

Jim
Challenge Trophies Won:

Offline Paul

  • Pentium
  • *****
  • Posts: 1490
  • Karma: 47
    • View Profile
Re: A-Star Pathfinding [BB2D]
« Reply #2 on: September 08, 2007 »
Very nice algorithm there mike_g
Doues this find the fastest path?
does it add a penalty even if the grid is set to 0? or are all grids set to the same penalty value?

thx, Paul
I will bite you - http://s5.bitefight.se/c.php?uid=31059
Challenge Trophies Won:

Offline Clyde

  • A Little Fuzzy Wuzzy
  • DBF Aficionado
  • ******
  • Posts: 7271
  • Karma: 71
    • View Profile
Re: A-Star Pathfinding [BB2D]
« Reply #3 on: September 08, 2007 »
Welldone Mike_G :clap:
Still Putting The IT Into Gravy
If Only I Knew Then What I Know Now.

Challenge Trophies Won:

Offline mike_g

  • Amiga 1200
  • ****
  • Posts: 435
  • Karma: 34
    • View Profile
Re: A-Star Pathfinding [BB2D]
« Reply #4 on: September 11, 2007 »
Paul: It wont necessarily find the fastest path. The path guessing code is really simple it just adds the difference in x squares to the difference in y squares to see how far from the target it is. I saw several variants to this but all they did was get a more accurate distance to the target. None of these would take into consideration obstructing walls and potential differences in move cost between different squares. Coding something that would be complicated, and a lot slower, but I might have a go at it sometime.

Also if you want to use this in a game or something, you will need to write a simple function that clears the lists after each pathfind. it may also be a good idea to add a break point in the case that the target is unreachable.

Cheers.


Offline Paul

  • Pentium
  • *****
  • Posts: 1490
  • Karma: 47
    • View Profile
Re: A-Star Pathfinding [BB2D]
« Reply #5 on: September 11, 2007 »
I wasn't thinking of using it in a game.. you'll see whay i was intending when I'm done(if i fininsh it)

Do you know of an alogrith that gets the fastest path every time? if not I'll try making one but it will probably be far too slow:(

THX

Edit: just had a try and darn it's slow :(
« Last Edit: September 11, 2007 by Paul »
I will bite you - http://s5.bitefight.se/c.php?uid=31059
Challenge Trophies Won:

Offline Jim

  • Founder Member
  • DBF Aficionado
  • ********
  • Posts: 5301
  • Karma: 402
    • View Profile
Re: A-Star Pathfinding [BB2D]
« Reply #6 on: September 11, 2007 »
Have a Google for Dijkstra's Algorithm.

Jim
Challenge Trophies Won:

Offline Tetra

  • DBF Aficionado
  • ******
  • Posts: 2532
  • Karma: 83
  • Pirate Monkey!
    • View Profile
Re: A-Star Pathfinding [BB2D]
« Reply #7 on: September 19, 2007 »
I'm not sure if this will help too, but from what I can remember from a Discrete Math lecture theres the eulerian / shortest path, hamiltonian and the Travelling Salesman problem mite be worth a look.

http://en.wikipedia.org/wiki/Eulerian_path
http://en.wikipedia.org/wiki/Hamiltonian_path
http://en.wikipedia.org/wiki/Traveling_salesman_problem

If I remember the process is easy to visualise on paper, even though its all maths.
It mite be way over the top, or not even exatly what your after, I cant remember that much about it, but it does find a path accurately and resonably fast I think and the path it takes can have cost value, so that it would take the cheapest rout.
Challenge Trophies Won:

Offline Paul

  • Pentium
  • *****
  • Posts: 1490
  • Karma: 47
    • View Profile
Re: A-Star Pathfinding [BB2D]
« Reply #8 on: September 20, 2007 »
This sounds like an algorithm to find each vertex only once, and not the pathfinding that i want :?
I'll keep reading a little more...
I will bite you - http://s5.bitefight.se/c.php?uid=31059
Challenge Trophies Won:

Offline Jim

  • Founder Member
  • DBF Aficionado
  • ********
  • Posts: 5301
  • Karma: 402
    • View Profile
Re: A-Star Pathfinding [BB2D]
« Reply #9 on: September 20, 2007 »
Again, Dijkstra's Algorithm is the one you want.

Jim
Challenge Trophies Won:

Offline mike_g

  • Amiga 1200
  • ****
  • Posts: 435
  • Karma: 34
    • View Profile
Re: A-Star Pathfinding [BB2D]
« Reply #10 on: June 16, 2008 »
I just edited my original post. Unfortunately my original code was broken; it now finds the shortest path.

Jim, A* is actually very similar to dijstras algorithm the only difference is that a* uses a heuristic that can make the pathfinding faster when you know your target.

Dijkstra's algo is also very useful as you dont need to know your target location before starting the search. A made a version of it for a game. If I can get around to untangling it from the code I'll add it to this thread.

Cheers.

Offline Pixel_Outlaw

  • Pentium
  • *****
  • Posts: 1382
  • Karma: 83
    • View Profile
Re: A-Star Pathfinding [BB2D]
« Reply #11 on: June 16, 2008 »
Great post.  :kewl:

This was going to be my next project of many.
Challenge Trophies Won:

Offline Jim

  • Founder Member
  • DBF Aficionado
  • ********
  • Posts: 5301
  • Karma: 402
    • View Profile
Re: A-Star Pathfinding [BB2D]
« Reply #12 on: June 17, 2008 »
It's a very important subject, especially when you try to apply it to internet traffic routing.

Jim
Challenge Trophies Won:

Offline rain_storm

  • Here comes the Rain
  • DBF Aficionado
  • ******
  • Posts: 3088
  • Karma: 182
  • Rain never hurt nobody
    • View Profile
    • org_100h
Re: A-Star Pathfinding [BB2D]
« Reply #13 on: June 17, 2008 »
A* can also find items without knowing exactly where to look much the same as Dijkstra's meathod. I forget the actual way its done but I think you only have to consider how far you have travelled (since you dont know how far away from the destination you are) and keep going until you find what you are looking. Its not as efficient but when you are using the same code to do different jobs its easy to work with.

Challenge Trophies Won:

Offline mike_g

  • Amiga 1200
  • ****
  • Posts: 435
  • Karma: 34
    • View Profile
Re: A-Star Pathfinding [BB2D]
« Reply #14 on: June 17, 2008 »
Quote
It's a very important subject, especially when you try to apply it to internet traffic routing.
Yeah, I heard that a lot of routing protocols use it.

Quote
A* can also find items without knowing exactly where to look much the same as Dijkstra's meathod. I forget the actual way its done but I think you only have to consider how far you have travelled (since you dont know how far away from the destination you are) and keep going until you find what you are looking. Its not as efficient but when you are using the same code to do different jobs its easy to work with.
Yeah I guess you could find it without a target just ignoring the heuristic. Then it would pretty much be dijkstra's algo.