1262 lines
40 KiB
Lua
1262 lines
40 KiB
Lua
-- pfQuest SmartArrow
|
|
-- Copyright (C) 2026 pfQuest SmartArrow contributors
|
|
--
|
|
-- This program is free software: you can redistribute it and/or modify it
|
|
-- under the terms of the GNU General Public License as published by the Free
|
|
-- Software Foundation, either version 3 of the License, or (at your option)
|
|
-- any later version. It is distributed WITHOUT ANY WARRANTY; see LICENSE.md.
|
|
|
|
-- pfQuest SmartArrow: local navigation
|
|
--
|
|
-- graph.lua decides *which* zone exits, flights and boats to take. This file
|
|
-- decides how to walk each stretch in between, so the arrow and the map path
|
|
-- bend around things instead of running straight at them:
|
|
--
|
|
-- obstacles circles you cannot walk through. A few ship in
|
|
-- data/obstacles.lua (placed from pfQuest's own NPC positions),
|
|
-- the rest are learned: when you keep sliding sideways while
|
|
-- facing the arrow, something is in the way, and a small circle
|
|
-- is added there.
|
|
-- trails the paths you actually walk, recorded as you play. Walked
|
|
-- ground is known to be passable and is mostly road, so the
|
|
-- planner prefers it.
|
|
-- danger a per-zone grid built from pfQuest's spawn data: hostile mobs
|
|
-- weighted by their level against yours (elites count triple,
|
|
-- grey mobs and critters not at all). Paths are charged extra
|
|
-- for crossing it, so they skirt camps when the detour is worth it.
|
|
--
|
|
-- Refine(a, b, zone) returns a polyline from a to b. The search runs on a
|
|
-- small local graph: a, b, points around nearby obstacles, nearby trail
|
|
-- points and a coarse lattice for detours, with straight edges between
|
|
-- neighbours that do not cross an obstacle.
|
|
--
|
|
-- Lua 5.0: no '#', no '%', no select().
|
|
|
|
local sqrt, floor, cos, sin, atan2, abs, pi = math.sqrt, math.floor, math.cos, math.sin, math.atan2, math.abs, math.pi
|
|
local getn, insert = table.getn, table.insert
|
|
|
|
local N = CreateFrame("Frame", "pfQuestSmartArrowNav", UIParent)
|
|
pfQuestSmartArrowNav = N
|
|
|
|
local TRAIL_STEP = 12 -- yards between recorded trail points
|
|
local TRAIL_SNAP = 6 -- reuse a trail point this close
|
|
local TRAIL_BREAK = 60 -- a jump this long is a teleport, not a walk
|
|
local TRAIL_FACTOR = 0.75 -- walked ground costs this much of open ground
|
|
local TRAIL_CAP = 30000 -- recorded points, account wide
|
|
local HASH = 50 -- spatial hash cell, yards
|
|
local RING = 8 -- points around each obstacle
|
|
local RING_PAD = 9 -- yards outside the obstacle edge
|
|
local MAX_TRAIL_NODES = 140
|
|
local MAX_LATTICE = 90
|
|
|
|
local function Dist(a, b)
|
|
local dn, dw = a.n - b.n, a.w - b.w
|
|
return sqrt(dn * dn + dw * dw)
|
|
end
|
|
|
|
local function Cfg()
|
|
return pfQuestSmartArrow_config
|
|
end
|
|
|
|
-- world <-> zone map ----------------------------------------------------------
|
|
|
|
local transforms = {}
|
|
function N:ResetTransforms() transforms = {} self.dangercache = {} end
|
|
function N:Transform(zone)
|
|
if not zone then return nil end
|
|
local t = transforms[zone]
|
|
if t == nil then
|
|
local G = pfQuestSmartArrowGraph
|
|
local c, n0, w0 = G.Resolve(zone, 0, 0)
|
|
local _, n1, w1 = G.Resolve(zone, 100, 100)
|
|
if c and n1 and n1 ~= n0 and w1 ~= w0 then
|
|
t = { c = c, n0 = n0, w0 = w0, dn = n1 - n0, dw = w1 - w0 }
|
|
else
|
|
t = false
|
|
end
|
|
transforms[zone] = t
|
|
end
|
|
return t or nil
|
|
end
|
|
|
|
-- zone map percent of a world point (may lie outside 0..100)
|
|
function N:WorldToMap(zone, n, w)
|
|
local t = self:Transform(zone)
|
|
if not t then return nil end
|
|
return (w - t.w0) / t.dw * 100, (n - t.n0) / t.dn * 100, t.c
|
|
end
|
|
|
|
-- danger ----------------------------------------------------------------------
|
|
|
|
N.grid = nil -- [zone][cell] = { [level] = weight }
|
|
N.dangercache = {} -- [zone][cell] = value, for one player level
|
|
N.dangerlevel = nil
|
|
|
|
local function MaxLevel(lvl)
|
|
if not lvl then return 1 end
|
|
local best = 1
|
|
for num in string.gfind(lvl, "%d+") do
|
|
local v = tonumber(num)
|
|
if v and v > best then best = v end
|
|
end
|
|
return best
|
|
end
|
|
|
|
local function CellKey(x, y)
|
|
return floor(x) * 128 + floor(y)
|
|
end
|
|
|
|
-- built once per login in small slices so the client does not hitch
|
|
function N:StartDangerBuild()
|
|
if self.builder or self.grid then return end
|
|
if not (pfDB and pfDB["units"] and pfDB["units"]["data"]) then return end
|
|
local mine = UnitFactionGroup("player") == "Horde" and "H" or "A"
|
|
local grid = {}
|
|
self.builder = coroutine.create(function()
|
|
local count = 0
|
|
for _, unit in pairs(pfDB["units"]["data"]) do
|
|
local fac = unit["fac"]
|
|
local coords = unit["coords"]
|
|
if coords and (not fac or not string.find(fac, mine)) then
|
|
local level = MaxLevel(unit["lvl"])
|
|
local rank = tonumber(unit["rnk"]) or 0
|
|
local weight = (rank == 1 or rank == 2 or rank == 3) and 3 or 1
|
|
for _, c in pairs(coords) do
|
|
local x, y, zone = c[1], c[2], c[3]
|
|
if zone and x and y then
|
|
local zgrid = grid[zone]
|
|
if not zgrid then zgrid = {} grid[zone] = zgrid end
|
|
local key = CellKey(x, y)
|
|
local cell = zgrid[key]
|
|
if not cell then cell = {} zgrid[key] = cell end
|
|
cell[level] = (cell[level] or 0) + weight
|
|
end
|
|
end
|
|
end
|
|
count = count + 1
|
|
if count >= 250 then
|
|
count = 0
|
|
coroutine.yield()
|
|
end
|
|
end
|
|
N.grid = grid
|
|
end)
|
|
end
|
|
|
|
local function LevelWeight(mob, me)
|
|
if mob <= 1 and me > 3 then return 0 end -- critters
|
|
local d = mob - me
|
|
if d <= -8 then return 0 end -- grey, will not attack
|
|
if d <= -4 then return 0.3 end
|
|
local w = 1 + 0.35 * d
|
|
if w > 4 then w = 4 end
|
|
if w < 0.5 then w = 0.5 end
|
|
return w
|
|
end
|
|
|
|
local function CellDanger(zgrid, key, me)
|
|
local cell = zgrid[key]
|
|
if not cell then return 0 end
|
|
local sum = 0
|
|
for level, weight in pairs(cell) do
|
|
sum = sum + weight * LevelWeight(level, me)
|
|
end
|
|
return sum
|
|
end
|
|
|
|
-- hostile pressure at a world point, roughly "mobs that may attack you here"
|
|
function N:DangerAt(zone, p)
|
|
local grid = self.grid
|
|
if not grid or not zone then return 0 end
|
|
local zgrid = grid[zone]
|
|
if not zgrid then return 0 end
|
|
local x, y = self:WorldToMap(zone, p.n, p.w)
|
|
if not x or x < 0 or x >= 100 or y < 0 or y >= 100 then return 0 end
|
|
|
|
local me = UnitLevel("player")
|
|
if self.dangerlevel ~= me then
|
|
self.dangerlevel = me
|
|
self.dangercache = {}
|
|
end
|
|
local zcache = self.dangercache[zone]
|
|
if not zcache then zcache = {} self.dangercache[zone] = zcache end
|
|
|
|
local key = CellKey(x, y)
|
|
local v = zcache[key]
|
|
if not v then
|
|
-- the cell itself plus some of its neighbours: aggro reaches across lines
|
|
v = CellDanger(zgrid, key, me)
|
|
+ 0.4 * (CellDanger(zgrid, key + 128, me) + CellDanger(zgrid, key - 128, me)
|
|
+ CellDanger(zgrid, key + 1, me) + CellDanger(zgrid, key - 1, me))
|
|
zcache[key] = v
|
|
end
|
|
return v
|
|
end
|
|
|
|
local function Safety()
|
|
local s = tonumber(Cfg().safety)
|
|
if not s then return 1 end
|
|
return s
|
|
end
|
|
|
|
-- multiplier on walking cost for a given danger value
|
|
local function DangerFactor(d)
|
|
local f = 1 + Safety() * 0.5 * d
|
|
if f > 6 then f = 6 end
|
|
return f
|
|
end
|
|
|
|
-- obstacles -------------------------------------------------------------------
|
|
|
|
N.shipped = {}
|
|
|
|
function N:ResolveObstacles()
|
|
self.shipped = {}
|
|
local G = pfQuestSmartArrowGraph
|
|
for _, o in ipairs(pfQuestSmartArrowData and pfQuestSmartArrowData.obstacles or {}) do
|
|
local c, n, w = G.Resolve(o.zone, o.x, o.y)
|
|
if c then
|
|
local ob = { c = c, n = n, w = w, r = o.r, name = o.name, area = o.area, up = o.up, down = o.down }
|
|
if o.doors then
|
|
ob.doors = {}
|
|
for _, d in ipairs(o.doors) do
|
|
local dc, dn, dw = G.Resolve(d.zone or o.zone, d.x, d.y)
|
|
if dc then insert(ob.doors, { c = dc, n = dn, w = dw }) end
|
|
end
|
|
end
|
|
insert(self.shipped, ob)
|
|
end
|
|
end
|
|
end
|
|
|
|
-- inside it? For a building that means you are going in or out, so it is
|
|
-- not in your way. A learned obstacle is only a guess at a rock or a wall,
|
|
-- so you have to be well inside before it stops counting.
|
|
local function Within(o, p)
|
|
return Dist(o, p) <= (o.learned and o.r * 0.5 or o.r)
|
|
end
|
|
|
|
local function EachObstacle(fn)
|
|
for _, o in ipairs(N.shipped) do fn(o) end
|
|
for _, o in ipairs(Cfg().obstacles) do fn(o) end
|
|
end
|
|
|
|
-- the structure (a tree or building with doors) a point is on or in
|
|
local function StructureAt(p)
|
|
for _, o in ipairs(N.shipped) do
|
|
if o.doors and o.area and o.c == p.c and Dist(o, p) < o.area then
|
|
return o
|
|
end
|
|
end
|
|
return nil
|
|
end
|
|
N.StructureAt = function(self, p) return StructureAt(p) end
|
|
|
|
-- does segment p-q pass through circle o?
|
|
local function SegmentHits(p, q, o)
|
|
local dn, dw = q.n - p.n, q.w - p.w
|
|
local len2 = dn * dn + dw * dw
|
|
local t = 0
|
|
if len2 > 0 then
|
|
t = ((o.n - p.n) * dn + (o.w - p.w) * dw) / len2
|
|
if t < 0 then t = 0 elseif t > 1 then t = 1 end
|
|
end
|
|
local cn, cw = p.n + dn * t - o.n, p.w + dw * t - o.w
|
|
return cn * cn + cw * cw < o.r * o.r
|
|
end
|
|
|
|
local function SegmentClear(p, q, obs)
|
|
for i = 1, getn(obs) do
|
|
if SegmentHits(p, q, obs[i]) then return false end
|
|
end
|
|
return true
|
|
end
|
|
|
|
local function InsideAny(p, obs)
|
|
for i = 1, getn(obs) do
|
|
local o = obs[i]
|
|
if Dist(p, o) < o.r then return true end
|
|
end
|
|
return false
|
|
end
|
|
|
|
-- trails ----------------------------------------------------------------------
|
|
|
|
N.hash = {} -- [c][key] = { index, ... }
|
|
N.roads = {} -- built-in roads from NPC patrols, same shape as trails
|
|
N.roadhash = {}
|
|
|
|
local function HashKey(n, w)
|
|
return floor(n / HASH) .. ":" .. floor(w / HASH)
|
|
end
|
|
|
|
local function Trails(c)
|
|
local all = Cfg().trails
|
|
local t = all[c]
|
|
if not t then
|
|
t = { n = {}, w = {}, l = {} }
|
|
all[c] = t
|
|
end
|
|
return t
|
|
end
|
|
|
|
function N:RebuildHash()
|
|
self.hash = {}
|
|
for c, t in pairs(Cfg().trails) do
|
|
local h = {}
|
|
self.hash[c] = h
|
|
for i = 1, getn(t.n) do
|
|
local key = HashKey(t.n[i], t.w[i])
|
|
if not h[key] then h[key] = {} end
|
|
insert(h[key], i)
|
|
end
|
|
end
|
|
end
|
|
|
|
function N:TrailCount()
|
|
local total = 0
|
|
for _, t in pairs(Cfg().trails) do total = total + getn(t.n) end
|
|
return total
|
|
end
|
|
|
|
local function NearestTrail(c, p, radius)
|
|
local h = N.hash[c]
|
|
if not h then return nil end
|
|
local t = Cfg().trails[c]
|
|
local best, bestd
|
|
local cn, cw = floor(p.n / HASH), floor(p.w / HASH)
|
|
for dn = -1, 1 do
|
|
for dw = -1, 1 do
|
|
local list = h[(cn + dn) .. ":" .. (cw + dw)]
|
|
if list then
|
|
for _, i in ipairs(list) do
|
|
local en, ew = t.n[i] - p.n, t.w[i] - p.w
|
|
local d = sqrt(en * en + ew * ew)
|
|
if d <= radius and (not bestd or d < bestd) then
|
|
best, bestd = i, d
|
|
end
|
|
end
|
|
end
|
|
end
|
|
end
|
|
return best
|
|
end
|
|
|
|
local function Link(t, a, b)
|
|
if a == b then return end
|
|
local la = t.l[a]
|
|
for _, v in ipairs(la) do if v == b then return end end
|
|
insert(la, b)
|
|
insert(t.l[b], a)
|
|
end
|
|
|
|
-- remember where you walk
|
|
function N:Record(player, now)
|
|
-- ground height for structures: wherever you stand outside one
|
|
if player.z and not player.taxi and not StructureAt(player) then
|
|
self.groundz = player.z
|
|
end
|
|
|
|
if Cfg().trails_on == "0" or player.taxi or not player.c then
|
|
self.lasttrail = nil
|
|
return
|
|
end
|
|
local last = self.lasttrail
|
|
if last and last.c == player.c and Dist(last, player) < TRAIL_STEP then
|
|
return
|
|
end
|
|
|
|
-- walking through the middle of a learned obstacle proves it was wrong
|
|
local obstacles = Cfg().obstacles
|
|
for i = getn(obstacles), 1, -1 do
|
|
local o = obstacles[i]
|
|
if o.c == player.c and Dist(o, player) < o.r * 0.5 then
|
|
table.remove(obstacles, i)
|
|
end
|
|
end
|
|
|
|
local t = Trails(player.c)
|
|
local index = NearestTrail(player.c, player, TRAIL_SNAP)
|
|
if not index then
|
|
if self:TrailCount() >= TRAIL_CAP then return end
|
|
insert(t.n, player.n)
|
|
insert(t.w, player.w)
|
|
insert(t.l, {})
|
|
index = getn(t.n)
|
|
local h = self.hash[player.c]
|
|
if not h then h = {} self.hash[player.c] = h end
|
|
local key = HashKey(player.n, player.w)
|
|
if not h[key] then h[key] = {} end
|
|
insert(h[key], index)
|
|
end
|
|
|
|
if last and last.c == player.c and last.index and now - last.time < 12
|
|
and Dist(last, player) < TRAIL_BREAK then
|
|
Link(t, last.index, index)
|
|
end
|
|
self.lasttrail = { c = player.c, n = player.n, w = player.w, index = index, time = now }
|
|
end
|
|
|
|
-- stuck detection -------------------------------------------------------------
|
|
|
|
N.history = {}
|
|
N.stuck = 0
|
|
|
|
-- Called every sample while the arrow points somewhere on foot. Returns true
|
|
-- when it has just learned an obstacle.
|
|
--
|
|
-- Running into something in WoW does not stop you dead: you slide along it,
|
|
-- keeping only the part of your movement that runs along the surface. So the
|
|
-- sign of a blocked path is moving, but at well under your usual speed, while
|
|
-- facing where the arrow points. Running straight into something stops you
|
|
-- instead, so "was running, now stopped dead, still facing the arrow" counts
|
|
-- too. Fighting (snares) and the last few yards are ignored. A wrong guess is
|
|
-- cheap: the circle is small, and walking through its middle later deletes it
|
|
-- (see Record).
|
|
function N:Observe(player, aim, goal, now, facing)
|
|
local hist = self.history
|
|
insert(hist, { t = now, n = player.n, w = player.w, c = player.c })
|
|
while hist[1] and now - hist[1].t > 1.05 do
|
|
table.remove(hist, 1)
|
|
end
|
|
local old = hist[1]
|
|
local span = old and (now - old.t) or 0
|
|
local speed = (span > 0 and old.c == player.c) and Dist(old, player) / span or 0
|
|
|
|
-- your usual speed: the fastest you moved lately, slowly forgotten
|
|
local usual = (self.usual or 7) * 0.995
|
|
if speed > usual and speed < 40 then usual = speed end
|
|
if usual < 7 then usual = 7 end
|
|
self.usual = usual
|
|
|
|
-- on a ramp or in a building we know about, turning and climbing is
|
|
-- expected; do not mistake it for a wall
|
|
if StructureAt(player) then
|
|
self.stuck = 0
|
|
return false
|
|
end
|
|
|
|
if Cfg().learn ~= "1" or not aim or not goal or not facing or player.taxi or span < 0.7
|
|
or (UnitAffectingCombat and UnitAffectingCombat("player")) or Dist(player, goal) < 15 then
|
|
self.stuck = 0
|
|
return false
|
|
end
|
|
|
|
local want = atan2(aim.w - player.w, aim.n - player.n)
|
|
local off = abs(want - facing)
|
|
while off > pi do off = abs(off - 2 * pi) end
|
|
|
|
if speed >= 0.8 * usual then
|
|
self.running = now
|
|
end
|
|
local sliding = speed > 0.5 and speed < 0.6 * usual
|
|
local stopped = speed <= 0.5 and self.running and now - self.running < 2.5
|
|
if (sliding or stopped) and off < 0.6 then
|
|
self.stuck = self.stuck + 0.25
|
|
else
|
|
self.stuck = 0
|
|
end
|
|
if self.stuck < 1.25 then
|
|
return false
|
|
end
|
|
self.stuck = 0
|
|
self.running = nil
|
|
|
|
-- you are at its edge: put the centre a little more than one radius ahead
|
|
local d = Dist(player, aim)
|
|
if d < 0.1 then return false end
|
|
local spot = {
|
|
c = player.c,
|
|
n = player.n + (aim.n - player.n) / d * 8,
|
|
w = player.w + (aim.w - player.w) / d * 8,
|
|
r = 6, learned = true,
|
|
}
|
|
-- bumping into the same thing again: it is bigger than we thought
|
|
for _, o in ipairs(Cfg().obstacles) do
|
|
if o.c == spot.c and Dist(o, spot) < o.r + 4 then
|
|
if o.r < 25 then
|
|
o.r = o.r + 3
|
|
o.n = o.n + (spot.n - o.n) * 0.3
|
|
o.w = o.w + (spot.w - o.w) * 0.3
|
|
end
|
|
return true
|
|
end
|
|
end
|
|
if getn(Cfg().obstacles) < 2000 then
|
|
insert(Cfg().obstacles, spot)
|
|
end
|
|
return true
|
|
end
|
|
|
|
-- /smartarrow stuck: you say something is in the way, right where the
|
|
-- arrow points. Same circle the automatic detection would add.
|
|
function N:MarkBlocked(player, aim)
|
|
if not player or not aim or aim.c ~= player.c then return false end
|
|
local d = Dist(player, aim)
|
|
if d < 0.1 then return false end
|
|
local spot = {
|
|
c = player.c,
|
|
n = player.n + (aim.n - player.n) / d * 8,
|
|
w = player.w + (aim.w - player.w) / d * 8,
|
|
r = 7, learned = true,
|
|
}
|
|
for _, o in ipairs(Cfg().obstacles) do
|
|
if o.c == spot.c and Dist(o, spot) < o.r + 4 then
|
|
if o.r < 25 then o.r = o.r + 4 end
|
|
return true
|
|
end
|
|
end
|
|
insert(Cfg().obstacles, spot)
|
|
return true
|
|
end
|
|
|
|
-- background work ---------------------------------------------------------------
|
|
|
|
-- Planning a path round obstacles can take a while on the 1.12 client. It
|
|
-- runs as a job, a little each frame: the planner calls Step() as it goes,
|
|
-- and when the frame's share is used up the job pauses until the next
|
|
-- frame. Outside a job (slash commands, tests) Step() does nothing and the
|
|
-- planner simply runs to the end.
|
|
local STEP_CHUNK = 25 -- units of work between clock checks
|
|
local STEP_MS = 2 -- milliseconds per frame, where there is a clock
|
|
local STEP_UNITS = 400 -- units per frame, where there is none
|
|
|
|
local function Step(units)
|
|
local j = N.slice
|
|
if not j then return end
|
|
j.count = j.count + (units or 1)
|
|
if j.count < j.check then return end
|
|
j.check = j.count + STEP_CHUNK
|
|
if j.clock then
|
|
if j.clock() - j.start < STEP_MS then return end
|
|
elseif j.count < STEP_UNITS then
|
|
return
|
|
end
|
|
coroutine.yield()
|
|
end
|
|
|
|
N.Step = Step -- for graph.lua's search
|
|
|
|
-- start fn as a job (replacing any job still running)
|
|
function N:RunJob(fn)
|
|
self.job = coroutine.create(fn)
|
|
end
|
|
|
|
-- one frame's share of the running job; true while it has more to do
|
|
function N:ResumeJob()
|
|
local co = self.job
|
|
if not co then return false end
|
|
local alive = self:Resume(co)
|
|
if not alive and self.job == co then self.job = nil end
|
|
return alive
|
|
end
|
|
|
|
-- one frame's share of coroutine co; false once it is finished (or failed)
|
|
function N:Resume(co)
|
|
local clock = debugprofilestop
|
|
self.slice = { count = 0, check = STEP_CHUNK, clock = clock, start = clock and clock() or 0 }
|
|
local ok, err = coroutine.resume(co)
|
|
self.slice = nil
|
|
if not ok then
|
|
if not self.joberror and DEFAULT_CHAT_FRAME then
|
|
self.joberror = true
|
|
DEFAULT_CHAT_FRAME:AddMessage("|cff33ffccpfQuest SmartArrow|r: path planning error: " .. tostring(err))
|
|
end
|
|
return false
|
|
end
|
|
return coroutine.status(co) ~= "dead"
|
|
end
|
|
|
|
-- the local planner -----------------------------------------------------------
|
|
|
|
local function EdgeCost(p, q, zone, dp, dq)
|
|
local len = Dist(p, q)
|
|
local d = (dp + dq) / 2
|
|
if len > 60 then
|
|
local mid = { n = (p.n + q.n) / 2, w = (p.w + q.w) / 2 }
|
|
d = (dp + dq + 2 * N:DangerAt(zone, mid)) / 4
|
|
end
|
|
return len * DangerFactor(d)
|
|
end
|
|
|
|
local function PerpDist(p, a, b)
|
|
local dn, dw = b.n - a.n, b.w - a.w
|
|
local len2 = dn * dn + dw * dw
|
|
if len2 == 0 then return Dist(p, a) end
|
|
local t = ((p.n - a.n) * dn + (p.w - a.w) * dw) / len2
|
|
if t < 0 then t = 0 elseif t > 1 then t = 1 end
|
|
local cn, cw = a.n + dn * t - p.n, a.w + dw * t - p.w
|
|
return sqrt(cn * cn + cw * cw)
|
|
end
|
|
|
|
|
|
local function BestDoor(o, a, b)
|
|
local best, bestd
|
|
for _, d in ipairs(o.doors) do
|
|
local cost = Dist(a, d) + Dist(d, b)
|
|
if not bestd or cost < bestd then best, bestd = d, cost end
|
|
end
|
|
return best
|
|
end
|
|
|
|
local function Join(first, rest)
|
|
local out = {}
|
|
for i = 1, getn(first) do insert(out, first[i]) end
|
|
for i = 2, getn(rest) do insert(out, rest[i]) end
|
|
return out
|
|
end
|
|
|
|
function N:Refine(a, b, zone)
|
|
if a.c ~= b.c then return { a, b } end
|
|
|
|
-- getting on or off a structure: through one of its doors. Standing at
|
|
-- ground level in its area (beside it, or stuck inside the trunk) is not
|
|
-- being *on* it: your height against the ground you last stood on outside
|
|
-- tells the two apart. Unknown height counts as up, the safe guess.
|
|
local sa, sb = StructureAt(a), StructureAt(b)
|
|
if sa and a.z and self.groundz and a.z - self.groundz < 6 then
|
|
sa = nil
|
|
end
|
|
if sa ~= sb then
|
|
if sa then
|
|
local door = BestDoor(sa, a, b)
|
|
if door then
|
|
door = { c = door.c, n = door.n, w = door.w }
|
|
local down = self:RefineDirect(a, door, zone)
|
|
if sb then
|
|
local door2 = BestDoor(sb, door, b)
|
|
if door2 then
|
|
door2 = { c = door2.c, n = door2.n, w = door2.w }
|
|
return Join(Join(down, self:RefineDirect(door, door2, zone)), { door2, b })
|
|
end
|
|
end
|
|
return Join(down, self:RefineDirect(door, b, zone))
|
|
end
|
|
else
|
|
local door = BestDoor(sb, a, b)
|
|
if door then
|
|
door = { c = door.c, n = door.n, w = door.w }
|
|
return Join(self:RefineDirect(a, door, zone), { door, b })
|
|
end
|
|
end
|
|
end
|
|
return self:RefineDirect(a, b, zone)
|
|
end
|
|
|
|
-- the one note a structure needs: how to get on it, or off it
|
|
function N:StructureNote(target, player)
|
|
if not target or not player or target.c ~= player.c then return nil end
|
|
local st, sp = StructureAt(target), StructureAt(player)
|
|
local ground = sp and player.z and self.groundz and player.z - self.groundz < 6
|
|
if ground then
|
|
-- beside it, or inside the trunk at ground level
|
|
if st == sp then return nil end
|
|
if Dist(sp, player) < sp.r then
|
|
return "Inside " .. (sp.name or "it") .. ": leave the way you came in"
|
|
end
|
|
sp = nil
|
|
end
|
|
if st and st ~= sp then return st.up end
|
|
if sp and sp ~= st then return sp.down end
|
|
return nil
|
|
end
|
|
|
|
function N:RefineDirect(a, b, zone)
|
|
if a.c ~= b.c then return { a, b } end
|
|
local len = Dist(a, b)
|
|
if len < 12 then return { a, b } end
|
|
|
|
local margin = len * 0.35
|
|
if margin < 60 then margin = 60 end
|
|
if margin > 400 then margin = 400 end
|
|
local minN, maxN = math.min(a.n, b.n) - margin, math.max(a.n, b.n) + margin
|
|
local minW, maxW = math.min(a.w, b.w) - margin, math.max(a.w, b.w) + margin
|
|
|
|
-- obstacles in the corridor. One that holds b is a building you are
|
|
-- going into, so it does not count. One that holds a is one you are stuck
|
|
-- inside: leaving it straight through the wall is allowed but expensive,
|
|
-- so the way you came in (your recorded trail) wins whenever there is one.
|
|
local obs, escape = {}, {}
|
|
EachObstacle(function(o)
|
|
if o.c == a.c and o.n + o.r >= minN and o.n - o.r <= maxN
|
|
and o.w + o.r >= minW and o.w - o.r <= maxW and not Within(o, b) then
|
|
if Within(o, a) then
|
|
insert(escape, o)
|
|
else
|
|
insert(obs, o)
|
|
end
|
|
end
|
|
end)
|
|
|
|
-- trail points in the corridor: your own walked trails (store 1) and the
|
|
-- built-in roads from NPC patrols (store 2)
|
|
local trailpts = {}
|
|
local stores = {
|
|
{ t = Cfg().trails[a.c], h = self.hash[a.c] },
|
|
{ t = self.roads[a.c], h = self.roadhash[a.c] },
|
|
}
|
|
for st = 1, 2 do
|
|
local t, h = stores[st].t, stores[st].h
|
|
if t and h then
|
|
for cn = floor(minN / HASH), floor(maxN / HASH) do
|
|
for cw = floor(minW / HASH), floor(maxW / HASH) do
|
|
local list = h[cn .. ":" .. cw]
|
|
Step()
|
|
if list then
|
|
for _, i in ipairs(list) do
|
|
Step()
|
|
local p = { n = t.n[i], w = t.w[i], c = a.c, tid = i, st = st }
|
|
local pd = PerpDist(p, a, b)
|
|
if pd <= margin then
|
|
p.pd = pd
|
|
insert(trailpts, p)
|
|
end
|
|
end
|
|
end
|
|
end
|
|
end
|
|
end
|
|
end
|
|
if getn(trailpts) > MAX_TRAIL_NODES then
|
|
table.sort(trailpts, function(x, y) return x.pd < y.pd end)
|
|
for i = getn(trailpts), MAX_TRAIL_NODES + 1, -1 do table.remove(trailpts, i) end
|
|
end
|
|
|
|
-- straight line already fine?
|
|
local hasdanger = self.grid and self.grid[zone]
|
|
if getn(obs) == 0 and getn(escape) == 0 and getn(trailpts) == 0 then
|
|
if not hasdanger then return { a, b } end
|
|
local worst, steps = 0, floor(len / 25) + 1
|
|
for i = 0, steps do
|
|
local f = i / steps
|
|
local d = self:DangerAt(zone, { n = a.n + (b.n - a.n) * f, w = a.w + (b.w - a.w) * f })
|
|
if d > worst then worst = d end
|
|
end
|
|
if worst < 0.5 then return { a, b } end
|
|
end
|
|
|
|
-- local graph
|
|
local nodes = { a, b }
|
|
local rings = {}
|
|
for _, o in ipairs(obs) do insert(rings, o) end
|
|
for _, o in ipairs(escape) do insert(rings, o) end
|
|
for _, o in ipairs(rings) do
|
|
for k = 0, RING - 1 do
|
|
local ang = k * 2 * pi / RING
|
|
local p = { c = a.c, n = o.n + cos(ang) * (o.r + RING_PAD), w = o.w + sin(ang) * (o.r + RING_PAD), ring = true }
|
|
if not InsideAny(p, obs) then insert(nodes, p) end
|
|
end
|
|
end
|
|
for _, p in ipairs(trailpts) do
|
|
Step()
|
|
if not InsideAny(p, obs) then insert(nodes, p) end
|
|
end
|
|
local spacing = len / 8
|
|
if spacing < 35 then spacing = 35 end
|
|
if spacing > 250 then spacing = 250 end
|
|
if hasdanger then
|
|
local added = 0
|
|
local n = minN
|
|
while n <= maxN and added < MAX_LATTICE do
|
|
local w = minW
|
|
while w <= maxW and added < MAX_LATTICE do
|
|
local p = { c = a.c, n = n, w = w }
|
|
if PerpDist(p, a, b) <= margin and not InsideAny(p, obs) then
|
|
insert(nodes, p)
|
|
added = added + 1
|
|
end
|
|
Step()
|
|
w = w + spacing
|
|
end
|
|
n = n + spacing
|
|
end
|
|
end
|
|
|
|
local count = getn(nodes)
|
|
local danger = {}
|
|
local tindex = { {}, {} }
|
|
for i = 1, count do
|
|
Step()
|
|
danger[i] = hasdanger and self:DangerAt(zone, nodes[i]) or 0
|
|
if nodes[i].tid then tindex[nodes[i].st][nodes[i].tid] = i end
|
|
end
|
|
|
|
-- edges: the start, the end and the points around obstacles see each
|
|
-- other at any range (a visibility graph: the shortest way round a circle
|
|
-- runs along such lines); trail and lattice points only link to neighbours
|
|
-- within reach. No edge may cross an obstacle. Recorded trail links are
|
|
-- added as well: walked, so passable by definition.
|
|
local reach = spacing * 1.6
|
|
if reach < 80 then reach = 80 end
|
|
local adj = {}
|
|
for i = 1, count do adj[i] = {} end
|
|
for i = 1, count do
|
|
local p = nodes[i]
|
|
for j = i + 1, count do
|
|
Step()
|
|
local q = nodes[j]
|
|
local d = Dist(p, q)
|
|
local far = (i <= 2 or p.ring) and (j <= 2 or q.ring)
|
|
if (d <= reach or far) and SegmentClear(p, q, obs) then
|
|
local cost = EdgeCost(p, q, zone, danger[i], danger[j])
|
|
if getn(escape) > 0 and not SegmentClear(p, q, escape) then
|
|
cost = cost * 6 -- through the wall of what you are stuck in
|
|
end
|
|
insert(adj[i], j) insert(adj[i], cost)
|
|
insert(adj[j], i) insert(adj[j], cost)
|
|
end
|
|
end
|
|
local store = p.tid and stores[p.st].t
|
|
if store then
|
|
for _, other in ipairs(store.l[p.tid] or {}) do
|
|
local j = tindex[p.st][other]
|
|
if j and j > i then
|
|
local cost = EdgeCost(p, nodes[j], zone, danger[i], danger[j]) * TRAIL_FACTOR
|
|
insert(adj[i], j) insert(adj[i], cost)
|
|
insert(adj[j], i) insert(adj[j], cost)
|
|
end
|
|
end
|
|
end
|
|
end
|
|
|
|
-- Dijkstra from a (1) to b (2)
|
|
local dist, prev, done = {}, {}, {}
|
|
for i = 1, count do dist[i] = 1e30 end
|
|
dist[1] = 0
|
|
for _ = 1, count do
|
|
local u, best = nil, 1e30
|
|
for i = 1, count do
|
|
if not done[i] and dist[i] < best then u, best = i, dist[i] end
|
|
end
|
|
if not u or u == 2 then break end
|
|
Step(floor(count / 20) + 1)
|
|
done[u] = true
|
|
local list = adj[u]
|
|
for k = 1, getn(list), 2 do
|
|
local v, cost = list[k], list[k + 1]
|
|
if not done[v] and best + cost < dist[v] then
|
|
dist[v] = best + cost
|
|
prev[v] = u
|
|
end
|
|
end
|
|
end
|
|
if dist[2] >= 1e30 then
|
|
return { a, b }
|
|
end
|
|
|
|
local path = {}
|
|
local i = 2
|
|
while i do
|
|
insert(path, 1, nodes[i])
|
|
i = prev[i]
|
|
end
|
|
|
|
-- pull the string: drop corners the path does not need
|
|
local out = { path[1] }
|
|
local k = 1
|
|
local total = getn(path)
|
|
while k < total do
|
|
local jump = k + 1
|
|
for j = total, k + 2, -1 do
|
|
Step(j - k)
|
|
local direct = EdgeCost(path[k], path[j], zone, self:DangerAt(zone, path[k]), self:DangerAt(zone, path[j]))
|
|
if getn(escape) > 0 and not SegmentClear(path[k], path[j], escape) then
|
|
direct = direct * 6
|
|
end
|
|
local along = 0
|
|
for s = k, j - 1 do
|
|
local f = EdgeCost(path[s], path[s + 1], zone, self:DangerAt(zone, path[s]), self:DangerAt(zone, path[s + 1]))
|
|
if path[s].tid and path[s + 1].tid then
|
|
f = f * TRAIL_FACTOR
|
|
elseif getn(escape) > 0 and not SegmentClear(path[s], path[s + 1], escape) then
|
|
f = f * 6
|
|
end
|
|
along = along + f
|
|
end
|
|
if direct <= along * 1.03 and SegmentClear(path[k], path[j], obs) then
|
|
jump = j
|
|
break
|
|
end
|
|
end
|
|
insert(out, path[jump])
|
|
k = jump
|
|
end
|
|
return out
|
|
end
|
|
|
|
-- following a polyline --------------------------------------------------------
|
|
|
|
-- where along the polyline the player is, and the point `ahead` yards on
|
|
-- from there: aiming at it makes the arrow lead around corners
|
|
function N:Carrot(poly, player, ahead)
|
|
local count = getn(poly)
|
|
if count < 2 then return poly[1], 0, 1 end
|
|
local bestd, bestseg, bestt
|
|
for i = 1, count - 1 do
|
|
local a, b = poly[i], poly[i + 1]
|
|
local dn, dw = b.n - a.n, b.w - a.w
|
|
local len2 = dn * dn + dw * dw
|
|
local t = 0
|
|
if len2 > 0 then
|
|
t = ((player.n - a.n) * dn + (player.w - a.w) * dw) / len2
|
|
if t < 0 then t = 0 elseif t > 1 then t = 1 end
|
|
end
|
|
local cn, cw = a.n + dn * t - player.n, a.w + dw * t - player.w
|
|
local d = cn * cn + cw * cw
|
|
if not bestd or d < bestd then bestd, bestseg, bestt = d, i, t end
|
|
end
|
|
|
|
-- remaining length from the projection to the end
|
|
local a, b = poly[bestseg], poly[bestseg + 1]
|
|
local seglen = Dist(a, b)
|
|
local remaining = seglen * (1 - bestt)
|
|
for i = bestseg + 1, count - 1 do
|
|
remaining = remaining + Dist(poly[i], poly[i + 1])
|
|
end
|
|
|
|
-- walk `ahead` yards along the line
|
|
local left = ahead
|
|
local i, t = bestseg, bestt
|
|
while i < count do
|
|
local p, q = poly[i], poly[i + 1]
|
|
local l = Dist(p, q)
|
|
local avail = l * (1 - t)
|
|
if avail >= left and l > 0 then
|
|
local f = t + left / l
|
|
return { c = p.c, n = p.n + (q.n - p.n) * f, w = p.w + (q.w - p.w) * f }, remaining + sqrt(bestd), bestseg
|
|
end
|
|
left = left - avail
|
|
i, t = i + 1, 0
|
|
end
|
|
return poly[count], remaining + sqrt(bestd), bestseg
|
|
end
|
|
|
|
-- how far the player is from the polyline
|
|
function N:OffPath(poly, player)
|
|
local best = 1e30
|
|
for i = 1, getn(poly) - 1 do
|
|
local d = PerpDist(player, poly[i], poly[i + 1])
|
|
if d < best then best = d end
|
|
end
|
|
return best
|
|
end
|
|
|
|
-- remembered routes -------------------------------------------------------------
|
|
|
|
-- Every walking stretch you finish is remembered as the way you actually
|
|
-- walked it, simplified to a few corners. The next time you walk between
|
|
-- the same two places, in either direction (there and back for a quest),
|
|
-- that route is used as it is: no planning, and the dotted line does not
|
|
-- change under you. A remembered route that gets you stuck is forgotten.
|
|
local MEM_MAX = 400 -- routes kept (least recently used go first)
|
|
local MEM_BUCKET = 60 -- yards: index cell size for route ends
|
|
local MEM_END = 15 -- yards: how close a route's end must be to the goal
|
|
local MEM_JOIN = 30 -- yards: how far off the route you may start
|
|
local MEM_MIN = 40 -- yards: shorter stretches are not worth keeping
|
|
local MEM_SIMPLIFY = 3 -- yards: how far the kept corners may stray from your walk
|
|
|
|
local function Routes()
|
|
local cfg = Cfg()
|
|
cfg.routes = cfg.routes or {}
|
|
return cfg.routes
|
|
end
|
|
|
|
local function MemKey(c, n, w)
|
|
return c .. ":" .. floor(n / MEM_BUCKET) .. ":" .. floor(w / MEM_BUCKET)
|
|
end
|
|
|
|
function N:MemoryIndex()
|
|
if self.memindex then return self.memindex end
|
|
local index = {}
|
|
for _, r in ipairs(Routes()) do
|
|
local p, last = r.p, getn(r.p) - 1
|
|
for _, k in ipairs({ MemKey(r.c, p[1], p[2]), MemKey(r.c, p[last], p[last + 1]) }) do
|
|
index[k] = index[k] or {}
|
|
insert(index[k], r)
|
|
end
|
|
end
|
|
self.memindex = index
|
|
return index
|
|
end
|
|
|
|
function N:RouteCount()
|
|
return getn(Routes())
|
|
end
|
|
|
|
function N:ForgetRoutes()
|
|
Cfg().routes = {}
|
|
self.memindex = nil
|
|
end
|
|
|
|
function N:ForgetRoute(r)
|
|
local routes = Routes()
|
|
for i = getn(routes), 1, -1 do
|
|
if routes[i] == r then table.remove(routes, i) end
|
|
end
|
|
self.memindex = nil
|
|
end
|
|
|
|
-- the routes with an end near point p
|
|
local function NearEnds(index, p)
|
|
local found, seen = {}, {}
|
|
local cn, cw = floor(p.n / MEM_BUCKET), floor(p.w / MEM_BUCKET)
|
|
for dn = -1, 1 do
|
|
for dw = -1, 1 do
|
|
for _, r in ipairs(index[p.c .. ":" .. (cn + dn) .. ":" .. (cw + dw)] or {}) do
|
|
if not seen[r] then seen[r] = true insert(found, r) end
|
|
end
|
|
end
|
|
end
|
|
return found
|
|
end
|
|
|
|
-- the corners of route r as points, ordered so the route ends nearest b
|
|
local function Oriented(r, b)
|
|
local p, count = r.p, getn(r.p) / 2
|
|
local pts = {}
|
|
for i = 1, count do pts[i] = { c = r.c, n = p[i * 2 - 1], w = p[i * 2] } end
|
|
if Dist(pts[1], b) < Dist(pts[count], b) then
|
|
local rev = {}
|
|
for i = count, 1, -1 do insert(rev, pts[i]) end
|
|
pts = rev
|
|
end
|
|
return pts
|
|
end
|
|
|
|
-- A remembered way from a to b: the rest of a remembered route, from the
|
|
-- spot on it nearest to a, when that is close and nothing is in the way.
|
|
function N:Recall(a, b)
|
|
if not a or not b or a.c ~= b.c then return nil end
|
|
local best, bestpoly, bestcost
|
|
for _, r in ipairs(NearEnds(self:MemoryIndex(), b)) do
|
|
if r.c == b.c then
|
|
local pts = Oriented(r, b)
|
|
local count = getn(pts)
|
|
if Dist(pts[count], b) <= MEM_END then
|
|
-- the nearest spot on the route to a
|
|
local bd, bs, bt
|
|
for i = 1, count - 1 do
|
|
local p, q = pts[i], pts[i + 1]
|
|
local dn, dw = q.n - p.n, q.w - p.w
|
|
local len2 = dn * dn + dw * dw
|
|
local t = len2 > 0 and ((a.n - p.n) * dn + (a.w - p.w) * dw) / len2 or 0
|
|
if t < 0 then t = 0 elseif t > 1 then t = 1 end
|
|
local x = { n = p.n + dn * t, w = p.w + dw * t }
|
|
local d = Dist(a, x)
|
|
if not bd or d < bd then bd, bs, bt = d, i, t end
|
|
end
|
|
if bd and bd <= MEM_JOIN then
|
|
local p, q = pts[bs], pts[bs + 1]
|
|
local join = { c = a.c, n = p.n + (q.n - p.n) * bt, w = p.w + (q.w - p.w) * bt }
|
|
local poly = { a }
|
|
if bd > 2 then insert(poly, join) end
|
|
for i = bs + 1, count - 1 do insert(poly, pts[i]) end
|
|
insert(poly, b)
|
|
-- the way onto the route, and the last bit to the goal, must be clear
|
|
local obs = {}
|
|
EachObstacle(function(o)
|
|
if o.c == a.c and (Dist(o, a) < o.r + MEM_JOIN + 5 or Dist(o, b) < o.r + MEM_END + 5)
|
|
and not Within(o, b) and not Within(o, a) then insert(obs, o) end
|
|
end)
|
|
local n = getn(poly)
|
|
if SegmentClear(poly[1], poly[2], obs) and SegmentClear(poly[n - 1], poly[n], obs) then
|
|
local cost = bd
|
|
for i = 1, n - 1 do cost = cost + Dist(poly[i], poly[i + 1]) end
|
|
if not bestcost or cost < bestcost then best, bestpoly, bestcost = r, poly, cost end
|
|
end
|
|
end
|
|
end
|
|
end
|
|
end
|
|
if best then best.t = time and time() or 0 end
|
|
return bestpoly, best
|
|
end
|
|
|
|
-- Douglas-Peucker: keep the corners that matter
|
|
local function Simplify(pts, first, last, out)
|
|
local p, q = pts[first], pts[last]
|
|
local worst, at = 0, nil
|
|
for i = first + 1, last - 1 do
|
|
local d = PerpDist(pts[i], p, q)
|
|
if d > worst then worst, at = d, i end
|
|
end
|
|
if at and worst > MEM_SIMPLIFY then
|
|
Simplify(pts, first, at, out)
|
|
Simplify(pts, at, last, out)
|
|
else
|
|
insert(out, q)
|
|
end
|
|
end
|
|
|
|
-- remember the walk `trace` (points from start to goal) as the way to goal
|
|
function N:Remember(trace, goal)
|
|
local count = getn(trace)
|
|
if count < 2 or not goal or trace[1].c ~= goal.c then return false end
|
|
local start = trace[1]
|
|
local straight = Dist(start, goal)
|
|
if straight < MEM_MIN then return false end
|
|
local walked = 0
|
|
for i = 1, count - 1 do walked = walked + Dist(trace[i], trace[i + 1]) end
|
|
walked = walked + Dist(trace[count], goal)
|
|
-- a long detour (a fight, a chase, a wrong turn) is not a route
|
|
if walked > straight * 2.2 and walked > straight + 150 then return false end
|
|
|
|
local pts = {}
|
|
for i = 1, count do pts[i] = trace[i] end
|
|
insert(pts, { c = goal.c, n = goal.n, w = goal.w })
|
|
local kept = { pts[1] }
|
|
Simplify(pts, 1, getn(pts), kept)
|
|
local flat = {}
|
|
for _, p in ipairs(kept) do
|
|
insert(flat, floor(p.n * 10 + 0.5) / 10)
|
|
insert(flat, floor(p.w * 10 + 0.5) / 10)
|
|
end
|
|
|
|
-- replaces a route between the same two places
|
|
local routes = Routes()
|
|
for i = getn(routes), 1, -1 do
|
|
local r = routes[i]
|
|
local last = getn(r.p) - 1
|
|
if r.c == goal.c then
|
|
local s = { n = r.p[1], w = r.p[2] }
|
|
local e = { n = r.p[last], w = r.p[last + 1] }
|
|
if (Dist(s, start) < MEM_JOIN and Dist(e, goal) < MEM_END) or (Dist(e, start) < MEM_JOIN and Dist(s, goal) < MEM_END) then
|
|
table.remove(routes, i)
|
|
end
|
|
end
|
|
end
|
|
insert(routes, { c = goal.c, p = flat, t = time and time() or 0 })
|
|
if getn(routes) > MEM_MAX then
|
|
table.sort(routes, function(x, y) return (x.t or 0) > (y.t or 0) end)
|
|
for i = getn(routes), MEM_MAX + 1, -1 do table.remove(routes, i) end
|
|
end
|
|
self.memindex = nil
|
|
return true
|
|
end
|
|
|
|
-- The aim point for the arrow: as far ahead as possible (up to 12 yards)
|
|
-- without the straight line to it clipping an obstacle, so cutting a corner
|
|
-- never takes you into the tree you are walking round.
|
|
function N:Aim(poly, player)
|
|
local near = {}
|
|
EachObstacle(function(o)
|
|
if o.c == player.c and Dist(o, player) < o.r + 60 and not Within(o, player) then
|
|
insert(near, o)
|
|
end
|
|
end)
|
|
if getn(near) == 0 then
|
|
return self:Carrot(poly, player, 12)
|
|
end
|
|
|
|
local padded = {}
|
|
for i = 1, getn(near) do
|
|
local o = near[i]
|
|
padded[i] = { c = o.c, n = o.n, w = o.w, r = o.r + 2 }
|
|
end
|
|
local ahead = { 12, 7, 3 }
|
|
local carrot, remaining
|
|
for i = 1, 3 do
|
|
carrot, remaining = self:Carrot(poly, player, ahead[i])
|
|
if SegmentClear(player, carrot, padded) then
|
|
return carrot, remaining
|
|
end
|
|
end
|
|
|
|
-- every short aim clips something: take the usual aim point and push it out
|
|
-- of each obstacle to a safe distance, so the arrow curves round the edge
|
|
carrot, remaining = self:Carrot(poly, player, 12)
|
|
local p = { c = carrot.c, n = carrot.n, w = carrot.w }
|
|
for i = 1, getn(near) do
|
|
local o = near[i]
|
|
local d = Dist(p, o)
|
|
local safe = o.r + 6
|
|
if d < safe then
|
|
if d < 0.01 then
|
|
p.n, p.w = o.n + (player.n - o.n), o.w + (player.w - o.w)
|
|
d = Dist(p, o)
|
|
end
|
|
p.n = o.n + (p.n - o.n) / d * safe
|
|
p.w = o.w + (p.w - o.w) / d * safe
|
|
end
|
|
end
|
|
return p, remaining
|
|
end
|
|
|
|
-- driver for the danger build -------------------------------------------------
|
|
|
|
N:SetScript("OnUpdate", function()
|
|
if this.builder then
|
|
local ok = coroutine.resume(this.builder)
|
|
if not ok or coroutine.status(this.builder) == "dead" then
|
|
this.builder = nil
|
|
N.dangercache = {}
|
|
end
|
|
elseif this.roadbuilder then
|
|
local ok = coroutine.resume(this.roadbuilder)
|
|
if not ok or coroutine.status(this.roadbuilder) == "dead" then
|
|
this.roadbuilder = nil
|
|
end
|
|
end
|
|
end)
|
|
|
|
-- the built-in roads (data/roads.lua), turned into world-space trail points
|
|
-- once per login, a few stretches per frame
|
|
function N:StartRoadBuild()
|
|
if not (pfQuestSmartArrowData and pfQuestSmartArrowData.roads) then return end
|
|
self.roads, self.roadhash = {}, {}
|
|
self.roadbuilder = coroutine.create(function()
|
|
local work = 0
|
|
for zone, list in pairs(pfQuestSmartArrowData.roads) do
|
|
local tr = N:Transform(zone)
|
|
if tr then
|
|
local store = N.roads[tr.c]
|
|
if not store then store = { n = {}, w = {}, l = {} } N.roads[tr.c] = store end
|
|
local hash = N.roadhash[tr.c]
|
|
if not hash then hash = {} N.roadhash[tr.c] = hash end
|
|
for _, line in ipairs(list) do
|
|
local prev
|
|
for x, y in string.gfind(line, "([%d%.]+),([%d%.]+)") do
|
|
local n = tr.n0 + tonumber(y) / 100 * tr.dn
|
|
local w = tr.w0 + tonumber(x) / 100 * tr.dw
|
|
-- reuse a road point within 4 yards, so crossing patrols join up
|
|
local index
|
|
local key = HashKey(n, w)
|
|
for _, i in ipairs(hash[key] or {}) do
|
|
local dn, dw = store.n[i] - n, store.w[i] - w
|
|
if dn * dn + dw * dw < 16 then index = i break end
|
|
end
|
|
if not index then
|
|
insert(store.n, n) insert(store.w, w) insert(store.l, {})
|
|
index = getn(store.n)
|
|
if not hash[key] then hash[key] = {} end
|
|
insert(hash[key], index)
|
|
end
|
|
if prev then Link(store, prev, index) end
|
|
prev = index
|
|
end
|
|
work = work + 1
|
|
if work >= 20 then work = 0 coroutine.yield() end
|
|
end
|
|
end
|
|
end
|
|
end)
|
|
end
|
|
|
|
function N:RoadCount()
|
|
local total = 0
|
|
for _, t in pairs(self.roads) do total = total + getn(t.n) end
|
|
return total
|
|
end
|
|
|
|
function N:Init()
|
|
local cfg = Cfg()
|
|
cfg.obstacles = cfg.obstacles or {}
|
|
cfg.trails = cfg.trails or {}
|
|
if cfg.safety == nil then cfg.safety = 1 end
|
|
if cfg.trails_on == nil then cfg.trails_on = "1" end
|
|
self:ResolveObstacles()
|
|
self:RebuildHash()
|
|
self:StartDangerBuild()
|
|
self:StartRoadBuild()
|
|
end
|