A* Pathfinding Demo

Game development specific discussions.
coderJeff
Site Admin
Posts: 2336
Joined: Nov 04, 2005 14:23
Location: Ontario, Canada
Contact:

A* Pathfinding Demo

Postby coderJeff » Nov 16, 2007 14:39

Source here: http://www.execulink.com/~coder/freebasic/astar.html
(need at least fbc-0.17)

This is an A* pathfinding demonstration written in FreeBASIC that generates a display similar to the excellent beginners tutorial by Patrick Lester found at http://www.policyalmanac.org/games/aStarTutorial.htm

Image

You can use the mouse buttons to set the starting and ending tiles, plus toggle the solid tiles.

Enjoy!
elsairon
Posts: 207
Joined: Jul 02, 2005 14:51

Postby elsairon » Nov 18, 2007 3:46

This is much easier to understand for me than other presentations of A*.

Thanks for sharing.
DaveUnit
Posts: 239
Joined: Apr 20, 2006 15:47
Location: Central MA
Contact:

Postby DaveUnit » Nov 18, 2007 5:37

nicely done.
I haven't had time to learn how to do this yet but when the time comes I will surely remember this excellent demonstration.
cha0s
Site Admin
Posts: 5317
Joined: May 27, 2005 6:42
Location: Illinois
Contact:

Postby cha0s » Nov 18, 2007 20:18

Thanks!
Frank Dodd
Posts: 444
Joined: Mar 10, 2006 19:22

Postby Frank Dodd » Nov 20, 2007 22:14

Thanks for this, I have a path finding solution as a requirement on my project list this looks like a great option for it.
coderJeff
Site Admin
Posts: 2336
Joined: Nov 04, 2005 14:23
Location: Ontario, Canada
Contact:

Postby coderJeff » Nov 21, 2007 14:17

The demo is just one way A* could be implemented which I think is easy to read, but likely not fast/efficient enough for a large grid or many paths. There are probably a dozen or more ways to implement the concept of nodes on an OPEN or CLOSED list. There are reference links on the tutorial's page that go in more depth to implementing the algorithm. Thanks for the positive feedback guys. :)
pr0gger
Posts: 47
Joined: Oct 27, 2006 23:10

Postby pr0gger » Nov 26, 2007 5:41

I've seen that page before -- it's the best A* tutorial I know of.

