footpath/init.lua

local dbg
if moddebug then dbg=moddebug.dbg("footpath") else dbg={v1=function() end,v2=function() end,v3=function() end} end

footpath = {}

-- This is the current node graph, which in actually in use. It only changes
-- when a footpath.make_pathnodes() produces a new and error-free graph.
local pathnodes = {}

-- This is the definition of all the junctions in the map. It's updated in
-- real time as junctions are added/removed/edited in the map. Changes to
-- this do not affect node or route finding until footpath.make_pathnodes()
-- is called (and detects no errors).
--
-- It's mostly a duplicate of information in pathnodes - the difference being
-- this is a live view of the actual map, which is not in use and may contain
-- routing errors or incompleteness.
local junctions = {}

-- This is just a cache of recently calculated routes, to avoid recalculating
-- the same thing.
local routecache = {}


--- Save the current footpath network status.
-- 'what' is a table with either pathnodes=true, junctions=true, or
-- both.
footpath.save = function(what)

    if what.pathnodes then
        -- For the purposes of serialisation, we want a copy of the nodes with
        -- neighbours referenced by node name, not a reference to the actual
        -- node, otherwise it will serialise horribly!
        local lnodes = {}
        for n, nn in pairs(pathnodes) do
            local nei = {}
            for dir, ne in pairs(nn.neighbours) do
                nei[dir] = ne.name
            end
            lnodes[n] = {name=n, pos=nn.pos, neighbours=nei}
        end

        local f = io.open(minetest.get_worldpath().."/footpath_pathnodes.json", "w+")
        if f then
            f:write(minetest.write_json(lnodes))
            f:close()
        end
    end

    if what.junctions then
        local f = io.open(minetest.get_worldpath().."/footpath_junctions.json", "w+")
        if f then
            f:write(minetest.write_json(junctions))
            f:close()
        end
    end

end

--- Load the footpath network status.
footpath.load = function()
    local f = io.open(minetest.get_worldpath().."/footpath_pathnodes.json", "r")
    if f then
        pathnodes = minetest.parse_json(f:read("*all"))
        f:close()

        -- Now we need to undo the dereferencing we did when we saved it...
        for _, nn in pairs(pathnodes) do
            local nei = {}
            if nn.neighbours then
                for dir, ne in pairs(nn.neighbours) do
                    nei[dir] = pathnodes[ne]
                end
            end
            nn.neighbours = nei
        end

    end

    f = io.open(minetest.get_worldpath().."/footpath_junctions.json", "r")
    if f then
        junctions = minetest.parse_json(f:read("*all"))
        f:close()
    end

end


--- Build the path nodes graph.
-- This is intended to be called via a chat command by a server administrator.
-- It builds a graph by interrogating the defined junctions. This graph is then
-- used when finding nodes and routes.
-- @return A string describing an error in the setup (in which case no changes
--         are made), or nil on success (in which case, the new graph will
--         take effect).
footpath.make_pathnodes = function()

    newpathnodes = {}
    for _, jct in pairs(junctions) do
        newpathnodes[jct.name] = {name=jct.name, pos=jct.pos, neighbours={}}
    end
    for _, jct in pairs(junctions) do
        if not jct.exits then
            return "Junction "..jct.name.." has no exits"
        end
        for dir, exit in pairs(jct.exits) do
            if exit:sub(1,1) ~= "@" then
                if not junctions[exit] then
                    return "Exit "..exit.." from "..jct.name.." has no destination"
                end
                newpathnodes[jct.name].neighbours[dir] = newpathnodes[exit]
            end
        end
    end

    for _, pn in pairs(newpathnodes) do
        for _, nn in pairs(pn.neighbours) do
            local ok = false
            for _, nnn in pairs(nn.neighbours) do
                if nnn == pn then
                    ok = true
                    break
                end
            end
            if not ok then
                return "Route from "..pn.name.." at "..minetest.pos_to_string(pn.pos)..
                        " to "..nn.name.." at "..minetest.pos_to_string(nn.pos)..
                        " does not return"
            end
        end
    end

    pathnodes = newpathnodes
    routecache = {}
    footpath.save{pathnodes=true}

    return nil

