-- lib/escape: how many seconds a unit dropped at a point stays out of reach of what saves him
-- (his towers, his fountain, his heroes walking at him, heroes in the fog from where they were
-- last seen), and the drop out of a list that keeps him out longest. no game knowledge beyond
-- the radii in CFG: the caller says who moves how fast and what the candidates are.
local E = {}

E.CFG = {
    tower = 700,        -- safe once this near one of his towers
    hero = 500,         -- or one of his heroes
    fountain = 1200,    -- or his fountain
    fog_walk = 3,       -- seconds of walking credited to a hero out of vision, at most
    paths = 3,          -- candidates re-priced by gridnav path
}

local function xy(p)
    if p == nil then return nil end
    local x = p.x
    if x == nil and p.GetX then return p:GetX(), p:GetY() end
    return x, p.y
end

local function dist(a, b)
    local ax, ay = xy(a)
    local bx, by = xy(b)
    return math.sqrt((ax - bx) ^ 2 + (ay - by) ^ 2)
end

-- gridnav path length, nil when there is no grid or no path (an empty answer, a capped search)
function E.path_len(a, b)
    local g = rawget(_G, "gridnav")
    if not (g and type(g.find_path) == "function") then return nil end
    local ok, pts = pcall(g.find_path, a, b)
    if not ok or type(pts) ~= "table" or #pts == 0 then return nil end
    local len, prev = 0, a
    for _, q in ipairs(pts) do len = len + dist(q, prev); prev = q end
    return len + dist(b, prev)
end

-- seconds until a gap closes: he walks at me.speed, slowed by me.slow (0..1) for the first
-- me.slow_for seconds and not at all for me.held; the saviour walks at v toward him the whole time
function E.meet(gap, me, v)
    if gap <= 0 then return 0 end
    v = v or 0
    local speed = math.max(me.speed or 300, 0)
    local held = math.max(me.held or 0, 0)
    local slow_for = math.max(me.slow_for or 0, 0)
    local slowed = speed * (1 - math.min(math.max(me.slow or 0, 0), 1))
    local marks = { held, slow_for }
    if held > slow_for then marks = { slow_for, held } end
    local t, left = 0, gap
    for i = 1, 3 do
        local stop = marks[i] or math.huge
        if stop > t then
            local own = (t < held) and 0 or ((t < slow_for) and slowed or speed)
            local rate = own + v
            if rate <= 0 then
                if stop == math.huge then return math.huge end
            elseif left <= rate * (stop - t) then
                return t + left / rate
            else
                left = left - rate * (stop - t)
            end
            t = stop
        end
    end
    return math.huge
end

-- a saviour: { p, r, v = his speed (0: a tower), walk = seconds he may already have walked at the
-- point unseen, kind, name }. the gap counts that walk, and `lead` (seconds between now and the
-- drop: a cast, a ride), as if it went straight at the point
local function gap_of(s, d, lead)
    return d - (s.r or 0) - (s.v or 0) * ((s.walk or 0) + (lead or 0))
end

function E.secs_to(s, d, me, lead)
    return E.meet(gap_of(s, d, lead), me, s.v)
end

