1299 lines
52 KiB
Python
1299 lines
52 KiB
Python
#!/usr/bin/env python3
|
|
# pfQuest SmartArrow: waypoint baker
|
|
# 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.
|
|
#
|
|
# This program is distributed in the hope that it will be useful,
|
|
# but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
# GNU General Public License for more details.
|
|
#
|
|
# You should have received a copy of the GNU General Public License
|
|
# along with this program. If not, see <https://www.gnu.org/licenses/>.
|
|
"""
|
|
Builds SmartArrow's waypoint network from a navmesh you built with
|
|
bake_navmesh.py, so that the arrow can plan good walking paths without the
|
|
navmesh itself.
|
|
|
|
python bake_waypoints.py [PATH/TO/pfQuest-SmartArrow-Navmesh]
|
|
|
|
It writes data/waypoints.lua into SmartArrow. Waypoints sit along the roads
|
|
and in the open middle of every walkable area, on every level (caves, ramps,
|
|
building floors), and two waypoints are joined only where the navmesh shows
|
|
you can walk straight from one to the other.
|
|
"""
|
|
|
|
import argparse
|
|
import math
|
|
import os
|
|
import re
|
|
import sys
|
|
import time
|
|
from collections import deque
|
|
|
|
CELL = 4.0
|
|
BLOCK = 64
|
|
TILE = 8 # cells (32 yards): one waypoint for every piece of ground in a square this size
|
|
STRAIGHT = 110.0 # yards: waypoints this close are joined when the straight walk between is clean
|
|
SECTORS = 16 # ... the nearest and the farthest in each of this many directions
|
|
SPOT = 30.0 # yards: spawns closer than this make one area of interest
|
|
TO_ROAD = 300.0 # yards: how far an area of interest looks for a road to join
|
|
NEIGHBOURS = 3 # areas of interest each one is joined to
|
|
TO_NEIGHBOUR = 160.0
|
|
MERGE = 6.0 # yards: a corner this close to a waypoint on its level reuses it
|
|
COVER = 75.0 # (sight lines are measured up to 80 yards)
|
|
JOIN = 170.0
|
|
ROAD_STEP = 40.0 # yards between waypoints along a road
|
|
REDUNDANT = 1.02 # a join is dropped when going via a shared neighbour is no longer than this
|
|
SOLID_PAD = 3.0
|
|
REPAIR_REACH = 3.0 * COVER
|
|
SIGHT_DIRS = 16 # directions in which each waypoint records how far it sees
|
|
CLEAR = 4 # cells (16 yards) within which a wall, tree or drop makes ground dearer
|
|
WALL_COST = [2.6, 1.7, 1.3, 1.1, 1.0] # by cells of room: right beside it ... in the open
|
|
SIGHT_DIST = [0, 5, 10, 20, 30, 50, 80, 120, 160] # yards a sight step stands for
|
|
SLOPE_CELLS = 8 # steep cells joined together that make a slope you cannot climb
|
|
SIGHT_STEP = 10.0 # ... in steps of this many yards, up to 8 steps
|
|
MAX_LEVELS = 8
|
|
|
|
DI = (0, 1, 0, -1) # directions as the navmesh stores them: +west, +north, -west, -north
|
|
DJ = (1, 0, -1, 0)
|
|
BACK = (2, 3, 0, 1)
|
|
|
|
ALPHABET = ''.join(chr(c) for c in range(35, 127) if c != 92)
|
|
DEC = {c: i for i, c in enumerate(ALPHABET)}
|
|
|
|
|
|
def enc(v):
|
|
return ALPHABET[v]
|
|
|
|
|
|
def num(n, width):
|
|
out = []
|
|
for _ in range(width):
|
|
out.append(ALPHABET[n % 91])
|
|
n //= 91
|
|
assert n == 0
|
|
return ''.join(reversed(out))
|
|
|
|
|
|
# --------------------------------------------------------------- the navmesh
|
|
|
|
class Grid:
|
|
"""The navmesh add-on's walk grid, decoded block by block (as navmesh.lua)."""
|
|
|
|
def __init__(self, blocks):
|
|
self.raw = blocks
|
|
self.cache = {}
|
|
|
|
def block(self, bi, bj):
|
|
key = (bi + 512) * 1024 + (bj + 512)
|
|
b = self.cache.get(key)
|
|
if b is None:
|
|
s = self.raw.get(key)
|
|
b = self.decode(s) if s else False
|
|
if len(self.cache) > 4000:
|
|
self.cache.clear()
|
|
self.cache[key] = b
|
|
return b
|
|
|
|
@staticmethod
|
|
def decode(s):
|
|
p1 = s.index('!')
|
|
p2 = s.index('!', p1 + 1)
|
|
codes = bytearray()
|
|
pos = 0
|
|
while pos < p1:
|
|
sym = DEC[s[pos]]
|
|
v, k = sym // 10, sym % 10
|
|
if k < 9:
|
|
run = k + 1
|
|
pos += 1
|
|
else:
|
|
run = 10 + DEC[s[pos + 1]] * 91 + DEC[s[pos + 2]]
|
|
pos += 3
|
|
codes.extend(bytes([v]) * run)
|
|
exc = set()
|
|
pos = p1 + 1
|
|
while pos < p2:
|
|
exc.add(DEC[s[pos]] * 91 + DEC[s[pos + 1]])
|
|
pos += 2
|
|
cx = {}
|
|
pos = p2 + 1
|
|
while pos < len(s):
|
|
idx = DEC[s[pos]] * 91 + DEC[s[pos + 1]]
|
|
count = DEC[s[pos + 2]]
|
|
pos += 3
|
|
hs, cls, links = [], [], [[], [], [], []]
|
|
for _ in range(count):
|
|
hs.append((DEC[s[pos]] * 91 + DEC[s[pos + 1]]) / 2.0 - 2048)
|
|
cls.append(DEC[s[pos + 2]])
|
|
v = DEC[s[pos + 3]]
|
|
if v == 90:
|
|
for d in range(4):
|
|
links[d].append(DEC[s[pos + 4 + d]])
|
|
pos += 8
|
|
else:
|
|
for d in range(4):
|
|
links[d].append(v % 3)
|
|
v //= 3
|
|
pos += 4
|
|
cx[idx] = (count, hs, cls, links)
|
|
return (bytes(codes), exc, cx)
|
|
|
|
def cell(self, i, j):
|
|
bi, bj = i // BLOCK, j // BLOCK
|
|
b = self.block(bi, bj)
|
|
if not b:
|
|
return 0, None, 0, None
|
|
idx = (i - bi * BLOCK) * BLOCK + (j - bj * BLOCK)
|
|
code = b[0][idx]
|
|
if code == 4:
|
|
return 4, b, idx, b[2].get(idx)
|
|
return code, b, idx, None
|
|
|
|
def count(self, i, j):
|
|
code, _, _, rec = self.cell(i, j)
|
|
if code == 0:
|
|
return 0
|
|
return rec[0] if rec else 1
|
|
|
|
def surface(self, i, j, s):
|
|
"""class, height (None for single-level cells)"""
|
|
code, _, _, rec = self.cell(i, j)
|
|
if code == 0:
|
|
return None, None
|
|
if rec:
|
|
return rec[2][s], rec[1][s]
|
|
return code, None
|
|
|
|
def links(self, i, j, s, d):
|
|
"""surfaces of the neighbour in direction d that surface s walks onto"""
|
|
ca, ba, ia, ra = self.cell(i, j)
|
|
if ca == 0:
|
|
return ()
|
|
ni, nj = i + DI[d], j + DJ[d]
|
|
cb, bb, ib, rb = self.cell(ni, nj)
|
|
if cb == 0:
|
|
return ()
|
|
if ra:
|
|
t = ra[3][d][s] if s < ra[0] else 0
|
|
return (t - 1,) if t > 0 else ()
|
|
if rb:
|
|
back = rb[3][BACK[d]]
|
|
return tuple(k for k in range(rb[0]) if back[k] == 1)
|
|
if d == 0 and ia * 2 in ba[1]:
|
|
return ()
|
|
if d == 1 and ia * 2 + 1 in ba[1]:
|
|
return ()
|
|
if d == 2 and ib * 2 in bb[1]:
|
|
return ()
|
|
if d == 3 and ib * 2 + 1 in bb[1]:
|
|
return ()
|
|
return (0,)
|
|
|
|
|
|
def load_navmesh(folder):
|
|
head = open(os.path.join(folder, 'Navmesh.lua'), encoding='ascii').read()
|
|
m = re.search(r'version = (\d+), cell = (\d+), block = (\d+)', head)
|
|
if not m or int(m.group(2)) != CELL or int(m.group(3)) != BLOCK:
|
|
raise SystemExit('%s does not look like a SmartArrow navmesh' % folder)
|
|
maps = {}
|
|
for name in sorted(os.listdir(folder)):
|
|
mm = re.match(r'Navmesh(\d+)_\d+\.lua$', name)
|
|
if not mm:
|
|
continue
|
|
blocks = maps.setdefault(int(mm.group(1)), {})
|
|
for line in open(os.path.join(folder, name), encoding='ascii'):
|
|
lm = re.match(r'D\[(\d+)\]="(.*)"$', line.rstrip('\n'))
|
|
if lm:
|
|
blocks[int(lm.group(1))] = lm.group(2)
|
|
return int(m.group(1)), maps
|
|
|
|
|
|
# ---------------------------------------------------------- the addon's data
|
|
|
|
def lua_text(addon, rel):
|
|
path = os.path.join(addon, rel)
|
|
return open(path, encoding='utf-8', errors='replace').read() if os.path.exists(path) else ''
|
|
|
|
|
|
def load_zones(addon):
|
|
zones = {}
|
|
for m in re.finditer(r'\[(\d+)\] = \{ c = (\d+), l = ([-\d.]+), t = ([-\d.]+), w = ([\d.]+), h = ([\d.]+)',
|
|
lua_text(addon, 'data/zones.lua')):
|
|
zones[int(m.group(1))] = tuple(float(x) for x in m.groups()[1:])
|
|
return zones
|
|
|
|
|
|
def to_world(zones, zone, x, y):
|
|
r = zones.get(zone)
|
|
if not r:
|
|
return None
|
|
c, l, t, w, h = r
|
|
return int(c), t - y / 100.0 * h, l - x / 100.0 * w
|
|
|
|
|
|
def load_roads(addon, zones):
|
|
"""built-in roads as world polylines, per continent"""
|
|
text = lua_text(addon, 'data/roads.lua')
|
|
out = {}
|
|
for zm in re.finditer(r'\[(\d+)\] = \{(.*?)\n \}', text, re.S):
|
|
zone = int(zm.group(1))
|
|
for line in re.findall(r'"([^"]*)"', zm.group(2)):
|
|
pts = []
|
|
for x, y in re.findall(r'([\d.]+),([\d.]+)', line):
|
|
p = to_world(zones, zone, float(x), float(y))
|
|
if p:
|
|
pts.append(p)
|
|
if len(pts) > 1:
|
|
out.setdefault(pts[0][0], []).append([(n, w) for _, n, w in pts])
|
|
return out
|
|
|
|
|
|
def load_walknet(addon):
|
|
m = re.search(r'nodes\s*=\s*\[\[(.*?)\]\]', lua_text(addon, 'data/walknet.lua'), re.S)
|
|
out = {}
|
|
if m:
|
|
for line in m.group(1).splitlines():
|
|
p = line.split()
|
|
if len(p) >= 5:
|
|
try:
|
|
out.setdefault(int(p[2]), []).append((float(p[3]), float(p[4])))
|
|
except ValueError:
|
|
pass
|
|
return out
|
|
|
|
|
|
def load_places(addon, zones):
|
|
out = {}
|
|
# places are named by zone constants; resolve them from the file's own table
|
|
text = lua_text(addon, 'data/places.lua')
|
|
consts = {k: int(v) for k, v in re.findall(r'local ([A-Z_]+) = (\d+)', text)}
|
|
for m in re.finditer(r'zone = ([A-Z_]+|\d+), x = ([\d.]+), y = ([\d.]+)', text):
|
|
z = consts.get(m.group(1)) if not m.group(1).isdigit() else int(m.group(1))
|
|
p = to_world(zones, z, float(m.group(2)), float(m.group(3))) if z else None
|
|
if p:
|
|
out.setdefault(p[0], []).append((p[1], p[2]))
|
|
return out
|
|
|
|
|
|
def load_spawns(pfquest, zones):
|
|
"""where pfQuest's quest NPCs, mobs and objects stand: one point per
|
|
50 yard square (a camp, a herb patch, a quest giver), per continent"""
|
|
out = {}
|
|
if not pfquest:
|
|
return out
|
|
for name in ('units.lua', 'objects.lua'):
|
|
path = os.path.join(pfquest, 'db', name)
|
|
if not os.path.exists(path):
|
|
continue
|
|
text = open(path, encoding='utf-8', errors='replace').read()
|
|
for x, y, z in re.findall(r'\{ ([\d.]+), ([\d.]+), (\d+), -?\d+ \}', text):
|
|
p = to_world(zones, int(z), float(x), float(y))
|
|
if p:
|
|
c, n, w = p
|
|
key = (int(n // SPOT), int(w // SPOT))
|
|
out.setdefault(c, {}).setdefault(key, []).append((n, w))
|
|
# one real spawn per square: the one nearest the middle, never an average
|
|
# (an average of spots either side of a wall can land inside it)
|
|
res = {}
|
|
for c, cells in out.items():
|
|
for pts in cells.values():
|
|
mn = sum(p[0] for p in pts) / len(pts)
|
|
mw = sum(p[1] for p in pts) / len(pts)
|
|
res.setdefault(c, []).append(min(pts, key=lambda p: (p[0] - mn) ** 2 + (p[1] - mw) ** 2))
|
|
return res
|
|
|
|
|
|
def load_solids(addon, zones):
|
|
"""structures with a solid base (Aldrassil): their ground level is out"""
|
|
out = {}
|
|
text = lua_text(addon, 'data/obstacles.lua')
|
|
for m in re.finditer(r'zone = (\d+), x = ([\d.]+), y = ([\d.]+), r = ([\d.]+)([^}]*)', text):
|
|
rest = m.group(5)
|
|
if 'doors' not in rest:
|
|
continue
|
|
g = re.search(r'ground = ([\d.]+)', rest)
|
|
p = to_world(zones, int(m.group(1)), float(m.group(2)), float(m.group(3)))
|
|
if p:
|
|
out.setdefault(p[0], []).append((p[1], p[2], float(m.group(4)), float(g.group(1)) if g else float(m.group(4))))
|
|
return out
|
|
|
|
|
|
# --------------------------------------------------------------- the network
|
|
|
|
class Baker:
|
|
def __init__(self, grid, solids, roads, log):
|
|
self.g = grid
|
|
self.solids = solids
|
|
self.log = log
|
|
self.road = set()
|
|
for line in roads:
|
|
for (n1, w1), (n2, w2) in zip(line, line[1:]):
|
|
steps = int(math.hypot(n2 - n1, w2 - w1) / 2) + 1
|
|
for k in range(steps + 1):
|
|
t = k / steps
|
|
self.road.add((int(math.floor((n1 + (n2 - n1) * t) / CELL)),
|
|
int(math.floor((w1 + (w2 - w1) * t) / CELL))))
|
|
self.covered = {}
|
|
self.slopes = {}
|
|
self.edges_memo = {}
|
|
self.clear_memo = {}
|
|
self.wp = [] # (i, j, s)
|
|
self.where = {} # (i, j, s) -> index
|
|
self.hash = {} # 32-cell squares -> waypoint indices
|
|
|
|
# standing places --------------------------------------------------------
|
|
|
|
def solid(self, i, j, s):
|
|
if s != 0:
|
|
return False
|
|
n, w = (i + 0.5) * CELL, (j + 0.5) * CELL
|
|
for sn, sw, r, ground in self.solids:
|
|
rr = ground + SOLID_PAD
|
|
if (sn - n) ** 2 + (sw - w) ** 2 < rr * rr:
|
|
return True
|
|
return False
|
|
|
|
def ok(self, i, j, s):
|
|
return self.g.count(i, j) > s and not self.solid(i, j, s)
|
|
|
|
def step(self, i, j, s, d, want=None):
|
|
ts = self.g.links(i, j, s, d)
|
|
if not ts:
|
|
return None
|
|
if want is not None and want in ts:
|
|
t = want
|
|
else:
|
|
t = ts[0]
|
|
ni, nj = i + DI[d], j + DJ[d]
|
|
if self.solid(ni, nj, t):
|
|
return None
|
|
# steep ground is too steep to walk up: you slide or drop down it. The
|
|
# network is walked both ways, so it never leads across a slope or a
|
|
# cliff face. Specks of it on a hillside are no slope: those stay.
|
|
if self.g.surface(i, j, s)[0] != 3 and self.slope(ni, nj, t):
|
|
return None
|
|
return t
|
|
|
|
def slope(self, i, j, s):
|
|
"""is this cell part of a stretch of steep ground bigger than a speck?"""
|
|
key = (i, j, s)
|
|
hit = self.slopes.get(key)
|
|
if hit is not None:
|
|
return hit
|
|
if self.g.surface(i, j, s)[0] != 3:
|
|
return False
|
|
seen = {key}
|
|
todo = [key]
|
|
while todo and len(seen) <= SLOPE_CELLS:
|
|
ci, cj, cs = todo.pop()
|
|
for d in range(4):
|
|
for t in (self.g.links(ci, cj, cs, d) or ()):
|
|
nk = (ci + DI[d], cj + DJ[d], t)
|
|
if nk not in seen and self.g.surface(nk[0], nk[1], t)[0] == 3:
|
|
seen.add(nk)
|
|
todo.append(nk)
|
|
big = len(seen) > SLOPE_CELLS
|
|
if big:
|
|
self.slopes[key] = True # only this cell: the rest is found from their own side
|
|
else:
|
|
for k in seen:
|
|
self.slopes[k] = False
|
|
return big
|
|
|
|
def line(self, i, j, s, ti, tj, ts=None, limit=None):
|
|
"""Walk the grid in a straight line from cell (i, j) level s to cell
|
|
(ti, tj). Yields the cells passed; stops early where it is blocked.
|
|
Returns (reached, level at the end, cells)."""
|
|
x0, y0 = i + 0.5, j + 0.5
|
|
dx, dy = ti - i, tj - j
|
|
si = 1 if dx > 0 else -1
|
|
sj = 1 if dy > 0 else -1
|
|
tdi = abs(1.0 / dx) if dx else 1e30
|
|
tdj = abs(1.0 / dy) if dy else 1e30
|
|
tmi = tdi * 0.5 if dx else 1e30
|
|
tmj = tdj * 0.5 if dy else 1e30
|
|
cells = [(i, j, s)]
|
|
guard = abs(dx) + abs(dy) + 2
|
|
while (i != ti or j != tj) and guard > 0:
|
|
guard -= 1
|
|
if abs(tmi - tmj) < 1e-9:
|
|
d1 = 1 if si > 0 else 3
|
|
d2 = 0 if sj > 0 else 2
|
|
m1 = self.step(i, j, s, d1)
|
|
m2 = self.step(i, j, s, d2)
|
|
if m1 is None or m2 is None:
|
|
return False, s, cells
|
|
t1 = self.step(i + DI[d1], j + DJ[d1], m1, d2)
|
|
t2 = self.step(i + DI[d2], j + DJ[d2], m2, d1)
|
|
if t1 is None or t1 != t2:
|
|
return False, s, cells
|
|
i, j, s = i + si, j + sj, t1
|
|
tmi += tdi
|
|
tmj += tdj
|
|
else:
|
|
if tmi < tmj:
|
|
d = 1 if si > 0 else 3
|
|
tmi += tdi
|
|
else:
|
|
d = 0 if sj > 0 else 2
|
|
tmj += tdj
|
|
want = ts if (i + DI[d], j + DJ[d]) == (ti, tj) else None
|
|
t = self.step(i, j, s, d, want)
|
|
if t is None:
|
|
return False, s, cells
|
|
i, j, s = i + DI[d], j + DJ[d], t
|
|
cells.append((i, j, s))
|
|
if limit and len(cells) > limit:
|
|
return False, s, cells
|
|
return (i == ti and j == tj), s, cells
|
|
|
|
# covering ---------------------------------------------------------------
|
|
|
|
def is_covered(self, i, j, s):
|
|
return (i, j, s) in self.covered
|
|
|
|
def openness(self, i, j, s):
|
|
"""how open the spot is: its walkable neighbours two cells round"""
|
|
score = 0
|
|
for d in range(4):
|
|
t = self.step(i, j, s, d)
|
|
if t is None:
|
|
score -= 3
|
|
continue
|
|
score += 1
|
|
t2 = self.step(i + DI[d], j + DJ[d], t, d)
|
|
if t2 is not None:
|
|
score += 1
|
|
if (i, j) in self.road:
|
|
score += 4
|
|
return score
|
|
|
|
def add(self, i, j, s, merge=0.0):
|
|
"""a waypoint at the spot, or the one already within `merge` yards on
|
|
the same level"""
|
|
key = (i, j, s)
|
|
if key in self.where:
|
|
return self.where[key]
|
|
if merge > 0:
|
|
r = int(merge / CELL) + 1
|
|
best = None
|
|
for hi in range((i - r) // 32, (i + r) // 32 + 1):
|
|
for hj in range((j - r) // 32, (j + r) // 32 + 1):
|
|
for o in self.hash.get((hi, hj), ()):
|
|
oi, oj, os_ = self.wp[o]
|
|
if os_ == s:
|
|
d = math.hypot(oi - i, oj - j) * CELL
|
|
if d <= merge and (best is None or d < best[0]):
|
|
best = (d, o)
|
|
if best:
|
|
return best[1]
|
|
k = len(self.wp)
|
|
self.wp.append(key)
|
|
self.where[key] = k
|
|
self.hash.setdefault((i // 32, j // 32), []).append(k)
|
|
return k
|
|
|
|
def spots(self, n, w, reach=4):
|
|
"""the open spots near a world point: every level of the nearest cell
|
|
you can stand on"""
|
|
i0, j0 = int(math.floor(n / CELL)), int(math.floor(w / CELL))
|
|
best = None
|
|
for di in range(-reach, reach + 1):
|
|
for dj in range(-reach, reach + 1):
|
|
i, j = i0 + di, j0 + dj
|
|
if self.g.count(i, j) and any(self.stand(i, j, s) for s in range(self.g.count(i, j))):
|
|
d = di * di + dj * dj
|
|
if best is None or d < best[0]:
|
|
best = (d, i, j)
|
|
if not best:
|
|
return []
|
|
_, i, j = best
|
|
return [(i, j, s) for s in range(min(2, self.g.count(i, j))) if self.stand(i, j, s)]
|
|
|
|
def stand(self, i, j, s):
|
|
"""a spot a waypoint can stand on: open, and not on steep ground"""
|
|
return self.ok(i, j, s) and self.g.surface(i, j, s)[0] != 3
|
|
|
|
def connect(self, k, o, edges, adj, maxlen):
|
|
"""join two waypoints: straight if the line is clear, else along the
|
|
best way on the navmesh (roads, open ground), with waypoints at its
|
|
corners. False when there is no way within maxlen yards."""
|
|
a, b = self.wp[k], self.wp[o]
|
|
ok, endlevel, cells = self.line(a[0], a[1], a[2], b[0], b[1], b[2])
|
|
straight = ok and endlevel == b[2]
|
|
wet = sum(1 for c in cells[1:-1] if self.g.surface(c[0], c[1], c[2])[0] == 2)
|
|
if straight and (wet >= 2 or sum(self.wall_factor(c) for c in cells) > 1.15 * len(cells)):
|
|
# clear, but through water or brushing walls and trees: the dry way through the open, if there is one
|
|
path = self.grid_path(a, b, maxlen=maxlen)
|
|
if path:
|
|
self.add_route(path, edges, adj, (k, o))
|
|
return True
|
|
if straight:
|
|
x, y = min(k, o), max(k, o)
|
|
d = math.hypot(a[0] - b[0], a[1] - b[1]) * CELL
|
|
edges[(x, y)] = (d, self.edge_flags(cells))
|
|
adj.setdefault(x, {})[y] = d
|
|
adj.setdefault(y, {})[x] = d
|
|
return True
|
|
path = self.grid_path(a, b, maxlen=maxlen)
|
|
if not path:
|
|
return False
|
|
self.add_route(path, edges, adj, (k, o))
|
|
return True
|
|
|
|
def snap(self, n, w, reach=3):
|
|
"""the nearest open spot near a world point, on the lowest level"""
|
|
i0, j0 = int(math.floor(n / CELL)), int(math.floor(w / CELL))
|
|
best = None
|
|
for di in range(-reach, reach + 1):
|
|
for dj in range(-reach, reach + 1):
|
|
i, j = i0 + di, j0 + dj
|
|
if self.ok(i, j, 0):
|
|
d = di * di + dj * dj
|
|
if best is None or d < best[0]:
|
|
best = (d, i, j)
|
|
return (best[1], best[2], 0) if best else None
|
|
|
|
def seed(self, points):
|
|
for n, w in points:
|
|
p = self.snap(n, w)
|
|
if p and not self.is_covered(*p):
|
|
self.add(*p)
|
|
|
|
def seed_roads(self, roads):
|
|
"""a waypoint every ROAD_STEP yards along each road"""
|
|
for line in roads:
|
|
carry = 0.0 # yards walked since the last waypoint
|
|
first = True
|
|
for (n1, w1), (n2, w2) in zip(line, line[1:]):
|
|
seg = math.hypot(n2 - n1, w2 - w1)
|
|
d = 0.0 if first else ROAD_STEP - carry
|
|
first = False
|
|
while d <= seg:
|
|
t = d / seg if seg > 0 else 0.0
|
|
p = self.snap(n1 + (n2 - n1) * t, w1 + (w2 - w1) * t, 2)
|
|
if p and not self.is_covered(*p):
|
|
self.add(*p)
|
|
d += ROAD_STEP
|
|
carry = seg - (d - ROAD_STEP) if seg >= 0 else 0.0
|
|
|
|
def fill(self, blocks):
|
|
"""a waypoint for every stretch of walkable ground no waypoint sees,
|
|
moved to the most open spot near it"""
|
|
keys = sorted(blocks)
|
|
started = time.time()
|
|
for n_done, key in enumerate(keys):
|
|
bi, bj = key // 1024 - 512, key % 1024 - 512
|
|
for li in range(BLOCK):
|
|
for lj in range(BLOCK):
|
|
i, j = bi * BLOCK + li, bj * BLOCK + lj
|
|
count = self.g.count(i, j)
|
|
for s in range(count):
|
|
if self.is_covered(i, j, s) or not self.ok(i, j, s):
|
|
continue
|
|
best = (self.openness(i, j, s), i, j, s)
|
|
# look round for a more open spot on the same ground
|
|
seen = {(i, j, s)}
|
|
frontier = [(i, j, s)]
|
|
for _ in range(3):
|
|
nxt = []
|
|
for ci, cj, cs in frontier:
|
|
for d in range(4):
|
|
t = self.step(ci, cj, cs, d)
|
|
if t is None:
|
|
continue
|
|
c = (ci + DI[d], cj + DJ[d], t)
|
|
if c not in seen:
|
|
seen.add(c)
|
|
nxt.append(c)
|
|
o = self.openness(*c)
|
|
if o > best[0]:
|
|
best = (o, c[0], c[1], c[2])
|
|
frontier = nxt
|
|
self.add(best[1], best[2], best[3])
|
|
self.covered[(i, j, s)] = True
|
|
if n_done % 50 == 0:
|
|
self.log(' covering: block %d/%d, %d waypoints, %.0fs' % (n_done + 1, len(keys), len(self.wp), time.time() - started))
|
|
|
|
# joining ----------------------------------------------------------------
|
|
|
|
def near(self, k, reach):
|
|
i, j, _ = self.wp[k]
|
|
r = int(reach / CELL / 32) + 1
|
|
for hi in range(i // 32 - r, i // 32 + r + 1):
|
|
for hj in range(j // 32 - r, j // 32 + r + 1):
|
|
for o in self.hash.get((hi, hj), ()):
|
|
if o != k:
|
|
oi, oj, _ = self.wp[o]
|
|
d = math.hypot(oi - i, oj - j) * CELL
|
|
if d <= reach:
|
|
yield o, d
|
|
|
|
def edge_flags(self, cells):
|
|
road = water = steep = 0
|
|
for i, j, s in cells:
|
|
if (i, j) in self.road:
|
|
road += 1
|
|
cls, _ = self.g.surface(i, j, s)
|
|
if cls == 2:
|
|
water += 1
|
|
elif cls == 3:
|
|
steep += 1
|
|
n = max(1, len(cells))
|
|
f = 0
|
|
if road / n >= 0.6:
|
|
f |= 1
|
|
if water >= 2:
|
|
f |= 2
|
|
if steep / n >= 0.3:
|
|
f |= 4
|
|
return f
|
|
|
|
def join(self):
|
|
edges = {}
|
|
started = time.time()
|
|
for k in range(len(self.wp)):
|
|
i, j, s = self.wp[k]
|
|
for o, d in self.near(k, JOIN):
|
|
if o < k and (o, k) in edges:
|
|
continue
|
|
oi, oj, os_ = self.wp[o]
|
|
ok, endlevel, cells = self.line(i, j, s, oi, oj, os_)
|
|
if ok and endlevel == os_:
|
|
a, b = min(k, o), max(k, o)
|
|
edges[(a, b)] = (d, self.edge_flags(cells))
|
|
if k % 2000 == 0:
|
|
self.log(' joining: %d/%d waypoints, %d joins, %.0fs' % (k, len(self.wp), len(edges), time.time() - started))
|
|
return edges
|
|
|
|
def prune(self, edges):
|
|
adj = {}
|
|
for (a, b), (d, f) in edges.items():
|
|
adj.setdefault(a, {})[b] = d
|
|
adj.setdefault(b, {})[a] = d
|
|
drop = set()
|
|
for (a, b), (d, f) in sorted(edges.items(), key=lambda e: -e[1][0]):
|
|
if f & 1:
|
|
continue # keep roads whole
|
|
na, nb = adj.get(a, {}), adj.get(b, {})
|
|
for c, dac in na.items():
|
|
if c != b and c in nb and dac + nb[c] <= d * REDUNDANT:
|
|
drop.add((a, b))
|
|
del adj[a][b]
|
|
del adj[b][a]
|
|
break
|
|
return {e: v for e, v in edges.items() if e not in drop}
|
|
|
|
# the network ------------------------------------------------------------
|
|
|
|
def hubs(self, blocks):
|
|
"""a waypoint in every piece of walkable ground, tile by tile (TILE
|
|
cells square), on every level: the most open spot of the piece"""
|
|
made = []
|
|
for key in sorted(blocks):
|
|
bi, bj = key // 1024 - 512, key % 1024 - 512
|
|
for ti in range(0, BLOCK, TILE):
|
|
for tj in range(0, BLOCK, TILE):
|
|
i0, j0 = bi * BLOCK + ti, bj * BLOCK + tj
|
|
seen = set()
|
|
for i in range(i0, i0 + TILE):
|
|
for j in range(j0, j0 + TILE):
|
|
for s in range(self.g.count(i, j)):
|
|
c = (i, j, s)
|
|
if c in seen or not self.stand(i, j, s):
|
|
continue
|
|
# the piece of ground this cell is in, inside the tile
|
|
piece = [c]
|
|
seen.add(c)
|
|
todo = [c]
|
|
while todo:
|
|
ci, cj, cs = todo.pop()
|
|
for d in range(4):
|
|
t = self.step(ci, cj, cs, d)
|
|
if t is None:
|
|
continue
|
|
nc = (ci + DI[d], cj + DJ[d], t)
|
|
if nc in seen or not (i0 <= nc[0] < i0 + TILE and j0 <= nc[1] < j0 + TILE):
|
|
continue
|
|
if not self.stand(nc[0], nc[1], t):
|
|
continue
|
|
seen.add(nc)
|
|
piece.append(nc)
|
|
todo.append(nc)
|
|
if len(piece) < 3:
|
|
continue
|
|
mi = sum(p[0] for p in piece) / len(piece)
|
|
mj = sum(p[1] for p in piece) / len(piece)
|
|
dry = [p for p in piece if self.g.surface(p[0], p[1], p[2])[0] != 2] or piece
|
|
best = max(dry, key=lambda p: (self.clearance(p), -((p[0] - mi) ** 2 + (p[1] - mj) ** 2)))
|
|
made.append(self.add(best[0], best[1], best[2], MERGE))
|
|
return sorted(set(made))
|
|
|
|
def clean_line(self, a, b):
|
|
"""a straight walk between two spots that is clear all the way, ends
|
|
on the right level, stays off the walls and trees between its ends
|
|
and out of the water. Returns its cells, or None."""
|
|
ok, endlevel, cells = self.line(a[0], a[1], a[2], b[0], b[1], b[2])
|
|
if not ok or endlevel != b[2]:
|
|
return None
|
|
wet_ends = self.g.surface(a[0], a[1], a[2])[0] == 2 or self.g.surface(b[0], b[1], b[2])[0] == 2
|
|
mid = cells[2:-2]
|
|
wet = touch = 0
|
|
for c in mid:
|
|
if self.g.surface(c[0], c[1], c[2])[0] == 2:
|
|
wet += 1
|
|
if self.is_edge(c):
|
|
touch += 1
|
|
if wet >= 2 and not wet_ends:
|
|
return None
|
|
if touch > 0:
|
|
return None
|
|
return cells
|
|
|
|
def put_edge(self, k, o, cells, edges, adj):
|
|
a, b = self.wp[k], self.wp[o]
|
|
x, y = min(k, o), max(k, o)
|
|
if x == y:
|
|
return
|
|
d = math.hypot(a[0] - b[0], a[1] - b[1]) * CELL
|
|
edges[(x, y)] = (d, self.edge_flags(cells))
|
|
adj.setdefault(x, {})[y] = d
|
|
adj.setdefault(y, {})[x] = d
|
|
|
|
def straight_joins(self, ks, edges, adj, log, started):
|
|
"""every waypoint joined straight to the nearest and the farthest
|
|
waypoint it can walk straight to, in each of SECTORS directions"""
|
|
pick = {}
|
|
lines = {}
|
|
ks = sorted(ks)
|
|
inset = set(ks)
|
|
for x, k in enumerate(ks):
|
|
for o, d in self.near(k, STRAIGHT):
|
|
if o <= k or o not in inset:
|
|
continue
|
|
cells = self.clean_line(self.wp[k], self.wp[o])
|
|
if not cells:
|
|
continue
|
|
lines[(k, o)] = cells
|
|
for p, q in ((k, o), (o, k)):
|
|
ang = math.atan2(self.wp[q][1] - self.wp[p][1], self.wp[q][0] - self.wp[p][0])
|
|
sec = int((ang + math.pi) / (2 * math.pi) * SECTORS) % SECTORS
|
|
cur = pick.setdefault(p, {}).setdefault(sec, [None, None])
|
|
if cur[0] is None or d < cur[0][0]:
|
|
cur[0] = (d, q)
|
|
if cur[1] is None or d > cur[1][0]:
|
|
cur[1] = (d, q)
|
|
if x % 500 == 0 and x:
|
|
log(' straight joins: %d/%d waypoints, %.0fs' % (x, len(ks), time.time() - started))
|
|
for p, secs in pick.items():
|
|
for near_far in secs.values():
|
|
for hit in near_far:
|
|
if hit:
|
|
q = hit[1]
|
|
key = (min(p, q), max(p, q))
|
|
if key not in edges:
|
|
self.put_edge(p, q, lines[key], edges, adj)
|
|
|
|
# repairing --------------------------------------------------------------
|
|
|
|
def is_edge(self, c):
|
|
hit = self.edges_memo.get(c)
|
|
if hit is None:
|
|
hit = any(self.step(c[0], c[1], c[2], e) is None for e in range(4))
|
|
self.edges_memo[c] = hit
|
|
return hit
|
|
|
|
def clearance(self, c):
|
|
"""cells between this one and the nearest wall, tree, drop or slope
|
|
(0 = right beside it), looked for up to CLEAR cells away"""
|
|
hit = self.clear_memo.get(c)
|
|
if hit is not None:
|
|
return hit
|
|
res = CLEAR
|
|
if self.is_edge(c):
|
|
res = 0
|
|
else:
|
|
seen = {c}
|
|
ring = [c]
|
|
for depth in range(1, CLEAR):
|
|
nxt = []
|
|
found = False
|
|
for (i, j, s) in ring:
|
|
for d in range(4):
|
|
t = self.step(i, j, s, d)
|
|
if t is None:
|
|
continue
|
|
nc = (i + DI[d], j + DJ[d], t)
|
|
if nc in seen:
|
|
continue
|
|
seen.add(nc)
|
|
if self.is_edge(nc):
|
|
found = True
|
|
break
|
|
nxt.append(nc)
|
|
if found:
|
|
break
|
|
if found:
|
|
res = depth
|
|
break
|
|
ring = nxt
|
|
self.clear_memo[c] = res
|
|
return res
|
|
|
|
def wall_factor(self, c):
|
|
return WALL_COST[self.clearance(c)]
|
|
|
|
def cell_cost(self, c):
|
|
i, j, s = c
|
|
cls, _ = self.g.surface(i, j, s)
|
|
f = 4.0 if cls == 2 else (1.3 if cls == 3 else 1.0) # water: only when there is no dry way near
|
|
if (i, j) in self.road:
|
|
f *= 0.7
|
|
return f * self.wall_factor(c) # the middle of the open space, where there is room
|
|
|
|
def grid_path(self, start, goal, limit=None, maxlen=None):
|
|
"""the best walking way between two spots on the grid: roads cheaper,
|
|
water and steep ground dearer, walls kept at a distance"""
|
|
import heapq
|
|
gi, gj, gs = goal
|
|
straight = math.hypot(start[0] - gi, start[1] - gj)
|
|
if limit is None:
|
|
reach = (maxlen / CELL) if maxlen else straight * 3
|
|
limit = int(2 * reach * reach) + 800
|
|
cap = (maxlen / CELL) if maxlen else None
|
|
def h(c):
|
|
return math.hypot(c[0] - gi, c[1] - gj) * 0.7 * 1.3
|
|
openh = [(h(start), 0.0, start)]
|
|
g = {start: 0.0}
|
|
steps = {start: 0}
|
|
prev = {}
|
|
cost = {}
|
|
n = 0
|
|
while openh:
|
|
f, gc, c = heapq.heappop(openh)
|
|
if c == goal:
|
|
path = [c]
|
|
while c in prev:
|
|
c = prev[c]
|
|
path.append(c)
|
|
return list(reversed(path))
|
|
if gc > g.get(c, 1e30):
|
|
continue
|
|
n += 1
|
|
if n > limit:
|
|
return None
|
|
i, j, s = c
|
|
for d in range(4):
|
|
t = self.step(i, j, s, d)
|
|
if t is None:
|
|
continue
|
|
nc = (i + DI[d], j + DJ[d], t)
|
|
cc = cost.get(nc)
|
|
if cc is None:
|
|
cc = self.cell_cost(nc)
|
|
cost[nc] = cc
|
|
cand = gc + cc
|
|
if cap and steps[c] + 1 > cap:
|
|
continue
|
|
if cand < g.get(nc, 1e30):
|
|
g[nc] = cand
|
|
steps[nc] = steps[c] + 1
|
|
prev[nc] = c
|
|
heapq.heappush(openh, (cand + h(nc), cand, nc))
|
|
return None
|
|
|
|
def repair(self, edges, adj):
|
|
"""join pieces of the network that ended up apart"""
|
|
parent = list(range(len(self.wp)))
|
|
|
|
def find(x):
|
|
while x >= len(parent):
|
|
parent.append(len(parent))
|
|
while parent[x] != x:
|
|
parent[x] = parent[parent[x]]
|
|
x = parent[x]
|
|
return x
|
|
|
|
for a, b in edges:
|
|
ra, rb = find(a), find(b)
|
|
if ra != rb:
|
|
parent[ra] = rb
|
|
joined = 0
|
|
tried = {}
|
|
# the closest pairs first: a ledge and the ground under it, the two
|
|
# sides of a doorway. A few passes, since each join changes the pieces.
|
|
for _ in range(3):
|
|
cands = []
|
|
for k in range(len(self.wp)):
|
|
rk = find(k)
|
|
best = None
|
|
for o, d in self.near(k, 400.0):
|
|
if find(o) != rk and (best is None or d < best[1]):
|
|
best = (o, d)
|
|
if best:
|
|
cands.append((best[1], k, best[0]))
|
|
if not cands:
|
|
break
|
|
cands.sort()
|
|
progress = False
|
|
for d, k, o in cands:
|
|
rk, ro = find(k), find(o)
|
|
if rk == ro:
|
|
continue
|
|
pair = (min(rk, ro), max(rk, ro))
|
|
tried[pair] = tried.get(pair, 0) + 1
|
|
if tried[pair] > 6:
|
|
continue
|
|
if self.connect(k, o, edges, adj, max(600.0, d * 3.0)):
|
|
joined += 1
|
|
progress = True
|
|
for a, b in list(edges):
|
|
ra, rb = find(a), find(b)
|
|
if ra != rb:
|
|
parent[ra] = rb
|
|
if not progress:
|
|
break
|
|
return joined
|
|
|
|
def sight(self, k):
|
|
"""how far the waypoint sees in each of 16 directions, in 10 yard
|
|
steps (0-8), packed two to a character. In the game this tells which
|
|
waypoints you can walk to straight from where you stand: one behind
|
|
a wall sees only up to the wall."""
|
|
i, j, s = self.wp[k]
|
|
steps = []
|
|
reach = int(SIGHT_DIST[8] / CELL) + 1
|
|
for r in range(SIGHT_DIRS):
|
|
a = 2 * math.pi * r / SIGHT_DIRS
|
|
ti = i + int(round(math.cos(a) * reach))
|
|
tj = j + int(round(math.sin(a) * reach))
|
|
ok, _, cells = self.line(i, j, s, ti, tj)
|
|
# sight ends at the water's edge: what it tells is where you can walk straight, dry
|
|
if self.g.surface(i, j, s)[0] != 2:
|
|
for x, c in enumerate(cells):
|
|
if self.g.surface(c[0], c[1], c[2])[0] == 2:
|
|
cells = cells[:max(1, x)]
|
|
ok = False
|
|
break
|
|
last = cells[-1]
|
|
d = math.hypot(last[0] - i, last[1] - j) * CELL
|
|
if not ok:
|
|
d = max(0.0, d - CELL / 2)
|
|
steps.append(max(x for x in range(9) if SIGHT_DIST[x] <= d))
|
|
return ''.join(enc(steps[x] * 9 + steps[x + 1]) for x in range(0, SIGHT_DIRS, 2))
|
|
|
|
def graph_dist(self, edges_adj, a, b, cutoff):
|
|
"""distance from waypoint a to b over the joins, or None beyond cutoff"""
|
|
import heapq
|
|
best = {a: 0.0}
|
|
h = [(0.0, a)]
|
|
while h:
|
|
d, u = heapq.heappop(h)
|
|
if u == b:
|
|
return d
|
|
if d > best.get(u, 1e30) or d > cutoff:
|
|
continue
|
|
for v, w in edges_adj.get(u, {}).items():
|
|
nd = d + w
|
|
if nd < best.get(v, 1e30) and nd <= cutoff:
|
|
best[v] = nd
|
|
heapq.heappush(h, (nd, v))
|
|
return None
|
|
|
|
def add_route(self, path, edges, adj, ends):
|
|
"""waypoints at the corners of a grid path (straightened into lines
|
|
the grid allows), joined one to the next"""
|
|
prevk = ends[0]
|
|
at = 0
|
|
cum = [0.0]
|
|
touch = [0]
|
|
for c in path:
|
|
cum.append(cum[-1] + self.cell_cost(c))
|
|
touch.append(touch[-1] + (1 if self.clearance(c) == 0 else 0))
|
|
while at < len(path) - 1:
|
|
nxt = at + 1
|
|
for m in range(min(len(path) - 1, at + 60), at + 1, -1):
|
|
ok, endlevel, cells = self.line(path[at][0], path[at][1], path[at][2], path[m][0], path[m][1], path[m][2])
|
|
if ok and endlevel == path[m][2]:
|
|
# straight only where that is no nearer the walls than the path was
|
|
# (a slanting line past a tree is fine while it stays a cell clear of it:
|
|
# that makes one smooth bend instead of a square step round it)
|
|
mean_line = sum(self.cell_cost(c) for c in cells) / len(cells)
|
|
mean_path = (cum[m + 1] - cum[at]) / (m - at + 1)
|
|
touch_line = sum(1 for c in cells if self.clearance(c) == 0)
|
|
touch_path = touch[m + 1] - touch[at]
|
|
if mean_line <= mean_path * 1.25 + 0.02 and touch_line <= touch_path:
|
|
nxt = m
|
|
break
|
|
spot = path[nxt]
|
|
kk = ends[1] if nxt == len(path) - 1 else self.add(spot[0], spot[1], spot[2], MERGE)
|
|
_, _, cells = self.line(path[at][0], path[at][1], path[at][2], spot[0], spot[1], spot[2])
|
|
a, b = min(prevk, kk), max(prevk, kk)
|
|
if a != b:
|
|
d = math.hypot(self.wp[a][0] - self.wp[b][0], self.wp[a][1] - self.wp[b][1]) * CELL
|
|
edges[(a, b)] = (d, self.edge_flags(cells))
|
|
adj.setdefault(a, {})[b] = d
|
|
adj.setdefault(b, {})[a] = d
|
|
prevk = kk
|
|
at = nxt
|
|
|
|
def passes(self, edges, log):
|
|
"""Waypoints in the narrow places: where two waypoints near each
|
|
other are much further apart over the network than on the ground
|
|
(a gap in a wall, a doorway, a bend), the real way between them gets
|
|
waypoints at its corners."""
|
|
adj = {}
|
|
for (a, b), (d, f) in edges.items():
|
|
adj.setdefault(a, {})[b] = d
|
|
adj.setdefault(b, {})[a] = d
|
|
pairs = []
|
|
for k in range(len(self.wp)):
|
|
for o, d in self.near(k, 2 * COVER):
|
|
if o > k and (k, o) not in edges:
|
|
pairs.append((d, k, o))
|
|
pairs.sort()
|
|
added = 0
|
|
started = time.time()
|
|
for n_done, (d, k, o) in enumerate(pairs):
|
|
if n_done % 5000 == 0 and n_done:
|
|
log(' narrow places: %d/%d pairs looked at, %d routes added, %.0fs' % (n_done, len(pairs), added, time.time() - started))
|
|
via = self.graph_dist(adj, k, o, d * 1.6)
|
|
if via is not None and via <= d * 1.5:
|
|
continue
|
|
path = self.grid_path(self.wp[k], self.wp[o], limit=int(4 * (d / CELL) ** 2) + 400)
|
|
if not path:
|
|
continue
|
|
length = CELL * (len(path) - 1)
|
|
if via is not None and length * 1.15 >= via:
|
|
continue
|
|
if length > d * 2.5:
|
|
continue
|
|
self.add_route(path, edges, adj, (k, o))
|
|
added += 1
|
|
return added
|
|
|
|
def report(self, edges, pois, log):
|
|
"""how good the network is: is everything joined, and how much longer
|
|
is a walk over it than the straight line"""
|
|
import heapq, random
|
|
adj = {}
|
|
for (a, b), (d, f) in edges.items():
|
|
adj.setdefault(a, []).append((b, d, f))
|
|
adj.setdefault(b, []).append((a, d, f))
|
|
comp = {}
|
|
sizes = []
|
|
for k in range(len(self.wp)):
|
|
if k in comp:
|
|
continue
|
|
comp[k] = len(sizes)
|
|
todo = [k]
|
|
n = 0
|
|
while todo:
|
|
u = todo.pop()
|
|
n += 1
|
|
for v, _, _ in adj.get(u, ()):
|
|
if v not in comp:
|
|
comp[v] = len(sizes)
|
|
todo.append(v)
|
|
sizes.append(n)
|
|
main = max(range(len(sizes)), key=lambda x: sizes[x]) if sizes else 0
|
|
off = sum(1 for k in range(len(self.wp)) if comp[k] != main)
|
|
offpoi = sum(1 for k in pois if comp[k] != main)
|
|
log(' check: %d pieces; %d waypoints (%d areas of interest) are cut off from the main one' % (len(sizes), off, offpoi))
|
|
wet = sum(1 for (a, b), (d, f) in edges.items() if f & 2)
|
|
log(' check: %d of %d joins go through water' % (wet, len(edges)))
|
|
rnd = random.Random(7)
|
|
inmain = [k for k in range(len(self.wp)) if comp[k] == main]
|
|
ratios = []
|
|
for _ in range(300):
|
|
if len(inmain) < 2:
|
|
break
|
|
a = rnd.choice(inmain)
|
|
cands = [o for o, d in self.near(a, 400.0) if d > 120 and comp[o] == main]
|
|
if not cands:
|
|
continue
|
|
b = rnd.choice(cands)
|
|
best = {a: 0.0}
|
|
h = [(0.0, a)]
|
|
while h:
|
|
d, u = heapq.heappop(h)
|
|
if u == b:
|
|
break
|
|
if d > best.get(u, 1e30):
|
|
continue
|
|
for v, w, _ in adj.get(u, ()):
|
|
if d + w < best.get(v, 1e30):
|
|
best[v] = d + w
|
|
heapq.heappush(h, (d + w, v))
|
|
straight = math.hypot(self.wp[a][0] - self.wp[b][0], self.wp[a][1] - self.wp[b][1]) * CELL
|
|
if b in best and straight > 0:
|
|
ratios.append(best[b] / straight)
|
|
if ratios:
|
|
ratios.sort()
|
|
log(' check: %d sample walks of 120-400 yards: over the network they are %.0f%% longer than the straight line on average, %.0f%% for the worst tenth'
|
|
% (len(ratios), (sum(ratios) / len(ratios) - 1) * 100, (ratios[int(len(ratios) * 0.9)] - 1) * 100))
|
|
|
|
def height(self, k):
|
|
i, j, s = self.wp[k]
|
|
_, h = self.g.surface(i, j, s)
|
|
return h
|
|
|
|
|
|
def write(path, maps, log):
|
|
lines = [
|
|
'-- pfQuest SmartArrow: waypoint network',
|
|
'-- Built by tools/bake_waypoints.py from a navmesh of the server\'s movement maps.',
|
|
'-- Waypoints along the roads, in every piece of walkable ground (every 32 yards,',
|
|
'-- every level) and at the areas of interest; two are joined where the walk',
|
|
'-- straight between them is clear on the navmesh.',
|
|
'-- Each waypoint: north, west (3 characters each, + 32768), height (2, + 4096,',
|
|
'-- or 0 where there is only one level), flags (1: on a road). Each join: two',
|
|
'-- waypoints (3 characters each, counted from 0) and flags (1 road, 2 water, 4 steep).',
|
|
'pfQuestSmartArrowData = pfQuestSmartArrowData or {}',
|
|
'pfQuestSmartArrowData.waypoints = { version = 4 }',
|
|
]
|
|
total = 0
|
|
for c, (nodes, edges) in sorted(maps.items()):
|
|
ns = ''.join(nodes)
|
|
es = ''.join(edges)
|
|
total += len(ns) + len(es)
|
|
lines.append('pfQuestSmartArrowData.waypoints[%d] = {' % c)
|
|
lines.append(' nodes = "%s",' % ns)
|
|
lines.append(' joins = "%s",' % es)
|
|
lines.append('}')
|
|
with open(path, 'w', encoding='ascii', newline='\n') as f:
|
|
f.write('\n'.join(lines) + '\n')
|
|
log('Wrote %s (%.2f MB)' % (path, os.path.getsize(path) / 1e6))
|
|
|
|
|
|
def main(argv=None):
|
|
ap = argparse.ArgumentParser(description=__doc__, formatter_class=argparse.RawDescriptionHelpFormatter)
|
|
here = os.path.dirname(os.path.abspath(__file__))
|
|
addon = os.path.dirname(here)
|
|
ap.add_argument('navmesh', nargs='?', default=os.path.join(os.path.dirname(addon), 'pfQuest-SmartArrow-Navmesh'))
|
|
ap.add_argument('--out', default=os.path.join(addon, 'data', 'waypoints.lua'))
|
|
ap.add_argument('--pfquest', default=None, help='pfQuest folder (default: next to SmartArrow)')
|
|
args = ap.parse_args(argv)
|
|
log = lambda s: print(s, flush=True)
|
|
|
|
version, maps = load_navmesh(args.navmesh)
|
|
zones = load_zones(addon)
|
|
roads = load_roads(addon, zones)
|
|
walknet = load_walknet(addon)
|
|
places = load_places(addon, zones)
|
|
solids = load_solids(addon, zones)
|
|
pfquest = args.pfquest or os.path.join(os.path.dirname(addon), 'pfQuest')
|
|
spawns = load_spawns(pfquest if os.path.isdir(pfquest) else None, zones)
|
|
if not spawns:
|
|
log('No pfQuest database found at %s: only roads, zone exits and places get waypoints' % pfquest)
|
|
out = {}
|
|
for c, blocks in sorted(maps.items()):
|
|
if not blocks:
|
|
continue
|
|
log('Map %d: %d navmesh blocks' % (c, len(blocks)))
|
|
grid = Grid(blocks)
|
|
b = Baker(grid, solids.get(c, []), roads.get(c, []), log)
|
|
edges, adj = {}, {}
|
|
started = time.time()
|
|
|
|
# the roads: a waypoint every ROAD_STEP yards, each joined to the next
|
|
road_ends = []
|
|
for line in roads.get(c, []):
|
|
prev = None
|
|
carry = 0.0
|
|
first = True
|
|
for (n1, w1), (n2, w2) in zip(line, line[1:]):
|
|
seg = math.hypot(n2 - n1, w2 - w1)
|
|
d = 0.0 if first else ROAD_STEP - carry
|
|
first = False
|
|
while d <= seg:
|
|
t = d / seg if seg > 0 else 0.0
|
|
sp = b.spots(n1 + (n2 - n1) * t, w1 + (w2 - w1) * t, 2)
|
|
if sp:
|
|
k = b.add(sp[0][0], sp[0][1], sp[0][2], MERGE)
|
|
if prev is not None and prev != k:
|
|
b.connect(prev, k, edges, adj, ROAD_STEP * 3)
|
|
prev = k
|
|
d += ROAD_STEP
|
|
carry = seg - (d - ROAD_STEP)
|
|
if prev is not None:
|
|
road_ends.append(prev)
|
|
roadset = set(range(len(b.wp)))
|
|
log(' %d waypoints along the roads, %.0fs' % (len(b.wp), time.time() - started))
|
|
# roads that meet or nearly meet
|
|
for k in list(roadset):
|
|
for o, d in b.near(k, 40.0):
|
|
if o in roadset and o != k and (min(k, o), max(k, o)) not in edges:
|
|
b.connect(k, o, edges, adj, 60.0)
|
|
|
|
# the ground itself: a waypoint in every piece of it, on every level
|
|
hubs = b.hubs(blocks)
|
|
log(' %d waypoints over the walkable ground (every %d yards, every level), %.0fs' % (len(hubs), TILE * CELL, time.time() - started))
|
|
base = sorted(set(hubs) | roadset)
|
|
b.straight_joins(base, edges, adj, log, started)
|
|
log(' %d straight joins, %.0fs' % (len(edges), time.time() - started))
|
|
# neighbours with no straight walk between: the real way (round the
|
|
# corner, through the doorway, up the ramp), with waypoints at its bends
|
|
made = 0
|
|
for x, k in enumerate(base):
|
|
for o, d in sorted(b.near(k, TILE * CELL * 1.6), key=lambda e: e[1]):
|
|
if o > k and (k, o) not in edges and b.graph_dist(adj, k, o, d * 1.6 + 8) is None:
|
|
if b.connect(k, o, edges, adj, d * 4.0 + 60):
|
|
made += 1
|
|
if x % 500 == 0 and x:
|
|
log(' ways round: %d/%d waypoints, %d made, %.0fs' % (x, len(base), made, time.time() - started))
|
|
log(' %d ways round corners (%d waypoints now), %.0fs' % (made, len(b.wp), time.time() - started))
|
|
|
|
# the areas of interest (spawn spots, zone exits, passes, places):
|
|
# each a waypoint of its own, joined to what is around it
|
|
netset = set(range(len(b.wp)))
|
|
pois = []
|
|
for n, w in spawns.get(c, []) + walknet.get(c, []) + places.get(c, []):
|
|
for sp in b.spots(n, w):
|
|
pois.append(b.add(sp[0], sp[1], sp[2], MERGE))
|
|
pois = sorted(set(pois) - netset)
|
|
for k in pois:
|
|
done = 0
|
|
for o, d in sorted(b.near(k, 70.0), key=lambda e: e[1]):
|
|
if o not in netset:
|
|
continue
|
|
cells = b.clean_line(b.wp[k], b.wp[o])
|
|
if cells:
|
|
b.put_edge(k, o, cells, edges, adj)
|
|
done += 1
|
|
if done >= 3:
|
|
break
|
|
if done == 0:
|
|
for o, d in sorted(b.near(k, 120.0), key=lambda e: e[1]):
|
|
if o in netset and b.connect(k, o, edges, adj, d * 4.0 + 60):
|
|
done += 1
|
|
if done >= 2:
|
|
break
|
|
log(' %d areas of interest added (%d waypoints now), %.0fs' % (len(pois), len(b.wp), time.time() - started))
|
|
added = b.repair(edges, adj)
|
|
log(' %d pieces joined (%d waypoints now), %.0fs' % (added, len(b.wp), time.time() - started))
|
|
edges = b.prune(edges)
|
|
log(' %d joins kept' % len(edges))
|
|
b.report(edges, pois, log)
|
|
nodes = []
|
|
for k, (i, j, s) in enumerate(b.wp):
|
|
n = int(round((i + 0.5) * CELL)) + 32768
|
|
w = int(round((j + 0.5) * CELL)) + 32768
|
|
h = b.height(k)
|
|
hz = 0 if h is None else max(1, min(91 * 91 - 1, int(round(h)) + 4096))
|
|
nodes.append(num(n, 3) + num(w, 3) + num(hz, 2) + enc(1 if (i, j) in b.road else 0))
|
|
es = [num(a, 3) + num(bb, 3) + enc(f) for (a, bb), (d, f) in sorted(edges.items())]
|
|
out[c] = (nodes, es)
|
|
write(args.out, out, log)
|
|
log('Done. SmartArrow uses these waypoints whenever the navmesh itself is not installed.')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
main()
|