A* in lua

astar.lua

[email protected]
-- This is an implementation of the basic A*

--[[
Summary of the A* Method

1) Add the starting square (or node) to the open list.
2) Repeat the following:
  a) Look for the lowest F cost square on the open list. We refer to this as the current square.
  b) Switch it to the closed list.
  c) For each of the 8 squares adjacent to this current square …
    If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.           
    If it isn’t on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square. 
    If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.
  d) Stop when you:
    Add the target square to the closed list, in which case the path has been found (see note below), or
    Fail to find the target square, and the open list is empty. In this case, there is no path.   
3) Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path. 

Note: In earlier versions of this article, it was suggested that you can stop when the target square (or node) has been added to the open list, rather than the closed list.  Doing this will be faster and it will almost always give you the shortest path, but not always.  Situations where doing this could make a difference are when the movement cost to move from the second to the last node to the last (target) node can vary significantly -- as in the case of a river crossing between two nodes, for example.
--]]

-- ////////////////////////////////////////////////////////////////////////////////////
-- ////////////////////////////////////////////////////////////////////////////////////
function IsWalkable(id)
  return id==-1 or id==0
end

-- ////////////////////////////////////////////////////////////////////////////////////
-- Heuristic function
-- Returns the manhattan cost from (x,y) to (endx,endy)
-- Doesn't take into account any obstacle
-- ////////////////////////////////////////////////////////////////////////////////////
function H( x, y, endx, endy )
  local lx, ly = endx-x, endy-y  
  return 10 * (math.abs(x-endx) + math.abs(y-endy))
  --return math.sqrt( lx*lx + ly*ly )
end

-- ////////////////////////////////////////////////////////////////////////////////////
-- Creates a node
-- ////////////////////////////////////////////////////////////////////////////////////
function MakeNode( x, y, parent, g, h )
  local l = {}
  l.x = x
  l.y = y
  l.parent = parent
  l.g = g
  l.h = h
  l.f = function(self) return self.g + self.h end
  return l
end

-- ////////////////////////////////////////////////////////////////////////////////////
-- Search if the node (x,y) is in the list 'l'
-- Returns the node if found, or nil otherwise
-- ////////////////////////////////////////////////////////////////////////////////////
function FindNode( x,y, l )
  for i=1,table.getn(l) do
    if l[i].x == x and l[i].y == y then 
      return l[i]
    end
  end
  return nil
end

-- ////////////////////////////////////////////////////////////////////////////////////
-- Try to add an adjacent node(x,y) from curNode to the open list 'olist'
-- ////////////////////////////////////////////////////////////////////////////////////
function TryAddAdjacent(grid,x,y,curNode,olist,clist,endx,endy)

  -- adding if walkable and not in closed list        
  if IsWalkable(grid[x][y]) and FindNode(x,y,clist)==nil then
    local newNode = MakeNode( x, y, curNode, curNode.g+1, H(x,y,endx,endy) )
    local exiNode = FindNode( x, y, olist )
    -- if not already in open list => add it directly
    if exiNode == nil then
      table.insert( olist, newNode )
    else
      --if already in open list => get the one with lowest 'g' value
      local finalNode = newNode
      if exiNode.g < newNode.g then  -- current added is better
        -- update the parent and 'g' values        
        exiNode.parent = curNode
        exiNode.g = curNode.g+1        
      end
    end
  end
  
end

-- ////////////////////////////////////////////////////////////////////////////////////
-- Add adjacent nodes to 'curNode' to the open list 'olist'
-- ////////////////////////////////////////////////////////////////////////////////////
function AddAdjacents( grid, dimx, dimy, curNode, olist, clist, endx, endy )  
  local x, y = curNode.x, curNode.y
  
  -- trying with horizontally adjacents left & right  
  if x-1 >= 0      then TryAddAdjacent(grid,x-1,y,curNode,olist,clist,endx,endy) end
  if x+1 < dimx  then TryAddAdjacent(grid,x+1,y,curNode,olist,clist,endx,endy) end
  
  -- vertically adjacents, top & down
  if y-1 >= 0      then TryAddAdjacent(grid,x,y-1,curNode,olist,clist,endx,endy) end
  if y+1 < dimy  then TryAddAdjacent(grid,x,y+1,curNode,olist,clist,endx,endy) end
  
  -- diagonal movement not allowed
  
  return olist
end

-- ////////////////////////////////////////////////////////////////////////////////////
-- Extract the node from open list 'ol' with lowest f()=g+h
-- the extracted node is removed from ol, and added to close list cl
-- ////////////////////////////////////////////////////////////////////////////////////
function ExtractLowestF( ol, cl )
  -- will keep the lowest value and index
  local lowestval, lowesti = 2^50, -1
  local extracted = nil
  for i=1,table.getn(ol) do
    local n = ol[i]
    if n:f() < lowestval then
      extracted = n
      lowestval = n:f()
      lowesti = i
    end
  end
  -- if found something
  if lowesti ~= -1 then
    table.insert( cl, extracted )
    table.remove( ol, lowesti )
  end
  return extracted
end

-- ////////////////////////////////////////////////////////////////////////////////////
-- Returns the close list if a path from (startx,starty) to (endx,endy) is found
-- If not found returns nil
-- You can build your path up from the endNode to the start by getting the parents
-- ////////////////////////////////////////////////////////////////////////////////////
function CanMoveFromTo( grid, dimx, dimy, startx, starty, endx, endy )
  
  -- Starting with the start node
  local openlist = { MakeNode( startx, starty, nil, 0.0, H(startx,starty,endx,endy) ) }  
  local closelist= { }
  
  -- refine this condition just in case for infinite loop?
  while ( true ) do
    -- Get the lowest F node
    local curNode = ExtractLowestF( openlist, closelist )  
    
    if curNode == nil then  
      -- path not found (no more nodes in open list)
      return nil
    elseif curNode.x == endx and curNode.y == endy then
      -- target node added to close list 
      -- it will be returned from open list because it's the lowest F
      return closelist  
    else
      AddAdjacents( grid, dimx, dimy, curNode, openlist, closelist, endx, endy )
    end
  end
end

-- ////////////////////////////////////////////////////////////////////////////////////
-- TEST CODE
-- ////////////////////////////////////////////////////////////////////////////////////
--[[
GRIDW, GRIDH = 8, 8
GRID = { { 0, 0,-1, 0, 0, 0, 0, 0 },         
         { 0, 0,-1, 0,-1,-1,-1, 0 },
         { 0, 0,-1, 0,-1,-1, 0, 0 },
         { 0, 0,-1, 0, 0,-1, 0, 0 },
         { 0, 0,-1,-1,-1,-1, 0, 0 },
         { 0, 0, 0, 0, 0, 0, 0,-1 },
         { 0, 0,-1,-1,-1,-1,-1, 0 },
         { 0, 0, 0, 0, 0, 0, 0, 0 } }
 

local startx, starty = 7, 2
local endx, endy = 4, 5
local cl = CanMoveFromTo( GRID, GRIDW, GRIDH, startx, starty, endx, endy )
print( "Can move? = ", cl ~= nil )

if cl ~= nil then
  -- get the end node from list
  local node = FindNode( endx, endy, cl )
  
  -- back to the start node getting the parents
  print ( "Path:\n" )  
  while node.parent ~= nil do
    print( node.x, ", ", node.y )
    node = node.parent
  end
end
 --]]