taxiDriverAI

taxiDriver-AI by maxxst / FU-Berlin

-- taxiDriver1.lua

--require '_utilities/utilities.lua'	-- moved to end of file
--require '_jumper/jumper.lua'

AI ="taxiDriver by maxxst"  -- FU-Berlin
-- Example-AI from https://github.com/maxxst/trAInsported-starterkit / 2013-07
-- All-in-1-file, translation, added comments, TODOs & debug:  hajo4  2014-02-26

local dbg=0

--
-- Without a passenger, the TaxiDriver-Bot drives randomly around the map.
-- When encountering passengers, he picks up the first, then searches 
-- the shortest path to its destination.
--

-- TODO: ai.passengerBoarded(), ai.enoughMoney(), ai.blocked()
-- TODO: use getNumberOfLines() to check cpu-quota on bigger maps
--  Note: on "Compete"-maps as small as 12x10, we get errors "Taking too long"
-- TODO: Do some of the obvious improvements :-)

-- #### #### ####

railMap = {}

-- Gets called at the start of the game.  Buy a train here!
function ai.init(map, money, maximumTrains)
	print('AI:', AI)
	railMap = map2railMap(map)

	if dbg >= 5 then  
		print('railMap:')
		printTable(railMap,2)  
		print("used codelines A:", getNumberOfLines() )  -- check cpu-quota
	end

    -- init. pathfinding-library:
    jumperMap = mapToJumperMap(map)
    local walkable = 1
    local Grid = Jumper.Grid  
    local Pathfinder = Jumper.Pathfinder 
    local grid = Grid(jumperMap) 
    myFinder = Pathfinder(grid, 'BFS', walkable)

    if dbg >= 5 then  print("used codelines B:", getNumberOfLines() )  end

    --TODO: buy train near passenger
    buyTrain(random(map.width), random(map.height))
end

-- Gets called when the train reaches a tile with passengers:
function ai.foundPassengers( train, passengers )
    local p = nil 
    if train.passenger then
        -- if the train is full, dont stop.
        -- TODO: look for VIPs
	-- TODO: remember passengers
        myPrint(5,'Train is full !')
    else
        p = passengers[1]			--take first passenger from list
        myPrint(3,"pickup:", p.name)
	-- TODO: choose the "best" passenger
    end  
    return p
end

-- Gets called when the train reaches the tile in front of a junction.
-- Should return one of the possible directions ("N", "S", "W", "E").
function ai.chooseDirection(train, possibleDirections)

    local dir = chooseRandomDir(possibleDirections) 	-- without passenger: random move
    if train.passenger then				-- with passenger: take shortest path to dest.
        -- calculate best direction
        local startx, starty = train.x ,train.y
        local endx, endy = train.passenger.destX, train.passenger.destY
        local path = myFinder:getPath(startx, starty, endx, endy) 
        if not (endx == path[2].x and endy == path[2].y) then -- avoid error
          kreuzung = makeLoc( path[2].x, path[2].y, train.dir)
          nachKreuzung = makeLoc( path[3].x, path[3].y, train.dir )
          for d, bool in pairs(possibleDirections) do
            local test_loc = goDir( railMap, kreuzung, d )
            if test_loc.x == nachKreuzung.x and test_loc.y == nachKreuzung.y then
              dir = d 
              break 
            end
          end
        end
    end

    if dbg >= 5 then  print("used codelines C:", getNumberOfLines() )  end

    return dir
end

-- Gets called  when a new passenger gets placed on the map:
function ai.newPassenger(name, x, y, destX, destY, vipTime)
    myPrint(1,"new passenger at ("..x..", "..y..")")
    --TODO: remember passengers
end

-- Gets called when the train arrives at the destination:
function ai.foundDestination( train )
	myPrint(3,"drop")
	dropPassenger(train)
	print("Money: " .. getMoney())
end