-- seconds he stays out at `point`, and the saviour that ends it. opts: lead (above), path (price
-- by gridnav path, nearest first by the straight line, stopping once a straight price cannot win),
-- via = { p, len }: a way out known to be open (a corridor a charge cut through trees), len to p
function E.seconds(point, saviours, me, opts)
    opts = opts or {}
    local lead = opts.lead or 0
    local rows = {}
    for _, s in ipairs(saviours) do
        local d = dist(point, s.p)
        rows[#rows + 1] = { s = s, d = d, t = E.secs_to(s, d, me, lead) }
    end
    if #rows == 0 then return math.huge, nil end
    table.sort(rows, function(a, b) return a.t < b.t end)
    if not opts.path then return rows[1].t, rows[1].s end
    local via = opts.via
    local best, who = math.huge, nil
    for _, r in ipairs(rows) do
        if r.t >= best then break end
        local d = E.path_len(point, r.s.p) or r.d
        if via and via.p then
            local dv = via.len + (E.path_len(via.p, r.s.p) or dist(via.p, r.s.p))
            d = math.min(d, dv)
        end
        local t = E.secs_to(r.s, math.max(d, r.d), me, lead)
        if t < best then best, who = t, r.s end
    end
    return best, who
end

-- candidates { drop = point, lead =, via = }: each gets .secs and .saviour; the list comes back
-- sorted, the longest first. the top CFG.paths by straight line are priced again by path
function E.rank(cands, saviours, me)
    for _, c in ipairs(cands) do
        c.secs, c.saviour = E.seconds(c.drop, saviours, me, { lead = c.lead })
    end
    table.sort(cands, function(a, b) return a.secs > b.secs end)
    for i = 1, math.min(E.CFG.paths, #cands) do
        local c = cands[i]
        c.secs, c.saviour = E.seconds(c.drop, saviours, me, { lead = c.lead, path = true, via = c.via })
    end
    table.sort(cands, function(a, b) return a.secs > b.secs end)
    return cands
end

local fog
local function fog_seen()
    if fog == nil then
        local ok, m = pcall(require, "lib/fog_seen")
        fog = ok and type(m) == "table" and m or false
    end
    return fog or nil
end

-- a hero saviour. pos when he is in vision; out of it, lib/fog_seen's estimate by unit name, else
-- `last` (where the caller saw him) with the full walk credit. nil when nothing is known
function E.hero(name, pos, speed, last)
    local r = E.CFG.hero
    if pos then return { p = pos, r = r, v = speed or 300, walk = 0, kind = "hero", name = name } end
    local FS = fog_seen()
    local est = FS and name and FS.estimate and select(2, pcall(FS.estimate, name)) or nil
    if type(est) == "table" and est.pos then
        if est.source == "visible" then
            return { p = est.pos, r = r, v = speed or est.speed or 300, walk = 0, kind = "hero", name = name }
        end
        local walk = est.walk or est.age or E.CFG.fog_walk
        return { p = est.pos, r = r, v = speed or est.speed or 300, walk = math.min(walk, E.CFG.fog_walk),
                 kind = "hero", name = name, fog = est.source, age = est.age }
    end
    if last then
        return { p = last, r = r, v = speed or 300, walk = E.CFG.fog_walk, kind = "hero", name = name, fog = "caller" }
    end
    return nil
end

function E.tower(p) return { p = p, r = E.CFG.tower, v = 0, walk = 0, kind = "tower" } end
function E.fountain(p) return { p = p, r = E.CFG.fountain, v = 0, walk = 0, kind = "fountain" } end

--------------------------------------------------------------------------------
-- jump: where an escape jump (blink, leap, dash) of our own hero lands (#671)
--------------------------------------------------------------------------------
-- one rule for every jump: never inside an enemy tower's reach or a known enemy's zone, the
-- full reach when that is open, toward home (fountain, own tower, own heroes) among equals.
-- a shorter jump only when every full-length heading is refused.

E.JUMP = {
    headings = 24,
    steps = { 1.0, 0.85, 0.7, 0.55, 0.4 },
    tower = 700 + 150,  -- tower attack range + both hulls and a step
    enemy_gap = 350,    -- what an enemy closes in a beat, on top of his attack range
    fog_age = 3,        -- seconds a hero last seen still counts where he was
    w_dist = 3.0,
    w_home = 1.0,
    w_clear = 0.5,
    clear_cap = 600,
}

local function seg_dist(p, a, b)
    local ax, ay = xy(a)
    local bx, by = xy(b)
    local px, py = xy(p)
    local dx, dy = bx - ax, by - ay
    local l2 = dx * dx + dy * dy
    local t = l2 > 0 and math.max(0, math.min(1, ((px - ax) * dx + (py - ay) * dy) / l2)) or 0
    return math.sqrt((ax + dx * t - px) ^ 2 + (ay + dy * t - py) ^ 2)
end

-- o.from, o.reach (units), o.min (shortest legal jump), o.enemies / o.towers = { { p, r } }
-- (zones to stay out of), o.home = unit vector { x, y } or nil, o.path (the jump travels:
-- its segment must not cross a tower zone either), o.ok(p) = the caller's veto (a spell's
-- area, a leash, unwalkable ground). returns point, row { d, home, clear, depth } or nil, why.
-- when no landing is clean, the least deep one comes back with row.dirty = true.
function E.jump(o)
    local J = E.JUMP
    local fx, fy = xy(o.from)
    local reach = o.reach or 0
    if not fx or reach <= 0 then return nil, "no_reach" end
    local min_d = math.max(o.min or 0, 1)
    local hx, hy = 0, 0
    if o.home then hx, hy = xy(o.home) end
    local towers, enemies = o.towers or {}, o.enemies or {}
    local best, best_s, dirty, dirty_depth
    local n = o.headings or J.headings
    for _, k in ipairs(o.steps or J.steps) do
        local d = reach * k
        if d >= min_d then
            for i = 0, n - 1 do
                local a = 2 * math.pi * i / n
                local cx, cy = math.cos(a), math.sin(a)
                local p = { x = fx + cx * d, y = fy + cy * d, z = o.from.z }
                local depth, clear, under = 0, J.clear_cap, false
                for _, t in ipairs(towers) do
                    local dd = dist(p, t.p)
                    -- a jump from inside the zone may cross it on the way out, never deeper
                    if dd < t.r or (o.path and seg_dist(t.p, o.from, p) < math.min(t.r, dist(o.from, t.p) - 25)) then
                        under = true
                    end
                    clear = math.min(clear, dd - t.r)
                end
                for _, e in ipairs(enemies) do
                    local dd = dist(p, e.p)
                    if dd < e.r then depth = depth + (e.r - dd) end
                    clear = math.min(clear, dd - e.r)
                end
                if not under and (not o.ok or o.ok(p)) then
                    local home = cx * hx + cy * hy
                    if depth == 0 then
                        local s = J.w_dist * k + J.w_home * home + J.w_clear * math.max(clear, 0) / J.clear_cap
                        if not best_s or s > best_s then
                            best, best_s = { p = p, d = d, home = home, clear = clear, depth = 0 }, s
                        end
                    elseif not dirty or depth < dirty_depth
                        or (depth == dirty_depth and home > dirty.home) then
                        dirty, dirty_depth = { p = p, d = d, home = home, clear = clear, depth = depth, dirty = true }, depth
                    end
                end
            end
        end
    end
    local row = best or dirty
    if not row then return nil, "all_refused" end
    return row.p, row
end

local function unit(x, y)
    local l = math.sqrt(x * x + y * y)
    if l < 1e-6 then return 0, 0 end
    return x / l, y / l
end

local function fountain_of(team)
    if team == 2 then return { x = -6733, y = -6163 } end
    if team == 3 then return { x = 6733, y = 6163 } end
    return nil
end
E.fountain_of = fountain_of

local function alive(u)
    return u and (not Entity.IsAlive or Entity.IsAlive(u))
        and (not Entity.IsDormant or not Entity.IsDormant(u))
end

-- enemy tower zones around `hero`, { { p, r } }: attack range + 150, at least E.JUMP.tower
function E.enemy_towers(hero, scan)
    local out = {}
    local from = hero and Entity.GetAbsOrigin(hero)
    if not (from and NPCs and NPCs.InRadius and NPC.IsTower and Enum and Enum.TeamType) then return out end
    local team = Entity.GetTeamNum and Entity.GetTeamNum(hero)
    local ok, near = pcall(NPCs.InRadius, from, scan or 3000, team, Enum.TeamType.TEAM_ENEMY)
    for _, u in ipairs(ok and type(near) == "table" and near or {}) do
        if alive(u) and NPC.IsTower(u) then
            local p = Entity.GetAbsOrigin(u)
            local r = (NPC.GetAttackRange and NPC.GetAttackRange(u)) or 700
            if p then out[#out + 1] = { p = p, r = math.max(r + 150, E.JUMP.tower) } end
        end
    end
    return out
end

-- a landing (blink, a unit to jump to, a tree, a portal) inside an enemy tower's zone. pass
-- `towers` from E.enemy_towers when checking many points
function E.under_tower(hero, p, towers)
    if not p then return false end
    for _, t in ipairs(towers or E.enemy_towers(hero)) do
        if dist(p, t.p) < t.r then return true end
    end
    return false
end

-- the world around `hero` the way E.jump reads it, from the public api. opts.scan (3000),
-- opts.gap (E.JUMP.enemy_gap). home = fountain + nearest own tower + own heroes near, each a
-- unit vector, summed: the way back to the team.
function E.world(hero, opts)
    opts = opts or {}
    local J = E.JUMP
    local from = Entity.GetAbsOrigin(hero)
    if not from then return nil end
    local scan = opts.scan or 3000
    local gap = opts.gap or J.enemy_gap
    local team = Entity.GetTeamNum and Entity.GetTeamNum(hero)
    local my_hull = (NPC.GetHullRadius and NPC.GetHullRadius(hero)) or 24
    local w = { from = from, enemies = {}, towers = {} }
    local seen = {}
    for _, u in ipairs(Heroes and Heroes.GetAll and Heroes.GetAll() or {}) do
        if u ~= hero and alive(u) and not (Entity.IsSameTeam and Entity.IsSameTeam(hero, u)) then
            local p = Entity.GetAbsOrigin(u)
            if p and dist(p, from) <= scan then
                local r = ((NPC.GetAttackRange and NPC.GetAttackRange(u)) or 150) + gap + my_hull
                    + ((NPC.GetHullRadius and NPC.GetHullRadius(u)) or 24)
                w.enemies[#w.enemies + 1] = { p = p, r = r }
                local nm = NPC.GetUnitName and NPC.GetUnitName(u)
                if nm then seen[nm] = true end
            end
        end
    end
    -- heroes out of vision for a moment are still where they were, plus their walk
    local FS = fog_seen()
    if FS and FS.estimate and Heroes and Heroes.GetAll then
        for _, u in ipairs(Heroes.GetAll()) do
            local nm = NPC.GetUnitName and NPC.GetUnitName(u)
            if nm and not seen[nm] and u ~= hero and Entity.IsAlive and Entity.IsAlive(u)
                and not (Entity.IsSameTeam and Entity.IsSameTeam(hero, u)) then
                local ok, est = pcall(FS.estimate, nm)
                if ok and type(est) == "table" and est.pos and (est.age or 99) <= J.fog_age
                    and dist(est.pos, from) <= scan then
                    local walk = (est.speed or 300) * (est.age or 0)
                    w.enemies[#w.enemies + 1] = { p = est.pos, r = 150 + gap + walk, fog = true }
                end
            end
        end
    end
    local hx, hy = 0, 0
    local f = fountain_of(team)
    if f then
        local ux, uy = unit(f.x - from.x, f.y - from.y)
        hx, hy = hx + ux, hy + uy
    end
    w.towers = E.enemy_towers(hero, scan)
    if NPCs and NPCs.InRadius and NPC.IsTower and Enum and Enum.TeamType then
        local okf, own = pcall(NPCs.InRadius, from, scan, team, Enum.TeamType.TEAM_FRIEND)
        local tp, td
        for _, u in ipairs(okf and own or {}) do
            if alive(u) and NPC.IsTower(u) then
                local p = Entity.GetAbsOrigin(u)
                local d = p and dist(p, from)
                if d and d > 300 and (not td or d < td) then tp, td = p, d end
            end
        end
        if tp then
            local ux, uy = unit(tp.x - from.x, tp.y - from.y)
            hx, hy = hx + ux, hy + uy
        end
    end
    local ax, ay, an = 0, 0, 0
    for _, u in ipairs(Heroes and Heroes.GetAll and Heroes.GetAll() or {}) do
        if u ~= hero and alive(u) and Entity.IsSameTeam and Entity.IsSameTeam(hero, u) then
            local p = Entity.GetAbsOrigin(u)
            if p and dist(p, from) <= 1500 and dist(p, from) > 200 then
                ax, ay, an = ax + p.x, ay + p.y, an + 1
            end
        end
    end
    if an > 0 then
        local ux, uy = unit(ax / an - from.x, ay / an - from.y)
        hx, hy = hx + 0.5 * ux, hy + 0.5 * uy
    end
    local ux, uy = unit(hx, hy)
    if ux ~= 0 or uy ~= 0 then w.home = { x = ux, y = uy } end
    return w
end

local function walkable(p)
    local G = rawget(_G, "GridNav")
    if G and G.IsTraversable then
        local ok, r = pcall(G.IsTraversable, p)
        if ok and r == false then return false end
    end
    return true
end
E.walkable = walkable

-- the landing for `hero` jumping up to `reach`: E.world + E.jump. opts: min, path, steps
-- ({ 1 } for a dash of fixed length), ok (an extra veto on top of walkable ground), scan, gap. returns point (a Vector when the api
-- has one), row, world.
function E.jump_from(hero, reach, opts)
    opts = opts or {}
    local w = E.world(hero, opts)
    if not w then return nil, "no_hero" end
    local veto = opts.ok
    local p, row = E.jump({
        from = w.from, reach = reach, min = opts.min, enemies = w.enemies, towers = w.towers,
        home = w.home, path = opts.path, steps = opts.steps, headings = opts.headings,
        ok = function(q)
            local v = rawget(_G, "Vector")
            local qv = v and v(q.x, q.y, q.z or 0) or q
            if not walkable(qv) then return false end
            return not veto or veto(qv)
        end,
    })
    if not p then return nil, row, w end
    local v = rawget(_G, "Vector")
    return v and v(p.x, p.y, p.z or 0) or p, row, w
end

return E

{ "kind": "lib", "version": "1.0.1" }