495 lines
18 KiB
JavaScript
495 lines
18 KiB
JavaScript
import { mkdir, readFile } from "node:fs/promises";
|
|
import path from "node:path";
|
|
import { Document, NodeIO } from "@gltf-transform/core";
|
|
import {
|
|
freeCompactHeightfield,
|
|
freeContourSet,
|
|
freeHeightfield,
|
|
freePolyMesh,
|
|
freePolyMeshDetail,
|
|
init,
|
|
Recast,
|
|
} from "@recast-navigation/core";
|
|
import { threeToSoloNavMesh, threeToTiledNavMesh, NavMeshHelper } from "@recast-navigation/three";
|
|
import { Vector3 } from "three";
|
|
import { GLTFLoader } from "three/examples/jsm/loaders/GLTFLoader.js";
|
|
import {
|
|
exists,
|
|
fixturesRoot,
|
|
loadRecipe,
|
|
projectRoot,
|
|
readJson,
|
|
relativeProjectPath,
|
|
sha256,
|
|
workRoot,
|
|
writeJson,
|
|
} from "./lib.mjs";
|
|
import {
|
|
nextTiledNavMeshSize,
|
|
planNavigationBuild,
|
|
shouldUseMonotonePartition,
|
|
validateTiledBuild,
|
|
} from "./recast-policy.mjs";
|
|
import { threeToMonotoneTiledNavMesh } from "./recast-monotone-fallback.mjs";
|
|
|
|
globalThis.self = globalThis;
|
|
globalThis.ProgressEvent ??= class ProgressEvent {
|
|
constructor(type, values = {}) { this.type = type; Object.assign(this, values); }
|
|
};
|
|
globalThis.createImageBitmap ??= async () => ({ width: 1, height: 1, close() {} });
|
|
|
|
async function loadScene(file) {
|
|
const bytes = await readFile(file);
|
|
const buffer = bytes.buffer.slice(bytes.byteOffset, bytes.byteOffset + bytes.byteLength);
|
|
return new Promise((resolve, reject) => new GLTFLoader().parse(buffer, "", (gltf) => resolve(gltf.scene), reject));
|
|
}
|
|
|
|
function meshesIn(scene) {
|
|
scene.updateMatrixWorld(true);
|
|
const meshes = [];
|
|
scene.traverse((object) => {
|
|
if (object.isMesh && object.geometry?.getAttribute("position")) meshes.push(object);
|
|
});
|
|
return meshes;
|
|
}
|
|
|
|
function inspectNavigationInput(meshes) {
|
|
const minimum = [Infinity, Infinity, Infinity];
|
|
const maximum = [-Infinity, -Infinity, -Infinity];
|
|
const a = new Vector3();
|
|
const b = new Vector3();
|
|
const c = new Vector3();
|
|
const edgeAb = new Vector3();
|
|
const edgeAc = new Vector3();
|
|
const normal = new Vector3();
|
|
let vertexCount = 0;
|
|
let triangleCount = 0;
|
|
let degenerateTriangleCount = 0;
|
|
let invalidIndexCount = 0;
|
|
let nonFiniteCoordinateCount = 0;
|
|
|
|
for (const mesh of meshes) {
|
|
const positions = mesh.geometry.getAttribute("position");
|
|
if (positions.itemSize !== 3) throw new Error(`${mesh.name || "collision mesh"}: POSITION must be VEC3.`);
|
|
const indices = mesh.geometry.getIndex();
|
|
const elementCount = indices?.count ?? positions.count;
|
|
if (elementCount % 3 !== 0) {
|
|
throw new Error(`${mesh.name || "collision mesh"}: triangle index count is not divisible by three.`);
|
|
}
|
|
vertexCount += positions.count;
|
|
triangleCount += elementCount / 3;
|
|
const vertexIndex = (element) => indices ? indices.getX(element) : element;
|
|
|
|
for (let element = 0; element < elementCount; element += 3) {
|
|
const triangleIndices = [
|
|
vertexIndex(element),
|
|
vertexIndex(element + 1),
|
|
vertexIndex(element + 2),
|
|
];
|
|
for (const index of triangleIndices) {
|
|
if (!Number.isInteger(index) || index < 0 || index >= positions.count) invalidIndexCount += 1;
|
|
}
|
|
if (triangleIndices.some((index) => !Number.isInteger(index) || index < 0 || index >= positions.count)) {
|
|
continue;
|
|
}
|
|
|
|
a.fromBufferAttribute(positions, triangleIndices[0]).applyMatrix4(mesh.matrixWorld);
|
|
b.fromBufferAttribute(positions, triangleIndices[1]).applyMatrix4(mesh.matrixWorld);
|
|
c.fromBufferAttribute(positions, triangleIndices[2]).applyMatrix4(mesh.matrixWorld);
|
|
for (const point of [a, b, c]) {
|
|
for (let axis = 0; axis < 3; axis += 1) {
|
|
const value = point.getComponent(axis);
|
|
if (!Number.isFinite(value)) {
|
|
nonFiniteCoordinateCount += 1;
|
|
} else {
|
|
minimum[axis] = Math.min(minimum[axis], value);
|
|
maximum[axis] = Math.max(maximum[axis], value);
|
|
}
|
|
}
|
|
}
|
|
normal.crossVectors(edgeAb.subVectors(b, a), edgeAc.subVectors(c, a));
|
|
if (normal.lengthSq() <= 1e-16) degenerateTriangleCount += 1;
|
|
}
|
|
}
|
|
|
|
if (triangleCount === 0) throw new Error("Collision input contains no triangles.");
|
|
if (invalidIndexCount) throw new Error(`Collision input contains ${invalidIndexCount} invalid triangle indices.`);
|
|
if (nonFiniteCoordinateCount) {
|
|
throw new Error(`Collision input contains ${nonFiniteCoordinateCount} non-finite world coordinates.`);
|
|
}
|
|
if (degenerateTriangleCount === triangleCount) throw new Error("Every collision triangle is degenerate.");
|
|
return {
|
|
bounds: [minimum, maximum],
|
|
meshCount: meshes.length,
|
|
vertexCount,
|
|
triangleCount,
|
|
degenerateTriangleCount,
|
|
invalidIndexCount,
|
|
nonFiniteCoordinateCount,
|
|
};
|
|
}
|
|
|
|
function releaseTiledIntermediates(intermediates) {
|
|
for (const tile of intermediates?.tileIntermediates ?? []) {
|
|
if (tile.heightfield) freeHeightfield(tile.heightfield);
|
|
if (tile.compactHeightfield) freeCompactHeightfield(tile.compactHeightfield);
|
|
if (tile.contourSet) freeContourSet(tile.contourSet);
|
|
if (tile.polyMesh) freePolyMesh(tile.polyMesh);
|
|
if (tile.polyMeshDetail) freePolyMeshDetail(tile.polyMeshDetail);
|
|
tile.heightfield = undefined;
|
|
tile.compactHeightfield = undefined;
|
|
tile.contourSet = undefined;
|
|
tile.polyMesh = undefined;
|
|
tile.polyMeshDetail = undefined;
|
|
}
|
|
}
|
|
|
|
function populatedNavMeshTileCount(navMesh) {
|
|
let populated = 0;
|
|
for (let index = 0; index < navMesh.getMaxTiles(); index += 1) {
|
|
const header = navMesh.getTile(index).header();
|
|
if (header && header.polyCount() > 0) populated += 1;
|
|
}
|
|
return populated;
|
|
}
|
|
|
|
async function writeGeometry(file, geometry, inputBounds, boundsTolerance) {
|
|
const sourcePositions = geometry.getAttribute("position")?.array;
|
|
const sourceIndices = geometry.getIndex()?.array;
|
|
if (!sourcePositions) throw new Error("Recast helper produced no position buffer.");
|
|
const sourceElementCount = sourceIndices?.length ?? sourcePositions.length / 3;
|
|
const [minimumInput, maximumInput] = inputBounds;
|
|
const compactPositions = [];
|
|
const compactIndices = [];
|
|
const remappedVertices = new Map();
|
|
let rejectedOutOfBoundsTriangles = 0;
|
|
|
|
const vertexWithinInputBounds = (index) => {
|
|
const offset = index * 3;
|
|
if (offset < 0 || offset + 2 >= sourcePositions.length) return false;
|
|
for (let axis = 0; axis < 3; axis += 1) {
|
|
const value = sourcePositions[offset + axis];
|
|
if (
|
|
!Number.isFinite(value)
|
|
|| value < minimumInput[axis] - boundsTolerance
|
|
|| value > maximumInput[axis] + boundsTolerance
|
|
) return false;
|
|
}
|
|
return true;
|
|
};
|
|
|
|
for (let offset = 0; offset < sourceElementCount; offset += 3) {
|
|
const triangle = [
|
|
sourceIndices?.[offset] ?? offset,
|
|
sourceIndices?.[offset + 1] ?? offset + 1,
|
|
sourceIndices?.[offset + 2] ?? offset + 2,
|
|
];
|
|
if (!triangle.every(vertexWithinInputBounds)) {
|
|
rejectedOutOfBoundsTriangles += 1;
|
|
continue;
|
|
}
|
|
for (const sourceIndex of triangle) {
|
|
if (!sourceIndices) {
|
|
const nextIndex = compactPositions.length / 3;
|
|
const sourceOffset = sourceIndex * 3;
|
|
compactPositions.push(
|
|
sourcePositions[sourceOffset],
|
|
sourcePositions[sourceOffset + 1],
|
|
sourcePositions[sourceOffset + 2],
|
|
);
|
|
compactIndices.push(nextIndex);
|
|
continue;
|
|
}
|
|
if (!remappedVertices.has(sourceIndex)) {
|
|
const nextIndex = compactPositions.length / 3;
|
|
const sourceOffset = sourceIndex * 3;
|
|
remappedVertices.set(sourceIndex, nextIndex);
|
|
compactPositions.push(
|
|
sourcePositions[sourceOffset],
|
|
sourcePositions[sourceOffset + 1],
|
|
sourcePositions[sourceOffset + 2],
|
|
);
|
|
}
|
|
compactIndices.push(remappedVertices.get(sourceIndex));
|
|
}
|
|
}
|
|
if (!compactIndices.length) {
|
|
throw new Error("Recast helper produced no triangles within the authoritative collision bounds.");
|
|
}
|
|
|
|
const positions = new Float32Array(compactPositions);
|
|
const indices = new Uint32Array(compactIndices);
|
|
const minimum = [Infinity, Infinity, Infinity];
|
|
const maximum = [-Infinity, -Infinity, -Infinity];
|
|
for (let offset = 0; offset < positions.length; offset += 3) {
|
|
for (let axis = 0; axis < 3; axis += 1) {
|
|
minimum[axis] = Math.min(minimum[axis], positions[offset + axis]);
|
|
maximum[axis] = Math.max(maximum[axis], positions[offset + axis]);
|
|
}
|
|
}
|
|
const document = new Document();
|
|
const buffer = document.createBuffer("navigation-buffer");
|
|
const positionAccessor = document.createAccessor("navigation-position", buffer).setType("VEC3").setArray(positions);
|
|
const indexAccessor = document.createAccessor("navigation-indices", buffer).setType("SCALAR").setArray(indices);
|
|
const primitive = document.createPrimitive().setAttribute("POSITION", positionAccessor).setIndices(indexAccessor);
|
|
document.createMesh("navigation").addPrimitive(primitive);
|
|
document.createNode("navigation").setMesh(document.getRoot().listMeshes()[0]);
|
|
document.createScene("navigation").addChild(document.getRoot().listNodes()[0]);
|
|
await new NodeIO().write(file, document);
|
|
return {
|
|
vertices: positions.length / 3,
|
|
triangles: indices.length / 3,
|
|
sourceVertices: sourcePositions.length / 3,
|
|
sourceTriangles: sourceElementCount / 3,
|
|
rejectedOutOfBoundsTriangles,
|
|
bounds: [minimum, maximum],
|
|
boundsTolerance,
|
|
};
|
|
}
|
|
|
|
export async function bakeNavigationFromCollisionAssets({
|
|
slug,
|
|
collisionAssets,
|
|
settings,
|
|
offMeshLinks = [],
|
|
output = path.join(workRoot, slug, "staging", `${slug}-navigation.glb`),
|
|
reportFile = path.join(workRoot, slug, "recast-report.json"),
|
|
source = undefined,
|
|
}) {
|
|
if (!collisionAssets.length) throw new Error(`${slug}: no collision chunks are available for Recast.`);
|
|
const normalizedPaths = collisionAssets.map((asset) => asset.path.replace(/\\/g, "/"));
|
|
if (new Set(normalizedPaths.map((value) => value.toLowerCase())).size !== normalizedPaths.length) {
|
|
throw new Error(`${slug}: collision chunks contain duplicate paths.`);
|
|
}
|
|
const resolvedInputs = collisionAssets.map((asset) => path.resolve(projectRoot, asset.path));
|
|
for (const [index, file] of resolvedInputs.entries()) {
|
|
if (!await exists(file)) throw new Error(`${slug}: missing collision chunk ${collisionAssets[index].path}.`);
|
|
}
|
|
const inputChunkChecksums = Object.fromEntries(await Promise.all(collisionAssets.map(async (asset, index) => [
|
|
normalizedPaths[index],
|
|
await sha256(resolvedInputs[index]),
|
|
])));
|
|
const scenes = await Promise.all(resolvedInputs.map(loadScene));
|
|
const meshes = scenes.flatMap(meshesIn);
|
|
if (!meshes.length) throw new Error(`${slug}: collision chunks contain no triangle meshes.`);
|
|
const input = inspectNavigationInput(meshes);
|
|
let build = planNavigationBuild(input.bounds, settings.cellSize, {
|
|
tileSize: settings.tileSize,
|
|
});
|
|
const generatorConfig = {
|
|
cs: settings.cellSize,
|
|
ch: settings.cellHeight,
|
|
walkableHeight: Math.ceil(settings.agentHeight / settings.cellHeight),
|
|
walkableRadius: Math.ceil(settings.agentRadius / settings.cellSize),
|
|
walkableClimb: Math.floor(settings.agentMaxClimb / settings.cellHeight),
|
|
walkableSlopeAngle: settings.agentMaxSlope,
|
|
maxEdgeLen: Math.round(12 / settings.cellSize),
|
|
maxSimplificationError: 1.3,
|
|
minRegionArea: 8,
|
|
mergeRegionArea: 20,
|
|
maxVertsPerPoly: 6,
|
|
detailSampleDist: 6,
|
|
detailSampleMaxError: 1,
|
|
offMeshConnections: offMeshLinks,
|
|
};
|
|
await init();
|
|
let generated = null;
|
|
let tiledValidation = null;
|
|
const buildAttempts = [];
|
|
const retainTileIntermediates = settings.retainTileIntermediates !== false;
|
|
const requestedPartition = settings.partition ?? "watershed";
|
|
if (!["watershed", "monotone"].includes(requestedPartition)) {
|
|
throw new Error(`${slug}: unsupported Recast partition ${requestedPartition}.`);
|
|
}
|
|
let tiledPartition = requestedPartition;
|
|
let monotoneProvenance = null;
|
|
let helper = null;
|
|
let geometry;
|
|
try {
|
|
if (build.mode === "tiled") {
|
|
while (true) {
|
|
if (tiledPartition === "monotone") {
|
|
const monotone = await threeToMonotoneTiledNavMesh(
|
|
meshes,
|
|
{ ...generatorConfig, tileSize: build.tileSize },
|
|
retainTileIntermediates,
|
|
);
|
|
generated = monotone.result;
|
|
monotoneProvenance = monotone.provenance;
|
|
} else {
|
|
generated = threeToTiledNavMesh(
|
|
meshes,
|
|
{ ...generatorConfig, tileSize: build.tileSize },
|
|
retainTileIntermediates,
|
|
);
|
|
}
|
|
if (!generated.success) throw new Error(`${slug}: Recast generation failed: ${generated.error}`);
|
|
tiledValidation = validateTiledBuild(generated.intermediates, {
|
|
errorCategory: Recast.RC_LOG_ERROR,
|
|
warningCategory: Recast.RC_LOG_WARNING,
|
|
intermediateRetention: retainTileIntermediates ? "retained" : "released",
|
|
populatedTileCount: retainTileIntermediates
|
|
? null
|
|
: populatedNavMeshTileCount(generated.navMesh),
|
|
});
|
|
buildAttempts.push({
|
|
partition: tiledPartition,
|
|
tileSize: build.tileSize,
|
|
tileCount: build.tileCount,
|
|
valid: tiledValidation.valid,
|
|
failures: tiledValidation.failures.map((failure) => ({
|
|
x: failure.x,
|
|
y: failure.y,
|
|
message: failure.message,
|
|
})),
|
|
});
|
|
if (tiledValidation.valid) break;
|
|
const nextTileSize = nextTiledNavMeshSize(tiledValidation, build.tileSize);
|
|
if (nextTileSize !== null) {
|
|
releaseTiledIntermediates(generated.intermediates);
|
|
generated.navMesh.destroy();
|
|
generated = null;
|
|
build = planNavigationBuild(input.bounds, settings.cellSize, {
|
|
tileSize: nextTileSize,
|
|
});
|
|
continue;
|
|
}
|
|
if (
|
|
tiledPartition === "watershed"
|
|
&& shouldUseMonotonePartition(tiledValidation)
|
|
) {
|
|
releaseTiledIntermediates(generated.intermediates);
|
|
generated.navMesh.destroy();
|
|
generated = null;
|
|
tiledPartition = "monotone";
|
|
build = planNavigationBuild(input.bounds, settings.cellSize, {
|
|
tileSize: settings.tileSize,
|
|
});
|
|
continue;
|
|
}
|
|
const sample = tiledValidation.failures
|
|
.slice(0, 3)
|
|
.map((failure) => `(${failure.x},${failure.y}) ${failure.message}`)
|
|
.join("; ");
|
|
throw new Error(`${slug}: tiled Recast validation failed: ${sample || "no populated navigation tiles"}`);
|
|
}
|
|
} else {
|
|
generated = threeToSoloNavMesh(meshes, generatorConfig);
|
|
buildAttempts.push({
|
|
tileSize: null,
|
|
tileCount: 1,
|
|
valid: generated.success,
|
|
failures: [],
|
|
});
|
|
if (!generated.success) throw new Error(`${slug}: Recast generation failed: ${generated.error}`);
|
|
}
|
|
helper = new NavMeshHelper(generated.navMesh);
|
|
if (!helper.navMeshGeometry.getAttribute("position")?.count) {
|
|
throw new Error(`${slug}: Recast produced no navigation geometry.`);
|
|
}
|
|
await mkdir(path.dirname(output), { recursive: true });
|
|
geometry = await writeGeometry(
|
|
output,
|
|
helper.navMeshGeometry,
|
|
input.bounds,
|
|
Math.max(settings.cellSize, settings.cellHeight) * 2,
|
|
);
|
|
} finally {
|
|
helper?.navMeshGeometry.dispose();
|
|
helper?.navMeshMaterial.dispose();
|
|
if (generated && build.mode === "tiled") releaseTiledIntermediates(generated.intermediates);
|
|
generated?.navMesh?.destroy();
|
|
}
|
|
const report = {
|
|
schemaVersion: 1,
|
|
dungeonId: slug,
|
|
generator: "@recast-navigation/three@0.43.1",
|
|
settings,
|
|
input,
|
|
build: {
|
|
...build,
|
|
partition: build.mode === "tiled" ? tiledPartition : "watershed",
|
|
...(monotoneProvenance ? { partitionProvenance: monotoneProvenance } : {}),
|
|
populatedTileCount: tiledValidation?.populatedTileCount ?? 1,
|
|
ignoredEmptyTilePackingFailures:
|
|
tiledValidation?.ignoredEmptyTilePackingFailures.length ?? 0,
|
|
intermediateRetention: tiledValidation?.intermediateRetention ?? null,
|
|
attempts: buildAttempts,
|
|
},
|
|
inputChunks: normalizedPaths,
|
|
inputChunkChecksums,
|
|
output: relativeProjectPath(output),
|
|
geometry,
|
|
...(source ? { source } : {}),
|
|
};
|
|
await writeJson(reportFile, report);
|
|
return { status: "green", ...report };
|
|
}
|
|
|
|
function navigationSettings(recipe) {
|
|
return {
|
|
cellSize: 0.2,
|
|
cellHeight: 0.1,
|
|
agentHeight: 1.8,
|
|
agentRadius: 0.36,
|
|
agentMaxClimb: 0.5,
|
|
agentMaxSlope: 50,
|
|
...(recipe.navigation ?? {}),
|
|
};
|
|
}
|
|
|
|
export async function bakeDungeonNavigation(slug) {
|
|
const recipe = await loadRecipe(slug);
|
|
const fixture = await readJson(path.join(fixturesRoot, slug, "runtime-fixture.json"));
|
|
const collisionAssets = fixture.assets.filter((asset) => asset.role === "collision");
|
|
return bakeNavigationFromCollisionAssets({
|
|
slug,
|
|
collisionAssets,
|
|
settings: navigationSettings(recipe),
|
|
offMeshLinks: fixture.offMeshLinks ?? [],
|
|
source: {
|
|
kind: "reviewed-runtime-fixture",
|
|
path: relativeProjectPath(path.join(fixturesRoot, slug, "runtime-fixture.json")),
|
|
},
|
|
});
|
|
}
|
|
|
|
export function collisionAssetsFromConversionReport(slug, conversionFile, conversion) {
|
|
if (!["green", "review-required"].includes(conversion.status)) {
|
|
throw new Error(`${slug}: conversion report is not reviewable.`);
|
|
}
|
|
if (!Array.isArray(conversion.collision) || !conversion.collision.length) {
|
|
throw new Error(`${slug}: conversion report has no collision chunks.`);
|
|
}
|
|
return conversion.collision.map((chunk, index) => {
|
|
if (!chunk.file) throw new Error(`${slug}: collision chunk ${index} has no file.`);
|
|
if (chunk.triangles > 100_000) {
|
|
throw new Error(`${slug}: collision chunk ${chunk.file} exceeds the 100000-triangle limit.`);
|
|
}
|
|
return {
|
|
id: chunk.id ?? `collision-${String(index).padStart(3, "0")}`,
|
|
role: "collision",
|
|
path: relativeProjectPath(path.join(path.dirname(conversionFile), chunk.file)),
|
|
};
|
|
});
|
|
}
|
|
|
|
export async function bakeConversionNavigation(slug) {
|
|
const recipe = await loadRecipe(slug);
|
|
const conversionFile = path.join(workRoot, slug, "staging/environment/conversion-report.json");
|
|
if (!await exists(conversionFile)) throw new Error(`${slug}: conversion report is missing.`);
|
|
const conversion = await readJson(conversionFile);
|
|
const collisionAssets = collisionAssetsFromConversionReport(slug, conversionFile, conversion);
|
|
return bakeNavigationFromCollisionAssets({
|
|
slug,
|
|
collisionAssets,
|
|
settings: navigationSettings(recipe),
|
|
source: {
|
|
kind: "blender-conversion-report",
|
|
path: relativeProjectPath(conversionFile),
|
|
checksum: await sha256(conversionFile),
|
|
collisionChunkCount: collisionAssets.length,
|
|
},
|
|
});
|
|
}
|