Pathfinding tutorial

In this tutorial we will be taking a look at a pathfinding module called MicroPather. MicroPather is a simple yet powerful library based around the A* search algorithm.

Graph representation

A 'graph' is basically a series of nodes linked together. MicroPather takes in two nodes from the graph and finds the shortest route between them. In this example, I have decided to represent the graph as a two-dimensional table. This table will contain either zeros or ones to represent passable and impassable nodes respectively.

-- graph representation
local map = {}
map[1] = { 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 }
map[2] = { 1, 1, 0, 1, 0, 1, 0, 0, 0, 0 }
map[3] = { 0, 0, 0, 1, 0, 1, 1, 1, 1, 0 }
map[4] = { 0, 1, 0, 1, 0, 0, 0, 0, 1, 0 }
map[5] = { 0, 1, 0, 1, 1, 1, 0, 0, 1, 0 }
map[6] = { 1, 1, 0, 0, 0, 1, 1, 0, 1, 0 }
map[7] = { 0, 0, 0, 0, 0, 0, 1, 0, 1, 0 }
map[8] = { 0, 1, 0, 1, 0, 0, 0, 0, 0, 0 }
map[9] = { 0, 1, 1, 1, 1, 1, 0, 1, 1, 0 }
map[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

Our script will be much simpler if we can index graph nodes using a single number. For utility purposes, we will use two functions that convert the two-dimensional index in the graph to a one-dimensional index and vice versa. Also notice that throughout this example, we will be using #map[1] and #map to refer to the width and height of the node graph.

-- converts node index to map position
function ToPosition ( n )
  local x = n % #map[1]
  local y = ( n - x ) / #map[1]
  return x + 1, y + 1
end

-- converts map position to node index
function ToIndex ( x, y )
  return ( y - 1 ) * #map[1] + ( x - 1 )
end

Using MicroPather

Next, we will set up MicroPather so that it can search through our node graph. In order to find the most efficient path, MicroPather has to know the 'cost' required to traverse between nodes. We will have to implement two functions: 'LeastCostEstimate' and 'AdjacentCost'. In 'LeastCostEstimate', I've used the Pythagorean theorem to find the Euclidean distance between any two nodes on our graph. 'AdjacentCost' finds the StateCost between a given node and all of its neighbors. I have set the cost for traversing adjacent nodes to 1. This value may be different if you plan on implementing various terrain types or if you want to allow traversing of nodes diagonally.

-- initializes MicroPather
require ( 'MicroPather' )

local graph = micropather.Map ( )

-- calculates the minimal traverse cost between two nodes
function graph:LeastCostEstimate ( s, e )
  local sx, sy = ToPosition ( s )
  local ex, ey = ToPosition ( e )
  local dx = ex - sx
  local dy = ey - sy
  return math.sqrt ( dx * dx + dy * dy )
end

-- calculates the traverse cost between neighboring nodes
function graph:AdjacentCost ( node, a )
  local x, y = ToPosition ( node )
  if map[y][x] ~= 0 then
    return
  end

  if x < #map[1] and map[y][x + 1] == 0 then
    local sc = micropather.StateCost ( ToIndex ( x + 1, y ), 1 )
    table.insert ( a, sc )
  end
  if x > 1 and map[y][x - 1] == 0 then
    local sc = micropather.StateCost ( ToIndex ( x - 1, y ), 1 )
    table.insert ( a, sc )
  end
  if y < #map and map[y + 1][x] == 0 then
    local sc = micropather.StateCost ( ToIndex ( x, y + 1 ), 1 )
    table.insert ( a, sc )
  end
  if y > 1 and map[y - 1][x] == 0 then
    local sc = micropather.StateCost ( ToIndex ( x, y - 1 ), 1 )
    table.insert ( a, sc )
  end
end

-- initializes node graph
local pather = micropather.MicroPather ( graph )

MicroPather is now ready to solve our graph. For this example, we'll use the top-left corner as a starting point and the bottom-right will be our goal. The "Solve" function returns the status code of the search (SOLVED, NO_SOLUTION or START_END_SAME) as well as the total cost for traversing the solved path. An actual node-by-node solution is inserted in the table supplied as the third parameter to 'Solve'.

-- attempts to solve the graph
local s = ToIndex ( 1, 1 )
local e = ToIndex ( #map[1], #map )
local path = {}
local ret, cost = pather:Solve ( s, e, path, 0 )

Rendering the graph

The last part of the script is fairly rudimentary. It creates an appropriately-sized window and draws the graph along with the solved path. The entire graph is rendered onto a single sprite. This approach is probably not the most efficient but it will do for the purposes of the tutorial. Impassable nodes are colored in red and passable ones are gray. The path returned by the 'Solve' function is drawn as a series of filled lime circles.

-- size of a single tile
local tile = 40

-- window size
local width = #map[1] * tile
local height = #map * tile

-- visual representation
display:create ( "MicroPather Demo", width, height, 32, true )

local offsetX = -width / 2 - tile / 2
local offsetY = height / 2 + tile / 2

local sprite = Sprite ( offsetX, offsetY )
display.viewport:add_child ( sprite )

sprite.canvas:clear ( )

-- draws the map
for y, yv in pairs ( map ) do
  for x, xv in pairs ( yv ) do
    sprite.canvas:move_to ( x * tile, -y * tile )
    sprite.canvas:rectangle ( tile - 1, tile - 1 )

    if xv == 1 then
      sprite.canvas:set_fill_style ( RED, 1 )
    elseif xv == 0 then
      sprite.canvas:set_fill_style ( GRAY, 0.5 )
    end
    sprite.canvas:fill ( )
  end
end

if ret == micropather.SOLVED then
  -- draws the solved path
  for i, v in pairs ( path ) do
    local x, y = ToPosition ( v )
    sprite.canvas:move_to ( x * tile, -y * tile )
    sprite.canvas:circle ( tile / 4 )
  end
  sprite.canvas:set_fill_style ( LIME, 1 )
  sprite.canvas:fill ( )
end

Download:

pathfinding.lua