A* Pathfinder in lua

--[[ Created by TehPers' Automatic Installer Maker ]]--
local root = {
["pathfinder"] = { ["deepcopy"] = [===[
--[[ deepcopy.lua

    Deep-copy function for Lua - v0.2
    ==============================
      - Does not overflow the stack.
      - Maintains cyclic-references
      - Copies metatables
      - Maintains common upvalues between copied functions (for Lua 5.2 only)

    TODO
    ----
      - Document usage (properly) and provide examples
      - Implement handling of LuaJIT FFI ctypes
      - Provide option to only set metatables, not copy (as if they were
        immutable)
      - Find a way to replicate `debug.upvalueid` and `debug.upvaluejoin` in
        Lua 5.1
      - Copy function environments in Lua 5.1 and LuaJIT
        (Lua 5.2's _ENV is actually a good idea!)
      - Handle C functions

    Usage
    -----
        copy = table.deecopy(orig)
        copy = table.deecopy(orig, params, customcopyfunc_list)

    `params` is a table of parameters to inform the copy functions how to
    copy the data. The default ones available are:
      - `value_ignore` (`table`/`nil`): any keys in this table will not be
        copied (value should be `true`). (default: `nil`)
      - `value_translate` (`table`/`nil`): any keys in this table will result
        in the associated value, rather than a copy. (default: `nil`)
        (Note: this can be useful for global tables: {[math] = math, ..})
      - `metatable_immutable` (`boolean`): assume metatables are immutable and
        do not copy them (only set). (default: `false`)
      - `function_immutable` (`boolean`): do not copy function values; instead
        use the original value. (default: `false`)
      - `function_env` (`table`/`nil`): Set the enviroment of functions to
        this value (via fourth arg of `loadstring`). (default: `nil`)
        this value. (default: `nil`)
      - `function_upvalue_isolate` (`boolean`): do not join common upvalues of
        copied functions (only applicable for Lua 5.2 and LuaJIT). (default:
        `false`)
      - `function_upvalue_dontcopy` (`boolean`): do not copy upvalue values
        (does not stop joining). (default: `false`)

    `customcopyfunc_list` is a table of typenames to copy functions.
    For example, a simple solution for userdata:
    { ["userdata"] = function(stack, orig, copy, state, arg1, arg2)
        if state == nil then
            copy = orig
            local orig_uservalue = debug.getuservalue(orig)
            if orig_uservalue ~= nil then
                stack:recurse(orig_uservalue)
                return copy, 'uservalue'
            end
            return copy, true
        elseif state == 'uservalue' then
            local copy_uservalue = arg2
            if copy_uservalue ~= nil then
                debug.setuservalue(copy, copy_uservalue)
            end
            return copy, true
        end
    end }
    Any parameters passed to the `params` are available in `stack`.
    You can use custom paramter names, but keep in mind that numeric keys and
    string keys prefixed with a single underscore are reserved.

    License
    -------
    Copyright (C) 2012 Declan White

    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.
]]
do
    local type = rawtype or type
    local rawget = rawget
    local rawset = rawset
    local next = rawnext or next
    local getmetatable = debug and debug.getmetatable or getmetatable
    local setmetatable = debug and debug.setmetatable or setmetatable
    local debug_getupvalue = debug and debug.getupvalue or nil
    local debug_setupvalue = debug and debug.setupvalue or nil
    local debug_upvalueid = debug and debug.upvalueid or nil
    local debug_upvaluejoin = debug and debug.upvaluejoin or nil
    local unpack = unpack
    local table = table
    table.deepcopy_copyfunc_list = {
      --["type"] = function(stack, orig, copy, state, temp1, temp2, temp..., tempN)
      --
      --    -- When complete:
      --    state = true
      --
      --    -- Store temporary variables between iterations using these:
      --    -- (Note: you MUST NOT call these AFTER recurse)
      --    stack:_push(tempN+1, tempN+2, tempN+..., tempN+M)
      --    stack:_pop(K)
      --    -- K is the number to pop.
      --    -- If you wanted to pop two from the last state and push four new ones:
      --    stack:_pop(2)
      --    stack:_push('t', 'e', 's', 't')
      --
      --    -- To copy a child value:
      --    -- (Note: any calls to push or pop MUST be BEFORE a call to this)
      --    state:recurse(childvalue_orig)
      --    -- This will leave two temp variables on the stack for the next iteration
      --    -- .., childvalue_orig, childvalue_copy
      --    -- which are available via the varargs (temp...)
      --    -- (Note: the copy may be nil if it was not copied (because caller
      --    -- specified it not to be)).
      --    -- You can only call this once per iteration.
      --
      --    -- Return like this:
      --    -- (Temp variables are not part of the return list due to optimisation.)
      --    return copy, state
      --
      --end,
        _plainolddata = function(stack, orig, copy, state)
            return orig, true
        end,
        ["table"] = function(stack, orig, copy, state, arg1, arg2, arg3, arg4)
            local orig_prevkey, grabkey = nil, false
            if state == nil then -- 'init'
                -- Initial state, check for metatable, or get first key
                -- orig, copy:nil, state
                copy = stack[orig]
                if copy ~= nil then -- Check if already copied
                    return copy, true
                else
                    copy = {} -- Would be nice if you could preallocate sizes!
                    stack[orig] = copy
                    local orig_meta = getmetatable(orig)
                    if orig_meta ~= nil then -- This table has a metatable, copy it
                        if not stack.metatable_immutable then
                            stack:_recurse(orig_meta)
                            return copy, 'metatable'
                        else
                            setmetatable(copy, orig_meta)
                        end
                    end
                end
                -- No metatable, go straight to copying key-value pairs
                orig_prevkey = nil -- grab first key
                grabkey = true --goto grabkey
            elseif state == 'metatable' then
                -- Metatable has been copied, set it and get first key
                -- orig, copy:{}, state, metaorig, metacopy
                local copy_meta = arg2--select(2, ...)
                stack:_pop(2)

                if copy_meta ~= nil then
                    setmetatable(copy, copy_meta)
                end

                -- Now start copying key-value pairs
                orig_prevkey = nil -- grab first key
                grabkey = true --goto grabkey
            elseif state == 'key' then
                -- Key has been copied, now copy value
                -- orig, copy:{}, state, keyorig, keycopy
                local orig_key = arg1--select(1, ...)
                local copy_key = arg2--select(2, ...)

                if copy_key ~= nil then
                    -- leave keyorig and keycopy on the stack
                    local orig_value = rawget(orig, orig_key)
                    stack:_recurse(orig_value)
                    return copy, 'value'
                else -- key not copied? move onto next
                    stack:_pop(2) -- pop keyorig, keycopy
                    orig_prevkey = orig_key
                    grabkey = true--goto grabkey
                end
            elseif state == 'value' then
                -- Value has been copied, set it and get next key
                -- orig, copy:{}, state, keyorig, keycopy, valueorig, valuecopy
                local orig_key   = arg1--select(1, ...)
                local copy_key   = arg2--select(2, ...)
              --local orig_value = arg3--select(3, ...)
                local copy_value = arg4--select(4, ...)
                stack:_pop(4)

                if copy_value ~= nil then
                    rawset(copy, copy_key, copy_value)
                end

                -- Grab next key to copy
                orig_prevkey = orig_key
                grabkey = true --goto grabkey
            end
            --return
            --::grabkey::
            if grabkey then
                local orig_key, orig_value = next(orig, orig_prevkey)
                if orig_key ~= nil then
                    stack:_recurse(orig_key) -- Copy key
                    return copy, 'key'
                else
                    return copy, true -- Key is nil, copying of table is complete
                end
            end
            return
        end,
        ["function"] = function(stack, orig, copy, state, arg1, arg2, arg3)
            local grabupvalue, grabupvalue_idx = false, nil
            if state == nil then
                -- .., orig, copy, state
                copy = stack[orig]
                if copy ~= nil then
                    return copy, true
                elseif stack.function_immutable then
                    copy = orig
                    return copy, true
                else
                    copy = loadstring(string.dump(orig), nil, nil, stack.function_env)
                    stack[orig] = copy

                    if debug_getupvalue ~= nil and debug_setupvalue ~= nil then
                        grabupvalue = true
                        grabupvalue_idx = 1
                    else
                        -- No way to get/set upvalues!
                        return copy, true
                    end
                end
            elseif this_state == 'upvalue' then
                -- .., orig, copy, state, uvidx, uvvalueorig, uvvaluecopy
                local orig_upvalue_idx   = arg1
              --local orig_upvalue_value = arg2
                local copy_upvalue_value = arg3
                stack:_pop(3)

                debug_setupvalue(copy, orig_upvalue_idx, copy_upvalue_value)

                grabupvalue_idx = orig_upvalue_idx+1
                stack:_push(grabupvalue_idx)
                grabupvalue = true
            end
            if grabupvalue then
                -- .., orig, copy, retto, state, uvidx
                local upvalue_idx_curr = grabupvalue_idx
                for upvalue_idx = upvalue_idx_curr, math.huge do
                    local upvalue_name, upvalue_value_orig = debug_getupvalue(orig, upvalue_idx)
                    if upvalue_name ~= nil then
                        local upvalue_handled = false
                        if not stack.function_upvalue_isolate and debug_upvalueid ~= nil and debug_upvaluejoin ~= nil then
                            local upvalue_uid = debug.upvalueid(orig, upvalue_idx)
                            -- Attempting to store an upvalueid of a function as a child of root is UB!
                            local other_orig = stack[upvalue_uid]
                            if other_orig ~= nil then
                                for other_upvalue_idx = 1, math.huge do
                                    if upvalue_uid == debug_upvalueid(other_orig, other_upvalue_idx) then
                                        local other_copy = stack[other_orig]
                                        debug_upvaluejoin(
                                            copy, upvalue_idx,
                                            other_copy, other_upvalue_idx
                                        )
                                        break
                                    end
                                end
                                upvalue_handled = true
                            else
                                stack[upvalue_uid] = orig
                            end
                        end
                        if not stack.function_upvalue_dontcopy and not upvalue_handled and upvalue_value_orig ~= nil then
                            stack:_recurse(upvalue_value_orig)
                            return copy, 'upvalue'
                        end
                    else
                        stack:_pop(1) -- pop uvidx
                        return copy, true
                    end
                end
            end
        end,
        ["userdata"] = nil,
        ["lightuserdata"] = nil,
        ["thread"] = nil,
    }
    table.deepcopy_copyfunc_list["number" ] = table.deepcopy_copyfunc_list._plainolddata
    table.deepcopy_copyfunc_list["string" ] = table.deepcopy_copyfunc_list._plainolddata
    table.deepcopy_copyfunc_list["boolean"] = table.deepcopy_copyfunc_list._plainolddata
    -- `nil` should never be encounted... but just in case:
    table.deepcopy_copyfunc_list["nil"    ] = table.deepcopy_copyfunc_list._plainolddata

    do
        local ORIG, COPY, RETTO, STATE, SIZE = 0, 1, 2, 3, 4
        function table.deepcopy_push(...)
            local arg_list_len = select('#', ...)
            local stack_offset = stack._top+1
            for arg_i = 1, arg_list_len do
                stack[stack_offset+arg_i] = select(arg_i, ...)
            end
            stack._top = stack_top+arg_list_len
        end
        function table.deepcopy_pop(stack, count)
            stack._top = stack._top-count
        end
        function table.deepcopy_recurse(stack, orig)
            local retto = stack._ptr
            local stack_top = stack._top
            local stack_ptr = stack_top+1
            stack._top = stack_top+SIZE
            stack._ptr = stack_ptr
            stack[stack_ptr+ORIG ] = orig
            stack[stack_ptr+COPY ] = nil
            stack[stack_ptr+RETTO] = retto
            stack[stack_ptr+STATE] = nil
        end
        function table.deepcopy(root, params, customcopyfunc_list)
            local stack = params or {}
            --orig,copy,retto,state,[temp...,] partorig,partcopy,partretoo,partstate
            stack[1+ORIG ] = root stack[1+COPY ] = nil
            stack[1+RETTO] = nil  stack[1+STATE] = nil
            stack._ptr = 1 stack._top = 4
            stack._push = table.deepcopy_push stack._pop = table.deepcopy_pop
            stack._recurse = table.deepcopy_recurse
            --[[local stack_dbg do -- debug
                stack_dbg = stack
                stack = setmetatable({}, {
                    __index = stack_dbg,
                    __newindex = function(t, k, v)
                        stack_dbg[k] = v
                        if tonumber(k) then
                            local stack = stack_dbg
                            local line_stack, line_label, line_stptr = "", "", ""
                            for stack_i = 1, math.max(stack._top, stack._ptr) do
                                local s_stack = (
                                        (type(stack[stack_i]) == 'table' or type(stack[stack_i]) == 'function')
                                            and string.gsub(tostring(stack[stack_i]), "^.-(%x%x%x%x%x%x%x%x)$", "<%1>")
                                    or  tostring(stack[stack_i])
                                ), type(stack[stack_i])
                                local s_label = ""--dbg_label_dict[stack_i] or "?!?"
                                local s_stptr = (stack_i == stack._ptr and "*" or "")..(stack_i == k and "^" or "")
                                local maxlen = math.max(#s_stack, #s_label, #s_stptr)+1
                                line_stack = line_stack..s_stack..string.rep(" ", maxlen-#s_stack)
                                --line_label = line_label..s_label..string.rep(" ", maxlen-#s_label)
                                line_stptr = line_stptr..s_stptr..string.rep(" ", maxlen-#s_stptr)
                            end
                            io.stdout:write(
                                          line_stack
                                --..  "\n"..line_label
                                ..  "\n"..line_stptr
                                ..  ""
                            )
                            io.read()
                        elseif false then
                            io.stdout:write(("stack.%s = %s"):format(
                                k,
                                (
                                        (type(v) == 'table' or type(v) == 'function')
                                            and string.gsub(tostring(v), "^.-(%x%x%x%x%x%x%x%x)$", "<%1>")
                                    or  tostring(v)
                                )
                            ))
                            io.read()
                        end
                    end,
                })
            end]]
            local copyfunc_list = table.deepcopy_copyfunc_list
            repeat
                local stack_ptr = stack._ptr
                local this_orig = stack[stack_ptr+ORIG]
                local this_copy, this_state
                stack[0] = stack[0]
                if stack.value_ignore and stack.value_ignore[this_orig] then
                    this_copy = nil
                    this_state = true --goto valuefound
                else
                    if stack.value_translate then
                        this_copy = stack.value_translate[this_orig]
                        if this_copy ~= nil then
                            this_state = true --goto valuefound
                        end
                    end
                    if not this_state then
                        local this_orig_type = type(this_orig)
                        local copyfunc = (
                                customcopyfunc_list and customcopyfunc_list[this_orig_type]
                            or  copyfunc_list[this_orig_type]
                            or  error(("cannot copy type %q"):format(this_orig_type), 2)
                        )
                        this_copy, this_state = copyfunc(
                            stack,
                            this_orig,
                            stack[stack_ptr+COPY],
                            unpack(stack--[[_dbg]], stack_ptr+STATE, stack._top)
                        )
                    end
                end
                stack[stack_ptr+COPY] = this_copy
                --::valuefound::
                if this_state == true then
                    local retto = stack[stack_ptr+RETTO]
                    stack._top = stack_ptr+1 -- pop retto, state, temp...
                    -- Leave orig and copy on stack for parent object
                    stack_ptr = retto -- return to parent's stack frame
                    stack._ptr = stack_ptr
                else
                    stack[stack_ptr+STATE] = this_state
                end
            until stack_ptr == nil
            return stack[1+COPY]
        end
    end
end

 ]===],
 ["MinHeap"] = [===[
dofile("pathfinder/deepcopy")

function new()
 r = {}

 function r:hasNext() return self.curNode ~= nil end

 function r:add(item)
  local curNode = self.curNode
  if curNode == nil then
   curNode = item
  elseif curNode.next == nil and item.cost < curNode.cost then
   item.nextListElem = curNode
   curNode = item
  else
   local ptr = curNode
   while ptr.nextListElem ~= nil and ptr.nextListElem.cost < item.cost do
    ptr = ptr.nextListElem
   end
   item.nextListElem = ptr.nextListElem
   ptr.nextListElem = item
  end
  self.curNode = curNode
 end

 function r:extractFirst()
  local result = self.curNode
  self.curNode = self.curNode.nextListElem
  return result
 end

 return r
end

 ]===],
 ["PathFinder"] = [===[
os.loadAPI("pathfinder/Point")
os.loadAPI("pathfinder/SearchNode")
os.loadAPI("pathfinder/MinHeap")
os.loadAPI("pathfinder/Surr")

local surrounding = {
 Surr.new(1, 0, 0), Surr.new(0, 1, 0), Surr.new(0, 0, 1),
 Surr.new(-1, 0, 0), Surr.new(0, -1, 0), Surr.new(0, 0, -1)
}

-- Flips path so you can follow it by pulling the last node off
function findPath(getCost, start, finish)
 return findPathReversed(getCost, finish, start)
end

function contains(t, value)
 for k, v in pairs(t) do if v == value then return true end end
end

function findPathReversed(getCost, start, finish)
 local startNode = SearchNode.new(start, start:getDistanceSquared(finish), 0)

 local openList = MinHeap.new()
 openList:add(startNode)

 brWorld = {}
 while openList:hasNext() do
  local current = openList:extractFirst()

  if current.position:getDistanceSquared(finish) <= 0 then
   return SearchNode.new(finish, current.pathCost + 1, current.cost + 1, current);
  end

  for i = 1, #surrounding do
   local surr = surrounding[i]
   local tmp = Point.new(current.position, surr.point)
   -- If surrounding node is passable and has not been calculated already
   if getCost(tmp.x, tmp.y, tmp.z) ~= nil and not brWorld[tmp:tostring()] then
    brWorld[tmp:tostring()] = true
    local pathCost = current.pathCost + getCost(tmp.x, tmp.y, tmp.z)
    local cost = pathCost + tmp:getDistanceSquared(finish)
    node = SearchNode.new(tmp, cost, pathCost, current);
    openList:add(node);
   end
  end
 end

 return nil
end

 ]===],
 ["pathfindTest"] = [===[
print(os.loadAPI("pathfinder/PathFinder"))
print(os.loadAPI("pathfinder/Point"))

world = {
 {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
 {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
 {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
 {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
 {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
 {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
 {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
 {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
 {1, 1, 1, 1, 1, 1, 1, 1, 1, 0},
 {1, 1, 1, 1, 1, 1, 1, 1, 0, 0}
}

sX, sY = 1, 1

function getCost(x, y)
 return world[y][x]
end

function getCost(x, y, z)
 if z and z ~= 0 then return nil end
 if world[y] then
  if world[y][x] then
   if world[y][x] == 0 then return nil end
   return world[y][x]
  end
 end
 return nil
end

function isPath(x, y)
 return world[y][x] < 0
end

function redraw()
 --term.clear()
 for x = 1, #world[1] do
  for y = 1, #world do
   local c = isPath(x, y) and colors.green or colors.black
   local g = getCost(x, y)
   g = g and math.abs(g) or 0
   if g == 0 then c = colors.red g = " " end
   term.setCursorPos(x, y)
   term.setBackgroundColor(c)
   write(g)
  end
 end
end

term.clear()
term.setCursorPos(1, 1)
path = PathFinder.findPath(getCost, Point.new(1, 1), Point.new(10, 10))
while path do
 if world[path.position.y] and world[path.position.y][path.position.x] and world[path.position.y][path.position.x] > 0 then
  world[path.position.y][path.position.x] = -world[path.position.y][path.position.x]
 end
 path = path.next
end
term.clear()
redraw()

 ]===],
 ["Point"] = [===[
function new(a1, a2, a3)
 if type(a1) == "table" then
  local x = a1.x + a2.x
  local y = a1.y + a2.y
  local z = (a1.z and a2.z) and (a1.z + a2.z) or 0
  return new(x, y, z)
 end

 local r = {
  x = a1,
  y = a2,
  z = a3,
 }

 function r:getDistanceSquared(point)
  local dx = math.abs(self.x - point.x)
  local dy = math.abs(self.y - point.y)
  local dz = 0
  if self.z and point.z then dz = math.abs(self.z - point.z) end
  return dx + dy + dz
 end

 function r:equals(p)
  return p.x == self.x and p.y == self.y and p.z == self.z
 end

 function r:tostring()
  return self.x .. ", " .. self.y .. (self.z and (", " .. self.z) or "")
 end

 function r:addX(n)
  return new(self.x + n, self.y, self.z)
 end

 function r:addY(n)
  return new(self.x, self.y + n, self.z)
 end

 function r:addZ(n)
  return new(self.x, self.y, self.z + n)
 end

 return r
end

zero = new(0, 0, 0)

 ]===],
 ["SearchNode"] = [===[
function new(_position, _cost, _pathCost, _next)
 return {
  position = _position,
  cost = _cost,
  pathCost = _pathCost,
  next = _next
 }
end

 ]===],
 ["Surr"] = [===[
function new(x, y, z)
 return {point = Point.new(x, y, z), cost = 1}
end

 ]===]
},
}
local function extractDirectory(directory, tDirectory)
 for name, contents in pairs(tDirectory) do
  local curPath = fs.combine(directory, name)
  if type(contents) == "table" then
   print("Creating directory " .. curPath)
   fs.makeDir(curPath)
   extractDirectory(curPath, contents)
  elseif type(contents) == "string" then
   print("Creating file " .. curPath)
   local file = io.open(curPath, "w")
   file:write(contents)
   file:close()
  else
   print("Passing over " .. curPath)
  end
 end
end
extractDirectory("", root)