958 lines
36 KiB
Python
958 lines
36 KiB
Python
#!/usr/bin/env python3
|
|
# pfQuest SmartArrow: navmesh baker
|
|
# Copyright (C) 2026 pfQuest SmartArrow contributors
|
|
#
|
|
# This program is free software: you can redistribute it and/or modify
|
|
# it under the terms of the GNU General Public License as published by
|
|
# the Free Software Foundation, either version 3 of the License, or
|
|
# (at your option) any later version.
|
|
#
|
|
# This program is distributed in the hope that it will be useful,
|
|
# but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
# GNU General Public License for more details.
|
|
#
|
|
# You should have received a copy of the GNU General Public License
|
|
# along with this program. If not, see <https://www.gnu.org/licenses/>.
|
|
"""
|
|
Turns a classic server's movement maps (the .mmtile files that CMaNGOS,
|
|
VMaNGOS and similar cores build from the game client with MoveMapGen, and
|
|
use to move pets and NPCs) into a compact walk grid for pfQuest SmartArrow.
|
|
|
|
The output is a separate load-on-demand addon, pfQuest-SmartArrow-Navmesh.
|
|
It is built from your own game files, so keep it for yourself rather than
|
|
sharing it.
|
|
|
|
python bake_navmesh.py PATH/TO/mmaps --out PATH/TO/Interface/AddOns
|
|
|
|
Only Python 3.6+ is needed, no extra packages. A full build of Eastern
|
|
Kingdoms and Kalimdor takes a while (tens of minutes); it prints progress.
|
|
|
|
What is stored, for every 4 x 4 yard cell:
|
|
- which surfaces you can stand on there (more than one where a bridge,
|
|
a ramp, a building floor or a cave overlaps other ground),
|
|
- what each is (ground, steep ground, water),
|
|
- and which surfaces of the neighbouring cells you can walk to.
|
|
"""
|
|
|
|
import argparse
|
|
import math
|
|
import os
|
|
import re
|
|
import struct
|
|
import sys
|
|
import time
|
|
from array import array
|
|
|
|
CELL = 4.0 # yards per cell
|
|
BLOCK = 64 # cells per block side (256 yards)
|
|
LAYER_GAP = 4.0 # surfaces further apart than this are separate levels:
|
|
# a character needs about this much room to stand
|
|
# under something, so steep ground stays one level
|
|
SAME_GAP = 1.0 # spots this close in height are one surface whatever the navmesh says
|
|
STEP_FLAT = 1.6 # rise between neighbouring cells that is always walkable
|
|
STEP_POLY = 4.5 # rise allowed when the navmesh joins the two spots
|
|
MMAP_MAGIC = 0x4D4D4150 # 'MMAP'
|
|
DT_MAGIC = (ord('D') << 24) | (ord('N') << 16) | (ord('A') << 8) | ord('V')
|
|
DT_EXT_LINK = 0x8000
|
|
MAPS = (0, 1) # Eastern Kingdoms, Kalimdor
|
|
REGION = 20 # cells looked at around each block when judging reachability
|
|
ISLAND = 16 # a patch this many cells across or less, not joined to the
|
|
# ground around it, is a roof, a canopy or a rock top
|
|
MAX_LEVELS = 8
|
|
|
|
# surface classes stored in the grid
|
|
C_NONE, C_GROUND, C_WATER, C_STEEP = 0, 1, 2, 3
|
|
CODE_COMPLEX = 4
|
|
|
|
# 91 printable characters that need no escaping inside "..." in Lua
|
|
ALPHABET = ''.join(chr(c) for c in range(35, 127) if c != 92)
|
|
assert len(ALPHABET) == 91
|
|
SEP = '!'
|
|
|
|
|
|
def enc(v):
|
|
return ALPHABET[v]
|
|
|
|
|
|
def num2(n):
|
|
assert 0 <= n < 91 * 91, n
|
|
return ALPHABET[n // 91] + ALPHABET[n % 91]
|
|
|
|
|
|
def align4(n):
|
|
return (n + 3) & ~3
|
|
|
|
|
|
# ---------------------------------------------------------------- tile files
|
|
|
|
TILE_NAMES = (
|
|
re.compile(r'^(\d{3})(\d{2})(\d{2})\.mmtile$', re.I), # CMaNGOS/VMaNGOS: MMMXXYY
|
|
re.compile(r'^(\d{4})_(\d{2})_(\d{2})\.mmtile$', re.I), # newer TrinityCore: MMMM_XX_YY
|
|
)
|
|
|
|
|
|
def find_tiles(folder):
|
|
found = {}
|
|
for name in os.listdir(folder):
|
|
for pat in TILE_NAMES:
|
|
m = pat.match(name)
|
|
if m:
|
|
mapid, tx, ty = int(m.group(1)), int(m.group(2)), int(m.group(3))
|
|
if mapid in MAPS:
|
|
found.setdefault(mapid, []).append((tx, ty, os.path.join(folder, name)))
|
|
break
|
|
return found
|
|
|
|
|
|
class Tile:
|
|
"""One navmesh tile: its detail triangles (in Recast axes: x, y up, z)."""
|
|
|
|
__slots__ = ('path', 'bmin', 'bmax', 'tris', 'tpoly', 'tarea', 'neigh',
|
|
'extedge', 'polycount', 'linksize', 'uid', 'buckets',
|
|
'verts', 'pverts', 'pneis', 'wv')
|
|
|
|
def __init__(self, path, uid):
|
|
self.path = path
|
|
self.uid = uid
|
|
self.buckets = None
|
|
with open(path, 'rb') as f:
|
|
data = f.read()
|
|
self.parse(data)
|
|
|
|
@staticmethod
|
|
def read_header(path):
|
|
"""Only the bounding box, for indexing tiles quickly."""
|
|
with open(path, 'rb') as f:
|
|
head = f.read(20 + 100)
|
|
off = Tile.data_offset(head)
|
|
if off is None or len(head) < off + 100:
|
|
return None
|
|
vals = struct.unpack_from('<15i3f3f3ff', head, off)
|
|
if vals[0] != DT_MAGIC:
|
|
return None
|
|
return (vals[18], vals[19], vals[20]), (vals[21], vals[22], vals[23])
|
|
|
|
@staticmethod
|
|
def data_offset(head):
|
|
# MmapTileHeader: magic, dtVersion, mmapVersion, size, usesLiquids (+pad) = 20 bytes.
|
|
# Some older builds wrote a 16 byte header; look for the Detour magic to be sure.
|
|
if len(head) >= 4 and struct.unpack_from('<I', head, 0)[0] == MMAP_MAGIC:
|
|
for off in (20, 16, 24):
|
|
if len(head) >= off + 4 and struct.unpack_from('<i', head, off)[0] == DT_MAGIC:
|
|
return off
|
|
if len(head) >= 4 and struct.unpack_from('<i', head, 0)[0] == DT_MAGIC:
|
|
return 0 # bare Detour tile
|
|
return None
|
|
|
|
def parse(self, data):
|
|
off = Tile.data_offset(data)
|
|
if off is None:
|
|
raise ValueError('not a navmesh tile: %s' % self.path)
|
|
h = struct.unpack_from('<15i3f3f3ff', data, off)
|
|
(magic, version, tx, ty, layer, userid, polycount, vertcount, maxlinks,
|
|
dmeshcount, dvertcount, dtricount, bvcount, offmeshcount, offmeshbase) = h[:15]
|
|
self.bmin = (h[18], h[19], h[20])
|
|
self.bmax = (h[21], h[22], h[23])
|
|
self.polycount = polycount
|
|
base = off + align4(100)
|
|
verts = struct.unpack_from('<%df' % (vertcount * 3), data, base)
|
|
p_off = base + align4(12 * vertcount)
|
|
polys = []
|
|
for i in range(polycount):
|
|
rec = struct.unpack_from('<I6H6HHBB', data, p_off + 32 * i)
|
|
polys.append(rec)
|
|
|
|
# The link record is 12 bytes with 32-bit polygon references and 16
|
|
# with 64-bit ones; servers differ. Take the one the rest makes sense
|
|
# with.
|
|
for linksize in (12, 16):
|
|
d_off = p_off + align4(32 * polycount) + align4(linksize * maxlinks)
|
|
dv_off = d_off + align4(12 * dmeshcount)
|
|
dt_off = dv_off + align4(12 * dvertcount)
|
|
end = dt_off + align4(4 * dtricount)
|
|
if end > len(data):
|
|
continue
|
|
ok = True
|
|
dmeshes = []
|
|
for i in range(dmeshcount):
|
|
vb, tb, vc, tc = struct.unpack_from('<IIBB', data, d_off + 12 * i)
|
|
if vb + vc > dvertcount or tb + tc > dtricount:
|
|
ok = False
|
|
break
|
|
dmeshes.append((vb, tb, vc, tc))
|
|
if ok:
|
|
break
|
|
else:
|
|
raise ValueError('could not read detail meshes in %s' % self.path)
|
|
self.linksize = linksize
|
|
dverts = struct.unpack_from('<%df' % (dvertcount * 3), data, dv_off) if dvertcount else ()
|
|
dtris = data[dt_off:dt_off + 4 * dtricount]
|
|
|
|
tris = array('f')
|
|
tpoly = array('i')
|
|
tarea = array('B')
|
|
neigh = []
|
|
extedge = []
|
|
self.verts = verts
|
|
self.pverts = []
|
|
self.pneis = []
|
|
self.wv = None
|
|
for pi, rec in enumerate(polys):
|
|
firstlink = rec[0]
|
|
pverts = rec[1:7]
|
|
neis = rec[7:13]
|
|
flags, nv, area_type = rec[13], rec[14], rec[15]
|
|
self.pverts.append(pverts[:nv])
|
|
self.pneis.append(neis[:nv])
|
|
ptype = area_type >> 6
|
|
area = area_type & 0x3F
|
|
nb = set()
|
|
ext = False
|
|
for e in range(nv):
|
|
n = neis[e]
|
|
if n & DT_EXT_LINK:
|
|
ext = True
|
|
elif n:
|
|
nb.add(n - 1)
|
|
neigh.append(nb)
|
|
extedge.append(ext)
|
|
if ptype != 0 or pi >= len(dmeshes):
|
|
continue # off-mesh connection
|
|
vb, tb, vc, tc = dmeshes[pi]
|
|
|
|
def vert(k):
|
|
if k < nv:
|
|
j = pverts[k] * 3
|
|
return verts[j], verts[j + 1], verts[j + 2]
|
|
j = (vb + k - nv) * 3
|
|
return dverts[j], dverts[j + 1], dverts[j + 2]
|
|
|
|
if tc == 0:
|
|
# no detail triangles: fan the polygon
|
|
for k in range(1, nv - 1):
|
|
a, b, c = vert(0), vert(k), vert(k + 1)
|
|
tris.extend(a + b + c)
|
|
tpoly.append(pi)
|
|
tarea.append(area)
|
|
continue
|
|
for t in range(tc):
|
|
o = (tb + t) * 4
|
|
i0, i1, i2 = dtris[o], dtris[o + 1], dtris[o + 2]
|
|
if max(i0, i1, i2) >= nv + vc:
|
|
continue
|
|
a, b, c = vert(i0), vert(i1), vert(i2)
|
|
tris.extend(a + b + c)
|
|
tpoly.append(pi)
|
|
tarea.append(area)
|
|
self.tris, self.tpoly, self.tarea = tris, tpoly, tarea
|
|
self.neigh, self.extedge = neigh, extedge
|
|
|
|
def count(self):
|
|
return len(self.tpoly)
|
|
|
|
def world_verts(self, m):
|
|
"""The polygon corners in world (north, west), for walking lines."""
|
|
if self.wv is None or self.wv[0] != m:
|
|
v = self.verts
|
|
self.wv = (m, [to_world(m, v[k * 3], v[k * 3 + 2]) for k in range(len(v) // 3)])
|
|
return self.wv[1]
|
|
|
|
|
|
class TileCache:
|
|
def __init__(self, limit=160):
|
|
self.limit = limit
|
|
self.tiles = {}
|
|
self.order = []
|
|
self.next_uid = 1
|
|
|
|
def get(self, path):
|
|
t = self.tiles.get(path)
|
|
if t is None:
|
|
t = Tile(path, self.next_uid)
|
|
self.next_uid += 1
|
|
self.tiles[path] = t
|
|
self.order.append(path)
|
|
if len(self.order) > self.limit:
|
|
old = self.order.pop(0)
|
|
del self.tiles[old]
|
|
return t
|
|
|
|
|
|
# ---------------------------------------------------------- axes and classes
|
|
|
|
# How Recast's horizontal axes (x, z) map onto the addon's world axes
|
|
# (north, west). MaNGOS-style cores use x = west, z = north; the baker
|
|
# checks this against walking-network points known to be on the ground.
|
|
MAPPINGS = []
|
|
for swap in (True, False):
|
|
for sn in (1, -1):
|
|
for sw in (1, -1):
|
|
MAPPINGS.append((swap, sn, sw))
|
|
|
|
|
|
def to_world(m, rx, rz):
|
|
swap, sn, sw = m
|
|
if swap:
|
|
return sn * rz, sw * rx
|
|
return sn * rx, sw * rz
|
|
|
|
|
|
def to_recast(m, n, w):
|
|
swap, sn, sw = m
|
|
if swap:
|
|
return sw * w, sn * n # rx, rz
|
|
return sn * n, sw * w
|
|
|
|
|
|
class AreaScheme:
|
|
"""Polygon area ids differ between cores; work out which set is in use."""
|
|
|
|
def __init__(self, histogram):
|
|
self.hist = histogram
|
|
total = sum(histogram.values()) or 1
|
|
newstyle = sum(v for k, v in histogram.items() if k >= 8) / total
|
|
self.newstyle = newstyle > 0.5
|
|
self.name = 'TrinityCore-style (ground 11, steep 10, water 9, magma/slime 8)' if self.newstyle \
|
|
else 'MaNGOS-style flags (ground 1, magma 2, slime 4, water 8)'
|
|
|
|
def classify(self, area):
|
|
if self.newstyle:
|
|
if area == 11 or area == 0:
|
|
return C_GROUND
|
|
if area == 10:
|
|
return C_STEEP
|
|
if area == 9:
|
|
return C_WATER
|
|
if area == 8:
|
|
return C_NONE
|
|
return C_GROUND
|
|
if area & 0x06:
|
|
return C_NONE # magma, slime
|
|
if area & 0x08:
|
|
return C_WATER
|
|
return C_GROUND
|
|
|
|
|
|
# ------------------------------------------------------------ rasterising
|
|
|
|
def point_in_tri(px, pz, ax, az, bx, bz, cx, cz):
|
|
d = (bz - cz) * (ax - cx) + (cx - bx) * (az - cz)
|
|
if d == 0:
|
|
return None
|
|
l1 = ((bz - cz) * (px - cx) + (cx - bx) * (pz - cz)) / d
|
|
l2 = ((cz - az) * (px - cx) + (ax - cx) * (pz - cz)) / d
|
|
l3 = 1.0 - l1 - l2
|
|
e = -1e-4
|
|
if l1 < e or l2 < e or l3 < e:
|
|
return None
|
|
return l1, l2, l3
|
|
|
|
|
|
def tile_buckets(tile, m, size=32.0):
|
|
"""Triangles of a tile binned by world (north, west) squares."""
|
|
if tile.buckets is not None and tile.buckets[0] == m:
|
|
return tile.buckets[1]
|
|
b = {}
|
|
tr = tile.tris
|
|
for t in range(tile.count()):
|
|
o = t * 9
|
|
n1, w1 = to_world(m, tr[o], tr[o + 2])
|
|
n2, w2 = to_world(m, tr[o + 3], tr[o + 5])
|
|
n3, w3 = to_world(m, tr[o + 6], tr[o + 8])
|
|
for bn in range(int(math.floor(min(n1, n2, n3) / size)), int(math.floor(max(n1, n2, n3) / size)) + 1):
|
|
for bw in range(int(math.floor(min(w1, w2, w3) / size)), int(math.floor(max(w1, w2, w3) / size)) + 1):
|
|
b.setdefault((bn, bw), []).append(t)
|
|
tile.buckets = (m, b)
|
|
return b
|
|
|
|
|
|
def on_mesh(tile, m, n, w):
|
|
"""Is the spot (north, west) on this tile's mesh (any height)?"""
|
|
b = tile_buckets(tile, m)
|
|
lst = b.get((int(math.floor(n / 32.0)), int(math.floor(w / 32.0))))
|
|
if not lst:
|
|
return False
|
|
tr = tile.tris
|
|
for t in lst:
|
|
o = t * 9
|
|
n1, w1 = to_world(m, tr[o], tr[o + 2])
|
|
n2, w2 = to_world(m, tr[o + 3], tr[o + 5])
|
|
n3, w3 = to_world(m, tr[o + 6], tr[o + 8])
|
|
if point_in_tri(n, w, n1, w1, n2, w2, n3, w3):
|
|
return True
|
|
return False
|
|
|
|
|
|
class Index:
|
|
"""Which tiles cover which part of the world, per map."""
|
|
|
|
def __init__(self, tiles):
|
|
self.entries = [] # (bmin, bmax, path)
|
|
for tx, ty, path in tiles:
|
|
hb = Tile.read_header(path)
|
|
if hb:
|
|
self.entries.append((hb[0], hb[1], path))
|
|
|
|
def at_recast(self, rx, rz):
|
|
for bmin, bmax, path in self.entries:
|
|
if bmin[0] - 1 <= rx <= bmax[0] + 1 and bmin[2] - 1 <= rz <= bmax[2] + 1:
|
|
yield path
|
|
|
|
def world_boxes(self, m):
|
|
out = []
|
|
for bmin, bmax, path in self.entries:
|
|
n1, w1 = to_world(m, bmin[0], bmin[2])
|
|
n2, w2 = to_world(m, bmax[0], bmax[2])
|
|
out.append((min(n1, n2), max(n1, n2), min(w1, w2), max(w1, w2), path))
|
|
return out
|
|
|
|
|
|
def walknet_points(addon_dir):
|
|
"""Ground truth: the walking network's points are on walkable ground."""
|
|
path = os.path.join(addon_dir, 'data', 'walknet.lua')
|
|
pts = {0: [], 1: []}
|
|
if not os.path.exists(path):
|
|
return pts
|
|
with open(path, encoding='utf-8', errors='replace') as f:
|
|
text = f.read()
|
|
m = re.search(r'nodes\s*=\s*\[\[(.*?)\]\]', text, re.S)
|
|
if not m:
|
|
return pts
|
|
for line in m.group(1).splitlines():
|
|
parts = line.split()
|
|
if len(parts) >= 5:
|
|
try:
|
|
c, n, w = int(parts[2]), float(parts[3]), float(parts[4])
|
|
except ValueError:
|
|
continue
|
|
if c in pts:
|
|
pts[c].append((n, w))
|
|
return pts
|
|
|
|
|
|
def detect_mapping(index, cache, points, log):
|
|
if not points:
|
|
log(' no walking-network points to check axes against; assuming x = west, z = north')
|
|
return MAPPINGS[0], None
|
|
sample = points[::max(1, len(points) // 150)][:150]
|
|
scores = []
|
|
for m in MAPPINGS:
|
|
hits = 0
|
|
for n, w in sample:
|
|
rx, rz = to_recast(m, n, w)
|
|
for path in index.at_recast(rx, rz):
|
|
if on_mesh(cache.get(path), m, n, w):
|
|
hits += 1
|
|
break
|
|
scores.append((hits / len(sample), m))
|
|
scores.sort(reverse=True)
|
|
best, second = scores[0], scores[1]
|
|
log(' axis check: %.0f%% of %d walking-network points on the mesh (next best %.0f%%)'
|
|
% (best[0] * 100, len(sample), second[0] * 100))
|
|
if best[0] < 0.5 or best[0] - second[0] < 0.15:
|
|
raise SystemExit('Could not work out how the navmesh lines up with the world '
|
|
'(best match only %.0f%%). Are these 1.12 movement maps?' % (best[0] * 100))
|
|
return best[1], best[0]
|
|
|
|
|
|
def raster_block(bi, bj, triangles, scheme, margin):
|
|
"""Surfaces for the cells of one block plus a margin of cells.
|
|
|
|
triangles: list of (tile, t, m). Returns {(i, j): [surface, ...]},
|
|
surface = [height, class, polys(set of (uid, poly)), samples].
|
|
"""
|
|
i0, j0 = bi * BLOCK - margin, bj * BLOCK - margin
|
|
i1, j1 = i0 + BLOCK + 2 * margin, j0 + BLOCK + 2 * margin # exclusive
|
|
nmin, nmax = i0 * CELL, i1 * CELL
|
|
wmin, wmax = j0 * CELL, j1 * CELL
|
|
samples = {}
|
|
for tile, t, m in triangles:
|
|
tr = tile.tris
|
|
o = t * 9
|
|
n1, w1 = to_world(m, tr[o], tr[o + 2])
|
|
n2, w2 = to_world(m, tr[o + 3], tr[o + 5])
|
|
n3, w3 = to_world(m, tr[o + 6], tr[o + 8])
|
|
y1, y2, y3 = tr[o + 1], tr[o + 4], tr[o + 7]
|
|
cls = scheme.classify(tile.tarea[t])
|
|
if cls == C_NONE:
|
|
continue
|
|
poly = (tile.uid, tile.tpoly[t])
|
|
lo_n, hi_n = max(min(n1, n2, n3), nmin), min(max(n1, n2, n3), nmax)
|
|
lo_w, hi_w = max(min(w1, w2, w3), wmin), min(max(w1, w2, w3), wmax)
|
|
if lo_n > hi_n or lo_w > hi_w:
|
|
continue
|
|
# sample lattice: odd yards (two samples per cell each way)
|
|
kn0 = int(math.ceil((lo_n - 1) / 2.0))
|
|
kn1 = int(math.floor((hi_n - 1) / 2.0))
|
|
kw0 = int(math.ceil((lo_w - 1) / 2.0))
|
|
kw1 = int(math.floor((hi_w - 1) / 2.0))
|
|
for kn in range(kn0, kn1 + 1):
|
|
pn = kn * 2 + 1
|
|
ci = kn >> 1
|
|
if ci < i0 or ci >= i1:
|
|
continue
|
|
for kw in range(kw0, kw1 + 1):
|
|
pw = kw * 2 + 1
|
|
cj = kw >> 1
|
|
if cj < j0 or cj >= j1:
|
|
continue
|
|
l = point_in_tri(pn, pw, n1, w1, n2, w2, n3, w3)
|
|
if l:
|
|
h = l[0] * y1 + l[1] * y2 + l[2] * y3
|
|
samples.setdefault((ci, cj), []).append((h, cls, poly, pn, pw))
|
|
cells = {}
|
|
for key, lst in samples.items():
|
|
lst.sort(key=lambda s: s[0])
|
|
surfs = []
|
|
for h, cls, poly, pn, pw in lst:
|
|
# One surface: spots close in height that the navmesh joins (the
|
|
# same polygon, or a straight walk over it from one to the other).
|
|
# Two spots a yard or two apart in height but on polygons that do
|
|
# not join are two surfaces: a ramp just above the ground, a root,
|
|
# a ledge. Taken as one they would make a way up where there is none.
|
|
s = None
|
|
for cand in reversed(surfs):
|
|
if h - cand[4] > LAYER_GAP:
|
|
break
|
|
if (h - cand[4] <= SAME_GAP or poly in cand[2]
|
|
or walk_line(cand[6], (pn, pw), {poly}) or walk_line((pn, pw, poly), cand[6], cand[2])):
|
|
s = cand
|
|
break
|
|
if s is not None:
|
|
s[0] += h
|
|
s[3] += 1
|
|
s[4] = h
|
|
s[2].add(poly)
|
|
s[5].add(cls)
|
|
else:
|
|
surfs.append([h, cls, {poly}, 1, h, {cls}, (pn, pw, poly)])
|
|
# Where a cell has several levels, a level that only touches one of
|
|
# its four sample spots is a rock top or a stump, not a floor: drop
|
|
# it (the biggest level always stays).
|
|
if len(surfs) > 1:
|
|
keep = max(surfs, key=lambda s: s[3])
|
|
surfs = [s for s in surfs if s is keep or s[3] >= 2]
|
|
if len(surfs) > MAX_LEVELS:
|
|
best = sorted(surfs, key=lambda s: -s[3])[:MAX_LEVELS]
|
|
surfs = [s for s in surfs if s in best]
|
|
out = []
|
|
for s in surfs:
|
|
# ground where any of it is ground, else steep, else water
|
|
kinds = s[5]
|
|
cls = C_GROUND if C_GROUND in kinds else (C_STEEP if C_STEEP in kinds else C_WATER)
|
|
out.append([s[0] / s[3], cls, s[2], s[3], s[6]])
|
|
cells[key] = out
|
|
return cells
|
|
|
|
|
|
BAND = {} # the tiles of the band being built, by uid
|
|
MAPPING = [None] # the axis mapping in use
|
|
|
|
|
|
def walk_line(start, end, targets):
|
|
"""Walk a straight line over the navmesh from start (north, west, poly)
|
|
to the spot end (north, west), polygon to polygon across their shared
|
|
edges, as the server's pathfinder does. True when it gets there on one
|
|
of the target polygons; False when it runs into an edge with nothing
|
|
beyond it (a wall, a drop) or ends on another level."""
|
|
n0, w0, (uid, pi) = start
|
|
n1, w1 = end[0], end[1]
|
|
tile = BAND.get(uid)
|
|
if tile is None:
|
|
return False
|
|
m = MAPPING[0]
|
|
wv = tile.world_verts(m)
|
|
dn, dw = n1 - n0, w1 - w0
|
|
t = 0.0
|
|
for _ in range(64):
|
|
vs = tile.pverts[pi]
|
|
nv = len(vs)
|
|
best_t, best_e = None, None
|
|
for e in range(nv):
|
|
an, aw = wv[vs[e]]
|
|
bn, bw = wv[vs[(e + 1) % nv]]
|
|
en, ew = bn - an, bw - aw
|
|
den = dn * ew - dw * en
|
|
if abs(den) < 1e-12:
|
|
continue
|
|
tt = ((an - n0) * ew - (aw - w0) * en) / den
|
|
uu = ((an - n0) * dw - (aw - w0) * dn) / den
|
|
if tt > t + 1e-7 and -1e-6 <= uu <= 1 + 1e-6:
|
|
if best_t is None or tt < best_t:
|
|
best_t, best_e = tt, e
|
|
if best_t is None or best_t >= 1.0:
|
|
return (uid, pi) in targets # the line ends in this polygon
|
|
nei = tile.pneis[pi][best_e]
|
|
if nei == 0:
|
|
return False # nothing beyond this edge
|
|
if nei & DT_EXT_LINK:
|
|
# into the next tile; the polygons there line up with this one
|
|
return any(q[0] != uid for q in targets) or (uid, pi) in targets
|
|
pi = nei - 1
|
|
t = best_t
|
|
return False
|
|
|
|
|
|
def polys_join(sa, sb):
|
|
"""Can you walk from surface sa straight onto surface sb? The same
|
|
polygon (convex: nothing in the way inside it), or a straight line over
|
|
the navmesh that gets there."""
|
|
if sa[2] & sb[2]:
|
|
return True
|
|
return walk_line(sa[4], sb[4], sb[2])
|
|
|
|
|
|
def link(sa, cb, neigh_of, ext_of):
|
|
"""Index of the surface in neighbour cell cb that surface sa walks onto."""
|
|
best, bestdz = -1, None
|
|
for k, sb in enumerate(cb):
|
|
dz = abs(sa[0] - sb[0])
|
|
if dz <= STEP_POLY and polys_join(sa, sb):
|
|
if bestdz is None or dz < bestdz:
|
|
best, bestdz = k, dz
|
|
return best
|
|
|
|
|
|
DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0)) # +west, +north, -west, -north
|
|
|
|
|
|
def prune_islands(cells, i0, j0, i1, j1, neigh_of, ext_of):
|
|
"""Drop small patches you can stand on but never reach from the ground
|
|
around them: roofs, tree canopies, rock tops. Judged over the block and
|
|
a wide margin, so neighbouring blocks agree on what is dropped."""
|
|
adj = {}
|
|
for (i, j), surfs in cells.items():
|
|
for k, sa in enumerate(surfs):
|
|
node = (i, j, k)
|
|
adj.setdefault(node, set())
|
|
for di, dj in DIRS:
|
|
cb = cells.get((i + di, j + dj))
|
|
if cb:
|
|
t = link(sa, cb, neigh_of, ext_of)
|
|
if t >= 0:
|
|
other = (i + di, j + dj, t)
|
|
adj[node].add(other)
|
|
adj.setdefault(other, set()).add(node)
|
|
seen = set()
|
|
drop = set()
|
|
for start in adj:
|
|
if start in seen:
|
|
continue
|
|
comp = [start]
|
|
seen.add(start)
|
|
k = 0
|
|
imin = imax = start[0]
|
|
jmin = jmax = start[1]
|
|
while k < len(comp):
|
|
node = comp[k]
|
|
k += 1
|
|
i, j = node[0], node[1]
|
|
if i < imin: imin = i
|
|
if i > imax: imax = i
|
|
if j < jmin: jmin = j
|
|
if j > jmax: jmax = j
|
|
for other in adj[node]:
|
|
if other not in seen:
|
|
seen.add(other)
|
|
comp.append(other)
|
|
border = imin <= i0 or jmin <= j0 or imax >= i1 - 1 or jmax >= j1 - 1
|
|
if not border and imax - imin < ISLAND and jmax - jmin < ISLAND:
|
|
drop.update(comp)
|
|
if not drop:
|
|
return cells, 0
|
|
out = {}
|
|
for (i, j), surfs in cells.items():
|
|
kept = [sf for k, sf in enumerate(surfs) if (i, j, k) not in drop]
|
|
if kept:
|
|
out[(i, j)] = kept
|
|
return out, len(drop)
|
|
|
|
|
|
def encode_block(bi, bj, cells, neigh_of, ext_of):
|
|
"""The block as a Lua string, or None if nothing is walkable in it."""
|
|
i0, j0 = bi * BLOCK, bj * BLOCK
|
|
codes = []
|
|
complexcells = []
|
|
exceptions = []
|
|
walkable = 0
|
|
for li in range(BLOCK):
|
|
for lj in range(BLOCK):
|
|
c = cells.get((i0 + li, j0 + lj))
|
|
if not c:
|
|
codes.append(0)
|
|
elif len(c) == 1:
|
|
codes.append(c[0][1])
|
|
walkable += 1
|
|
else:
|
|
codes.append(CODE_COMPLEX)
|
|
walkable += 1
|
|
if walkable == 0:
|
|
return None, 0, 0
|
|
|
|
def code_at(i, j):
|
|
c = cells.get((i, j))
|
|
if not c:
|
|
return 0
|
|
return c[0][1] if len(c) == 1 else CODE_COMPLEX
|
|
|
|
for li in range(BLOCK):
|
|
for lj in range(BLOCK):
|
|
i, j = i0 + li, j0 + lj
|
|
idx = li * BLOCK + lj
|
|
ca = cells.get((i, j))
|
|
if not ca:
|
|
continue
|
|
if len(ca) > 1:
|
|
rec = [num2(idx), enc(len(ca))]
|
|
for s in ca:
|
|
hq = int(round(s[0] * 2)) + 4096
|
|
hq = max(0, min(91 * 91 - 1, hq))
|
|
rec.append(num2(hq))
|
|
rec.append(enc(s[1]))
|
|
ts = []
|
|
for di, dj in ((0, 1), (1, 0), (0, -1), (-1, 0)):
|
|
cb = cells.get((i + di, j + dj))
|
|
t = link(s, cb, neigh_of, ext_of) if cb else -1
|
|
ts.append(min(t + 1, 2) if len(ca) == 2 and (not cb or len(cb) <= 2) else t + 1)
|
|
if len(ca) == 2 and max(ts) <= 2:
|
|
# two levels whose neighbours have two at most: the four
|
|
# links (0 none, 1 first, 2 second) fit one character
|
|
rec.append(enc(ts[0] + 3 * ts[1] + 9 * ts[2] + 27 * ts[3]))
|
|
else:
|
|
rec.append(enc(90)) # marker: four separate characters follow
|
|
rec.extend(enc(t) for t in ts)
|
|
complexcells.append(''.join(rec))
|
|
continue
|
|
# a simple cell: links to simple neighbours are assumed; list
|
|
# the ones that are missing. Links with a complex neighbour are
|
|
# kept in the neighbour's record.
|
|
for d, (di, dj) in enumerate(((0, 1), (1, 0))):
|
|
cb = cells.get((i + di, j + dj))
|
|
if cb and len(cb) == 1:
|
|
if link(ca[0], cb, neigh_of, ext_of) < 0:
|
|
exceptions.append(num2(idx * 2 + d))
|
|
|
|
# run-length codes
|
|
out = []
|
|
k = 0
|
|
total = len(codes)
|
|
while k < total:
|
|
v = codes[k]
|
|
run = 1
|
|
while k + run < total and codes[k + run] == v:
|
|
run += 1
|
|
k += run
|
|
while run > 0:
|
|
if run <= 9:
|
|
out.append(enc(v * 10 + run - 1))
|
|
run = 0
|
|
else:
|
|
take = min(run, 91 * 91 - 1 + 10)
|
|
out.append(enc(v * 10 + 9) + num2(take - 10))
|
|
run -= take
|
|
rle, exc, cx = ''.join(out), ''.join(exceptions), ''.join(complexcells)
|
|
encode_block.parts = (len(rle), len(exc), len(cx))
|
|
return rle + SEP + exc + SEP + cx, walkable, len(complexcells)
|
|
|
|
|
|
def bake_map(mapid, tiles, cache, points, out_lines, log, limit_box=None):
|
|
index = Index(tiles)
|
|
if not index.entries:
|
|
return {}
|
|
log('Map %d: %d tiles' % (mapid, len(index.entries)))
|
|
|
|
# area ids in use
|
|
hist = {}
|
|
for _, _, path in index.entries[:: max(1, len(index.entries) // 12)]:
|
|
t = cache.get(path)
|
|
for a in t.tarea:
|
|
hist[a] = hist.get(a, 0) + 1
|
|
scheme = AreaScheme(hist)
|
|
log(' area ids: %s -> %s' % (', '.join('%d:%d' % kv for kv in sorted(hist.items())), scheme.name))
|
|
|
|
m, score = detect_mapping(index, cache, points.get(mapid, []), log)
|
|
|
|
boxes = index.world_boxes(m)
|
|
if limit_box:
|
|
boxes = [b for b in boxes if b[1] >= limit_box[0] and b[0] <= limit_box[1]
|
|
and b[3] >= limit_box[2] and b[2] <= limit_box[3]]
|
|
nmin = min(b[0] for b in boxes)
|
|
nmax = max(b[1] for b in boxes)
|
|
wmin = min(b[2] for b in boxes)
|
|
wmax = max(b[3] for b in boxes)
|
|
span = BLOCK * CELL
|
|
bi0, bi1 = int(math.floor(nmin / span)), int(math.floor(nmax / span))
|
|
bj0, bj1 = int(math.floor(wmin / span)), int(math.floor(wmax / span))
|
|
|
|
band = BAND
|
|
MAPPING[0] = m
|
|
|
|
def tile_by_uid(uid):
|
|
return band.get(uid)
|
|
|
|
def neigh_of(p):
|
|
t = tile_by_uid(p[0])
|
|
return t.neigh[p[1]] if t else ()
|
|
|
|
def ext_of(p):
|
|
t = tile_by_uid(p[0])
|
|
return t.extedge[p[1]] if t else True
|
|
|
|
stats = {'blocks': 0, 'walkable': 0, 'complex': 0, 'bytes': 0, 'rle': 0, 'exc': 0, 'cx': 0}
|
|
started = time.time()
|
|
rows = bi1 - bi0 + 1
|
|
for r, bi in enumerate(range(bi0, bi1 + 1)):
|
|
band_n0, band_n1 = (bi * BLOCK - REGION - 1) * CELL, ((bi + 1) * BLOCK + REGION + 1) * CELL
|
|
band_tiles = [b for b in boxes if b[1] >= band_n0 and b[0] <= band_n1]
|
|
if not band_tiles:
|
|
continue
|
|
# this band's triangles, binned by block column
|
|
bycol = {}
|
|
band.clear()
|
|
for b in band_tiles:
|
|
tile = cache.get(b[4])
|
|
band[tile.uid] = tile
|
|
for (bn, bw), lst in tile_buckets(tile, m).items():
|
|
if bn * 32.0 + 32.0 < band_n0 or bn * 32.0 > band_n1:
|
|
continue
|
|
reach = (REGION + 1) * CELL
|
|
for bj in range(int(math.floor((bw * 32.0 - reach) / span)), int(math.floor((bw * 32.0 + 32.0 + reach) / span)) + 1):
|
|
bycol.setdefault(bj, set()).update((tile.uid, t) for t in lst)
|
|
tiles_by_uid = band
|
|
for bj in range(bj0, bj1 + 1):
|
|
tris = bycol.get(bj)
|
|
if not tris:
|
|
continue
|
|
margin = REGION + 1
|
|
cells = raster_block(bi, bj, [(tiles_by_uid[u], t, m) for u, t in tris if u in tiles_by_uid], scheme, margin)
|
|
if not cells:
|
|
continue
|
|
cells, dropped = prune_islands(cells, bi * BLOCK - margin, bj * BLOCK - margin,
|
|
(bi + 1) * BLOCK + margin, (bj + 1) * BLOCK + margin, neigh_of, ext_of)
|
|
stats['dropped'] = stats.get('dropped', 0) + dropped
|
|
s, walk, cx = encode_block(bi, bj, cells, neigh_of, ext_of)
|
|
if s is None:
|
|
continue
|
|
key = (bi + 512) * 1024 + (bj + 512)
|
|
out_lines.append('D[%d]="%s"' % (key, s))
|
|
stats['blocks'] += 1
|
|
stats['walkable'] += walk
|
|
stats['complex'] += cx
|
|
stats['bytes'] += len(s) + 12
|
|
pr, pe, pc = encode_block.parts
|
|
stats['rle'] += pr
|
|
stats['exc'] += pe
|
|
stats['cx'] += pc
|
|
el = time.time() - started
|
|
log(' row %d/%d blocks %d %.1f MB %.0fs' % (r + 1, rows, stats['blocks'], stats['bytes'] / 1e6, el))
|
|
stats['mapping'] = m
|
|
stats['score'] = score
|
|
stats['scheme'] = scheme.name
|
|
return stats
|
|
|
|
|
|
TOC = """## Interface: 11200
|
|
## Title: |cff33ffccpf|cffffffffQuest |cffaaaaaaSmartArrow Navmesh
|
|
## Notes: Walk grid for pfQuest SmartArrow, built from your own game client's movement maps. Loaded by SmartArrow when present.
|
|
## Author: built locally with pfQuest SmartArrow's bake_navmesh.py
|
|
## Version: {version}
|
|
## X-License: built from your own game files; do not redistribute
|
|
## Dependencies: pfQuest-SmartArrow
|
|
## LoadOnDemand: 1
|
|
|
|
Navmesh.lua
|
|
{files}
|
|
"""
|
|
|
|
HEADER = """-- pfQuest SmartArrow navmesh, built {date} from {source}
|
|
-- {cell} yard cells in blocks of {block}. Built from your own game files:
|
|
-- keep it for yourself.
|
|
pfQuestSmartArrowNavmesh = {{ version = 4, cell = {cell}, block = {block}, built = "{date}", cont = {{ [0] = {{}}, [1] = {{}} }}, stats = {{}} }}
|
|
"""
|
|
|
|
|
|
def write_addon(outdir, parts, version, source, log):
|
|
folder = os.path.join(outdir, 'pfQuest-SmartArrow-Navmesh')
|
|
os.makedirs(folder, exist_ok=True)
|
|
# only the maps built now are replaced: a bake of one continent keeps the
|
|
# other's files
|
|
built = set(mapid for mapid, _ in parts)
|
|
kept = []
|
|
for name in sorted(os.listdir(folder)):
|
|
m = re.match(r'^Navmesh(\d+)_(\d+)\.lua$', name, re.I)
|
|
if m and int(m.group(1)) not in built:
|
|
kept.append(name)
|
|
elif name.lower().endswith('.lua') or name.lower().endswith('.toc'):
|
|
os.remove(os.path.join(folder, name))
|
|
if kept:
|
|
log('Kept the files of map %s from an earlier bake' % ', '.join(sorted(set(re.match(r'^Navmesh(\d+)', k, re.I).group(1) for k in kept))))
|
|
date = time.strftime('%Y-%m-%d')
|
|
with open(os.path.join(folder, 'Navmesh.lua'), 'w', encoding='ascii', newline='\n') as f:
|
|
f.write(HEADER.format(date=date, source=source.replace('"', "'"), cell=int(CELL), block=BLOCK))
|
|
files = list(kept)
|
|
total = sum(os.path.getsize(os.path.join(folder, k)) for k in kept)
|
|
for mapid, lines in parts:
|
|
chunk = 1500 # blocks per file
|
|
for p in range(0, len(lines), chunk):
|
|
name = 'Navmesh%d_%d.lua' % (mapid, p // chunk + 1)
|
|
with open(os.path.join(folder, name), 'w', encoding='ascii', newline='\n') as f:
|
|
f.write('local D = pfQuestSmartArrowNavmesh.cont[%d]\n' % mapid)
|
|
for line in lines[p:p + chunk]:
|
|
f.write(line)
|
|
f.write('\n')
|
|
total += os.path.getsize(os.path.join(folder, name))
|
|
files.append(name)
|
|
with open(os.path.join(folder, 'pfQuest-SmartArrow-Navmesh.toc'), 'w', encoding='ascii', newline='\n') as f:
|
|
f.write(TOC.format(version=version, files='\n'.join(files)))
|
|
log('Wrote %s (%d data files, %.2f MB)' % (folder, len(files), total / 1e6))
|
|
return folder, total
|
|
|
|
|
|
def main(argv=None):
|
|
ap = argparse.ArgumentParser(description=__doc__, formatter_class=argparse.RawDescriptionHelpFormatter)
|
|
ap.add_argument('mmaps', help='folder with the .mmtile files')
|
|
ap.add_argument('--out', default=None, help='your Interface\\AddOns folder (default: next to this addon)')
|
|
ap.add_argument('--maps', default='0,1', help='which maps: 0 = Eastern Kingdoms, 1 = Kalimdor')
|
|
ap.add_argument('--box', default=None, help='only part of the world: north1,north2,west1,west2 (for a test)')
|
|
args = ap.parse_args(argv)
|
|
|
|
here = os.path.dirname(os.path.abspath(__file__))
|
|
addon = os.path.dirname(here)
|
|
outdir = args.out or os.path.dirname(addon)
|
|
log = lambda s: print(s, flush=True)
|
|
|
|
if not os.path.isdir(args.mmaps):
|
|
raise SystemExit('No such folder: %s' % args.mmaps)
|
|
found = find_tiles(args.mmaps)
|
|
if not found:
|
|
raise SystemExit('No .mmtile files for maps 0 or 1 in %s' % args.mmaps)
|
|
points = walknet_points(addon)
|
|
cache = TileCache()
|
|
want = [int(x) for x in args.maps.split(',') if x.strip()]
|
|
box = [float(x) for x in args.box.split(',')] if args.box else None
|
|
parts = []
|
|
allstats = []
|
|
for mapid in want:
|
|
if mapid not in found:
|
|
log('Map %d: no tiles, skipped' % mapid)
|
|
continue
|
|
lines = []
|
|
st = bake_map(mapid, found[mapid], cache, points, lines, log, box)
|
|
parts.append((mapid, lines))
|
|
allstats.append((mapid, st))
|
|
folder, total = write_addon(outdir, parts, '1', os.path.abspath(args.mmaps), log)
|
|
for mapid, st in allstats:
|
|
if st:
|
|
log('Map %d: %d blocks, %d walkable cells, %d on more than one level (%.1f%%)'
|
|
% (mapid, st['blocks'], st['walkable'], st['complex'],
|
|
100.0 * st['complex'] / max(1, st['walkable'])))
|
|
log(' dropped %d unreachable spots (roofs, canopies, rock tops), counted with the margins' % st.get('dropped', 0))
|
|
log(' size: ground codes %.2f MB, missing links %.2f MB, extra levels %.2f MB (%.0f bytes a block)'
|
|
% (st['rle'] / 1e6, st['exc'] / 1e6, st['cx'] / 1e6, st['bytes'] / max(1, st['blocks'])))
|
|
log('Done. Enable "pfQuest SmartArrow Navmesh" in the AddOns list; SmartArrow loads it by itself.')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
main()
|