Jumper

gistfile1.txt

--# Main
-- A stress test for the pathfinding library Jumper
-- https://github.com/Yonaba/Jumper/tree/jumper-1.8.1-1
-- The purpose of this is to compare the relative performance of the different
-- search algorithms implemented in Jumper
-- Time measurements uses Lua's native os.clock with  milliseconds precision
 
function setup()
    local Grid = grid()
    local Pathfinder = pathfinder()
    local cg = collectgarbage
    local floor, rand = math.floor, math.random
    local ipairs = ipairs
    math.randomseed(os.time())         
    local walkable = 0
    local test_sizes = {10, 25, 50, 100, 128}
    for i, resol in ipairs(test_sizes) do
        collectgarbage()
        print(('\nGenerating a grid of : %d cells x %d cells...'):format(resol, resol))
        local grid, size = makeGrid(resol, resol)
        print(('Memory used to store the grid (%d x %d): %d kiB'):format(resol, resol, size))
        local results = {}
        for _,finderName in ipairs(Pathfinder:getFinders()) do
            local finder = Pathfinder:new(grid, finderName, walkable)
            local p, len, tm = findPath(finder, resol, resol)
            if p then
                results[#results+1] = {f = finderName, len = len, time = tm}
            end
        end
        table.sort(results, function(a,b) return a.time < b.time end)
        for k,v in ipairs(results) do
            print((' %-08s - path length: %.2f - Time: %.2f ms'):format(v.f, v.len, v.time))
        end
    end
end

local function obstruct(map, h, w)
    local switch = false
    for i = 2,h-1,2 do
        local s = switch and 1 or 2
        local e = s==1 and w-1 or w
        for j = s,e do
            map[i][j] = 1
        end
        switch = not switch
    end
end
 
local function drawGrid(m)
    for y,row in ipairs(m) do
        print(table.concat(row))
    end
end
 
local function makeGrid(w, h)
  local m = {}
  for y = 1, h do m[y] = {}
    for x = 1, w do m[y][x] = 0 end
  end
  obstruct(m, h, w)
  --drawGrid(m)
  local sizeCount = cg('count')
  local grid = Grid(m)
  return grid , (cg('count')-sizeCount)
end
 
local function findPath(finder, w, h)
    local tm = os.clock()
    local path = finder:getPath(1, 1, w, h)
    if path then return path, path:getLength(), (os.clock()-tm)*1000 end
end
--# astar
--- <strong>`A-star` algorithm</strong>.
-- Implementation of <a href="http://en.wikipedia.org/wiki/A-star">A*</a> search algorithm.
--
-- @author Roland Yonaba
-- @copyright 2012-2013
-- @license <a href="http://www.opensource.org/licenses/mit-license.php">MIT</a>
-- @script jumper.search.astar


-- This implementation of A-star was based on Nash A. & al. pseudocode
-- Added override args to support dijkstra and thetaStar
-- http://aigamedev.com/open/tutorials/theta-star-any-angle-paths/

if (...) then

    -- Internalization
    local ipairs = ipairs
    local huge = math.huge

    -- Depandancies
    local Heuristics = require ((...):match('(.+)%.search.astar$') .. '.core.heuristics')

    -- Updates G-cost
    local function computeCost(node, neighbour, finder)
        local mCost = Heuristics.EUCLIDIAN(neighbour.x - node.x, neighbour.y - node.y)
        if node.g + mCost < neighbour.g then
            neighbour.parent = node
            neighbour.g = node.g + mCost
        end    
    end

    -- Updates vertex node-neighbour
    local function updateVertex(finder, node, neighbour, endNode, heuristic, overrideCostEval)
        local oldG = neighbour.g
        local cmpCost = overrideCostEval or computeCost
        cmpCost(node, neighbour, finder)
        if neighbour.g < oldG then
            if neighbour.opened then
                neighbour.opened = false
            end
            neighbour.h = heuristic(endNode.x - neighbour.x, endNode.y - neighbour.y)
            neighbour.f = neighbour.g + neighbour.h
            finder.openList:push(neighbour)
            neighbour.opened = true
        end    
    end

  -- Calculates a path.
  -- Returns the path from location `<startX, startY>` to location `<endX, endY>`.
  return function (finder, startNode, endNode, toClear, tunnel, overrideHeuristic, overrideCostEval)
        local heuristic = overrideHeuristic or finder.heuristic

        finder.openList:clear()
        startNode.g = 0
        startNode.h = heuristic(endNode.x - startNode.x, endNode.y - startNode.y)
        startNode.f = startNode.g + startNode.h
        finder.openList:push(startNode)
        toClear[startNode] = true
        startNode.opened = true

        while not finder.openList:empty() do
            local node = finder.openList:pop()
            node.closed = true
            if node == endNode then
                return node
            end
            local neighbours = finder.grid:getNeighbours(node, finder.walkable, finder.allowDiagonal, tunnel)
            for i, neighbour in ipairs(neighbours) do
                if not neighbour.closed then
                    toClear[neighbour] = true
                    if not neighbour.opened then
                        neighbour.g = huge
                        neighbour.parent = nil                    
                    end
                    updateVertex(finder, node, neighbour, endNode, heuristic, overrideCostEval)
                end            
            end        
        end        

        return nil
    end

end

--[[
Copyright (c) 2012-2013 Roland Yonaba

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
--]]
--# bfs
--- <strong>`Breadth-First Search` algorithm</strong>.
-- Implementation of <a href="http://en.wikipedia.org/wiki/Breadth-first_search">Breadth-First Search</a> search algorithm.
--
-- @author Roland Yonaba
-- @copyright 2012-2013
-- @license <a href="http://www.opensource.org/licenses/mit-license.php">MIT</a>
-- @script jumper.search.bfs



if (...) then
  -- Internalization
  local t_remove = table.remove

  local function breadth_first_search(finder, node, openList, toClear, tunnel)
    local neighbours = finder.grid:getNeighbours(node, finder.walkable, finder.allowDiagonal, tunnel)
    for i = 1,#neighbours do
      local neighbour = neighbours[i]
      if not neighbour.closed and not neighbour.opened then
        openList[#openList+1] = neighbour
        neighbour.opened = true
        neighbour.parent = node
        toClear[neighbour] = true
      end
    end

  end

  -- Calculates a path.
  -- Returns the path from location `<startX, startY>` to location `<endX, endY>`.
  return function (finder, startNode, endNode, toClear, tunnel)

    local openList = {} -- We'll use a FIFO queue (simple array)
    openList[1] = startNode
    startNode.opened = true
    toClear[startNode] = true

    local node
    while (#openList > 0) do
      node = openList[1]
      t_remove(openList,1)
      node.closed = true

      if node == endNode then
        return node
      end

      breadth_first_search(finder, node, openList, toClear, tunnel)
    end

    return nil
  end

end

--[[
Copyright (c) 2012-2013 Roland Yonaba

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
--]]
--# bheap
--- <strong>A light implementation of `binary heaps`</strong>.
-- While running a search, some algorithms have to maintains a list of nodes called __open list__.
-- Finding in this list the lowest cost node from the node being processed can be quite slow, 
-- (as it requires to skim through the collection of nodes stored in this list) 
-- especially when dozens of nodes are being processed (large maps). 
--
-- The current module implements a <a href="http://www.policyalmanac.org/games/binaryHeaps.htm">binary heap</a> data structure,
-- from which the internal open list will be instantiated. As such, looking up for lower-cost 
-- node will run faster, and globally makes the search algorithm run faster.
--
-- This module should normally not be used explicitely. The algorithm uses it internally.
--
-- @author Roland Yonaba
-- @copyright 2012-2013
-- @license <a href="http://www.opensource.org/licenses/mit-license.php">MIT</a>
-- @module jumper.core.bheap

--[[
  Notes:
  Lighter implementation of binary heaps, based on :
    https://github.com/Yonaba/Binary-Heaps
--]]

local floor = math.floor

-- Lookup for value in a table
local indexOf = function(t,v)
  for i = 1,#t do
    if t[i] == v then return i end
  end
  return nil
end

-- Default comparison function
local function f_min(a,b) 
  return a < b 
end

-- Percolates up
local function percolate_up(heap, index)
  if index == 1 then return end
  local pIndex
  if index <= 1 then return end
  if index%2 == 0 then
    pIndex =  index/2
  else pIndex = (index-1)/2
  end
  if not heap.sort(heap.__heap[pIndex], heap.__heap[index]) then
    heap.__heap[pIndex], heap.__heap[index] = 
      heap.__heap[index], heap.__heap[pIndex]
    percolate_up(heap, pIndex)
  end
end

-- Percolates down
local function percolate_down(heap,index)
  local lfIndex,rtIndex,minIndex
  lfIndex = 2*index
  rtIndex = lfIndex + 1
  if rtIndex > heap.size then
    if lfIndex > heap.size then return
    else minIndex = lfIndex  end
  else
    if heap.sort(heap.__heap[lfIndex],heap.__heap[rtIndex]) then
      minIndex = lfIndex
    else
      minIndex = rtIndex
    end
  end
  if not heap.sort(heap.__heap[index],heap.__heap[minIndex]) then
    heap.__heap[index],heap.__heap[minIndex] = heap.__heap[minIndex],heap.__heap[index]
    percolate_down(heap,minIndex)
  end
end

-- Produces a new heap
local function newHeap(template,comp)
  return setmetatable({__heap = {},
    sort = comp or f_min, size = 0},
  template)
end

--- The `heap` class
-- @class table
-- @name heap
local heap = setmetatable({},
  {__call = function(self,...)
    return newHeap(self,...)
  end})
heap.__index = heap

--- Checks if a `heap` is empty
-- @class function
-- @name heap:empty
-- @treturn bool `true` of no item is queued in the heap, `false` otherwise
function heap:empty()
  return (self.size==0)
end

--- Clears the `heap` (removes all items queued in the heap)
-- @class function
-- @name heap:clear
function heap:clear()
  self.__heap = {}
  self.size = 0
  self.sort = self.sort or f_min
  return self
end

--- Adds a new item in the `heap`
-- @class function
-- @name heap:push
-- @tparam object item a new object to be queued in the heap
function heap:push(item)
    if item then
        self.size = self.size + 1
        self.__heap[self.size] = item
        percolate_up(self, self.size)
    end
  return self
end

--- Pops from the `heap`.
-- Removes and returns the lowest cost item (with respect to the comparison function used) from the `heap`.
-- @class function
-- @name heap:pop
-- @treturn object an object stored in the heap
function heap:pop()
  local root
  if self.size > 0 then
    root = self.__heap[1]
    self.__heap[1] = self.__heap[self.size]
    self.__heap[self.size] = nil
    self.size = self.size-1
    if self.size>1 then
      percolate_down(self, 1)
    end
  end
  return root
end

--- Restores the `heap` property.
-- Reorders the `heap` with respect to the comparison function being used. 
-- When given arg `item`, will sort that very item in the `heap`. 
-- Otherwise, the whole `heap` will be sorted. 
-- @class function
-- @name heap:heapify
-- @tparam[opt] object item the modified object 
function heap:heapify(item)
  if item then
    local i = indexOf(self.__heap,item)
    if i then 
      percolate_down(self, i)
      percolate_up(self, i)
    end
    return
  end
  for i = floor(self.size/2),1,-1 do
    percolate_down(self,i)
  end
  return self
end

return heap

--[[
Copyright (c) 2012-2013 Roland Yonaba
Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
--]]
--# dfs
--- <strong>`Depth First Search` algorithm</strong>.
-- Implementation of <a href="http://en.wikipedia.org/wiki/Depth-first_search">Depth First Search</a> search algorithm.
--
-- @author Roland Yonaba
-- @copyright 2012-2013
-- @license <a href="http://www.opensource.org/licenses/mit-license.php">MIT</a>
-- @script jumper.search.dfs



if (...) then
  -- Internalization
  local t_remove = table.remove

  local function depth_first_search(finder, node, openList, toClear)
    local neighbours = finder.grid:getNeighbours(node, finder.walkable, finder.allowDiagonal, tunnel)
    for i = 1,#neighbours do
      local neighbour = neighbours[i]
      if (not neighbour.closed and not neighbour.opened) then
        openList[#openList+1] = neighbour
        neighbour.opened = true
        neighbour.parent = node
        toClear[neighbour] = true
      end
    end

  end

  -- Calculates a path.
  -- Returns the path from location `<startX, startY>` to location `<endX, endY>`.
  return function (finder, startNode, endNode, toClear, tunnel)

    local openList = {} -- We'll use a LIFO queue (simple array)
    openList[1] = startNode
    startNode.opened = true
    toClear[startNode] = true

    local node
    while (#openList > 0) do
      node = openList[#openList]
      t_remove(openList)
      node.closed = true

      if node == endNode then
        return node
      end

      depth_first_search(finder, node, openList, toClear, tunnel)
    end

    return nil
  end

end

--[[
Copyright (c) 2012-2013 Roland Yonaba

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
--]]
--# dijkstra
--- <strong>`Dijkstra` algorithm</strong>.
-- Implementation of <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">Dijkstra</a> search algorithm
--
-- @author Roland Yonaba
-- @copyright 2012-2013
-- @license <a href="http://www.opensource.org/licenses/mit-license.php">MIT</a>
-- @script jumper.search.dijkstra



if (...) then

  local astar_search = require ((...):gsub('%.dijkstra$','.astar'))
  -- Dijkstra is similar to aStar, with no heuristic
  local dijkstraHeuristic = function() return 0 end

  -- Calculates a path.
  -- Returns the path from location `<startX, startY>` to location `<endX, endY>`.
  return function (finder, startNode, endNode, toClear, tunnel)
    return astar_search(finder, startNode, endNode, toClear, tunnel, dijkstraHeuristic)
  end

end

--[[
Copyright (c) 2012-2013 Roland Yonaba

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
--]]
--# grid
--- <strong>The <code>grid</code> class API</strong>.
--
-- Implementation of a `grid` class, which represents the 2D map (graph) on which a `pathfinder` will perform.
--
-- During a search, the pathfinder evaluates __costs values__ for each node being processed, in order to
-- select, after each step of iteration, what node should be expanded next to reach the target
-- optimally. Those values are cached within an array of nodes inside the `grid` object.
--
-- @author Roland Yonaba
-- @copyright 2012-2013
-- @license <a href="http://www.opensource.org/licenses/mit-license.php">MIT</a>
-- @module jumper.grid

--- @usage
local usage = [[
-- Usage Example
-- First, set a collision map
local map = {
    {0,1,0,1,0},
    {0,1,0,1,0},
    {0,1,1,1,0},
    {0,0,0,0,0},
}
-- Value for walkable tiles
local walkable = 0

-- Library setup
--local Grid = require ("jumper.grid") -- The grid class

-- Creates a grid object
local grid = Grid(map)
]]

if (...) then
  local _PATH = (...):gsub('%.grid$','')
  local pairs = pairs
  local assert = assert
  local next = next
  local floor = math.floor
    local otype = type
  local Node = require (_PATH .. '.core.node')

  ---------------------------------------------------------------------
  -- Private utilities

    -- Is i and integer ?
    local isInt = function(i)
        return otype(i) =='number' and floor(i)==i
    end

    -- Override type to report integers
    local type = function(v)
        if isInt(v) then return 'int' end
        return otype(v)
    end

    -- Real count of for values in an array
    local size = function(t)
        local count = 0
        for k,v in pairs(t) do count = count+1 end
        return count
    end

    -- Checks array contents
    local check_contents = function(t,...)
        local n_count = size(t)
        if n_count < 1 then return false end
        local init_count = t[0] and 0 or 1
        local n_count = (t[0] and n_count-1 or n_count)
        local types = {...}
        if types then types = table.concat(types) end
        for i=init_count,n_count,1 do
            if not t[i] then return false end
            if types then
                if not types:match(type(t[i])) then return false end
            end
        end
        return true
    end

    -- Checks if m is a regular map
  local function isMap(m)
        if not check_contents(m, 'table') then return false end
        local lsize = size(m[next(m)])
        for k,v in pairs(m) do
            if not check_contents(m[k], 'string', 'int') then return false end
            if size(v)~=lsize then return false end
        end
        return true
  end

  -- Is arg a valid string map
  local function isStringMap(s)
    if type(m) ~= 'string' then return false end
    local w
    for row in s:gmatch('[^\n\r]+') do
      if not row then return false end
      w = w or #row
      if w ~= #row then return false end
    end
    return true
  end

  -- Parses a map
  local function parseStringMap(str)
        local map = {}
        local w, h
    for line in str:gmatch('[^\n\r]+') do
      if line then
        w = not w and #line or w
        assert(#line == w, 'Error parsing map, rows must have the same size!')
        h = (h or 0) + 1
        map[h] = {}
        for char in line:gmatch('.') do 
                    map[h][#map[h]+1] = char 
                end
      end
    end
    return map
  end

  -- Postprocessing : Get map bounds
  local function getBounds(map)
    local min_bound_x, max_bound_x
    local min_bound_y, max_bound_y

      for y in pairs(map) do
        min_bound_y = not min_bound_y and y or (y<min_bound_y and y or min_bound_y)
        max_bound_y = not max_bound_y and y or (y>max_bound_y and y or max_bound_y)
        for x in pairs(map[y]) do
          min_bound_x = not min_bound_x and x or (x<min_bound_x and x or min_bound_x)
          max_bound_x = not max_bound_x and x or (x>max_bound_x and x or max_bound_x)
        end
      end
    return min_bound_x,max_bound_x,min_bound_y,max_bound_y
  end

  -- Preprocessing
  local function buildGrid(map)
    local min_bound_x, max_bound_x
    local min_bound_y, max_bound_y

    local nodes = {}
      for y in pairs(map) do
        min_bound_y = not min_bound_y and y or (y<min_bound_y and y or min_bound_y)
        max_bound_y = not max_bound_y and y or (y>max_bound_y and y or max_bound_y)
        nodes[y] = {}
        for x in pairs(map[y]) do
          min_bound_x = not min_bound_x and x or (x<min_bound_x and x or min_bound_x)
          max_bound_x = not max_bound_x and x or (x>max_bound_x and x or max_bound_x)
          nodes[y][x] = Node:new(x,y)
        end
      end
    return nodes,
             (min_bound_x or 0), (max_bound_x or 0),
             (min_bound_y or 0), (max_bound_y or 0)
  end

  -- Checks if a value is out of and interval [lowerBound,upperBound]
  local function outOfRange(i,lowerBound,upperBound)
    return (i< lowerBound or i > upperBound)
  end

  -- Offsets for straights moves
  local straightOffsets = {
    {x = 1, y = 0} --[[W]], {x = -1, y =  0}, --[[E]]
    {x = 0, y = 1} --[[S]], {x =  0, y = -1}, --[[N]]
  }

  -- Offsets for diagonal moves
  local diagonalOffsets = {
    {x = -1, y = -1} --[[NW]], {x = 1, y = -1}, --[[NE]]
    {x = -1, y =  1} --[[SW]], {x = 1, y =  1}, --[[SE]]
  }

  ---------------------------------------------------------------------
  --- The `grid` class
  -- @class table
  -- @name grid
  -- @field width The grid width
  -- @field height The grid height
  -- @field map A reference to the collision map
  -- @field nodes A 2D array of nodes, each node matching a cell on the collision map
  local Grid = {}
  Grid.__index = Grid

  -- Specialized grids
  local PreProcessGrid = setmetatable({},Grid)
  local PostProcessGrid = setmetatable({},Grid)
  PreProcessGrid.__index = PreProcessGrid
  PostProcessGrid.__index = PostProcessGrid
  PreProcessGrid.__call = function (self,x,y)
    return self:getNodeAt(x,y)
  end
  PostProcessGrid.__call = function (self,x,y,create)
    if create then return self:getNodeAt(x,y) end
    return self.nodes[y] and self.nodes[y][x]
  end

  --- Inits a new `grid` object
  -- @class function
  -- @name grid:new
  -- @tparam table|string map A collision map - (2D array) with consecutive integer indices or a string with line-break symbol as a row delimiter.
  -- @tparam[optchain] bool processOnDemand whether or not caching nodes in the internal grid should be processed on-demand
  -- @treturn grid a new `grid` object
  function Grid:new(map, processOnDemand)
        map = type(map)=='string' and parseStringMap(map) or map
    assert(isMap(map) or isStringMap(map),('Bad argument #1. Not a valid map'))
    assert(type(processOnDemand) == 'boolean' or not processOnDemand,
      ('Bad argument #2. Expected \'boolean\', got %s.'):format(type(processOnDemand)))

    if processOnDemand then
      return PostProcessGrid:new(map,walkable)
    end
    return PreProcessGrid:new(map,walkable)
  end

  --- Checks walkability. Tests if `node` [x,y] exists on the collision map and is walkable
  -- @class function
  -- @name grid:isWalkableAt
  -- @tparam int x the x-coordinate of the node
  -- @tparam int y the y-coordinate of the node
  -- @tparam string|int|function walkable the value for walkable nodes on the passed-in map array.
  -- If this parameter is a function, it should be prototyped as `f(value)`, returning a boolean:
  -- `true` when value matches a *walkable* node, `false` otherwise. If this parameter is not given and
  -- node [x,y] exists, this function return `true`.
  -- @treturn bool `true` if the node exist and is walkable, `false` otherwise
  function Grid:isWalkableAt(x, y, walkable)
    local nodeValue = self.map[y] and self.map[y][x]
    if nodeValue then
      if not walkable then return true end
    else 
            return false
    end
    if self.__eval then return walkable(nodeValue) end
    return (nodeValue == walkable)
  end

  --- Gets the `grid` width.
  -- @class function
  -- @name grid:getWidth
  -- @treturn int the `grid` object width
  function Grid:getWidth()
    return self.width
  end

  --- Gets the `grid` height.
  -- @class function
  -- @name grid:getHeight
  -- @treturn int the `grid` object height
  function Grid:getHeight()
     return self.height
  end

  --- Gets the collision map.
  -- @class function
  -- @name grid:getMap
  -- @treturn {{value},...} the collision map previously passed to the `grid` object on initalization
  function Grid:getMap()
    return self.map
  end

  --- Gets the `grid` nodes.
  -- @class function
  -- @name grid:getNodes
  -- @treturn {{node},...} the `grid` nodes
  function Grid:getNodes()
    return self.nodes
  end

  --- Returns the neighbours of a given `node` on a `grid`
  -- @class function
  -- @name grid:getNeighbours
  -- @tparam node node `node` object
  -- @tparam string|int|function walkable the value for walkable nodes on the passed-in map array.
  -- If this parameter is a function, it should be prototyped as `f(value)`, returning a boolean:
  -- `true` when value matches a *walkable* node, `false` otherwise.
  -- @tparam[opt] bool allowDiagonal whether or not adjacent nodes (8-directions moves) are allowed
  -- @tparam[optchain] bool tunnel Whether or not the pathfinder can tunnel though walls diagonally
  -- @treturn {node,...} an array of nodes neighbouring a passed-in node on the collision map
  function Grid:getNeighbours(node, walkable, allowDiagonal, tunnel)
        local neighbours = {}
    for i = 1,#straightOffsets do
      local n = self:getNodeAt(
        node.x + straightOffsets[i].x,
        node.y + straightOffsets[i].y
      )
      if n and self:isWalkableAt(n.x, n.y, walkable) then
        neighbours[#neighbours+1] = n
      end
    end

    if not allowDiagonal then return neighbours end

        tunnel = not not tunnel
    for i = 1,#diagonalOffsets do
      local n = self:getNodeAt(
        node.x + diagonalOffsets[i].x,
        node.y + diagonalOffsets[i].y
      )
      if n and self:isWalkableAt(n.x, n.y, walkable) then
                if tunnel then
                    neighbours[#neighbours+1] = n
                else
                    local skipThisNode = false
                    local n1 = self:getNodeAt(node.x+diagonalOffsets[i].x, node.y)
                    local n2 = self:getNodeAt(node.x, node.y+diagonalOffsets[i].y)
                    if ((n1 and n2) and not self:isWalkableAt(n1.x, n1.y, walkable) and not self:isWalkableAt(n2.x, n2.y, walkable)) then
                        skipThisNode = true
                    end
                    if not skipThisNode then neighbours[#neighbours+1] = n end
                end
      end
    end

    return neighbours
  end

  --- Iterates on nodes on the grid. When given no args, will iterate on every single node
  -- on the grid, in case the grid is pre-processed. Passing `lx, ly, ex, ey` args will iterate
  -- on nodes inside a bounding-rectangle delimited by those coordinates.
  -- @class function
  -- @name grid:iter
  -- @tparam[opt] int lx the leftmost x-coordinate coordinate of the rectangle
  -- @tparam[optchain] int ly the topmost y-coordinate of the rectangle
  -- @tparam[optchain] int ex the rightmost x-coordinate of the rectangle
  -- @tparam[optchain] int ey the bottom-most y-coordinate of the rectangle
  -- @treturn node a node on the collision map, upon each iteration step
  function Grid:iter(lx,ly,ex,ey)
    local min_x = lx or self.min_bound_x
    local min_y = ly or self.min_bound_y
    local max_x = ex or self.max_bound_x
    local max_y = ey or self.max_bound_y

    local x, y
    y = min_y
    return function()
      x = not x and min_x or x+1
      if x>max_x then
        x = min_x
        y = y+1
      end
      if y > max_y then
        y = nil
      end
      return self.nodes[y] and self.nodes[y][x] or self:getNodeAt(x,y)
    end
  end

  --- Each transformation. Executes a function on each `node` in the `grid`, passing the `node` as the first arg to function `f`.
  -- @class function
  -- @name grid:each
  -- @tparam function f a function prototyped as `f(node,...)`
  -- @tparam[opt] vararg ... args to be passed to function `f`
  function Grid:each(f,...)
    for node in self:iter() do f(node,...) end
  end

  --- Each in range transformation. Executes a function on each `node` in the range of a rectangle of cells, passing the `node` as the first arg to function `f`.
  -- @class function
  -- @name grid:eachRange
  -- @tparam int lx the leftmost x-coordinate coordinate of the rectangle
  -- @tparam int ly the topmost y-coordinate of the rectangle
  -- @tparam int ex the rightmost x-coordinate of the rectangle
  -- @tparam int ey the bottom-most y-coordinate of the rectangle
  -- @tparam function f a function prototyped as `f(node,...)`
  -- @tparam[opt] vararg ... args to be passed to function `f`
  function Grid:eachRange(lx,ly,ex,ey,f,...)
    for node in self:iter(lx,ly,ex,ey) do f(node,...) end
  end

  --- Map transformation. Maps function `f(node,...)` on each `node` in a given range, passing the `node` as the first arg to function `f`. The passed-in function should return a `node` object.
  -- @class function
  -- @name grid:imap
  -- @tparam function f a function prototyped as `f(node,...)`
  -- @tparam[opt] vararg ... args to be passed to function `f`
  function Grid:imap(f,...)
    for node in self:iter() do
      node = f(node,...)
    end
  end

  --- Map in range transformation. Maps `f(node,...)` on each `nod`e in the range of a rectangle of cells, passing the `node` as the first arg to function `f`. The passed-in function should return a `node` object.
  -- @class function
  -- @name grid:imapRange
  -- @tparam int lx the leftmost x-coordinate coordinate of the rectangle
  -- @tparam int ly the topmost y-coordinate of the rectangle
  -- @tparam int ex the rightmost x-coordinate of the rectangle
  -- @tparam int ey the bottom-most y-coordinate of the rectangle
  -- @tparam function f a function prototyped as `f(node,...)`
  -- @tparam[opt] vararg ... args to be passed to function `f`
  function Grid:imapRange(lx,ly,ex,ey,f,...)
    for node in self:iter(lx,ly,ex,ey) do
      node = f(node,...)
    end
  end


  -- Specialized grids
  -- Inits a preprocessed grid
  function PreProcessGrid:new(map)
    local newGrid = {}
    newGrid.map = map
    newGrid.nodes, newGrid.min_bound_x, newGrid.max_bound_x, newGrid.min_bound_y, newGrid.max_bound_y = buildGrid(newGrid.map)
    newGrid.width = (newGrid.max_bound_x-newGrid.min_bound_x)+1
    newGrid.height = (newGrid.max_bound_y-newGrid.min_bound_y)+1
    return setmetatable(newGrid,PreProcessGrid)
  end

  -- Inits a postprocessed grid
  function PostProcessGrid:new(map)
    local newGrid = {}
    newGrid.map = map
    newGrid.nodes = {}
    newGrid.min_bound_x, newGrid.max_bound_x, newGrid.min_bound_y, newGrid.max_bound_y = getBounds(newGrid.map)
    newGrid.width = (newGrid.max_bound_x-newGrid.min_bound_x)+1
    newGrid.height = (newGrid.max_bound_y-newGrid.min_bound_y)+1
    return setmetatable(newGrid,PostProcessGrid)
  end

  --- Returns the `node`[x,y] on a `grid`.
  -- @class function
  -- @name grid:getNodeAt
  -- @tparam int x the x-coordinate coordinate
  -- @tparam int y the y-coordinate coordinate
  -- @treturn node a `node` object
  -- Gets the node at location <x,y> on a preprocessed grid
  function PreProcessGrid:getNodeAt(x,y)
    return self.nodes[y] and self.nodes[y][x] or nil
  end

  -- Gets the node at location <x,y> on a postprocessed grid
  function PostProcessGrid:getNodeAt(x,y)
    if not x or not y then return end
    if outOfRange(x,self.min_bound_x,self.max_bound_x) then return end
    if outOfRange(y,self.min_bound_y,self.max_bound_y) then return end
    if not self.nodes[y] then self.nodes[y] = {} end
    if not self.nodes[y][x] then self.nodes[y][x] = Node:new(x,y) end
    return self.nodes[y][x]
  end

  return setmetatable(Grid,{
    __call = function(self,...)
      return self:new(...)
    end
  })

end


--[[
Copyright (c) 2012 Roland Yonaba

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
--]]
--# heuristics
--- <strong>Heuristics for the search algorithm</strong>.
-- A <a href="http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html">heuristic</a> 
-- provides an *estimate of the optimal cost* from a given location to a target. 
-- As such, it guides the pathfinder to the goal, helping it to decide which route is the best.
--
-- This script holds the definition of built-in heuristics available.
--
-- Distance functions are internally used by the `pathfinder` to evaluate the optimal path
-- from the start location to the goal. These functions share the same prototype:
-- <ul>
-- <pre class="example">
-- local function myHeuristic(dx, dy)
--   -- function body
-- end
-- </pre></ul>
-- Jumper features some built-in distance heuristics, named `MANHATTAN`, `EUCLIDIAN`, `DIAGONAL`, `CARDINTCARD`.
-- You can also supply your own heuristic function, using the template given above.
-- @author Roland Yonaba
-- @copyright 2012-2013
-- @license MIT
-- @module jumper.core.heuristics

--- @usage
local usage = [[
  -- Example
  local Distance = require ('jumper.core.heuristics')
  local Grid = require ("jumper.grid")
  local Pathfinder = require ("jumper.pathfinder")
  local walkable = 0
  -- Placeholder: local map = {...}
  local grid = Grid(map)
  local myFinder = Pathfinder('ASTAR', grid, walkable)
  
  -- Use Euclidian heuristic to evaluate distance
  myFinder:setHeuristic('EUCLIDIAN') 
  -- etc ... 
]]

local abs = math.abs
local sqrt = math.sqrt
local sqrt2 = sqrt(2)
local max, min = math.max, math.min

local Heuristics = {}
  --- Manhattan distance.
  -- <br/>This heuristic is the default one being used by the `pathfinder` object.
  -- <br/>Evaluates as `distance = |dx|+|dy|`
  -- @class function
  -- @name Heuristics.MANHATTAN
  -- @tparam int dx the difference endX-startX
  -- @tparam int dy the difference endY-startY
  -- @treturn number the distance from location `startX, startY` to location `endX, endY`
  -- <ul>
  -- <pre class="example">
  -- -- First method
  -- pathfinder:setHeuristic('MANHATTAN')<br/>
  -- -- Second method
  -- local Distance = require ('jumper.core.heuristics')
  -- pathfinder:setHeuristic(Distance.MANHATTAN)
  -- </pre></ul>
  function Heuristics.MANHATTAN(dx,dy) return abs(dx)+abs(dy) end
  
  --- Euclidian distance.
  -- <br/>Evaluates as `distance = squareRoot(dx*dx+dy*dy)`
  -- @class function
  -- @name Heuristics.EUCLIDIAN
  -- @tparam int dx the difference endX-startX
  -- @tparam int dy the difference endY-startY
  -- @treturn number the distance from location `startX, startY` to location `endX, endY`
  -- <ul>
  -- <pre class="example">
  -- -- First method
  -- pathfinder:setHeuristic('EUCLIDIAN')<br/>
  -- -- Second method
  -- local Distance = require ('jumper.core.heuristics')
  -- pathfinder:setHeuristic(Distance.EUCLIDIAN)
  -- </pre></ul>  
  function Heuristics.EUCLIDIAN(dx,dy) return sqrt(dx*dx+dy*dy) end
  
  --- Diagonal distance.
  -- <br/>Evaluates as `distance = max(|dx|, abs|dy|)`
  -- @class function
  -- @name Heuristics.DIAGONAL
  -- @tparam int dx the difference endX-startX
  -- @tparam int dy the difference endY-startY
  -- @treturn number the distance from location `startX, startY` to location `endX, endY`
  -- <ul>
  -- <pre class="example">
  -- -- First method
  -- pathfinder:setHeuristic('DIAGONAL')<br/>
  -- -- Second method
  -- local Distance = require ('jumper.core.heuristics')
  -- pathfinder:setHeuristic(Distance.DIAGONAL)
  -- </pre></ul>   
  function Heuristics.DIAGONAL(dx,dy) return max(abs(dx),abs(dy)) end
  
  --- Cardinal/Intercardinal distance.
  -- <br/>Evaluates as `distance = min(dx, dy)*squareRoot(2) + max(dx, dy) - min(dx, dy)`
  -- @class function
  -- @name Heuristics.CARDINTCARD
  -- @tparam int dx the difference endX-startX
  -- @tparam int dy the difference endY-startY
  -- @treturn number the distance from location `startX, startY` to location `endX, endY`
  -- <ul>
  -- <pre class="example">
  -- -- First method
  -- pathfinder:setHeuristic('CARDINTCARD')<br/>
  -- -- Second method
  -- local Distance = require ('jumper.core.heuristics')
  -- pathfinder:setHeuristic(Distance.CARDINTCARD)
  -- </pre></ul>  
  function Heuristics.CARDINTCARD(dx,dy) 
    dx, dy = abs(dx), abs(dy)
    return min(dx,dy) * sqrt2 + max(dx,dy) - min(dx,dy)
  end

return Heuristics

--[[
Copyright (c) 2012-2013 Roland Yonaba

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
--]]
--# jps
--- <strong>`Jump Point Search` algorithm</strong>.
-- This file holds an implementation of <a href="http://harablog.wordpress.com/2011/09/07/jump-point-search/">Jump Point Search</a> algorithm.
-- To quote its authors, __Jump Point Search__ is basically
-- "*an online symmetry breaking algorithm which speeds up pathfinding
-- on uniform-cost grid maps by __jumping over__ many locations that would otherwise
-- need to be explicitly considered* ".
--
-- It neither requires preprocessing, nor generates memory overhead, and thus performs consistently fast than classical A*.
--
-- The following implementation was written with respect to the core pseudo-code given in
-- its <a href="http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf">
-- technical papers,</a> plus a wide
-- range of optimizations and additional features.
--
-- @author Roland Yonaba
-- @copyright 2012-2013
-- @license <a href="http://www.opensource.org/licenses/mit-license.php">MIT</a>
-- @script jumper.search.jps


if (...) then

  -- Dependancies
  local _PATH = (...):match('(.+)%.search.jps$')
  local Heuristics = require (_PATH .. '.core.heuristics')

  -- Internalization
  local max, abs = math.max, math.abs

  -- Local helpers, these routines will stay private
  -- As they are internally used by the public interface

  -- Check if a node is reachable in diagonal-search mode
  -- Will prevent from "tunneling" issue when
  -- the goal node is neighbouring a starting location
  local step_first = false
  local function testFirstStep(finder, jNode, node)
    local is_reachable = true
    local jx, jy = jNode.x, jNode.y
    local dx,dy = jx-node.x, jy-node.y
    if dx <= -1 then
      if not finder.grid:isWalkableAt(jx+1,jy,finder.walkable) then is_reachable = false end
    elseif dx >= 1 then
      if not finder.grid:isWalkableAt(jx-1,jy,finder.walkable) then is_reachable = false end
    end
    if dy <= -1 then
      if not finder.grid:isWalkableAt(jx,jy+1,finder.walkable) then is_reachable = false end
    elseif dy >= 1 then
      if not finder.grid:isWalkableAt(jx,jy-1,finder.walkable) then is_reachable = false end
    end
    return not is_reachable
 end

  -- Resets properties of nodes expanded during a search
  -- This is a lot faster than resetting all nodes
  -- between consecutive pathfinding requests

  --[[
    Looks for the neighbours of a given node.
    Returns its natural neighbours plus forced neighbours when the given
    node has no parent (generally occurs with the starting node).
    Otherwise, based on the direction of move from the parent, returns
    neighbours while pruning directions which will lead to symmetric paths.

    In case diagonal moves are forbidden, when the given node has no
    parent, we return straight neighbours (up, down, left and right).
    Otherwise, we add left and right node (perpendicular to the direction
    of move) in the neighbours list.
  --]]
  local function findNeighbours(finder,node, tunnel)

    if node.parent then
      local neighbours = {}
      local x,y = node.x, node.y
      -- Node have a parent, we will prune some neighbours
      -- Gets the direction of move
      local dx = (x-node.parent.x)/max(abs(x-node.parent.x),1)
      local dy = (y-node.parent.y)/max(abs(y-node.parent.y),1)

        -- Diagonal move case
      if dx~=0 and dy~=0 then
        local walkY, walkX

        -- Natural neighbours
        if finder.grid:isWalkableAt(x,y+dy,finder.walkable) then
          neighbours[#neighbours+1] = finder.grid:getNodeAt(x,y+dy)
          walkY = true
        end
        if finder.grid:isWalkableAt(x+dx,y,finder.walkable) then
          neighbours[#neighbours+1] = finder.grid:getNodeAt(x+dx,y)
          walkX = true
        end
        if walkX or walkY then
          neighbours[#neighbours+1] = finder.grid:getNodeAt(x+dx,y+dy)
        end

        -- Forced neighbours
        if (not finder.grid:isWalkableAt(x-dx,y,finder.walkable)) and walkY then
          neighbours[#neighbours+1] = finder.grid:getNodeAt(x-dx,y+dy)
        end
        if (not finder.grid:isWalkableAt(x,y-dy,finder.walkable)) and walkX then
          neighbours[#neighbours+1] = finder.grid:getNodeAt(x+dx,y-dy)
        end

      else
        -- Move along Y-axis case
        if dx==0 then
          local walkY
          if finder.grid:isWalkableAt(x,y+dy,finder.walkable) then
            neighbours[#neighbours+1] = finder.grid:getNodeAt(x,y+dy)

            -- Forced neighbours are left and right ahead along Y
            if (not finder.grid:isWalkableAt(x+1,y,finder.walkable)) then
              neighbours[#neighbours+1] = finder.grid:getNodeAt(x+1,y+dy)
            end
            if (not finder.grid:isWalkableAt(x-1,y,finder.walkable)) then
              neighbours[#neighbours+1] = finder.grid:getNodeAt(x-1,y+dy)
            end
          end
          -- In case diagonal moves are forbidden : Needs to be optimized
          if not finder.allowDiagonal then
            if finder.grid:isWalkableAt(x+1,y,finder.walkable) then
              neighbours[#neighbours+1] = finder.grid:getNodeAt(x+1,y)
            end
            if finder.grid:isWalkableAt(x-1,y,finder.walkable)
              then neighbours[#neighbours+1] = finder.grid:getNodeAt(x-1,y)
            end
          end
        else
        -- Move along X-axis case
          if finder.grid:isWalkableAt(x+dx,y,finder.walkable) then
            neighbours[#neighbours+1] = finder.grid:getNodeAt(x+dx,y)

            -- Forced neighbours are up and down ahead along X
            if (not finder.grid:isWalkableAt(x,y+1,finder.walkable)) then
              neighbours[#neighbours+1] = finder.grid:getNodeAt(x+dx,y+1)
            end
            if (not finder.grid:isWalkableAt(x,y-1,finder.walkable)) then
              neighbours[#neighbours+1] = finder.grid:getNodeAt(x+dx,y-1)
            end
          end
          -- : In case diagonal moves are forbidden
          if not finder.allowDiagonal then
            if finder.grid:isWalkableAt(x,y+1,finder.walkable) then
              neighbours[#neighbours+1] = finder.grid:getNodeAt(x,y+1)
            end
            if finder.grid:isWalkableAt(x,y-1,finder.walkable) then
              neighbours[#neighbours+1] = finder.grid:getNodeAt(x,y-1)
            end
          end
        end
      end
      return neighbours
    end

    -- Node do not have parent, we return all neighbouring nodes
    return finder.grid:getNeighbours(node, finder.walkable, finder.allowDiagonal, tunnel)
  end

  --[[
    Searches for a jump point (or a turning point) in a specific direction.
    This is a generic translation of the algorithm 2 in the paper:
      http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf
    The current expanded node is a jump point if near a forced node

    In case diagonal moves are forbidden, when lateral nodes (perpendicular to
    the direction of moves are walkable, we force them to be turning points in other
    to perform a straight move.
  --]]
  local function jump(finder, node, parent, endNode)
    if not node then return end

    local x,y = node.x, node.y
    local dx, dy = x - parent.x,y - parent.y

    -- If the node to be examined is unwalkable, return nil
    if not finder.grid:isWalkableAt(x,y,finder.walkable) then return end

    -- If the node to be examined is the endNode, return this node
    if node == endNode then return node end

    -- Diagonal search case
    if dx~=0 and dy~=0 then
      -- Current node is a jump point if one of his leftside/rightside neighbours ahead is forced
      if (finder.grid:isWalkableAt(x-dx,y+dy,finder.walkable) and (not finder.grid:isWalkableAt(x-dx,y,finder.walkable))) or
         (finder.grid:isWalkableAt(x+dx,y-dy,finder.walkable) and (not finder.grid:isWalkableAt(x,y-dy,finder.walkable))) then
        return node
      end
    else
      -- Search along X-axis case
      if dx~=0 then
        if finder.allowDiagonal then
          -- Current node is a jump point if one of his upside/downside neighbours is forced
          if (finder.grid:isWalkableAt(x+dx,y+1,finder.walkable) and (not finder.grid:isWalkableAt(x,y+1,finder.walkable))) or
             (finder.grid:isWalkableAt(x+dx,y-1,finder.walkable) and (not finder.grid:isWalkableAt(x,y-1,finder.walkable))) then
            return node
          end
        else
          -- : in case diagonal moves are forbidden
          if finder.grid:isWalkableAt(x+1,y,finder.walkable) or finder.grid:isWalkableAt(x-1,y,finder.walkable) then return node end
        end
      else
      -- Search along Y-axis case
        -- Current node is a jump point if one of his leftside/rightside neighbours is forced
        if finder.allowDiagonal then
          if (finder.grid:isWalkableAt(x+1,y+dy,finder.walkable) and (not finder.grid:isWalkableAt(x+1,y,finder.walkable))) or
             (finder.grid:isWalkableAt(x-1,y+dy,finder.walkable) and (not finder.grid:isWalkableAt(x-1,y,finder.walkable))) then
            return node
          end
        else
          -- : in case diagonal moves are forbidden
          if finder.grid:isWalkableAt(x,y+1,finder.walkable) or finder.grid:isWalkableAt(x,y-1,finder.walkable) then return node end
        end
      end
    end

    -- Recursive horizontal/vertical search
    if dx~=0 and dy~=0 then
      if jump(finder,finder.grid:getNodeAt(x+dx,y),node,endNode) then return node end
      if jump(finder,finder.grid:getNodeAt(x,y+dy),node,endNode) then return node end
    end

    -- Recursive diagonal search
    if finder.allowDiagonal then
      if finder.grid:isWalkableAt(x+dx,y,finder.walkable) or finder.grid:isWalkableAt(x,y+dy,finder.walkable) then
        return jump(finder,finder.grid:getNodeAt(x+dx,y+dy),node,endNode)
      end
    end
end

  --[[
    Searches for successors of a given node in the direction of each of its neighbours.
    This is a generic translation of the algorithm 1 in the paper:
      http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf

    Also, we notice that processing neighbours in a reverse order producing a natural
    looking path, as the pathfinder tends to keep heading in the same direction.
    In case a jump point was found, and this node happened to be diagonal to the
    node currently expanded in a straight mode search, we skip this jump point.
  --]]
  local function identifySuccessors(finder,node,endNode,toClear, tunnel)

    -- Gets the valid neighbours of the given node
    -- Looks for a jump point in the direction of each neighbour
    local neighbours = findNeighbours(finder,node, tunnel)
    for i = #neighbours,1,-1 do

      local skip = false
      local neighbour = neighbours[i]
      local jumpNode = jump(finder,neighbour,node,endNode)

      -- : in case a diagonal jump point was found in straight mode, skip it.
      if jumpNode and not finder.allowDiagonal then
        if ((jumpNode.x ~= node.x) and (jumpNode.y ~= node.y)) then skip = true end
      end

            --[[
      -- Hacky trick to discard "tunneling" in diagonal mode search for the first step
      if jumpNode and finder.allowDiagonal and not step_first then
        if jumpNode.x == endNode.x and jumpNode.y == endNode.y then
          step_first = true
          if not skip then
            skip = testFirstStep(finder, jumpNode, node)
          end
        end
      end
            --]]
      -- Performs regular A-star on a set of jump points
      if jumpNode and not skip then
        -- Update the jump node and move it in the closed list if it wasn't there
        if not jumpNode.closed then
          local extraG = Heuristics.EUCLIDIAN(jumpNode.x-node.x,jumpNode.y-node.y)
          local newG = node.g + extraG
          if not jumpNode.opened or newG < jumpNode.g then
            toClear[jumpNode] = true -- Records this node to reset its properties later.
            jumpNode.g = newG
            jumpNode.h = jumpNode.h or
              (finder.heuristic(jumpNode.x-endNode.x,jumpNode.y-endNode.y))
            jumpNode.f = jumpNode.g+jumpNode.h
            jumpNode.parent = node
            if not jumpNode.opened then
              finder.openList:push(jumpNode)
              jumpNode.opened = true
              if not step_first then step_first = true end
            else
              finder.openList:heapify(jumpNode)
            end
          end
        end
      end
    end
  end

  -- Calculates a path.
  -- Returns the path from location `<startX, startY>` to location `<endX, endY>`.
  return function(finder, startNode, endNode, toClear, tunnel)

    step_first = false
    startNode.g, startNode.f = 0,0
    finder.openList:clear()
    finder.openList:push(startNode)
    startNode.opened = true
    toClear[startNode] = true

    local node
    while not finder.openList:empty() do
      -- Pops the lowest F-cost node, moves it in the closed list
      node = finder.openList:pop()
      node.closed = true
        -- If the popped node is the endNode, return it
        if node == endNode then
          return node
        end
      -- otherwise, identify successors of the popped node
      identifySuccessors(finder, node, endNode, toClear, tunnel)
    end

    -- No path found, return nil
    return nil
  end

end

--[[
Copyright (c) 2012-2013 Roland Yonaba

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
--]]
--# node
--- <strong>The <code>node</code> class</strong>.
-- The `node` class represents a cell on a collision map. Basically, for each single cell
-- in the collision map passed-in upon initialization, a `node` object would be generated
-- and then stored within the `grid` object.
--
-- In the following implementation, nodes can be compared using the `<` operator. The comparison is
-- made on the basis of their `f` cost. From a processed node, the `pathfinder` would expand the search 
-- to the next neighbouring node having the lowest `f` cost. This comparison is internally used within the
-- *open list* `heap` to quickly sort all nodes queued inside the heap.
-- 
-- @author Roland Yonaba
-- @copyright 2012-2013
-- @license <a href="http://www.opensource.org/licenses/mit-license.php">MIT</a>
-- @module jumper.core.node

if (...) then

    local assert = assert

  --- Internal `node` Class
  -- @class table
  -- @name node
  -- @field x the x-coordinate of the node on the collision map
  -- @field y the y-coordinate of the node on the collision map
  local Node = {}
  Node.__index = Node

  --- Inits a new `node` object
  -- @class function
  -- @name node:new
  -- @tparam int x the x-coordinate of the node on the collision map
  -- @tparam int y the y-coordinate of the node on the collision map
  -- @treturn node a new `node` object
  function Node:new(x,y)
    return setmetatable({x = x, y = y}, Node)
  end

  -- Enables the use of operator '<' to compare nodes.
  -- Will be used to sort a collection of nodes in a binary heap on the basis of their F-cost
  function Node.__lt(A,B) return (A.f < B.f) end

  return setmetatable(Node,
        {__call = function(self,...) 
            return Node:new(...) 
        end}
    )
end


--[[
Copyright (c) 2012-2013 Roland Yonaba

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
--]]
--# path
--- <strong>The <code>path</code> class</strong>.
-- The `path` class represents a path from a `start` location to a `goal`.
-- An instance from this class would be a result of a request addressed to `pathfinder:getPath`.
-- A `path` is basically a set of `nodes`, aligned in a specific order, defining a way to follow for moving agents.
--
-- @author Roland Yonaba
-- @copyright 2012-2013
-- @license <a href="http://www.opensource.org/licenses/mit-license.php">MIT</a>
-- @module jumper.core.path

if (...) then

  -- Internalization
  local abs, max = math.abs, math.max
    local t_insert, t_remove = table.insert, table.remove

  -- Depandancies
  local Heuristic = require ((...):gsub('%.path$','.heuristics'))

  --- The `path` class
  -- @class table
  -- @name path
  local Path = {}
  Path.__index = Path

  --- Inits a new `path` object.
  -- @class function
  -- @name path:new
  -- @treturn path a `path` object
  function Path:new()
    return setmetatable({}, Path)
  end

  --- Iterates on each single `node` along a `path`. At each step of iteration,
  -- returns a `node` and plus a count value. Aliased as @{path:nodes}
  -- @class function
  -- @name path:iter
  -- @treturn node a `node`
  -- @treturn int the count for the number of nodes
    -- @see path:nodes
  function Path:iter()
    local i,pathLen = 1,#self
    return function()
      if self[i] then
        i = i+1
        return self[i-1],i-1
      end
    end
  end
  
  --- Iterates on each single `node` along a `path`. At each step of iteration,
  -- returns a `node` and plus a count value. Aliased for @{path:iter}
  -- @class function
  -- @name path:nodes
  -- @treturn node a `node`
  -- @treturn int the count for the number of nodes
    -- @see path:iter    
    Path.nodes = Path.iter

  --- Evaluates the `path` length
  -- @class function
  -- @name path:getLength
  -- @treturn number the `path` length
  function Path:getLength()
    local len = 0
    for i = 2,#self do
      local dx = self[i].x - self[i-1].x
      local dy = self[i].y - self[i-1].y
      len = len + Heuristic.EUCLIDIAN(dx, dy)
    end
    return len
  end

  --- Path filling function. Interpolates between non contiguous locations along a `path`
  -- to build a fully continuous `path`. This maybe useful when using `Jump Point Search` finder.
  -- Does the opposite of @{path:filter}
  -- @class function
  -- @name path:fill
  -- @see path:filter
  function Path:fill()
    local i = 2
    local xi,yi,dx,dy
    local N = #self
    local incrX, incrY
    while true do
      xi,yi = self[i].x,self[i].y
      dx,dy = xi-self[i-1].x,yi-self[i-1].y
      if (abs(dx) > 1 or abs(dy) > 1) then
        incrX = dx/max(abs(dx),1)
        incrY = dy/max(abs(dy),1)
        t_insert(self, i, self.grid:getNodeAt(self[i-1].x + incrX, self[i-1].y +incrY))
        N = N+1
      else i=i+1
      end
      if i>N then break end
    end
  end

  --- Path compression. Given a `path`, eliminates useless nodes to return a lighter `path`. Does
  -- the opposite of @{path:fill}
  -- @class function
  -- @name path:filter
  -- @see path:fill
  function Path:filter()
    local i = 2
    local xi,yi,dx,dy, olddx, olddy
    xi,yi = self[i].x, self[i].y
    dx, dy = xi - self[i-1].x, yi-self[i-1].y
    while true do
      olddx, olddy = dx, dy
      if self[i+1] then
        i = i+1
        xi, yi = self[i].x, self[i].y
        dx, dy = xi - self[i-1].x, yi - self[i-1].y
        if olddx == dx and olddy == dy then
          t_remove(self, i-1)
          i = i - 1
        end
      else break end
    end
  end

  return setmetatable(Path,
    {__call = function(self,...)
      return Path:new(...)
    end
  })
end

--[[
Copyright (c) 2012-2013 Roland Yonaba

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
--]]
--# pathfinder
--- <strong>The <strong>pathfinder</strong> class API</strong>.
--
-- Implementation of the `pathfinder` class.
--
-- @author Roland Yonaba
-- @copyright 2012-2013
-- @license <a href="http://www.opensource.org/licenses/mit-license.php">MIT</a>
-- @module jumper.pathfinder

local _VERSION = "1.8.1"
local _RELEASEDATE = "03/01/2013"

--- @usage
local usage = [[
-- Usage Example
-- First, set a collision map
local map = {
    {0,1,0,1,0},
    {0,1,0,1,0},
    {0,1,1,1,0},
    {0,0,0,0,0},
}
-- Value for walkable tiles
local walkable = 0

-- Library setup
local Grid = require ("jumper.grid") -- The grid class
local Pathfinder = require ("jumper.pathfinder") -- The pathfinder lass

-- Creates a grid object
local grid = Grid(map)
-- Creates a pathfinder object using Jump Point Search
local myFinder = Pathfinder(grid, 'JPS', walkable)

-- Define start and goal locations coordinates
local startx, starty = 1,1
local endx, endy = 5,1

-- Calculates the path, and its length
local path, length = myFinder:getPath(startx, starty, endx, endy)
if path then
  print(('Path found! Length: %.2f'):format(length))
    for node, count in path:iter() do
      print(('Step: %d - x: %d - y: %d'):format(count, node.x, node.y))
    end
end

--> Output:
--> Path found! Length: 8.83
--> Step: 1 - x: 1 - y: 1
--> Step: 2 - x: 1 - y: 3
--> Step: 3 - x: 2 - y: 4
--> Step: 4 - x: 4 - y: 4
--> Step: 5 - x: 5 - y: 3
--> Step: 6 - x: 5 - y: 1
]]

if (...) then

  -- Internalization
  local t_insert, t_remove = table.insert, table.remove
    local floor = math.floor
  local pairs = pairs
  local assert = assert
  local setmetatable, getmetatable = setmetatable, getmetatable

    -- Type function ovverride, to support integers
    local otype = type
    local isInt = function(v) 
        return otype(v) == 'number' and floor(v) == v and 'int' or nil 
    end
    local type = function(v)
        return isInt(v) or otype(v)
    end

  -- Dependancies
  local _PATH = (...):gsub('%.pathfinder$','')
  local Heap      = require (_PATH .. '.core.bheap')
  local Heuristic = require (_PATH .. '.core.heuristics')
  local Grid      = require (_PATH .. '.grid')
  local Path      = require (_PATH .. '.core.path')

  -- Is arg a grid object
  local function isAGrid(grid)
    return getmetatable(grid) and getmetatable(getmetatable(grid)) == Grid
  end

  -- Available search algorithms
  local Finders = {
    ['ASTAR']     = require (_PATH .. '.search.astar'),    
    ['DIJKSTRA']  = require (_PATH .. '.search.dijkstra'),
    ['BFS']       = require (_PATH .. '.search.bfs'),
    ['DFS']       = require (_PATH .. '.search.dfs'),
    ['JPS']       = require (_PATH .. '.search.jps'),
  }

  -- Collect keys in an array
  local function collect_keys(t)
    local keys = {}
    for k,v in pairs(t) do keys[#keys+1] = k end
    return keys
  end

  -- Will keep track of all nodes expanded during the search
  -- to easily reset their properties for the next pathfinding call
  local toClear = {}

  -- Resets properties of nodes expanded during a search
  -- This is a lot faster than resetting all nodes
  -- between consecutive pathfinding requests
  local function reset()
    for node in pairs(toClear) do
      node.g, node.h, node.f = nil, nil, nil
      node.opened, node.closed, node.parent = nil, nil, nil
    end
    toClear = {}
  end

  -- Keeps track of the last computed path cost
  local lastPathCost = 0

  -- Availables search modes
  local searchModes = {['DIAGONAL'] = true, ['ORTHOGONAL'] = true}

  -- Performs a traceback from the goal node to the start node
  -- Only happens when the path was found
  local function traceBackPath(finder, node, startNode)
    local path = Path:new()
    path.grid = finder.grid
    lastPathCost = node.f or path:getLength()

    while true do
      if node.parent then
        t_insert(path,1,node)
        node = node.parent
      else
        t_insert(path,1,startNode)
        return path
      end
    end
  end

  --- The `pathfinder` class
  -- @class table
  -- @name pathfinder
  local Pathfinder = {}
  Pathfinder.__index = Pathfinder

  --- Inits a new `pathfinder` object
  -- @class function
  -- @name pathfinder:new
  -- @tparam grid grid a `grid` object
  -- @tparam[opt] string finderName the name of the `finder` (search algorithm) to be used for further searches.
    -- Defaults to `ASTAR` when not given. Use @{pathfinder:getFinders} to get the full list of available finders..
  -- @tparam[optchain] string|int|function walkable the value for walkable nodes on the passed-in map array.
  -- If this parameter is a function, it should be prototyped as `f(value)`, returning a boolean:
  -- `true` when value matches a *walkable* node, `false` otherwise.
  -- @treturn pathfinder a new `pathfinder` object
  function Pathfinder:new(grid, finderName, walkable)
    local newPathfinder = {}
    setmetatable(newPathfinder, Pathfinder)
      newPathfinder:setGrid(grid)
    newPathfinder:setFinder(finderName)
    newPathfinder:setWalkable(walkable)
    newPathfinder:setMode('DIAGONAL')
    newPathfinder:setHeuristic('MANHATTAN')
    newPathfinder.openList = Heap()
    return newPathfinder
  end

  --- Sets a `grid` object. Defines the `grid` on which the `pathfinder` will make path searches.
  -- @class function
  -- @name pathfinder:setGrid
  -- @tparam grid grid a `grid` object
  function Pathfinder:setGrid(grid)
    assert(isAGrid(grid), 'Bad argument #1. Expected a \'grid\' object')
    self.grid = grid
    self.grid.__eval = self.walkable and type(self.walkable) == 'function'
    return self
  end

  --- Returns the `grid` object. Returns a reference to the internal `grid` object used by the `pathfinder` object.
  -- @class function
  -- @name pathfinder:getGrid
  -- @treturn grid the `grid` object
  function Pathfinder:getGrid()
    return self.grid
  end

  --- Sets the `walkable` value or function.
  -- @class function
  -- @name pathfinder:setWalkable
  -- @tparam string|int|function walkable the value for walkable nodes on the passed-in map array.
  -- If this parameter is a function, it should be prototyped as `f(value)`, returning a boolean:
  -- `true` when value matches a *walkable* node, `false` otherwise.
  function Pathfinder:setWalkable(walkable)
    assert(('stringintfunctionnil'):match(type(walkable)),
      ('Bad argument #2. Expected \'string\', \'number\' or \'function\', got %s.'):format(type(walkable)))
    self.walkable = walkable
    self.grid.__eval = type(self.walkable) == 'function'
    return self
  end

  --- Gets the `walkable` value or function.
  -- @class function
  -- @name pathfinder:getWalkable
  -- @treturn string|int|function the `walkable` previously set
  function Pathfinder:getWalkable()
    return self.walkable
  end

  --- Sets a finder. The finder refers to the search algorithm used by the `pathfinder` object.
  -- The default finder is `ASTAR`. Use @{pathfinder:getFinders} to get the list of available finders.
  -- @class function
  -- @name pathfinder:setFinder
  -- @tparam string finderName the name of the finder to be used for further searches.
  -- @see pathfinder:getFinders
  function Pathfinder:setFinder(finderName)
        local finderName = finderName
        if not finderName then
            if not self.finder then 
                finderName = 'ASTAR' 
            else return 
            end
        end
    assert(Finders[finderName],'Not a valid finder name!')
    self.finder = finderName
    return self
  end

  --- Gets the name of the finder being used. The finder refers to the search algorithm used by the `pathfinder` object.
  -- @class function
  -- @name pathfinder:getFinder
  -- @treturn string the name of the finder to be used for further searches.
  function Pathfinder:getFinder()
    return self.finder
  end

  --- Gets the list of all available finders names.
  -- @class function
  -- @name pathfinder:getFinders
  -- @treturn {string,...} array of finders names.
  function Pathfinder:getFinders()
    return collect_keys(Finders)
  end

  --- Set a heuristic. This is a function internally used by the `pathfinder` to get the optimal path during a search.
  -- Use @{pathfinder:getHeuristics} to get the list of all available heuristics. One can also defined
  -- his own heuristic function.
  -- @class function
  -- @name pathfinder:setHeuristic
  -- @tparam function|string heuristic a heuristic function, prototyped as `f(dx,dy)` or a string.
  -- @see pathfinder:getHeuristics
  function Pathfinder:setHeuristic(heuristic)
    assert(Heuristic[heuristic] or (type(heuristic) == 'function'),'Not a valid heuristic!')
    self.heuristic = Heuristic[heuristic] or heuristic
    return self
  end

  --- Gets the heuristic used. Returns the function itself.
  -- @class function
  -- @name pathfinder:getHeuristic
  -- @treturn function the heuristic function being used by the `pathfinder` object
  function Pathfinder:getHeuristic()
    return self.heuristic
  end

  --- Gets the list of all available heuristics.
  -- @class function
  -- @name pathfinder:getHeuristics
  -- @treturn {string,...} array of heuristic names.
  function Pathfinder:getHeuristics()
    return collect_keys(Heuristic)
  end

  --- Changes the search mode. Defines a new search mode for the `pathfinder` object.
  -- The default search mode is `DIAGONAL`, which implies 8-possible directions when moving (north, south, east, west and diagonals).
  -- In `ORTHOGONAL` mode, only 4-directions are allowed (north, south, east and west).
  -- Use @{pathfinder:getModes} to get the list of all available search modes.
  -- @class function
  -- @name pathfinder:setMode
  -- @tparam string mode the new search mode.
  -- @see pathfinder:getModes
  function Pathfinder:setMode(mode)
    assert(searchModes[mode],'Invalid mode')
    self.allowDiagonal = (mode == 'DIAGONAL')
    return self
  end

  --- Gets the search mode.
  -- @class function
  -- @name pathfinder:getMode
  -- @treturn string the current search mode
  function Pathfinder:getMode()
    return (self.allowDiagonal and 'DIAGONAL' or 'ORTHOGONAL')
  end

  --- Gets the list of all available search modes.
  -- @class function
  -- @name pathfinder:getModes
  -- @treturn {string,...} array of search modes.
  function Pathfinder:getModes()
    return collect_keys(searchModes)
  end

  --- Returns version and release date.
  -- @class function
  -- @name pathfinder:version
  -- @treturn string the version of the current implementation
  -- @treturn string the release of the current implementation
  function Pathfinder:version()
    return _VERSION, _RELEASEDATE
  end

  --- Calculates a path. Returns the path from location `<startX, startY>` to location `<endX, endY>`.
  -- Both locations must exist on the collision map.
  -- @class function
  -- @name pathfinder:getPath
  -- @tparam number startX the x-coordinate for the starting location
  -- @tparam number startY the y-coordinate for the starting location
  -- @tparam number endX the x-coordinate for the goal location
  -- @tparam number endY the y-coordinate for the goal location
  -- @tparam[opt] bool tunnel Whether or not the pathfinder can tunnel though walls diagonally (not compatible with `Jump Point Search`)
  -- @treturn {node,...} a path (array of `nodes`) when found, otherwise `nil`
  -- @treturn number the path length when found, `0` otherwise
  function Pathfinder:getPath(startX, startY, endX, endY, tunnel)
        reset()
    local startNode = self.grid:getNodeAt(startX, startY)
    local endNode = self.grid:getNodeAt(endX, endY)
    assert(startNode, ('Invalid location [%d, %d]'):format(startX, startY))
    assert(endNode and self.grid:isWalkableAt(endX, endY),
      ('Invalid or unreachable location [%d, %d]'):format(endX, endY))
    local _endNode = Finders[self.finder](self, startNode, endNode, toClear, tunnel)
    if _endNode then 
            return traceBackPath(self, _endNode, startNode), lastPathCost
    end
    lastPathCost = 0
    return nil, lastPathCost
  end

  -- Returns Pathfinder class
  return setmetatable(Pathfinder,{
    __call = function(self,...)
      return self:new(...)
    end
  })

end

--[[
Copyright (c) 2012-2013 Roland Yonaba

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
--]]