end


-- Get the build direction from the junction with the given name
footpath.get_build_dir = function(name)
    if not junctions[name] then return nil end
    for dir, exit in pairs(junctions[name].exists) do
        if exit == "@build" then
            return dir
        end
    end
    return nul
end

footpath.get_junction = function(name)
    return junctions[name]
end

-- Get the position of the path node with the given name.
footpath.get_nodepos = function(name)
    if not pathnodes[name] then return nil end
    return pathnodes[name].pos
end

-- Returns the nearest vacant building plot to the given position.
-- Returns the junction the plot is at, or nil if none found.
footpath.nearest_vacant_plot = function(pos)

    local nearest, nearestdist
    for _, jct in pairs(junctions) do
        -- Only if this junction is already in the pathnodes graph...
        if pathnodes[jct.name] then
            for dir, exit in pairs(jct.exits) do
                if exit == "@plot" then
                    local dist = vector.distance(pos, jct.pos)
                    if not nearestdist or dist < nearestdist then
                        nearest = jct
                        nearestdist = nearestdist
                    end
                end
            end
        end
    end

    return nearest

end

-- Claim a free plot at the given position (presumably one previously
-- retrieved via nearest_vacant_plot().
-- Returns true if successful, in which case a new junction called
-- name will have been created.
footpath.claim_plot = function(at, name)

    if not junctions[at] then return "No junction called "..at end

    local pn = pathnodes[at]
    if not pn then return "No pathode called "..at end
    local jct = junctions[pn.name]
    if not jct then return "Some kind of mixup"  end
    for dir, exit in pairs(jct.exits) do
        if exit == "@plot" then
            local backdir, newpos
            if dir == "n" then
                backdir = "s"
                newpos = vector.add(jct.pos, {x=0, y=0, z=2})
            elseif dir == "s" then
                backdir = "n"
                newpos = vector.add(jct.pos, {x=0, y=0, z=-2})
            elseif dir == "e" then
                backdir = "w"
                newpos = vector.add(jct.pos, {x=2, y=0, z=0})
            else
                backdir = "e"
                newpos = vector.add(jct.pos, {x=-2, y=0, z=0})
            end
            newjct = {name=name, pos=newpos,
                        exits={}}
            newjct.exits[backdir] = jct.name
            newjct.exits[dir] = "@build"
            jct.exits[dir] = name
            newpn = {name=name, pos=newpos,
                        neighbours = {}}
            newpn.neighbours[backdir] = pn
            pn.neighbours[dir] = newpn
            pathnodes[name] = newpn
            junctions[name] = newjct
            -- We've updated both the junctions data and the live pathnodes
            -- graph at the same time. We save them both. It's done like this
            -- to avoid interfering with human editing.
            footpath.save{pathnodes=true, junctions=true}
            return true
        end
    end
    return "No vacant plot here"

end


-- Returns the nearest footpath junction to the given position, optionally
-- checking only those matching a given pattern (which is a lua regex).
-- The pattern will be amended to make it case-insensitive.
-- Returns nil if nothing could be found, otherwise the footpath junction
-- and the distance to it.
-- maxdist is the maximum distance at which to search.
footpath.nearest_junction = function(pos, pattern, maxdist)

    local nearest, nearestdist
    if pattern then
        -- Make the pattern case-insensitive...
            pattern = pattern:gsub("(%%?)(.)", function(percent, letter)
            if percent ~= "" or not letter:match("%a") then
                return percent .. letter
        else
                return string.format("[%s%s]", letter:lower(), letter:upper())
            end
        end)
    end
    for _, pn in pairs(pathnodes) do
        if (not pattern) or string.find(pn.name, pattern) then
            local dist = vector.distance(pos, pn.pos)
            if ((not nearestdist) or dist < nearestdist) and ((not maxdist) or dist <= maxdist) then
                nearest = pn
                nearestdist = dist
            end
        end
    end
    return nearest, nearestdist
end


--- Fast removal of a value from a table
-- Avoids shuffling by swapping the last item with the one to be removed.
-- @param t The table
-- @param v The value to remove
local function table_fast_remove(t, v)
    for i, tv in ipairs(t) do
        if tv == v then
            t[i] = t[#t]
            t[#t] = nil
            return
        end
    end	
end

--- Check if a table contains the given value
-- @param t The table
-- @param v The value to check for
-- @return True if the table contains the value
local function table_contains(t, v)

    for _, tv in ipairs(t) do
        if tv == v then return true end
    end
    return false
end

--- Choose the best node from the list of open ones
-- @param open List of nodes
-- @param f Corresponding list of f scores for those node
-- @return The node with the lowest f score
local function choose_best(open, f)

    local lowest, best = 1/0, nil
    for _, node in ipairs(open) do
        local ts = f[node]
        if ts < lowest then
            lowest, best = ts, node
        end
    end
    return best
end

--- Reverse-iterate along the found route to construct the final path.
local function get_path(path, prev, current)

    if not prev[current] then return path end
    table.insert(path, 1, prev[current])
    return get_path(path, prev, prev[current])
end

--- Use A* to calculate the route from start to goal. Paths are cached.
local function astar(start, goal)

    if not routecache[start] then
        routecache[start] = {}
    elseif routecache[start][goal] then
        dbg.v3("astar used cached path")
        return routecache[start][goal]
    end

    local g = {[start]=0}
    local f = {[start]=vector.distance(start.pos, goal.pos)}
    local open = {start}
    local closed = {}
    local prev = {}

    while #open > 0 do

        local current = choose_best(open, f)
        if current == goal then
            local path = get_path({}, prev, goal)
            table.insert(path, goal)
            routecache[start][goal] = path
            return path
        end

        table_fast_remove(open, current)
        table.insert(closed, current)

        for _, neighbour in pairs(current.neighbours) do
            if not table_contains(closed, neighbour) then

                local newg = g[current] + vector.distance(current.pos, neighbour.pos)

                if not table_contains(open, neighbour) or newg < g[neighbour] then
                    prev[neighbour] = current
                    g[neighbour] = newg
                    f[neighbour] = g[neighbour] + vector.distance(neighbour.pos, goal.pos)
                    if not table_contains(open, neighbour) then
                        table.insert(open, neighbour)
                    end
                end
            end
        end
    end
    return nil
end


--- Get a footpath route
-- @param start Starting node name, e.g. "path_My House"
-- @param goal Goal node name, e.g. "path_Your House"
-- @return A list of path node names defining the route, including the start
--         and the goal, or nil if no route was found.
footpath.get_route = function(start, goal)

    if not pathnodes then return nil end
    if not pathnodes[start] then
        dbg.v3("Route start "..start.." doesn't exist")
        return nil
    end
    if not pathnodes[goal] then
        dbg.v3("Route goal "..goal.." doesn't exist")
        return nil
    end

    local path = astar(pathnodes[start], pathnodes[goal])
    if not path then
        dbg.v3("Route from "..start.." to "..goal.." not found")
        return nil
    end

    local rpath = {}
    for _, n in ipairs(path) do
        table.insert(rpath, n.name)
    end
    dbg.v3("Route from "..start.." to "..goal.." is "..dump(rpath))
    return rpath

end

--- Find the next node along a footpath
-- All positions are exact (rounded) node positions.
-- @param curpos The position of a current footpath node
-- @param lastpos The position of the previous footpath node
-- @param samedironly True to only look in the current direction of travel
-- @return The position of the next footpath node, or nil if there isn't
--         one, or "unloaded" if there may or may not be one, but we can't
--         tell because of unloaded blocks.
--         And true to first dig above the given node (there will be snow
--         there!)
footpath.findnext = function(curpos, lastpos, samedironly)
    --dbg.v3("footpath_findnext, cur="..minetest.pos_to_string(curpos)..", last="..minetest.pos_to_string(lastpos)..", same="..dump(samedironly))
    local xz
    if samedironly then
        xz = {}
    else
        xz = {{x=1,z=0}, {x=0,z=1}, {x=-1,z=0}, {x=0,z=-1}}
    end
    -- Favour the direction we're already going
    -- TODO - that means we could check it twice (but then again, only
    --        if we reach an invalid bit of footpath!
    table.insert(xz, 1, {x=curpos.x-lastpos.x, z=curpos.z-lastpos.z})
    for _, cxz in ipairs(xz) do
        for y = 1, -1, -1 do
            local x = cxz.x
            local z = cxz.z
            local npos = vector.add(curpos, vector.new(x, y, z))
            if not vector.equals(npos, lastpos) then
                local n = minetest.get_node(npos)
                if n.name == "ignore" then return "unloaded" end
                if n.name == 'default:cobble' or
                    n.name == 'footpath:junction' or 
                    n.name == 'default:mossycobble' or
                    n.name == 'stairs:stair_cobble' or
                    n.name == 'stairs:stair_stone' or
                    n.name == 'default:wood' or
                    n.name:sub(1,5) == 'wool:' or        -- because wool is a carpet!
                    n.name == 'stairs:stair_wood' then
                    local n = minetest.get_node({x=npos.x,y=npos.y+1,z=npos.z})
                    if n.name == "default:snow" then
                        -- Snow is walkable, but we will either walk over it
                        -- or dig it out of the way, so that's fine...
                        dbg.v3("footpath_findnext found (snow-covered) "..minetest.pos_to_string(npos))
                        return npos, true
                    end

                    -- Otherwise, so long as there's nothing walkable above the
                    -- node it should be a valid footpath node...
                    -- TODO - allowing doors/gates here, as we do elsewhere, but
                    --        really we need to know if the entity can use doors!
                    local nd = minetest.registered_nodes[n.name]
                    local iswalkable = nd.walkable
                    if iswalkable and (
                            (nd.groups.door and nd.groups.door ~= 0) or
                            (nd.groups.gate and nd.groups.gate ~= 0)) then
                        iswalkable = false
                    end

                    if not iswalkable then
                        --dbg.v3("footpath_findnext found "..minetest.pos_to_string(npos))
                        return npos, false
                    end
                end
            end
        end
    end
    return nil
end


footpath.cur_edit_pos = {}
footpath.cur_node_pos = {}

footpath.show_junction_formspec = function(player, pos, nodepos, errmsg)

    local playername = player:get_player_name()
    if not minetest.check_player_privs(playername, {server=true}) then
        return false
    end

    local editjct
    for _, jj in pairs(junctions) do
        if vector.equals(jj.pos, pos) then
            editjct = jj
            if not editjct.exits then editjct.exits = {} end
            break
        end
    end
    if not editjct then
        editjct = {name=nil, exits={}}
    end

    local formspec = "size[8,9.5]"..
        "field[1,1;7,1;name;Name:;"..(editjct.name or "").."]"..
        "field[1,2;7,1;n;North:;"..(editjct.exits["n"] or "").."]"..
        "field[1,3;7,1;s;South:;"..(editjct.exits["s"] or "").."]"..
        "field[1,4;7,1;e;East:;"..(editjct.exits["e"] or "").."]"..
        "field[1,5;7,1;w;West:;"..(editjct.exits["w"] or "").."]"..
        "button_exit[1,6;2,1;save;Save]"..
        "button_exit[5,6;2,1;update;Update]"

    if errmsg then
	formspec = formspec.."label[0.1,8;"..errmsg.."]"
    end

    footpath.cur_edit_pos[playername] = pos
    footpath.cur_node_pos[playername] = nodepos
    minetest.show_formspec(playername, "footpath:junction_formspec",
	    formspec)

end

minetest.register_on_player_receive_fields(function(sender, formname, fields)
    if formname == "footpath:junction_formspec" then

	if fields.save or fields.update then
	    local playername = sender:get_player_name()
	    local pos = footpath.cur_edit_pos[playername]
	    local nodepos = footpath.cur_node_pos[playername]
	    if not pos then return end

            local showerr = function(errmsg)
                footpath.show_junction_formspec(sender, pos, nodepos, errmsg)
            end

            if fields.name == "" then
                showerr("Name cannot be blank")
                return
            end

            local editjct
            local new = true
            for _, jj in pairs(junctions) do
                if vector.equals(jj.pos, pos) then
                    editjct = jj
                    new = false
                    break
                end
            end
            if not editjct then
                editjct = {name=nil, pos=pos, exits={}}
            end

            local dirs = {"n", "s", "e", "w"}

            -- Check for duplicate name
            if new or editjct.name ~= fields.name then
                for _, jj in pairs(junctions) do
                    if jj.name == fields.name then
                        showerr("A junction with this name already exists")
                        return
                    end
                end
            end

            local renamefrom = nil
            if not new and editjct.name ~= fields.name then
                renamefrom = editjct.name
            end
            editjct.name = fields.name
            for _, dir in pairs(dirs) do
                if fields[dir] == "" then
                    editjct.exits[dir] = nil
                else
                    editjct.exits[dir] = fields[dir]
                end
            end

            if renamefrom then
                for _, jct in pairs(junctions) do
                    for _, dir in pairs(dirs) do
                        if jct.exits[dir] == renamefrom then
                            jct.exits[dir] = editjct.name
                        end
                    end
                end
                junctions[editjct.name] = editjct
                junctions[renamefrom] = nil
            elseif new then
                junctions[editjct.name] = editjct
            end

	    local meta = minetest.get_meta(nodepos)
            meta:set_string("infotext", editjct.name)

            footpath.save{junctions=true}
	    dbg.v1(playername.." updated junction "..editjct.name.." at "..minetest.pos_to_string(pos))

            if fields.update then
                errmsg = footpath.make_pathnodes()
                if errmsg then
                    showerr(errmsg)
                    return
                end
                minetest.chat_send_player(playername, "Footpath node graph updated successfully")
            end

	end
    end
end)


footpath.load()

minetest.register_node("footpath:junction", {
    description = "Footpath junction marker",
    tiles = {"footpath_top.png", "footpath_side.png", "footpath_side.png",
             "footpath_side.png", "footpath_side.png", "footpath_side.png"},
    groups = {cracky=2},
    legacy_facedir_simple = true,
    is_ground_content = false,
    on_rightclick = function(pos, node, clicker)
        local jctpos = vector.add(pos, {x=0, y=1, z=0})
        footpath.show_junction_formspec(clicker, jctpos, pos);
    end,
    on_destruct = function(pos)
        local jctpos = vector.add(pos, {x=0, y=1, z=0})

        for _, jj in pairs(junctions) do
            if vector.equals(jj.pos, jctpos) then
                junctions[jj.name] = nil
                break
            end
        end
        footpath.save{junctions=true}

    end,
    can_dig = function(pos, player)
        return minetest.check_player_privs(player:get_player_name(), {server=true})
    end
})

minetest.register_node("footpath:junction_buried", {
    description = "Footpath junction marker",
    tiles = {"footpathb_top.png", "footpathb_side.png", "footpathb_side.png",
             "footpathb_side.png", "footpathb_side.png", "footpathb_side.png"},
    groups = {cracky=2},
    legacy_facedir_simple = true,
    is_ground_content = false,
    on_rightclick = function(pos, node, clicker)
        local jctpos = vector.add(pos, {x=0, y=2, z=0})
        footpath.show_junction_formspec(clicker, jctpos, pos);
    end,
    on_destruct = function(pos)
        local jctpos = vector.add(pos, {x=0, y=2, z=0})

        for _, jj in pairs(junctions) do
            if vector.equals(jj.pos, jctpos) then
                junctions[jj.name] = nil
                break
            end
        end
        footpath.save{junctions=true}

    end,
    can_dig = function(pos, player)
        return minetest.check_player_privs(player:get_player_name(), {server=true})
    end
})