767 lines
32 KiB
Python
767 lines
32 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 rectangles of 4 yard cells that are fully
|
|
joined inside: between any two spots of one rectangle you can walk in a
|
|
straight line. Two rectangles that touch share a border you can cross. A
|
|
walk is then a chain of rectangles, and its line is pulled tight across
|
|
their borders: straight over open ground, round the corners of what is in
|
|
the way, up the middle of nothing in particular. No spot has to be walked
|
|
over that is not on the way.
|
|
|
|
python3 bake_rects.py build data/paths.lua
|
|
python3 bake_rects.py --verify 500 also walk 500 test trips on the
|
|
navmesh with the arrow's own rules
|
|
"""
|
|
import argparse
|
|
import heapq
|
|
import math
|
|
import os
|
|
import sys
|
|
import time
|
|
|
|
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
|
|
import bake_waypoints as bw
|
|
import bake_paths as bp
|
|
|
|
CELL = bw.CELL
|
|
DI, DJ = bw.DI, bw.DJ
|
|
BLOCK = bw.BLOCK
|
|
FORMAT = 10
|
|
FAR = 91 * 91 # what two characters can hold
|
|
SWIM = 1.0 # yards of water over ground that make it the bed, not a ford
|
|
JUMP = 8 # yards of height one step between two cells may climb
|
|
NEAR = 920 # places in a block's list that fit beside the block in two characters
|
|
MAX = 16 # cells a side of a rectangle
|
|
SLIVER = 2 # cells: a rectangle this small at a dead end is left out
|
|
ISLAND = 40 # cells: ground cut off from everything bigger is left out
|
|
ROAD, WATER = 0.7, 6.0
|
|
JOG = 6.0 # yards: two opposite turns this close are a side step, not turns
|
|
bp.TURN = 99.0 # (on this network the arrow stops at real corners only)
|
|
bp.LOOK = 12.0
|
|
|
|
|
|
def direction(di, dj):
|
|
for d in range(4):
|
|
if DI[d] == di and DJ[d] == dj:
|
|
return d
|
|
|
|
|
|
# the four sides of a rectangle: +i (north), +j (west), -i, -j
|
|
SIDES = (direction(1, 0), direction(0, 1), direction(-1, 0), direction(0, -1))
|
|
|
|
|
|
def tri(a, b, c):
|
|
return (c[0] - a[0]) * (b[1] - a[1]) - (b[0] - a[0]) * (c[1] - a[1])
|
|
|
|
|
|
def funnel(start, portals, end):
|
|
"""the shortest line from start to end through the portals, each
|
|
(left end, right end, way through). A corner of the line is an end of a
|
|
border; there it steps through the border square on, from the middle of
|
|
the cell this side to the middle of the cell beyond, so the turn comes
|
|
after the border and not on it."""
|
|
ports = [(start, start, None)] + portals + [(end, end, None)]
|
|
pts = [start]
|
|
apex = left = right = start
|
|
ai = li = ri = 0
|
|
i = 1
|
|
guard = 0
|
|
|
|
def corner(p, x):
|
|
nrm = ports[x][2]
|
|
if nrm is None:
|
|
pts.append(p)
|
|
else:
|
|
pts.append((p[0] - nrm[0] * CELL / 2, p[1] - nrm[1] * CELL / 2))
|
|
pts.append((p[0] + nrm[0] * CELL / 2, p[1] + nrm[1] * CELL / 2))
|
|
while i < len(ports):
|
|
guard += 1
|
|
if guard > 20000:
|
|
break
|
|
L, R = ports[i][0], ports[i][1]
|
|
if tri(apex, right, R) <= 0:
|
|
if apex == right or tri(apex, left, R) > 0:
|
|
right, ri = R, i
|
|
else:
|
|
corner(left, li)
|
|
apex, ai = left, li
|
|
left = right = apex
|
|
li = ri = ai
|
|
i = ai + 1
|
|
continue
|
|
if tri(apex, left, L) >= 0:
|
|
if apex == left or tri(apex, right, L) < 0:
|
|
left, li = L, i
|
|
else:
|
|
corner(right, ri)
|
|
apex, ai = right, ri
|
|
left = right = apex
|
|
li = ri = ai
|
|
i = ai + 1
|
|
continue
|
|
i += 1
|
|
pts.append(end)
|
|
out = [pts[0]]
|
|
for p in pts[1:]:
|
|
if math.hypot(p[0] - out[-1][0], p[1] - out[-1][1]) > 0.01:
|
|
out.append(p)
|
|
return out
|
|
|
|
|
|
def jogs(pts):
|
|
"""The corners of side steps: two turns a few yards apart, one left and
|
|
one right by about as much, so the line goes on the way it was going,
|
|
a little to one side. That is the grid's step along something narrow
|
|
that runs at a slant (the top of a winding ramp). The arrow looks on
|
|
past those instead of turning square at each."""
|
|
def turn(x):
|
|
an, aw = pts[x][0] - pts[x - 1][0], pts[x][1] - pts[x - 1][1]
|
|
bn, bw = pts[x + 1][0] - pts[x][0], pts[x + 1][1] - pts[x][1]
|
|
return math.atan2(an * bw - aw * bn, an * bn + aw * bw)
|
|
out = set()
|
|
for x in range(1, len(pts) - 2):
|
|
if math.hypot(pts[x + 1][0] - pts[x][0], pts[x + 1][1] - pts[x][1]) <= JOG:
|
|
t1, t2 = turn(x), turn(x + 1)
|
|
if t1 * t2 < 0 and abs(t1 + t2) < 0.35:
|
|
out.add(x)
|
|
out.add(x + 1)
|
|
return out
|
|
|
|
|
|
class RectNet(bp.Net):
|
|
def sunk(self, c):
|
|
"""Ground under water you swim in: the level of the water over it,
|
|
else None. The movement maps keep the bed of the sea and of lakes as
|
|
ground of its own, under the water's surface. A player is up on the
|
|
surface there, so the bed is no part of the network; the water is."""
|
|
sunken = self.__dict__.setdefault('sunken', {})
|
|
hit = sunken.get(c, 0)
|
|
if hit != 0:
|
|
return hit
|
|
i, j, s = c
|
|
cls, h = self.g.surface(i, j, s)
|
|
up = None
|
|
if cls != 2 and h is not None:
|
|
best = None
|
|
for t in range(self.g.count(i, j)):
|
|
if t == s:
|
|
continue
|
|
c2, h2 = self.g.surface(i, j, t)
|
|
if h2 is None or h2 <= h + SWIM:
|
|
continue
|
|
if best is None or h2 < best[0]:
|
|
best = (h2, c2, t) # the first level over this one
|
|
if best is not None and best[1] == 2:
|
|
up = best[2]
|
|
sunken[c] = up
|
|
return up
|
|
|
|
def usable(self, c):
|
|
"""ground a player can walk on: open, not steep, not the bed under
|
|
water. The movement maps mark ground too steep for a player
|
|
(creatures still cross it): a root, a bank, the side of a ramp. Not
|
|
even a single cell of it is part of the network."""
|
|
return (self.b.ok(c[0], c[1], c[2]) and self.g.surface(c[0], c[1], c[2])[0] != 3
|
|
and self.sunk(c) is None)
|
|
|
|
def step_to(self, cell, d, same=True):
|
|
"""the usable cell a step leads to: of the same kind of ground (land
|
|
or water) for the inside of a rectangle, of either for a border. A
|
|
step onto the bed under water is a step into that water."""
|
|
b = self.b
|
|
for want in self.g.links(cell[0], cell[1], cell[2], d) or ():
|
|
t = b.step(cell[0], cell[1], cell[2], d, want)
|
|
if t is None:
|
|
continue
|
|
nc = (cell[0] + DI[d], cell[1] + DJ[d], t)
|
|
up = self.sunk(nc)
|
|
if up is not None:
|
|
nc = (nc[0], nc[1], up)
|
|
if self.usable(nc) and (not same or self.wet(nc) == self.wet(cell)):
|
|
return nc
|
|
return None
|
|
|
|
# -- rectangles ------------------------------------------------------------
|
|
def grow(self, c0, along, across):
|
|
"""rows of cells from c0: along one way while they join up, then
|
|
more rows the other way while every cell has its neighbour there"""
|
|
row = [c0]
|
|
while len(row) < MAX:
|
|
nc = self.step_to(row[-1], along)
|
|
if nc is None or nc in self.label:
|
|
break
|
|
row.append(nc)
|
|
rows = [row]
|
|
while len(rows) < MAX:
|
|
nxt = []
|
|
for cell in rows[-1]:
|
|
nc = self.step_to(cell, across)
|
|
if nc is None or nc in self.label or (nxt and self.step_to(nxt[-1], along) != nc):
|
|
nxt = None
|
|
break
|
|
nxt.append(nc)
|
|
if not nxt:
|
|
break
|
|
rows.append(nxt)
|
|
return rows
|
|
|
|
def build_rects(self):
|
|
started = time.time()
|
|
north, west = SIDES[0], SIDES[1]
|
|
self.rects = []
|
|
for key in sorted(self.g.raw.keys()):
|
|
bi, bj = key // 1024 - 512, key % 1024 - 512
|
|
for i in range(bi * BLOCK, (bi + 1) * BLOCK):
|
|
for j in range(bj * BLOCK, (bj + 1) * BLOCK):
|
|
for s in range(self.g.count(i, j)):
|
|
c0 = (i, j, s)
|
|
if c0 in self.label or not self.usable(c0):
|
|
continue
|
|
a = self.grow(c0, west, north) # rows along j, stacked along i
|
|
c = self.grow(c0, north, west) # rows along i, stacked along j
|
|
if len(c) * len(c[0]) > len(a) * len(a[0]):
|
|
h, w = len(c[0]), len(c)
|
|
cells = [cell for row in c for cell in row]
|
|
else:
|
|
h, w = len(a), len(a[0])
|
|
cells = [cell for row in a for cell in row]
|
|
k = len(self.rects)
|
|
for cell in cells:
|
|
self.label[cell] = k
|
|
self.rects.append({'i0': i, 'j0': j, 'h': h, 'w': w, 'cells': cells, 'water': self.wet(c0)})
|
|
steep = 0
|
|
for key in self.g.raw.keys():
|
|
bi, bj = key // 1024 - 512, key % 1024 - 512
|
|
for i in range(bi * BLOCK, (bi + 1) * BLOCK):
|
|
for j in range(bj * BLOCK, (bj + 1) * BLOCK):
|
|
for s in range(self.g.count(i, j)):
|
|
if self.g.surface(i, j, s)[0] == 3:
|
|
steep += 1
|
|
self.log(' %d rectangles, %d steep cells left out, %.0fs' % (len(self.rects), steep, time.time() - started))
|
|
|
|
def build_borders(self):
|
|
"""for each rectangle, the stretches of its sides you can cross into another"""
|
|
started = time.time()
|
|
jumps = []
|
|
for k, r in enumerate(self.rects):
|
|
at = {}
|
|
for cell in r['cells']:
|
|
at[(cell[0] - r['i0'], cell[1] - r['j0'])] = cell
|
|
r['at'] = at
|
|
runs = {}
|
|
for side in range(4):
|
|
if side == 0:
|
|
edge = [((r['h'] - 1, x), x) for x in range(r['w'])]
|
|
elif side == 1:
|
|
edge = [((x, r['w'] - 1), x) for x in range(r['h'])]
|
|
elif side == 2:
|
|
edge = [((0, x), x) for x in range(r['w'])]
|
|
else:
|
|
edge = [((x, 0), x) for x in range(r['h'])]
|
|
cur = None
|
|
for pos, x in edge:
|
|
nc = self.step_to(at[pos], SIDES[side], False)
|
|
o = self.label.get(nc) if nc is not None else None
|
|
if o is None or o == k:
|
|
cur = None
|
|
continue
|
|
# one step is never a climb of many yards: such a join
|
|
# is two levels at one spot (the top of a ramp and the
|
|
# ground under it) taken for one
|
|
za, zb = self.g.surface(*at[pos])[1], self.g.surface(*nc)[1]
|
|
if za is not None and zb is not None and abs(za - zb) > JUMP:
|
|
jumps.append(((nc[0] + 0.5) * CELL, (nc[1] + 0.5) * CELL, za, zb))
|
|
cur = None
|
|
continue
|
|
if cur is not None and cur[0] == o and cur[2] + cur[3] == x:
|
|
cur[3] += 1
|
|
else:
|
|
cur = [o, side, x, 1]
|
|
runs.setdefault((o, side), []).append(cur)
|
|
# every stretch you can cross, as
|
|
# [other, side, where the border's line is (cells from this rectangle's corner), start, length]
|
|
r['nb'] = []
|
|
for rs in runs.values():
|
|
for o, side, start, length in rs:
|
|
r['nb'].append([o, side, (r['h'], r['w'], 0, 0)[side], start, length])
|
|
self.log(' %d steps between ground more than %d yd apart in height left out' % (len(jumps), JUMP))
|
|
if jumps:
|
|
places = {}
|
|
for n, w, za, zb in jumps:
|
|
places.setdefault((int(n // 40), int(w // 40)), (n, w, za, zb))
|
|
for n, w, za, zb in sorted(places.values())[:12]:
|
|
self.log(' near %d N %d W: height %.0f against %.0f' % (n, w, za, zb))
|
|
# A border must be crossable both ways. Where a ramp or a ledge
|
|
# starts in the middle of a bigger rectangle of ground, only the ramp
|
|
# sees the border (it is on the ramp's side, but inside the ground's
|
|
# rectangle): the ground gets it too, as a line across its inside.
|
|
added = 0
|
|
for k, r in enumerate(self.rects):
|
|
for o, side, pos, start, length in list(r['nb']):
|
|
other = self.rects[o]
|
|
back = (side + 2) % 4
|
|
if any(q[0] == k and q[1] == back for q in other['nb']):
|
|
continue
|
|
if side in (0, 2):
|
|
line = r['i0'] + pos - other['i0']
|
|
first = r['j0'] + start - other['j0']
|
|
else:
|
|
line = r['j0'] + pos - other['j0']
|
|
first = r['i0'] + start - other['i0']
|
|
if 0 <= line <= MAX and 0 <= first <= MAX - 1:
|
|
other['nb'].append([k, back, line, first, length])
|
|
added += 1
|
|
if added:
|
|
self.log(' %d borders inside a rectangle (the foot of a ramp, a ledge) made two-way' % added)
|
|
self.log(' %d borders, %.0fs' % (sum(len(r['nb']) for r in self.rects) // 2, time.time() - started))
|
|
shore = sum(1 for r in self.rects for q in r['nb'] if r['water'] != self.rects[q[0]]['water']) // 2
|
|
beds = sum(1 for v in self.__dict__.get('sunken', {}).values() if v is not None)
|
|
self.log(' %d of them between land and water; %d cells of ground under water left out' % (shore, beds))
|
|
|
|
def cut(self, boxes):
|
|
"""leave out borders the movement maps join but a player cannot cross
|
|
(the face of a root, ground buried under a ramp): every border whose
|
|
middle lies in one of the boxes (n0, w0, n1, w1, z0, z1), from both
|
|
sides. With heights, only where both rectangles have ground between
|
|
z0 and z1, so the levels above or below at the same spot are kept."""
|
|
if not boxes:
|
|
return
|
|
|
|
def span(r):
|
|
if 'zspan' not in r:
|
|
hs = [h for h in (self.g.surface(*c)[1] for c in r['cells']) if h is not None]
|
|
r['zspan'] = (min(hs), max(hs)) if hs else None
|
|
return r['zspan']
|
|
|
|
def inz(r, b):
|
|
z = span(r)
|
|
return b[4] is None or z is None or (z[0] <= b[5] and z[1] >= b[4])
|
|
|
|
gone = 0
|
|
for r in self.rects:
|
|
keep = []
|
|
for q in r['nb']:
|
|
o, side, pos, start, length = q
|
|
if side in (0, 2):
|
|
n, w = (r['i0'] + pos) * CELL, (r['j0'] + start + length / 2.0) * CELL
|
|
else:
|
|
n, w = (r['i0'] + start + length / 2.0) * CELL, (r['j0'] + pos) * CELL
|
|
if any(b[0] <= n <= b[2] and b[1] <= w <= b[3] and inz(r, b) and inz(self.rects[o], b)
|
|
for b in boxes):
|
|
gone += 1
|
|
else:
|
|
keep.append(q)
|
|
r['nb'] = keep
|
|
self.log(' %d borders left out by tools/cuts.txt' % gone)
|
|
|
|
def prune(self):
|
|
"""leave out slivers at dead ends and cut-off bits of ground"""
|
|
dead = set()
|
|
changed = True
|
|
while changed:
|
|
changed = False
|
|
for k, r in enumerate(self.rects):
|
|
if k in dead or len(r['cells']) > SLIVER:
|
|
continue
|
|
if len(set(q[0] for q in r['nb'] if q[0] not in dead)) <= 1:
|
|
dead.add(k)
|
|
changed = True
|
|
slivers = len(dead)
|
|
seen = set()
|
|
for k in range(len(self.rects)):
|
|
if k in seen or k in dead:
|
|
continue
|
|
group = [k]
|
|
seen.add(k)
|
|
todo = [k]
|
|
while todo:
|
|
u = todo.pop()
|
|
for q in self.rects[u]['nb']:
|
|
if q[0] not in seen and q[0] not in dead:
|
|
seen.add(q[0])
|
|
group.append(q[0])
|
|
todo.append(q[0])
|
|
if sum(len(self.rects[x]['cells']) for x in group) < ISLAND:
|
|
dead.update(group)
|
|
index = {}
|
|
kept = []
|
|
for k, r in enumerate(self.rects):
|
|
if k not in dead:
|
|
index[k] = len(kept)
|
|
kept.append(r)
|
|
for r in kept:
|
|
r['nb'] = [[index[q[0]]] + q[1:] for q in r['nb'] if q[0] in index]
|
|
self.rects = kept
|
|
self.label = {c: index[k] for c, k in self.label.items() if k in index}
|
|
self.log(' %d slivers and %d cut-off rectangles left out, %d kept' % (slivers, len(dead) - slivers, len(kept)))
|
|
|
|
def finish(self):
|
|
"""what the test walks and the heights need of each rectangle"""
|
|
self.nodes = []
|
|
self.tiles = {}
|
|
for k, r in enumerate(self.rects):
|
|
mid = r['at'][(r['h'] // 2, r['w'] // 2)]
|
|
roads = sum(1 for c in r['cells'] if (c[0], c[1]) in self.b.road)
|
|
r['road'] = roads * 4 >= len(r['cells'])
|
|
r.update({'cell': mid, 'tile': (mid[0] // bp.TILE, mid[1] // bp.TILE), 'z': self.g.surface(*mid)[1]})
|
|
self.nodes.append(r)
|
|
self.tiles.setdefault(r['tile'], []).append(k)
|
|
self.heights()
|
|
# the borders as lines in the world: (left end, right end) seen from inside
|
|
for r in self.rects:
|
|
r['ports'] = [self.portal(r, q) for q in r['nb']]
|
|
|
|
def portal(self, r, q):
|
|
"""a border as the two ends of its line, in yards: (other, left, right)"""
|
|
_, side, pos, start, length = q
|
|
if length >= 3: # keep a cell away from each end where there is room
|
|
start, length = start + 1, length - 2
|
|
lo, hi = start + 0.5, start + length - 0.5
|
|
if side in (0, 2):
|
|
n = (r['i0'] + pos) * CELL
|
|
e0, e1 = (n, (r['j0'] + lo) * CELL), (n, (r['j0'] + hi) * CELL)
|
|
else:
|
|
w = (r['j0'] + pos) * CELL
|
|
e0, e1 = ((r['i0'] + lo) * CELL, w), ((r['i0'] + hi) * CELL, w)
|
|
# left and right as seen walking out through the side, and the way out
|
|
nrm = ((1, 0), (0, 1), (-1, 0), (0, -1))[side]
|
|
if side in (0, 3):
|
|
return (q[0], e1, e0, nrm)
|
|
return (q[0], e0, e1, nrm)
|
|
|
|
def pos(self, k):
|
|
i, j, _ = self.rects[k]['cell']
|
|
return (i + 0.5) * CELL, (j + 0.5) * CELL
|
|
|
|
# -- the data file ----------------------------------------------------------
|
|
def encode(self):
|
|
"""A block of 64 x 64 cells is one string, its rectangles one after the
|
|
other, from the south-east corner row by row:
|
|
corner: how far west (1 character) when it starts in the same
|
|
row as the one before; else rows on and how far west (2), or
|
|
a mark and both (3)
|
|
size, water, road and kind of heights (2)
|
|
heights where known (2): the lowest as steps from the rectangle
|
|
with heights before it, and how far up they go; or (4) a mark,
|
|
the lowest itself, and how far up
|
|
how many borders follow (1)
|
|
each border (2): the side, where on the side and how long, and
|
|
the rectangle beyond as steps on or back in this list; or (4)
|
|
the same without the steps, then which block and the place in
|
|
its list; or (7) with a mark where that place is past 920
|
|
Every border is written once, by a rectangle that has it on one of
|
|
its own sides; paths.lua gives it to the other rectangle too."""
|
|
blocks = {}
|
|
for k, r in enumerate(self.rects):
|
|
blocks.setdefault((r['i0'] // BLOCK, r['j0'] // BLOCK), []).append(k)
|
|
local = {}
|
|
for key, ks in blocks.items():
|
|
ks.sort(key=lambda k: (self.rects[k]['i0'], self.rects[k]['j0'], k))
|
|
for x, k in enumerate(ks):
|
|
local[k] = x
|
|
|
|
# each border once: by the rectangle that has it on its own side (the
|
|
# lower numbered one when both do)
|
|
def where(k, q):
|
|
r = self.rects[k]
|
|
_, side, pos, start, length = q
|
|
if side in (0, 2):
|
|
return ('n', r['i0'] + pos, r['j0'] + start, length)
|
|
return ('w', r['j0'] + pos, r['i0'] + start, length)
|
|
|
|
def own(k, q):
|
|
r = self.rects[k]
|
|
return q[2] == (r['h'], r['w'], 0, 0)[q[1]]
|
|
|
|
keep = {}
|
|
for k, r in enumerate(self.rects):
|
|
for q in r['nb']:
|
|
key = (min(k, q[0]), max(k, q[0])) + where(k, q)
|
|
if own(k, q) and (key not in keep or k < keep[key][0]):
|
|
keep[key] = (k, q)
|
|
writes = {}
|
|
for k, q in keep.values():
|
|
writes.setdefault(k, []).append(q)
|
|
lost = sum(len(r['nb']) for r in self.rects) - 2 * len(keep)
|
|
|
|
size = {'rectangles': 0, 'borders': 0}
|
|
count = {'short': 0, 'long': 0, 'zshort': 0, 'zlong': 0}
|
|
out = {}
|
|
for key, ks in sorted(blocks.items()):
|
|
parts = []
|
|
prev = None
|
|
row = 0
|
|
for k in ks:
|
|
r = self.rects[k]
|
|
kind = r['zkind']
|
|
flags = (1 if r['water'] else 0) + (2 if r['road'] else 0) + 4 * kind
|
|
# the corner: in the row of the one before, only how far west (1);
|
|
# else how many rows on and how far west (2), or a mark and both (3)
|
|
li, lj = r['i0'] - key[0] * BLOCK, r['j0'] - key[1] * BLOCK
|
|
if li == row:
|
|
rec = bw.enc(lj)
|
|
elif li - row <= 26:
|
|
rec = bw.enc(63 + li - row) + bw.enc(lj)
|
|
else:
|
|
rec = bw.enc(90) + bw.enc(li) + bw.enc(lj)
|
|
row = li
|
|
rec += bw.num(((r['h'] - 1) * 16 + (r['w'] - 1)) * 12 + flags, 2)
|
|
if kind:
|
|
lo = max(0, min(8280, int(math.floor(r['zlo'])) + 2000))
|
|
up = bw.enc(max(0, min(90, int(math.ceil(r['zhi'])) + 2000 - lo)))
|
|
d = None if prev is None else lo - prev
|
|
zig = None if d is None else (2 * d if d >= 0 else -2 * d - 1)
|
|
if zig is not None and zig < 90:
|
|
rec += bw.enc(zig) + up
|
|
count['zshort'] += 1
|
|
else:
|
|
rec += bw.enc(90) + bw.num(lo, 2) + up
|
|
count['zlong'] += 1
|
|
prev = lo
|
|
nb = []
|
|
for o, side, pos, start, length in sorted(writes.get(k, [])):
|
|
ok = (self.rects[o]['i0'] // BLOCK, self.rects[o]['j0'] // BLOCK)
|
|
di, dj = ok[0] - key[0], ok[1] - key[1]
|
|
L = r['w'] if side in (0, 2) else r['h']
|
|
assert abs(di) <= 1 and abs(dj) <= 1 and start + length <= L
|
|
T = L * (L + 1) // 2
|
|
run = start * L - start * (start - 1) // 2 + (length - 1) # 0..T-1
|
|
far = FAR // (4 * T) - 1
|
|
d = local[o] - local[k]
|
|
step = (2 * d - 1 if d > 0 else -2 * d)
|
|
if di == 0 and dj == 0 and step <= far:
|
|
nb.append(bw.num((step * T + run) * 4 + side, 2))
|
|
count['short'] += 1
|
|
else:
|
|
blk = (di + 1) * 3 + (dj + 1)
|
|
if local[o] < NEAR:
|
|
nb.append(bw.num(run * 4 + side, 2) + bw.num(blk * NEAR + local[o], 2))
|
|
else:
|
|
nb.append(bw.num(run * 4 + side, 2) + bw.num(FAR - 1, 2) + bw.num(local[o], 2) + bw.enc(blk))
|
|
count['long'] += 1
|
|
assert len(nb) <= 90, 'a rectangle with more than 90 borders'
|
|
rec += bw.enc(len(nb))
|
|
size['rectangles'] += len(rec)
|
|
size['borders'] += sum(len(x) for x in nb)
|
|
parts.append(rec + ''.join(nb))
|
|
out[key] = ''.join(parts)
|
|
if lost:
|
|
# the two rectangles see different stretches of it: both are written
|
|
self.log(' %d borders seen differently from their two sides, written from both' % -lost)
|
|
self.log(' characters: %s' % ', '.join('%s %d' % kv for kv in size.items()))
|
|
self.log(' written short and long: borders %d and %d, heights %d and %d' % (
|
|
count['short'], count['long'], count['zshort'], count['zlong']))
|
|
return out
|
|
|
|
# -- the arrow's own rules, for the test walks (paths.lua does the same) -----
|
|
def factor(self, k):
|
|
r = self.rects[k]
|
|
return (WATER if r['water'] else 1.0) * (ROAD if r['road'] else 1.0)
|
|
|
|
def plan(self, a, starts, b_, goals):
|
|
goals = set(goals)
|
|
g, entry, prev = {}, {}, {}
|
|
heap = []
|
|
for k in starts:
|
|
g[k] = 0.0
|
|
entry[k] = a
|
|
heapq.heappush(heap, (math.hypot(a[0] - b_[0], a[1] - b_[1]) * ROAD, k))
|
|
best, bestk = None, None
|
|
done = set()
|
|
while heap:
|
|
f, u = heapq.heappop(heap)
|
|
if best is not None and f >= best:
|
|
break
|
|
if u in done:
|
|
continue
|
|
done.add(u)
|
|
e = entry[u]
|
|
if u in goals:
|
|
total = g[u] + math.hypot(e[0] - b_[0], e[1] - b_[1]) * self.factor(u)
|
|
if best is None or total < best:
|
|
best, bestk = total, u
|
|
for x, (o, left, right, _) in enumerate(self.rects[u]['ports']):
|
|
if o in done:
|
|
continue
|
|
# the spot of the border nearest to where this rectangle was entered
|
|
dn, dw = right[0] - left[0], right[1] - left[1]
|
|
l2 = dn * dn + dw * dw
|
|
t = max(0.0, min(1.0, ((e[0] - left[0]) * dn + (e[1] - left[1]) * dw) / l2)) if l2 > 0 else 0.0
|
|
q = (left[0] + dn * t, left[1] + dw * t)
|
|
cand = g[u] + (math.hypot(q[0] - e[0], q[1] - e[1]) + 0.1) * self.factor(u)
|
|
if cand < g.get(o, 1e30):
|
|
g[o] = cand
|
|
entry[o] = q
|
|
prev[o] = (u, x)
|
|
heapq.heappush(heap, (cand + math.hypot(q[0] - b_[0], q[1] - b_[1]) * ROAD, o))
|
|
if bestk is None:
|
|
return None
|
|
chain = [bestk]
|
|
ports = []
|
|
while chain[-1] in prev:
|
|
u, x = prev[chain[-1]]
|
|
_, left, right, nrm = self.rects[u]['ports'][x]
|
|
ports.append((left, right, nrm))
|
|
chain.append(u)
|
|
chain.reverse()
|
|
ports.reverse()
|
|
self.route = set(chain)
|
|
self.order = dict((k, x) for x, k in enumerate(chain))
|
|
self.at = 0
|
|
pts = funnel(a, ports, b_)
|
|
self.pz = {}
|
|
self.isvia = set()
|
|
self.tight = set(range(1, len(pts) - 1)) - jogs(pts)
|
|
return pts
|
|
|
|
def move(self, cell, ni, nj):
|
|
"""a step of the test walker. Where two levels start from one cell
|
|
(the foot of a ramp) you go onto the one your walk goes over: the
|
|
rectangle you are in, or the next ones of the chain."""
|
|
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):
|
|
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)
|
|
at = self.order.get(self.label.get(nc))
|
|
# onto the next rectangle of the walk where the step can lead there (a ramp's foot:
|
|
# you go up it, not under it), else on in this one, else whatever is nearest in the chain
|
|
if at is None:
|
|
score = 1000
|
|
elif at == self.at + 1:
|
|
score = 0
|
|
elif at >= self.at:
|
|
score = 1 + at - self.at
|
|
else:
|
|
score = 500 + self.at - at
|
|
if bests is None or score < bests:
|
|
best, bests = nc, score
|
|
return best
|
|
if di and dj:
|
|
end = None
|
|
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:
|
|
break
|
|
else:
|
|
end = one(cell, direction(di, dj))
|
|
if end is not None:
|
|
at = self.order.get(self.label.get(end))
|
|
if at is not None and at > self.at:
|
|
self.at = at
|
|
return end
|
|
|
|
|
|
def write(path, maps, log):
|
|
lines = [
|
|
'-- pfQuest SmartArrow: path network',
|
|
'-- Built by tools/bake_rects.py from a navmesh of the server\'s movement maps:',
|
|
'-- the walkable ground as rectangles of 4 yard cells you can walk straight',
|
|
'-- across, and the borders between them. Coordinates and connections only.',
|
|
'pfQuestSmartArrowData = pfQuestSmartArrowData or {}',
|
|
'pfQuestSmartArrowData.paths = { version = %d, cell = %d, block = %d }' % (FORMAT, int(CELL), BLOCK),
|
|
]
|
|
for c, blocks in sorted(maps.items()):
|
|
lines.append('pfQuestSmartArrowData.paths[%d] = {' % c)
|
|
for (bi, bj), s in sorted(blocks.items()):
|
|
lines.append('["%d:%d"]="%s",' % (bi, bj, 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 load_cuts(addon):
|
|
"""tools/cuts.txt: lines of 'map n0 w0 n1 w1 [z0 z1] note' -> {map: [(n0, w0, n1, w1, z0, z1)]}"""
|
|
cuts = {}
|
|
path = os.path.join(addon, 'tools', 'cuts.txt')
|
|
if not os.path.exists(path):
|
|
return cuts
|
|
|
|
def num(x):
|
|
try:
|
|
return float(x)
|
|
except ValueError:
|
|
return None
|
|
|
|
with open(path, encoding='utf-8') as f:
|
|
for line in f:
|
|
line = line.split('#')[0].split()
|
|
if len(line) < 5:
|
|
continue
|
|
m = int(line[0])
|
|
n0, w0, n1, w1 = [float(x) for x in line[1:5]]
|
|
z0 = num(line[5]) if len(line) > 6 else None
|
|
z1 = num(line[6]) if len(line) > 6 else None
|
|
if z0 is None or z1 is None:
|
|
z0 = z1 = None
|
|
else:
|
|
z0, z1 = min(z0, z1), max(z0, z1)
|
|
cuts.setdefault(m, []).append((min(n0, n1), min(w0, w1), max(n0, n1), max(w0, w1), z0, z1))
|
|
return cuts
|
|
|
|
|
|
def build(grid, solids, roads, log, cuts=None):
|
|
net = RectNet(grid, solids, roads, log)
|
|
net.build_rects()
|
|
net.build_borders()
|
|
net.cut(cuts)
|
|
net.prune()
|
|
net.finish()
|
|
return net
|
|
|
|
|
|
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)
|
|
cuts = load_cuts(addon)
|
|
out, nets = {}, {}
|
|
for c, blocks in sorted(maps.items()):
|
|
if not blocks:
|
|
continue
|
|
log('Map %d: %d navmesh blocks' % (c, len(blocks)))
|
|
net = build(bw.Grid(blocks), solids.get(c, []), roads.get(c, []), log, cuts.get(c))
|
|
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()
|