Files

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