Files

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