Files

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()