function chooseRandom(train, possibleDirections)
  tbl = {}
  for dir,bool in pairs(possibleDirections) do
    tbl[#tbl+1] = dir
  end
  return tbl[random(#tbl)]
end 

function mapToJumperMap(map)
  local jumperMap = {}
  for i=1, map.width do
      for j=1, map.height do
          if not jumperMap[j] then
           jumperMap[j] = {}
          end
          if map[i][j] == 'C' then
              jumperMap[j][i] = 1
          else
              jumperMap[j][i] = 0
          end
      end
  end
  myPrint(5,'jumperMap:')
  if dbg>=5 then  printTable(jumperMap,2)  end
  return jumperMap
end

--Debug-print:
function myPrint(dbgLevel, ...)
	if dbg >= dbgLevel then  print(...)  end
end

-- #### #### #### ####

--[[
For running the AI in matches on the online server,
the include-files need to be appended directly:

--require '_utilities/utilities.lua'
--require '_jumper/jumper.lua'
]]--

-- utilities.lua
function map2railMap(map)
    local railMap = {}
    for i=1, map.width do
        railMap[i] = {}
        for j=1, map.height do
            if map[i][j] == "C" then
                railMap[i][j] = true
            else
                railMap[i][j] = false
            end
        end
    end
    railMap.width  = map.width
    railMap.height = map.height
    return railMap
end

function getDirections( railMap, loc)
    x = loc.x
    y = loc.y
    dir = loc.dir
    local directions = {}
    -- only check if x y is actually a rail
    if railMap[x][y] then
        -- lookup: possible directions
        if y > 1 and railMap[x][y-1] and dir ~= 'S'  then 
            table.insert(directions, "N")
        end
        if y < railMap.height and railMap[x][y+1] and dir ~= 'N' then
            table.insert(directions, "S")
        end
        if x > 1 and railMap[x-1][y] and dir ~= 'E' then 
            table.insert(directions, "W")
        end
        if x < railMap.width and railMap[x+1][y] and dir ~= 'W' then 
            table.insert(directions, "E")
        end
    end
    return directions
end

function chooseRandomDir( directions )
    local tbl = {}
    for dir,bool in pairs(directions) do
        tbl[#tbl+1] = dir
    end
    return tbl[random(#tbl)]
end

function depthFirstSearch( level, railMap, location, target  )
    max_level = 30 -- tinker with this, maybe you can dig deeper! ;)
    if max_level == level then
        return "TOOLONG"
    else
        if location.x == target.x and location.y == target.y then
            return {}
        else
            local path = {}
            local min = max_level+100
            local dirs = getDirections( railMap, location )
            for index, dir in pairs(dirs) do 
                local new_loc = goDir( railMap, location, dir )
                local res = depthFirstSearch( level+1, railMap, new_loc, target )
                if res ~= "TOOLONG" then
                    table.insert(res, {["x"]=location.x, ["y"]=location.y, ["dir"]=dir})
                    if #res < min then
                        path = res
                        min = #path
                    end
                end
            end
            return path
        end
    end
end

function goDir( railMap, loc, dir )
    h = railMap.height
    w = railMap.width
    x = loc.x
    y = loc.y
    if dir == "S" then y = y+1 end
    if dir == "N" then y = y-1 end
    if dir == "W" then x = x-1 end
    if dir == "E" then x = x+1 end
    if x > w or y > h or x < 1 or y < 1 then
        print("goDir: out of range "..x.." "..y)
    else
        return {["x"]=x, ["y"]=y, ["dir"]=dir}
    end
end 

function loc2String( loc )
    return loc.x.." "..loc.y.." "..loc.dir
end

function makeLoc( x, y, dir)
    return { ["x"]=x, ["y"]=y, ["dir"]=dir }
end

function dir2String( map, loc )
    x = loc.x
    y = loc.y
    dir = loc.dir
    dirs = getDirections( map, loc )
    str = "loc("..x.." "..y.." "..dir..") -> "
    if dirs[1] then
        str = str..dirs[1].." "
    end
    if dirs[2] then
        str = str..dirs[2].." "
    end
    if dirs[3] then
        str = str..dirs[2].." "
    end
    if dirs[4] then
        str = str..dirs[2].." "
    end
    return str
end

function manhattanDist(x1, y1, x2, y2)
    return math.abs(x1-x2) + math.abs(y1-y2)
end

-- Ausgabehelfer
-- Function to print a Table
function printTable(table, lvl)
  if type(table) == "table" then
    lvl = lvl or 0
    for k, v in pairs(table) do
      if type(v) == "table" then
        printTable(v, lvl + 1)
      else
        str = ""
        for i = 1,lvl do
          str = str .. "\t"
        end
        print(str, k, v)
      end
    end
  else
    print('Not a table')
  end
end

-- #### #### ####


-- jumper.lua
-- Raw source, to be prettified later

-- Defining core modules
------------------------------  Binary Heaps (local) ------------------------------
-- See: 
-- * http://en.wikipedia.org/wiki/Binary_heap
-- * http://www.policyalmanac.org/games/binaryHeaps.htm

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.f < b.f
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

local Heap = function()

	local newHeap = {
		__heap = {},
		size = 0,
		sort = comp or f_min,
	}

	function newHeap:empty()
		return (self.size==0)
	end
	
	function newHeap:clear()
		self.__heap = {}
		self.size = 0
		self.sort = self.sort or f_min
		return self
	end

	function newHeap:push(item)
		if item then
			self.size = self.size + 1
			self.__heap[self.size] = item
			percolate_up(self, self.size)
		end
		return self
	end

	function newHeap: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

	function newHeap: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 newHeap
	
end

------------------------------  Heuristics (global) ------------------------------

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

local Heuristics = {}

function Heuristics.MANHATTAN(dx,dy) return abs(dx)+abs(dy) end
function Heuristics.EUCLIDIAN(dx,dy) return sqrt(dx*dx+dy*dy) end
function Heuristics.DIAGONAL(dx,dy)  return max(abs(dx),abs(dy)) end
function Heuristics.CARDINTCARD(dx,dy) 
	dx, dy = abs(dx), abs(dy)
	return min(dx,dy) * sqrt2 + max(dx,dy) - min(dx,dy)
end

------------------------------  Node (global) ------------------------------

local Node = function(x,y)
	local newNode = {x = x, y = y}
	return newNode
end

------------------------------  Path (global) ------------------------------

local t_insert, t_remove = table.insert, table.remove

local Path = function()
	local newPath = {}

	function newPath:iter()
		local i,pathLen = 1,#self
		return function()
			if self[i] then
				i = i+1
				return self[i-1],i-1
			end
		end
	end	
	
	newPath.nodes = newPath.iter
	
	function newPath: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 + Heuristics.EUCLIDIAN(dx, dy)
		end
		return len
	end

	function newPath: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

	function newPath: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 newPath
end

-- Search algorithms:

------------------------------  ASTAR ------------------------------
-- See: http://en.wikipedia.org/wiki/A_star

local ipairs = ipairs
local huge = math.huge

-- 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>`.
local function ASTARSEARCH(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

------------------------------  BFS ------------------------------
-- See: http://en.wikipedia.org/wiki/Breadth-first_search
local t_remove = table.remove

-- BFS logic
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>`.
local function BFSEARCH(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

------------------------------  DFS ------------------------------
-- See: http://en.wikipedia.org/wiki/Depth-first_search

-- DFS logic
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>`.
local function DFSEARCH(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

------------------------------  DIJKSTRA ------------------------------
-- See: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

local dijkstraHeuristic = function(...) return 0 end

-- Calculates a path.
-- Returns the path from location `<startX, startY>` to location `<endX, endY>`.
local function DIJKSTRASEARCH(finder, startNode, endNode, toClear, tunnel)
	return ASTARSEARCH(finder, startNode, endNode, toClear, tunnel, dijkstraHeuristic)
end
	
------------------------------  JPS ------------------------------
-- See:  http://harablog.wordpress.com/2011/09/07/jump-point-search/

local step_first = false

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

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

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

		-- 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

local function JUMPPOINTSEARCH(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

------------------------------  Grid Module (global) ------------------------------
-- See: ...

local pairs = pairs
local next  = next
local otype = type
local _grids = {}
	
-- Local helpers

-- 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
			if not (#line == w) then 
				error('Error parsing map, rows must have the same size!') 
			end
			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(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]]
}

-- Specialized grids
-- Inits a preprocessed grid
local function PreProcessGrid(newGrid, map)
	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

	function newGrid:getNodeAt(x,y)
		return self.nodes[y] and self.nodes[y][x] or nil
	end
	
	return newGrid
	
end

-- Inits a postprocessed grid
local function PostProcessGrid(newGrid, map)
	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

	function newGrid: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(x,y) end
		return self.nodes[y][x]
	end
	
	return newGrid
	
end

local Grid = function(map, processOnDemand)

	map = type(map)=='string' and parseStringMap(map) or map
	if not (isMap(map) or isStringMap(map)) then
		error('Bad argument #1. Not a valid map')
	end
	if not (type(processOnDemand) == 'boolean' or not processOnDemand) then
		error(('Bad argument #2. Expected \'boolean\', got %s.'):format(type(processOnDemand)))
	end
	
	local newGrid = {}
	
	function newGrid: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
	
	function newGrid:getWidth() return self.width end

	function newGrid:getHeight() return self.height end

	function newGrid:getMap() return self.map end

	function newGrid:getNodes() return self.nodes end
	
	function newGrid: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

	function newGrid: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

	function newGrid:each(f,...)
		for node in self:iter() do f(node,...) end
	end

	function newGrid:eachRange(lx,ly,ex,ey,f,...)
		for node in self:iter(lx,ly,ex,ey) do f(node,...) end
	end

	function newGrid:imap(f,...)
		for node in self:iter() do
			node = f(node,...)
		end
	end

	function newGrid:imapRange(lx,ly,ex,ey,f,...)
		for node in self:iter(lx,ly,ex,ey) do
			node = f(node,...)
		end
	end
	
	_grids[newGrid] = true
	
	if processOnDemand then
		return PostProcessGrid(newGrid,map)
	end
	
	return PreProcessGrid(newGrid,map)
	
end

	
------------------------------  Pathfinder Module (global) ------------------------------	
-- See: http://en.wikipedia.org/wiki/Pathfinding

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

local function isAGrid(grid)
	return _grids[grid] or false
end
	
local Finders = {
	['ASTAR']     = ASTARSEARCH,	
	['DIJKSTRA']  = DIJKSTRASEARCH,
	['BFS']       = BFSEARCH,
	['DFS']       = DFSEARCH,
	['JPS']       = JUMPPOINTSEARCH,
}	

-- 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

local toClear = {}

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}

local function traceBackPath(finder, node, startNode)
	local path = Path()
	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

local Pathfinder = function(grid, finderName, walkable)
	local newPathfinder = {}

	function newPathfinder:setGrid(grid)
		if not (isAGrid(grid)) then
			error('Bad argument #1. Expected a \'grid\' object')
		end
		self.grid = grid
		self.grid.__eval = self.walkable and type(self.walkable) == 'function'
		return self
	end	
	
	function newPathfinder:getGrid()
		return self.grid
	end

	function newPathfinder:setWalkable(walkable)
		if not (('stringintfunctionnil'):match(type(walkable))) then
			error(('Bad argument #2. Expected \'string\', \'number\' or \'function\', got %s.'):format(type(walkable)))
		end
		self.walkable = walkable
		self.grid.__eval = type(self.walkable) == 'function'
		return self
	end

	function newPathfinder:getWalkable()
		return self.walkable
	end

	function newPathfinder:setFinder(finderName)
		local finderName = finderName
		if not finderName then
			if not self.finder then 
				finderName = 'ASTAR' 
			else return 
			end
		end
		if not (Finders[finderName]) then 
			error('Not a valid finder name!')
		end
		self.finder = finderName
		return self
	end

	function newPathfinder:getFinder()
		return self.finder
	end

	function newPathfinder:getFinders()
		return collect_keys(Finders)
	end

	function newPathfinder:setHeuristic(heuristic)
		if not (Heuristics[heuristic] or (type(heuristic) == 'function')) then
			error('Not a valid heuristic!')
		end
		self.heuristic = Heuristics[heuristic] or heuristic
		return self
	end

	function newPathfinder:getHeuristic()
		return self.heuristic
	end

	function newPathfinder:getHeuristics()
		return collect_keys(Heuristics)
	end

	function newPathfinder:setMode(mode)
		if not (searchModes[mode]) then
			error('Invalid mode')
		end
		self.allowDiagonal = (mode == 'DIAGONAL')
		return self
	end

	function newPathfinder:getMode()
		return (self.allowDiagonal and 'DIAGONAL' or 'ORTHOGONAL')
	end

	function newPathfinder:getModes()
		return collect_keys(searchModes)
	end

	function newPathfinder:version()
		return _VERSION, _RELEASEDATE
	end

	function newPathfinder:getPath(startX, startY, endX, endY, tunnel)
		reset()
		local startNode = self.grid:getNodeAt(startX, startY)
		local endNode = self.grid:getNodeAt(endX, endY)
		if not (startNode) then 
			error(('Invalid location [%d, %d]'):format(startX, startY))
		end
		if not (endNode and self.grid:isWalkableAt(endX, endY)) then
			error(('Invalid or unreachable location [%d, %d]'):format(endX, endY))
		end
		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
	
	newPathfinder:setGrid(grid)
	newPathfinder:setFinder(finderName)
	newPathfinder:setWalkable(walkable)
	newPathfinder:setMode('ORTHOGONAL')
	newPathfinder:setHeuristic('MANHATTAN')
	newPathfinder.openList = Heap()
	
	return newPathfinder
	
end

------------------------------  Spawns module into the global env ------------------------------
Jumper = {
	Heuristics = Heuristics,
	Node = Node,
	Path = Path,
	Grid = Grid,
	Pathfinder = Pathfinder
}

-- #### #### ####