1204 lines
53 KiB
Python
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()
|