Very nice demo, jeff (:

--j_k
Dr_D
Posts: 2337
Joined: May 27, 2005 4:59
Contact:

Postby Dr_D » Nov 26, 2007 7:54

Very cool. Here's something I made a long time ago after reading that same tutorial and adding a few ideas of my own and a few things to make it faster. You'll have to use -lang QB to compile it, but it's still pretty cool I think. :p

http://copy-pasta.com/pasta2052
Conexion
Posts: 236
Joined: Feb 23, 2006 6:04

Postby Conexion » Nov 26, 2007 21:43

It is a very good tutorial in it's own right, but this is a great presentation on how to do it in FreeBasic. Excellent work :D

I like making mazes for it to figure out :D
Pritchard
Posts: 5418
Joined: Sep 12, 2005 20:06
Location: Ohio, USA

Postby Pritchard » Jan 09, 2008 2:53

Looks useful. I should learn it.
D.J.Peters
Posts: 6882
Joined: May 28, 2005 3:28
Location: Germany

Postby D.J.Peters » Jan 09, 2008 3:12

@coderJeff
thanx the tutorial is super simple while you wrote it for FB i wrote it for Basic4GL
the exe apath.zip

Joshy

Code: Select all

' A* Pathfinder
'
' usage:
'   left  mouse button set   PathStart (green)
'   right mouse button set   PathEnd   (red)
'   midle mouse button togle Walkable  (blue)

struc VECTOR2D
  dim x,y
end struc

struc COSTS
  dim f,g,h
endstruc

struc CELL
  dim VECTOR2D Position
  dim VECTOR2D Array
  dim COSTS    Cost
  dim State    ' NONE / OPEN / CLOSED
  dim CELL     &Parent
  dim Walkable ' True/False
  dim Index
endstruc

struc DIRECTIONS
  dim VECTOR2D Add
  dim Cost,Flag
end struc

' cost,xadd,yadd,direction
DataDirs:
  Data 1000, 0,-1, 1 ' north
  Data 1000, 1, 0, 2 ' east
  Data 1000, 0, 1, 4 ' south
  Data 1000,-1, 0, 8 ' west
  Data 1414, 1,-1, 3 ' north east
  Data 1414, 1, 1, 6 ' south east
  Data 1414,-1, 1,12 ' south west
  Data 1414,-1,-1, 9 ' north west

const _XCELLS=4*10,_YCELLS=3*10
const _LASTCELL=_XCELLS*_YCELLS-1
const _NONE =0,_OPEN=1,_CLOSED=2

dim CELL Terain(_LASTCELL)
dim CELL &PathStart
dim CELL &PathEnd
dim CELL &Cell
dim CELL &Parent
dim CellWidth#,CellHeight#
dim Index,CellIndex,NewCellIndex
dim DIRECTIONS Test
dim DIRECTIONS Dirs(7),DIndex,DirFlag
dim MustUpdate

Gosub InitOpenGL2D
Gosub InitTerain
Gosub InitDirections

MustUpdate=True

' init any PathStart and PathEnd
Index     =int(_YCELLS*0.25)*_XCELLS+int(_XCELLS*0.25)
&PathStart=&Terain(Index)
Index     =int(_YCELLS*0.75)*_XCELLS+int(_XCELLS*0.75)
&PathEnd  =&Terain(Index)

' draw a wall in center of the Terain
Index      =int(_YCELLS*0.1 )*_XCELLS+int(_XCELLS*0.5 )
while Index<int(_YCELLS*0.9 )*_XCELLS+int(_XCELLS*0.5 )
  Terain(Index).Walkable=False:Index=Index+_XCELLS
wend

'
' main loop
'
while True
   
  if Mouse_Button(MOUSE_LBUTTON) then
    ' set new PathStart  (green)
    Gosub GetNewCellIndex
    if NewCellIndex<>CellIndex then
      if &PathEnd<>&Terain(NewCellIndex) then
        CellIndex=NewCellIndex:&PathStart=&Terain(CellIndex)
        Terain(CellIndex).Walkable=True:MustUpdate=True
      endif
    endif
  elseif Mouse_Button(MOUSE_RBUTTON) then
    ' set new PathEnd  (red)
    Gosub GetNewCellIndex
    if NewCellIndex<>CellIndex then
      if &PathStart<>&Terain(NewCellIndex) then
        CellIndex=NewCellIndex:&PathEnd=&Terain(CellIndex)
        Terain(CellIndex).Walkable=True:MustUpdate=True
      endif
    endif
  elseif Mouse_Button(MOUSE_MBUTTON) then
    ' make TerainCell as Walkable (blue) or not (rectangle)
    Gosub GetNewCellIndex
    if NewCellIndex<>CellIndex then
      if (&Terain(NewCellIndex)<>&PathStart) land (&Terain(NewCellIndex)<>&PathEnd) then
        CellIndex=NewCellIndex:MustUpdate=True
        Terain(CellIndex).Walkable= not Terain(CellIndex).Walkable
      endif
    endif
  endif

  if MustUpdate=True then
    glClear(GL_COLOR_BUFFER_BIT)
    Gosub DrawTerain
    Gosub GetPath
    Gosub DrawPath
    MustUpdate=False
    SwapBuffers()
  else
    Sleep(10)
  endif
wend

InitOpenGL2D:
  glMatrixMode  (GL_PROJECTION)
  glLoadIdentity()
  glOrtho       (0,WindowWidth(),WindowHeight(),0,  0,1)
  glMatrixMode  (GL_MODELVIEW)
  glLoadIdentity()
  glDisable     (GL_DEPTH_TEST)
  glDisable     (GL_CULL_FACE)
  glMatrixMode  (GL_MODELVIEW)
  CellWidth# =WindowWidth ()/_XCELLS
  CellHeight#=WindowHeight()/_YCELLS
  return

InitDirections:
  Reset DataDirs
  for DIndex=0 to 7
    read Dirs(DIndex).Cost
    read Dirs(DIndex).Add.x
    read Dirs(DIndex).Add.y
    read Dirs(DIndex).Flag
  next
  return

InitTerain:
  ' get center of all TerainCells
  for Index=0 to _LASTCELL
    Terain(Index).Index      = Index
    Terain(Index).Array.x    = (Index % _XCELLS)
    Terain(Index).Array.y    = (Index / _XCELLS)
    Terain(Index).Position.x = (CellWidth# *0.5)+Terain(Index).Array.x*CellWidth#
    Terain(Index).Position.y = (CellHeight#*0.5)+Terain(Index).Array.y*CellHeight#
    Terain(Index).Walkable   = True
  next
  return

ClearTerain:
  ' clear all cost and set to STATE_NONE
  for Index=0 to _LASTCELL
   &Terain(Index).Parent = NULL
    Terain(Index).Cost.f = 0
    Terain(Index).Cost.g = 0
    Terain(Index).Cost.h = 0
    Terain(Index).State  = _NONE
  next
  return

DrawTerain:
  for Index=0 to _LASTCELL
    if &Terain(Index)=&PathStart then
      glColor3f(0,.75,0):Gosub DrawQuad
    elseif &Terain(Index)=&PathEnd then
      glColor3f(.75,0,0):Gosub DrawQuad
    elseif Terain(Index).Walkable=False then
      glColor3f(0,0,.75):Gosub DrawQuad
    endif
    glColor3f(.75,.75,.75):Gosub DrawRectangle
  next
  return

DrawPath:
  &Cell=&PathEnd
  while (&Cell.Parent<>NULL)
    if (&Cell<>&PathEnd) then
      Index=Cell.Index
      glColor3f(.75,.75,0):Gosub DrawDiamond
    endif
    &Cell=&Cell.Parent
  wend
  return

DrawQuad:
  glPushMatrix ()
    glTranslatef (Terain(Index).Position.x,Terain(Index).Position.y, 0)
    glScalef     (CellWidth#,CellHeight#, 1)
    glBegin      (GL_QUADS)
      glVertex2f (-0.5, 0.5)
      glVertex2f (-0.5,-0.5)
      glVertex2f ( 0.5,-0.5)
      glVertex2f ( 0.5, 0.5)
    glEnd()
  glPopMatrix()
  return

DrawDiamond:
  glPushMatrix ()
    glTranslatef (Terain(Index).Position.x,Terain(Index).Position.y, 0)
    glScalef     (CellWidth#,CellHeight#, 1)
    glBegin      (GL_QUADS)
      glVertex2f ( 0, 0.25)
      glVertex2f (-0.25, 0)
      glVertex2f ( 0,-0.25)
      glVertex2f ( 0.25, 0)
    glEnd()
  glPopMatrix()
  return 

DrawRectangle:
  glPushMatrix()
    glTranslatef (Terain(Index).Position.x,Terain(Index).Position.y, 0)
    glScalef     (CellWidth#,CellHeight#, 1)
    glBegin      (GL_LINE_LOOP)
      glVertex2f (-0.5, 0.5)
      glVertex2f (-0.5,-0.5)
      glVertex2f ( 0.5,-0.5)
      glVertex2f ( 0.5, 0.5)
    glEnd()
  glPopMatrix()
  return
 
GetNewCellIndex:
  ' get TerainCell from curent Mouse position
  NewCellIndex=             int((Mouse_x()*WindowWidth() )/CellWidth#)
  NewCellIndex=NewCellIndex+int((Mouse_y()*WindowHeight())/CellHeight#)*_XCELLS
  return

GetMinCost:
  &Parent=NULL
  for Index=0 to _LASTCELL
    if Terain(Index).State=_OPEN then
      if &Parent=NULL then
        &Parent = &Terain(Index)
      elseif Terain(Index).Cost.F < Parent.Cost.F then
        &Parent = &Terain(Index)
      endif
    end if
  next
  return

TestNeighbour:
  Test.Flag=False
  if Test.add.X<       0 then return:endif
  if Test.add.X>=_XCELLS then return:endif
  if Test.add.Y<       0 then return:endif
  if Test.add.Y>=_YCELLS then return:endif
  Index=Test.add.X+Test.add.Y*_XCELLS

  &Cell=&Terain(Index)
  if Cell.Walkable=False then return:endif
  if Cell.State<>_NONE then
    if (Parent.Cost.g+Test.Cost)<Cell.Cost.g then
      Cell.State=_NONE
    endif
  endif
  if Cell.State=_NONE then
   &Cell.Parent = &Parent
    Cell.State  = _OPEN
    Cell.Cost.h =               ABS(Cell.Position.x-PathEnd.Position.x)*1000
    Cell.Cost.h = Cell.Cost.h + ABS(Cell.Position.y-PathEnd.Position.y)*1000
    Cell.Cost.g = Parent.Cost.g + Test.Cost
    Cell.Cost.f = Cell.Cost.g + Cell.Cost.h
  endif
  Test.Flag=True
  return 

TestNeighbours:
  DirFlag =0
  For DIndex=0 to 7
    Test.Cost=Dirs(DIndex).Cost
    Test.add.X=Parent.Array.x+Dirs(DIndex).Add.x
    Test.add.Y=Parent.Array.y+Dirs(DIndex).Add.y
    if DIndex<4 then
      Gosub TestNeighbour
      if Test.Flag=True then
        DirFlag=DirFlag or Dirs(DIndex).Flag
      endif
    else
      if (DirFlag and Dirs(DIndex).Flag)=Dirs(DIndex).Flag then
        Gosub TestNeighbour
      endif
    endif
  next
  return

GetPath:
  ' Calc a Path between PathEnd and PathStart
  Gosub ClearTerain
  PathStart.State=_OPEN
  Do
    Gosub GetMinCost
    if (&Parent=NULL) lor (&Parent=&PathEnd) then return:endif
    Parent.State=_CLOSED
    Gosub TestNeighbours
  Loop
  return

Image
Image
~EXIS~
Posts: 21
Joined: Sep 01, 2006 18:57
Location: RUSSIA

Postby ~EXIS~ » Jan 29, 2008 17:19

Good examples =)
tincrowdor
Posts: 9
Joined: Aug 07, 2008 6:26

Postby tincrowdor » Aug 09, 2008 6:53

very nice. I'm trying to work on a quick longest path generator, so the code looks very useful
Frank Dodd
Posts: 444
Joined: Mar 10, 2006 19:22

Postby Frank Dodd » Aug 10, 2008 8:19

Nice work D.J.Peters, one thing I am curious about is in the first 'here' example at the first turn, the solution takes 9 steps to move from one junction to the next however the eastern route at the first junction would result in 5 steps. The path looks good and reaches its destination but why was the more optimal route not taken?
HD_
Posts: 215
Joined: Jun 10, 2006 12:15
Contact:

Postby HD_ » Aug 10, 2008 10:54

I believe that comes down to the heuristic used- which calculates the distance between two cells. Good heuristics are slow, so maybe a fast/innacurate one was used.

I think this is the offending code:

Code: Select all

    Cell.Cost.h =               Abs(Cell.Position.x-PathEnd.Position.x)*1000
    Cell.Cost.h = Cell.Cost.h + Abs(Cell.Position.y-PathEnd.Position.y)*1000


Looks like manhatten method. Changing the 1000 can affect the result I believe- however if you wish to try other methods, this page is helpful:
http://theory.stanford.edu/~amitp/GameP ... stics.html

Return to “Game Dev”

Who is online

Users browsing this forum: No registered users and 0 guests