Files

1204 lines
53 KiB
Python

#!/usr/bin/env python3
# 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.
"""Build SmartArrow's path network (data/paths.lua) from the navmesh add-on.
The walkable ground is cut into squares of 28 yards. Every separate piece of
ground in a square (each side of a wall, each level, water apart from dry
land) gets one point, in its most open spot, on the road where there is one.
Two points are joined where the walk between them was checked on the navmesh:
straight where that is clear, otherwise round the corner, with the corner
kept. So the network reaches everything the navmesh reaches, and never leads
anywhere it does not.
python3 bake_paths.py build data/paths.lua
python3 bake_paths.py --verify 300 also walk 300 test trips on the
navmesh with the arrow's own rules
"""
import argparse
import heapq
import math
import os
import random
import sys
import time
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import bake_waypoints as bw # the navmesh grid reader and its walking rules
CELL = bw.CELL
DI, DJ = bw.DI, bw.DJ
TILE = 7 # cells to a square (28 yards)
PBLOCK = 16 # squares to a block of the data file
FORMAT = 5
HOLE = 4 # columns: a patch of missing ground this small is a tree or a rock
MAX_VIAS = 12 # corners kept on one join
TINY = 2 # cells: a piece this small joins the piece beside it
ISLAND = 40 # cells: pieces of ground smaller than this, joined to nothing bigger, are left out
MAX_COMPS = 40 # pieces of ground kept in one square
DIRS = ((1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1),
(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1))
FAR_DIRS = DIRS + ((0, 0), (2, 0), (0, 2), (-2, 0), (0, -2), (2, 2), (-2, 2), (-2, -2), (2, -2)) # joins kept one by one
ASIDE = 6.0 # yards a point must lie off that walk
BYPASS = 3.0 # yards a walk past a point must save to get a join of its own
SAME = 16 # "direction" of a join inside one square
ROAD, WATER = 0.7, 6.0
START_REACH = 45.0 # yards: how far from you the first point may be
OPEN_ROOM = 8.0 # yards of room round a point that let the aim pass its corner
DRIFT = 10.0 # yards beside the line at which the arrow points straight back at it
TURN = 0.1 # radians the line may turn before the aim stops at a corner
LOOK = 20.0 # yards the arrow aims ahead along the path
OPEN = 3 # cells of room all round a point that let the aim cut its corner
CUT = 0.85 # cosine of the sharpest turn the aim may cut across (about 30 degrees)
OFF = 20.0 # yards off the path that call for a new plan
class Net:
def __init__(self, grid, solids, roads, log):
self.b = bw.Baker(grid, solids, roads, log)
self.g = grid
self.log = log
self.label = {} # (i, j, s) -> node
self.nodes = [] # dicts: cell, tile, comp, road, water, z, cells
self.tiles = {} # (tx, ty) -> [node ids]
self.adj = [] # per node: {other: (vias, length)}
self.route = set()
self.holes = {}
self.cutting = True
self.wander = 0.0
self.why = {}
self.want_z = None
self.pz = {}
# -- pieces of ground ----------------------------------------------------
def wet(self, c):
return self.g.surface(c[0], c[1], c[2])[0] == 2
def usable(self, c):
return self.b.ok(c[0], c[1], c[2]) and not self.b.slope(c[0], c[1], c[2])
def build_nodes(self):
b = self.b
started = time.time()
keys = sorted(self.g.raw.keys())
for n_done, key in enumerate(keys):
bi, bj = key // 1024 - 512, key % 1024 - 512
for i in range(bi * bw.BLOCK, (bi + 1) * bw.BLOCK):
for j in range(bj * bw.BLOCK, (bj + 1) * bw.BLOCK):
for s in range(self.g.count(i, j)):
c = (i, j, s)
if c in self.label or not self.usable(c):
continue
self.flood(c)
if n_done % 200 == 199:
self.log(' pieces of ground: %d/%d navmesh blocks, %d points, %.0fs' % (n_done + 1, len(keys), len(self.nodes), time.time() - started))
self.log(' %d points, %.0fs' % (len(self.nodes), time.time() - started))
def flood(self, start):
b = self.b
tile = (start[0] // TILE, start[1] // TILE)
water = self.wet(start)
k = len(self.nodes)
cells = [start]
self.label[start] = k
todo = [start]
while todo:
i, j, s = todo.pop()
for d in range(4):
t = b.step(i, j, s, d)
if t is None:
continue
nc = (i + DI[d], j + DJ[d], t)
if nc in self.label or (nc[0] // TILE, nc[1] // TILE) != tile:
continue
if self.wet(nc) != water or not self.usable(nc):
continue
self.label[nc] = k
cells.append(nc)
todo.append(nc)
for c in cells:
del self.label[c]
self.split(cells, tile, water)
def small_hole(self, i, j):
"""a column with no ground you can use, part of a patch of at most
HOLE such columns: a tree, a rock, a post. You walk round those
without thinking; a wall, a cliff or the world's edge is bigger."""
hit = self.holes.get((i, j))
if hit is not None:
return hit
def empty(ci, cj):
return not any(self.usable((ci, cj, s)) for s in range(self.g.count(ci, cj)))
if not empty(i, j):
self.holes[(i, j)] = False
return False
seen = {(i, j)}
todo = [(i, j)]
while todo and len(seen) <= HOLE:
ci, cj = todo.pop()
for d in range(4):
nc = (ci + DI[d], cj + DJ[d])
if nc not in seen and empty(*nc):
seen.add(nc)
todo.append(nc)
small = len(seen) <= HOLE
for c in seen:
self.holes[c] = small
return small
def past_trees(self, a, c, cells):
"""is the straight walk from a to c clear but for small holes on it
(never a wall, a drop or another level)?"""
b = self.b
di, dj = c[0] - a[0], c[1] - a[1]
n = max(abs(di), abs(dj)) * 2
if n == 0:
return True
cur = a # the cell you are on; None while passing a hole
last = (a[0], a[1])
for k in range(1, n + 1):
col = (int(math.floor(a[0] + 0.5 + di * k / n)), int(math.floor(a[1] + 0.5 + dj * k / n)))
if col == last:
continue
if self.small_hole(*col):
cur, last = None, col
continue
if cur is None:
# out of the hole: onto this column's one cell of the piece
levels = [x for x in cells if x[0] == col[0] and x[1] == col[1]]
if len(levels) != 1:
return False
cur = levels[0]
else:
nxt = self.move(cur, col[0], col[1])
if nxt is None or nxt not in cells:
return False
cur = nxt
last = col
return cur == c
def split(self, cells, tile, water):
"""one piece of ground -> points that every cell of theirs can walk
straight to: the most open spot first, then what it cannot see"""
b = self.b
mi, mj = tile[0] * TILE + TILE // 2, tile[1] * TILE + TILE // 2
def score(c):
return ((10 if (c[0], c[1]) in b.road else 0) + b.clearance(c)
- 0.05 * (abs(c[0] - mi) + abs(c[1] - mj)))
left = set(cells)
first = len(self.nodes)
while left:
# the next piece: connected cells still left, from the best of them
best = max(left, key=score)
# how many steps each cell is from the point, inside what is left
steps = {best: 0}
ring = [best]
while ring:
nxt = []
for (i, j, s) in ring:
for d in range(4):
t = b.step(i, j, s, d)
if t is None:
continue
nc = (i + DI[d], j + DJ[d], t)
if nc in left and nc not in steps:
steps[nc] = steps[(i, j, s)] + 1
nxt.append(nc)
ring = nxt
# the point's own: cells it sees, and cells just round a tree or a rock from it
# (hardly further on foot than in a straight line; a wall makes it much further)
mine = [c for c in left if c in steps and (
c == best or self.line_ok(best, c, False)
or (steps[c] <= abs(c[0] - best[0]) + abs(c[1] - best[1]) + 4 and self.past_trees(best, c, left)))]
# keep it in one piece: only what joins up with the point through seen cells
seen = {best}
mset = set(mine)
todo = [best]
while todo:
i, j, s = todo.pop()
for d in range(4):
t = b.step(i, j, s, d)
if t is None:
continue
nc = (i + DI[d], j + DJ[d], t)
if nc in mset and nc not in seen:
seen.add(nc)
todo.append(nc)
k = len(self.nodes)
for c in seen:
self.label[c] = k
left -= seen
self.nodes.append({'cell': best, 'tile': tile, 'road': (best[0], best[1]) in b.road, 'water': water,
'z': self.g.surface(best[0], best[1], best[2])[1], 'cells': list(seen)})
self.adj.append({})
# A piece of one or two cells (a ragged bit of an edge the point of
# its neighbour just cannot see) is not worth a point of its own: it
# goes to the biggest piece it touches.
made = self.nodes[first:]
if len(made) > 1:
owner = list(range(len(made)))
for x in sorted(range(len(made)), key=lambda x: len(made[x]['cells'])):
if len(made[x]['cells']) > TINY:
break
best = None
for (i, j, s) in made[x]['cells']:
for d in range(4):
for want in self.g.links(i, j, s, d) or ():
t = b.step(i, j, s, d, want)
if t is None:
continue
o = self.label.get((i + DI[d], j + DJ[d], t))
if o is None or o < first:
continue
o = owner[o - first]
while owner[o] != o:
o = owner[o]
if o != x and (best is None or len(made[o]['cells']) > len(made[best]['cells'])):
best = o
if best is not None:
owner[x] = best
made[best]['cells'].extend(made[x]['cells'])
made[x]['cells'] = []
kept = [m for m in made if m['cells']]
del self.nodes[first:]
del self.adj[first:]
for m in kept:
k = len(self.nodes)
for c in m['cells']:
self.label[c] = k
self.nodes.append(m)
self.adj.append({})
def relocate(self):
"""Move each piece's point to where the walks through the piece
pass: near the middle of its borders with the pieces round it, off
the edges, on the road if it has one. (The most open spot can be a
bay to one side: a route through the piece would turn into it and
out again.) Only to a spot that sees as much of the piece as the
old point did."""
b = self.b
started = time.time()
moved = 0
for k, node in enumerate(self.nodes):
cells = node['cells']
if len(cells) < 4:
continue
borders = {}
for c in cells:
for d in range(4):
for want in self.g.links(c[0], c[1], c[2], d) or ():
t = b.step(c[0], c[1], c[2], d, want)
if t is None:
continue
o = self.label.get((c[0] + DI[d], c[1] + DJ[d], t))
if o is not None and o != k:
borders.setdefault(o, []).append(c)
if len(borders) < 2:
continue
mids = [(sum(c[0] for c in cs) / len(cs), sum(c[1] for c in cs) / len(cs)) for cs in borders.values()]
roads = [c for c in cells if (c[0], c[1]) in b.road]
pool = roads or cells
def cost(c):
return (sum(math.hypot(c[0] - m[0], c[1] - m[1]) for m in mids) / len(mids)
+ (2 - min(2, b.clearance(c))) * 1.5)
def sees(c):
return sum(1 for x in cells if x == c or self.line_ok(c, x, False))
old = node['cell']
if old not in pool:
continue
base = cost(old)
need = None
for c in sorted(pool, key=cost)[:10]:
if c == old or cost(c) > base - 1.0: # (cells: 4 yards nearer on average, or not worth it)
break
if need is None:
need = sees(old)
if sees(c) >= need * 0.9:
node['cell'] = c
node['road'] = (c[0], c[1]) in b.road
node['z'] = self.g.surface(c[0], c[1], c[2])[1]
moved += 1
break
self.log(' %d points moved to where the walks pass, %.0fs' % (moved, time.time() - started))
def heights(self):
"""the range of heights of each piece: from its own cells where the
navmesh keeps them (ground with levels over each other), otherwise
from the nearest cell that has one, a few steps away (an estimate:
good to a few yards, enough to tell the ramp from the ground under it)"""
b = self.b
for node in self.nodes:
hs = [h for h in (self.g.surface(c[0], c[1], c[2])[1] for c in node['cells']) if h is not None]
if hs:
node['zlo'], node['zhi'], node['zkind'] = min(hs), max(hs), 1
continue
node['zlo'] = node['zhi'] = None
node['zkind'] = 0
seen = {node['cell']}
ring = [node['cell']]
for _ in range(8):
nxt = []
found = None
for (i, j, s) in ring:
for d in range(4):
t = b.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)
h = self.g.surface(nc[0], nc[1], nc[2])[1]
if h is not None:
found = h
break
nxt.append(nc)
if found is not None:
break
if found is not None:
node['zlo'] = node['zhi'] = found
node['zkind'] = 2
break
ring = nxt
# -- joins ---------------------------------------------------------------
def line_ok(self, a, c, strict):
"""clear walked either way (the grid steps differ a little by direction)"""
return self.line_one(a, c, strict) and self.line_one(c, a, strict)
def line_one(self, a, c, strict):
"""the straight walk between two cells: clear, dry (unless both ends
are in water), and, when strict, not brushing walls"""
b = self.b
ok, endlevel, cells = b.line(a[0], a[1], a[2], c[0], c[1], c[2])
if not ok or endlevel != c[2]:
return False
wet_ends = self.wet(a) or self.wet(c)
for x in cells[1:-1]:
if not self.usable(x):
return False
if not wet_ends and self.wet(x):
return False
if strict and sum(b.wall_factor(x) for x in cells) > 1.35 * len(cells):
return False
return True
def wide_ok(self, a, c, strict=True):
"""the straight walk with a cell to spare on every side: the same
walk from one cell beside each end must be clear too"""
b = self.b
if not self.line_ok(a, c, strict):
return False
for d in range(4):
ta, tc = b.step(a[0], a[1], a[2], d), b.step(c[0], c[1], c[2], d)
if ta is None or tc is None:
return False
if not self.line_ok((a[0] + DI[d], a[1] + DJ[d], ta), (c[0] + DI[d], c[1] + DJ[d], tc), False):
return False
return True
def edge_cells(self, a, c):
"""how many cells of the straight walk lie right at an edge (a wall,
a drop, the side of a ramp); None when the walk is not clear"""
if not self.line_ok(a, c, False):
return None
_, _, cells = self.b.line(a[0], a[1], a[2], c[0], c[1], c[2])
return sum(1 for x in cells[1:-1] if self.b.is_edge(x))
def mid_corners(self, path):
"""a grid path as its corner cells, keeping to the middle: a stretch
is made straight only where that brings it no nearer the edges than
the path was. (The cells are 4 yards wide: a straight line that
grazes the cells along a ramp's inner side cuts its corner.)"""
edge = [0]
for x in path:
edge.append(edge[-1] + (1 if self.b.is_edge(x) else 0))
out = []
at = 0
while at < len(path) - 1:
nxt = at + 1
for m in range(len(path) - 1, at + 1, -1):
n = self.edge_cells(path[at], path[m])
if n is not None and n <= edge[m] - edge[at + 1]:
nxt = m
break
if nxt < len(path) - 1:
out.append(path[nxt])
at = nxt
if len(out) > MAX_VIAS:
out = [out[int((x + 0.5) * len(out) / MAX_VIAS)] for x in range(MAX_VIAS)]
return out
def corners(self, path, wide):
"""a grid path as its corner cells: straight stretches the navmesh
allows (with a cell to spare each side, when wide)"""
out = []
at = 0
while at < len(path) - 1:
nxt = at + 1
for m in range(len(path) - 1, at + 1, -1):
if (self.wide_ok(path[at], path[m], False) if wide else self.line_ok(path[at], path[m], False)):
nxt = m
break
if nxt < len(path) - 1:
out.append(path[nxt])
at = nxt
return out
def build_joins(self):
b = self.b
started = time.time()
# which pieces touch: a step from a cell of one lands in the other
touch = set()
for c, k in self.label.items():
for d in range(4):
t = b.step(c[0], c[1], c[2], d)
if t is None:
continue
o = self.label.get((c[0] + DI[d], c[1] + DJ[d], t))
if o is not None and o != k:
touch.add((min(k, o), max(k, o)))
for k, node in enumerate(self.nodes):
self.tiles.setdefault(node['tile'], []).append(k)
self.touch = touch
straight = round_ = tight = 0
# touching pieces: always joined, round the corner if need be
for a, c in sorted(touch):
ca, cc = self.nodes[a]['cell'], self.nodes[c]['cell']
if self.line_ok(ca, cc, True):
self.join(a, c, []) # straight, and not brushing walls
straight += 1
continue
path = self.path_within(a, c)
if path:
vias = self.corners(path, False) # every stretch between corners is a checked straight walk
if len(vias) <= MAX_VIAS:
self.join(a, c, vias)
round_ += 1
continue
if self.line_ok(ca, cc, False):
self.join(a, c, [])
straight += 1
tight += 1
# the squares further round: only where the straight walk is clear and in the open
for k, node in enumerate(self.nodes):
tx, ty = node['tile']
for dx, dy in DIRS:
for o in self.tiles.get((tx + dx, ty + dy), ()):
if o > k and o not in self.adj[k]:
if self.line_ok(node['cell'], self.nodes[o]['cell'], True):
self.join(k, o, [])
straight += 1
self.log(' %d joins (%d straight, %d round a corner, %d through tight places), %.0fs' % (straight + round_, straight - tight, round_, tight, time.time() - started))
def bypasses(self):
"""A route through a piece has to touch its point, and that can be
a turn aside (a ramp runs along one side of a wide landing: the
point is in the landing). So where the walk from one neighbour of a
piece to another, through the piece but not over its point, is
shorter, the two neighbours get a join of their own."""
started = time.time()
added = 0
for v in range(len(self.nodes)):
# (only its own neighbours: the pieces that touch it)
near = [(o, e) for o, e in self.adj[v].items() if (min(o, v), max(o, v)) in self.touch]
if len(near) < 2:
continue
for x in range(len(near)):
u, (_, lu) = near[x]
for y in range(x + 1, len(near)):
w, (_, lw) = near[y]
if w in self.adj[u]:
continue
tu, tw = self.nodes[u]['tile'], self.nodes[w]['tile']
if (tw[0] - tu[0], tw[1] - tu[1]) not in FAR_DIRS:
continue
(un, uw), (wn, ww) = self.pos(u), self.pos(w)
if lu + lw - math.hypot(un - wn, uw - ww) < BYPASS:
continue # nothing to gain: the point is on the way
if self.nodes[u]['water'] != self.nodes[w]['water']:
continue
path = self.path_within(u, w, (u, v, w))
if not path:
continue
vias = self.corners(path, False)
if len(vias) > 4:
continue
pts = [path[0]] + vias + [path[-1]]
length = sum(math.hypot(p[0] - q[0], p[1] - q[1]) for p, q in zip(pts, pts[1:])) * CELL
# how far aside the point is from that walk
vn, vw = self.pos(v)
aside = 1e9
for p, q in zip(pts, pts[1:]):
pn, pw, qn, qw = (p[0] + 0.5) * CELL, (p[1] + 0.5) * CELL, (q[0] + 0.5) * CELL, (q[1] + 0.5) * CELL
l2 = (qn - pn) ** 2 + (qw - pw) ** 2
t = max(0.0, min(1.0, ((vn - pn) * (qn - pn) + (vw - pw) * (qw - pw)) / l2)) if l2 > 0 else 0.0
aside = min(aside, math.hypot(pn + (qn - pn) * t - vn, pw + (qw - pw) * t - vw))
if lu + lw - length >= BYPASS and aside >= ASIDE:
self.join(u, w, vias)
added += 1
self.log(' %d joins added past a point that was a turn aside, %.0fs' % (added, time.time() - started))
def path_within(self, a, c, inside=None):
"""the best walk from one point to the other inside their two pieces
(or the pieces given)"""
b = self.b
inside = inside or (a, c)
start, goal = self.nodes[a]['cell'], self.nodes[c]['cell']
dist = {start: 0.0}
prev = {}
heap = [(0.0, start)]
while heap:
g, u = heapq.heappop(heap)
if u == goal:
path = [u]
while u in prev:
u = prev[u]
path.append(u)
return path[::-1]
if g > dist[u]:
continue
for d in range(4):
for want in self.g.links(u[0], u[1], u[2], d) or ():
t = b.step(u[0], u[1], u[2], d, want)
if t is None:
continue
v = (u[0] + DI[d], u[1] + DJ[d], t)
if self.label.get(v) not in inside:
continue
cand = g + b.cell_cost(v)
if cand < dist.get(v, 1e30):
dist[v] = cand
prev[v] = u
heapq.heappush(heap, (cand, v))
return None
def join(self, a, c, vias):
pts = [self.nodes[a]['cell']] + vias + [self.nodes[c]['cell']]
length = sum(math.hypot(p[0] - q[0], p[1] - q[1]) for p, q in zip(pts, pts[1:])) * CELL
self.adj[a][c] = (vias, length)
self.adj[c][a] = (list(reversed(vias)), length)
def drop_islands(self):
seen = {}
keep = set()
for k in range(len(self.nodes)):
if k in seen:
continue
group = [k]
seen[k] = True
todo = [k]
while todo:
u = todo.pop()
for v in self.adj[u]:
if v not in seen:
seen[v] = True
group.append(v)
todo.append(v)
if sum(len(self.nodes[x]['cells']) for x in group) >= ISLAND:
keep.update(group)
dropped = len(self.nodes) - len(keep)
index = {}
nodes, adj = [], []
for k in range(len(self.nodes)):
if k in keep:
index[k] = len(nodes)
nodes.append(self.nodes[k])
for k in range(len(self.nodes)):
if k in keep:
adj.append({index[o]: v for o, v in self.adj[k].items()})
self.nodes, self.adj = nodes, adj
self.label = {c: index[k] for c, k in self.label.items() if k in index}
self.tiles = {}
for k, node in enumerate(self.nodes):
self.tiles.setdefault(node['tile'], []).append(k)
for t, ks in list(self.tiles.items()):
if len(ks) > MAX_COMPS:
self.log(' square %s has %d pieces of ground; the smallest are left out' % (t, len(ks)))
self.log(' %d small cut-off pieces left out, %d points kept' % (dropped, len(self.nodes)))
# -- the data file -------------------------------------------------------
def encode(self):
"""blocks of 16 x 16 squares -> string"""
comp = {}
for t, ks in self.tiles.items():
for x, k in enumerate(ks):
comp[k] = x
blocks = {}
self.size = {'points': 0, 'joins to other pieces or round corners': 0, 'maps of pieces': 0}
for (tx, ty) in self.tiles:
blocks.setdefault((tx // PBLOCK, ty // PBLOCK), True)
out = {}
for (bx, by) in sorted(blocks):
parts = []
empty = 0
for tx in range(bx * PBLOCK, (bx + 1) * PBLOCK):
for ty in range(by * PBLOCK, (by + 1) * PBLOCK):
ks = self.tiles.get((tx, ty), ())[:MAX_COMPS]
if not ks:
empty += 1
if empty == 31:
parts.append(bw.enc(59 + empty))
empty = 0
continue
if empty:
parts.append(bw.enc(59 + empty))
empty = 0
parts.append(bw.enc(len(ks)))
before = sum(len(x) for x in parts)
masks = self.encode_map(ks, tx, ty, parts)
self.size['maps of pieces'] += sum(len(x) for x in parts) - before + (sum(len(m) for m in masks) if masks else 0)
for x, k in enumerate(ks):
e = self.encode_node(k, tx, ty, comp)
base = 9 if self.nodes[k]['zkind'] else 6
self.size['points'] += base
self.size['joins to other pieces or round corners'] += len(e) - base
parts.append(e)
if masks:
parts.append(masks[x])
out[(bx, by)] = ''.join(parts)
multi = sum(1 for ks in self.tiles.values() if len(ks) > 1)
self.log(' %d squares, %d of them with more than one piece of ground; characters: %s' % (
len(self.tiles), multi, ', '.join('%s %d' % kv for kv in self.size.items())))
return out
def encode_map(self, ks, tx, ty, parts):
"""which piece each cell of a square belongs to, for squares with
several: one piece per cell (kind 0), or, where levels lie over each
other, each piece's own cells (kind 1, returned to go after each point)"""
if len(ks) < 2:
return None
cellmap = {}
over = len(ks) > 8
for x, k in enumerate(ks):
for (i, j, _) in self.nodes[k]['cells']:
idx = (i - tx * TILE) * TILE + (j - ty * TILE)
if idx in cellmap and cellmap[idx] != x:
over = True
cellmap[idx] = x
if not over:
vals = [cellmap.get(idx, -1) + 1 for idx in range(TILE * TILE)] + [0]
parts.append(bw.enc(0) + ''.join(bw.enc(vals[x] * 9 + vals[x + 1]) for x in range(0, TILE * TILE + 1, 2)))
return None
parts.append(bw.enc(1))
masks = []
for k in ks:
bits = [0] * 54
for (i, j, _) in self.nodes[k]['cells']:
bits[(i - tx * TILE) * TILE + (j - ty * TILE)] = 1
masks.append(''.join(bw.enc(sum(bits[x + y] << y for y in range(6))) for x in range(0, 54, 6)))
return masks
def encode_node(self, k, tx, ty, comp):
node = self.nodes[k]
i, j, _ = node['cell']
mask = 0
exc = []
for o, (vias, _) in sorted(self.adj[k].items()):
other = self.nodes[o]
if comp.get(o, 99) >= MAX_COMPS:
continue
delta = (other['tile'][0] - tx, other['tile'][1] - ty)
d = FAR_DIRS.index(delta) if delta in FAR_DIRS else None
if d is None:
continue
if d < 16 and comp[o] == 0 and not vias:
mask |= 1 << d
else:
e = bw.enc(d) + bw.enc(comp[o]) + bw.enc(len(vias))
for v in vias:
e += bw.enc(max(0, min(90, v[0] - i + 45))) + bw.enc(max(0, min(90, v[1] - j + 45)))
exc.append(e)
exc = exc[:90]
kind = node['zkind']
flags = (1 if node['road'] else 0) + (2 if node['water'] else 0) + 4 * kind + 16 * self.b.clearance(node['cell'])
zc = ''
if kind:
lo = max(0, min(8280, int(math.floor(node['zlo'])) + 2000))
zc = bw.num(lo, 2) + bw.enc(max(0, min(90, int(math.ceil(node['zhi'])) + 2000 - lo)))
return (bw.enc((i - tx * TILE) * TILE + (j - ty * TILE)) + bw.enc(flags) + zc
+ bw.num(mask, 3) + bw.enc(len(exc)) + ''.join(exc))
# -- the arrow's own rules, for the test walks ---------------------------
def cost(self, u, v):
length = self.adj[u][v][1]
a, c = self.nodes[u], self.nodes[v]
if a['road'] and c['road']:
length *= ROAD
if a['water'] or c['water']:
length *= WATER
return length
def near(self, n, w, z, reach):
tx, ty = int(math.floor(n / CELL)) // TILE, int(math.floor(w / CELL)) // TILE
found = []
for dx in (-2, -1, 0, 1, 2):
for dy in (-2, -1, 0, 1, 2):
for k in self.tiles.get((tx + dx, ty + dy), ())[:MAX_COMPS]:
pn, pw = self.pos(k)
d = math.hypot(pn - n, pw - w)
if d > reach:
continue
nz = self.nodes[k]['z']
if z is not None and nz is not None:
if abs(nz - z) > 8:
continue
d += abs(nz - z) * 2
found.append((d, k))
found.sort()
return found[:3]
def pos(self, k):
i, j, _ = self.nodes[k]['cell']
return (i + 0.5) * CELL, (j + 0.5) * CELL
def plan(self, a, za, b_, zb):
# the piece of ground you stand on, and the one the goal is on (the
# game knows both from the squares' maps of their pieces)
starts = [(math.hypot(self.pos(k)[0] - a[0], self.pos(k)[1] - a[1]), k) for k in za]
goals = dict((k, math.hypot(self.pos(k)[0] - b_[0], self.pos(k)[1] - b_[1]) * 1.3) for k in zb)
if not starts or not goals:
return None
g, prev = {}, {}
heap = []
for d, k in starts:
g[k] = d * 1.3
heapq.heappush(heap, (g[k], k))
best, bestk = None, None
done = set()
while heap:
f, u = heapq.heappop(heap)
if best is not None and f - 0.0 >= best + 400:
break
if u in done:
continue
done.add(u)
if u in goals and (best is None or g[u] + goals[u] < best):
best, bestk = g[u] + goals[u], u
break
for v in self.adj[u]:
cand = g[u] + self.cost(u, v)
if cand < g.get(v, 1e30):
g[v] = cand
prev[v] = u
pn, pw = self.pos(v)
heapq.heappush(heap, (cand + math.hypot(pn - b_[0], pw - b_[1]) * ROAD, v))
if bestk is None:
return None
chain = [bestk]
while chain[-1] in prev:
chain.append(prev[chain[-1]])
chain.reverse()
self.route = set(chain)
line = [(a[0], a[1], 0.0, None)]
for x, k in enumerate(chain):
if x > 0:
for v in self.adj[chain[x - 1]][k][0]:
line.append(((v[0] + 0.5) * CELL, (v[1] + 0.5) * CELL, 0.0, None))
pn, pw = self.pos(k)
room = self.b.clearance(self.nodes[k]['cell']) * CELL * 0.7
if self.nodes[k]['z'] is not None:
room = 0.0
line.append((pn, pw, room, self.nodes[k]['z']))
line.append((b_[0], b_[1], 0.0, None))
# out to a point and back the same way: the point is left out (paths.lua)
x = 1
while x < len(line) - 1:
p, r = line[x - 1], line[x + 1]
if 1 < x < len(line) - 2 and abs(p[0] - r[0]) < 0.5 and abs(p[1] - r[1]) < 0.5:
del line[x:x + 2]
if x > 1:
x -= 1
else:
x += 1
# the same rounding of corners as the game does (paths.lua)
pts = [a]
self.pz = {}
self.isvia = set()
self.tight = set()
for x in range(1, len(line) - 1):
p, q, r = line[x - 1], line[x], line[x + 1]
din, dout = math.hypot(p[0] - q[0], p[1] - q[1]), math.hypot(r[0] - q[0], r[1] - q[1])
room = q[2]
if room > 2 and din > 0 and dout > 0:
rin = min(room, din / 2) if x > 1 else room
rout = min(room, dout / 2) if x < len(line) - 2 else room
if rin < din:
pts.append((q[0] + (p[0] - q[0]) * rin / din, q[1] + (p[1] - q[1]) * rin / din))
self.pz[len(pts) - 1] = q[3]
if room < OPEN_ROOM:
self.tight.add(len(pts) - 1)
if rout < dout:
pts.append((q[0] + (r[0] - q[0]) * rout / dout, q[1] + (r[1] - q[1]) * rout / dout))
self.pz[len(pts) - 1] = q[3]
if room < OPEN_ROOM:
self.tight.add(len(pts) - 1)
else:
pts.append((q[0], q[1]))
self.pz[len(pts) - 1] = q[3]
self.tight.add(len(pts) - 1)
if q[3] is None and room == 0:
self.isvia.add(len(pts) - 1)
pts.append(b_)
# two corners on one spot (the way out of one point's room is the way into the next's) are one
keep, pz, via, tight = [pts[0]], {}, set(), set()
for x in range(1, len(pts)):
if x < len(pts) - 1 and math.hypot(pts[x][0] - keep[-1][0], pts[x][1] - keep[-1][1]) < 0.5:
continue
keep.append(pts[x])
if self.pz.get(x) is not None:
pz[len(keep) - 1] = self.pz[x]
if x in self.isvia:
via.add(len(keep) - 1)
if x in self.tight:
tight.add(len(keep) - 1)
self.pz, self.isvia, self.tight = pz, via, tight
return keep
def is_open(self, k):
return self.b.clearance(self.nodes[k]['cell']) >= OPEN
def walk(self, start, goal):
"""follow the arrow from one cell to another on the navmesh.
Returns (result, yards walked, wet steps)"""
b = self.b
cell = start
n, w = (start[0] + 0.5) * CELL, (start[1] + 0.5) * CELL
gn, gw = (goal[0] + 0.5) * CELL, (goal[1] + 0.5) * CELL
pts = self.plan((n, w), [self.label[start]], (gn, gw), [self.label[goal]])
if not pts:
return 'no plan', 0.0, 0
seg = 0
walked, wet, slid, side = 0.0, 0, 0, 1
phase = (start[0] * 7 + start[1] * 13) % 6
for _ in range(6000):
if math.hypot(gn - n, gw - w) < 3.0:
return ('arrived' if cell[2] == goal[2] or (cell[0], cell[1]) != (goal[0], goal[1]) else 'wrong level'), walked, wet
# where you are along the path: forward only
bestd, bests, bestt = None, seg, 0.0
for x in range(seg, min(seg + 2, len(pts) - 1)):
(an, aw), (cn, cw) = pts[x], pts[x + 1]
dn, dw = cn - an, cw - aw
l2 = dn * dn + dw * dw
t = max(0.0, min(1.0, ((n - an) * dn + (w - aw) * dw) / l2)) if l2 > 0 else 0.0
d = math.hypot(an + dn * t - n, aw + dw * t - w)
if bestd is None or d < bestd - 1e-6:
bestd, bests, bestt = d, x, t
seg = bests
(an, aw), (cn, cw) = pts[seg], pts[seg + 1]
if seg < len(pts) - 2 and math.hypot(cn - an, cw - aw) * (1 - bestt) <= 1.5:
seg, bestt = seg + 1, 0.0 # at the corner: on to the next stretch
self.want_z = next((self.pz[x] for x in range(seg + 1, min(seg + 4, len(pts))) if self.pz.get(x) is not None), None)
if bestd > OFF:
return 'strayed', walked, wet
# the aim, as the game's arrow (paths.lua): LOOK yards ahead along the line, stopping at a tight corner
left = LOOK
x, t = seg, bestt
cut = False
turned = 0.0
while True:
(an, aw), (cn, cw) = pts[x], pts[x + 1]
slen = math.hypot(cn - an, cw - aw)
rest = slen * (1 - t)
if left <= rest or x == len(pts) - 2:
t2 = min(1.0, t + (left / slen if slen > 0 else 1.0))
aim = (an + (cn - an) * t2, aw + (cw - aw) * t2)
break
en, ew = pts[x + 2]
l2 = math.hypot(en - cn, ew - cw)
if slen > 0 and l2 > 0:
turned += math.acos(max(-1.0, min(1.0, ((cn - an) * (en - cn) + (cw - aw) * (ew - cw)) / (slen * l2))))
if rest > 1.5 and ((x + 1) in self.tight or turned > TURN or not self.cutting):
aim = (cn, cw)
break
left -= rest
x, t = x + 1, 0.0
cut = True
d = math.hypot(aim[0] - n, aim[1] - w)
if d < 0.01:
return 'stopped', walked, wet
# beside the line in the open: the way the path goes, more towards it the further off (paths.lua)
(an, aw), (cn, cw) = pts[seg], pts[seg + 1]
slen = math.hypot(cn - an, cw - aw)
tight_aim = any(abs(aim[0] - pts[y][0]) + abs(aim[1] - pts[y][1]) < 0.01 for y in self.tight)
if not tight_aim and (seg + 1) not in self.tight and bestd > 1 and slen > 0 and bestd < DRIFT:
wgt = bestd / DRIFT
dn = (aim[0] - n) / d * wgt + (cn - an) / slen * (1 - wgt)
dw = (aim[1] - w) / d * wgt + (cw - aw) / slen * (1 - wgt)
dl = math.hypot(dn, dw)
if dl > 0.01:
aim = (n + dn / dl * 12, w + dw / dl * 12)
d = 12.0
# a player does not walk dead straight: the heading swings a little either side
if self.wander:
ang = math.atan2(aim[1] - w, aim[0] - n) + self.wander * math.sin(walked / 9.0 + phase)
aim = (n + math.cos(ang) * d, w + math.sin(ang) * d)
stepl = min(1.75, d)
nn, nw = n + (aim[0] - n) / d * stepl, w + (aim[1] - w) / d * stepl
ni, nj = int(math.floor(nn / CELL)), int(math.floor(nw / CELL))
if (ni, nj) != (cell[0], cell[1]):
nc = self.move(cell, ni, nj)
if nc is None:
# the game slides you along what you run into: keep the part of
# the step that is free, or (head on at a tree trunk) step round it
slid += 1
ux, uy = (aim[0] - n) / d, (aim[1] - w) / d
for sn, sw in ((nn, w), (n, nw), (n - uy * stepl * side, w + ux * stepl * side),
(n + uy * stepl * side, w - ux * stepl * side)):
if abs(sn - n) + abs(sw - w) < 0.2:
continue
si, sj = int(math.floor(sn / CELL)), int(math.floor(sw / CELL))
nc = cell if (si, sj) == (cell[0], cell[1]) else self.move(cell, si, sj)
if nc is not None:
nn, nw = sn, sw
break
if slid > 60:
nc = None
if nc is None:
where = 'on the way to the first point' if seg == 0 else ('on the last stretch to the goal' if seg >= len(pts) - 2 else 'between points')
# what stopped it, for the summary
if self.g.count(ni, nj) == 0:
what = 'the edge of the ground'
elif any(b.slope(ni, nj, t) for t in range(self.g.count(ni, nj))):
what = 'a steep slope'
elif any(b.solid(ni, nj, t) for t in range(self.g.count(ni, nj))):
what = 'a building'
elif self.g.count(ni, nj) > 1 or self.g.count(cell[0], cell[1]) > 1:
what = 'another level (a ledge, a ramp side)'
else:
what = 'a wall or a drop'
if seg == 0 or seg >= len(pts) - 2:
kind = 'to or from its own point'
elif seg in self.isvia or seg + 1 in self.isvia:
kind = 'on a join round a corner'
else:
kind = 'on a straight join'
off = 'on the line' if bestd < 2 else ('%d-%d yd off the line' % ((2, 5) if bestd < 5 else (5, 15)))
key = '%s, %s, %s%s' % (what, kind, off, ', cutting a corner' if cut else '')
self.why[key] = self.why.get(key, 0) + 1
return 'blocked ' + where, walked, wet
cell = nc
if self.wet(cell):
wet += 1
n, w = nn, nw
walked += stepl
return 'never arrived', walked, wet
def move(self, cell, ni, nj):
b = self.b
i, j, s = cell
di, dj = ni - i, nj - j
if abs(di) > 1 or abs(dj) > 1:
return None
def one(c, d):
# where two levels start from one cell (the foot of a ramp), the one the path goes over
best, bests = None, None
for want in self.g.links(c[0], c[1], c[2], d) or ():
t = b.step(c[0], c[1], c[2], d, want)
if t is None:
continue
nc = (c[0] + DI[d], c[1] + DJ[d], t)
h = self.g.surface(nc[0], nc[1], nc[2])[1]
here = self.g.surface(c[0], c[1], c[2])[1]
# the level the path goes over; else the one at the height you are on
# (you do not change level by walking); else the one the path is heading for
sc = (0 if self.label.get(nc) in self.route else 1,
abs(h - here) if (h is not None and here is not None) else 0,
abs(h - self.want_z) if (h is not None and self.want_z is not None) else 0)
if bests is None or sc < bests:
best, bests = nc, sc
return best
def direction(a, c):
for d in range(4):
if DI[d] == a and DJ[d] == c:
return d
if di and dj:
for first, second in (((di, 0), (0, dj)), ((0, dj), (di, 0))):
mid = one(cell, direction(*first))
if mid:
end = one(mid, direction(*second))
if end:
return end
return None
return one(cell, direction(di, dj))
def verify(self, trips, seed=1):
self.verify_once(trips, seed)
if self.why:
self.log(' what stopped the blocked walks:')
for key, n in sorted(self.why.items(), key=lambda e: -e[1]):
self.log(' %3d %s' % (n, key))
self.best_possible(seed)
def best_possible(self, seed):
"""how much longer the network's walks are than the best walk on the navmesh"""
rnd = random.Random(seed + 1)
usable = [k for k in range(len(self.nodes)) if not self.nodes[k]['water']]
ratios = []
tries = 0
while len(ratios) < 60 and tries < 3000:
tries += 1
a = rnd.choice(usable)
an, aw = self.pos(a)
tx, ty = self.nodes[a]['tile']
c = None
for _ in range(8):
ks = self.tiles.get((tx + rnd.randint(-6, 6), ty + rnd.randint(-6, 6)))
if ks:
c = rnd.choice(ks)
break
if c is None or self.nodes[c]['water']:
continue
start, goal = self.nodes[a]['cell'], self.nodes[c]['cell']
straight = math.hypot(start[0] - goal[0], start[1] - goal[1]) * CELL
if straight < 60:
continue
res, walked, _ = self.walk(start, goal)
if res != 'arrived':
continue
path = self.b.grid_path(start, goal, maxlen=max(400.0, straight * 4))
if not path:
continue
pts = [start] + self.corners(path, False) + [goal]
best = sum(math.hypot(p[0] - q[0], p[1] - q[1]) for p, q in zip(pts, pts[1:])) * CELL
if best > 0:
ratios.append((walked / best, best / straight))
if ratios:
r1 = sorted(r[0] for r in ratios)
r2 = sorted(r[1] for r in ratios)
self.log(' %d walks of 60-250 yards against the best walk the navmesh allows:' % len(ratios))
self.log(' the network\'s walk / the best walk: median %.2f, 9 in 10 under %.2f, worst %.2f' % (r1[len(r1) // 2], r1[int(len(r1) * 0.9)], r1[-1]))
self.log(' the best walk / straight line (the ground itself): median %.2f, 9 in 10 under %.2f' % (r2[len(r2) // 2], r2[int(len(r2) * 0.9)]))
def verify_once(self, trips, seed=1, brief=False):
rnd = random.Random(seed)
started = time.time()
results = {}
ratios = []
wet_total = 0
examples = {}
usable = [k for k in range(len(self.nodes)) if not self.nodes[k]['water']]
tries = 0
done = 0
while done < trips and tries < trips * 200 and usable:
tries += 1
a = rnd.choice(usable)
an, aw = self.pos(a)
# somewhere 80 to 400 yards off, reachable on the network
tx, ty = self.nodes[a]['tile']
ks = self.tiles.get((tx + rnd.randint(-14, 14), ty + rnd.randint(-14, 14)))
if not ks:
continue
c = rnd.choice(ks)
if self.nodes[c]['water']:
continue
cn, cw = self.pos(c)
dist = math.hypot(cn - an, cw - aw)
if dist < 80 or dist > 400:
continue
start = rnd.choice(self.nodes[a]['cells'])
goal = rnd.choice(self.nodes[c]['cells'])
res, walked, wet = self.walk(start, goal)
if res == 'no plan':
continue # not joined: two separate pieces of the world
done += 1
results[res] = results.get(res, 0) + 1
wet_total += wet
if res == 'arrived':
straight = math.hypot(start[0] - goal[0], start[1] - goal[1]) * CELL
if straight > 0:
ratios.append(walked / straight)
elif res not in examples:
examples[res] = (start, goal)
self.log(' test walks: %d, %.0fs' % (done, time.time() - started))
if brief:
self.log(' arrived %d (%.1f%%)' % (results.get('arrived', 0), 100.0 * results.get('arrived', 0) / max(1, done)))
return results
for res, n in sorted(results.items(), key=lambda e: -e[1]):
line = ' %-40s %4d (%.1f%%)' % (res, n, 100.0 * n / max(1, done))
if res in examples:
s, g_ = examples[res]
line += ' e.g. from %.0f, %.0f to %.0f, %.0f' % ((s[0] + 0.5) * CELL, (s[1] + 0.5) * CELL, (g_[0] + 0.5) * CELL, (g_[1] + 0.5) * CELL)
self.log(line)
if ratios:
ratios.sort()
self.log(' walked / straight line: median %.2f, 9 in 10 under %.2f, worst %.2f' % (
ratios[len(ratios) // 2], ratios[int(len(ratios) * 0.9)], ratios[-1]))
self.log(' steps taken in water: %d' % wet_total)
return results
def write(path, maps, log):
lines = [
'-- pfQuest SmartArrow: path network',
'-- Built by tools/bake_paths.py from a navmesh of the server\'s movement maps:',
'-- one point for every piece of walkable ground in each 28 yard square, joined',
'-- where the walk between two was checked on the navmesh. Coordinates and',
'-- connections only.',
'pfQuestSmartArrowData = pfQuestSmartArrowData or {}',
'pfQuestSmartArrowData.paths = { version = %d, cell = %d, tile = %d, block = %d }' % (FORMAT, int(CELL), TILE, PBLOCK),
]
for c, blocks in sorted(maps.items()):
lines.append('pfQuestSmartArrowData.paths[%d] = {' % c)
for (bx, by), s in sorted(blocks.items()):
lines.append('["%d:%d"]="%s",' % (bx, by, s))
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', 'paths.lua'))
ap.add_argument('--verify', type=int, default=0, metavar='N', help='walk N test trips on the navmesh')
args = ap.parse_args(argv)
log = lambda s: print(s, flush=True)
version, maps = bw.load_navmesh(args.navmesh)
zones = bw.load_zones(addon)
roads = bw.load_roads(addon, zones)
solids = bw.load_solids(addon, zones)
out = {}
nets = {}
for c, blocks in sorted(maps.items()):
if not blocks:
continue
log('Map %d: %d navmesh blocks' % (c, len(blocks)))
net = Net(bw.Grid(blocks), solids.get(c, []), roads.get(c, []), log)
net.build_nodes()
net.relocate()
net.heights()
net.build_joins()
net.bypasses()
net.drop_islands()
out[c] = net.encode()
nets[c] = net
write(args.out, out, log)
if args.verify:
for c, net in sorted(nets.items()):
log('Map %d:' % c)
net.verify(args.verify)
log('Done.')
return nets
if __name__ == '__main__':
main()