A fast 2D and 3D game engine — TypeScript SDK, C++/WebAssembly core, visual editor. Ship one project to web, desktop, WeChat MiniGames, playable ads, and native Android / iOS.
TypeScript 2d-game-engine3d3d-game-engineandroidcppecsgame-editorgame-enginegamedeviostypescriptwebassemblywebglwebgpuwechat-minigame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright (c) 2024-present ESEngine Team
import { describe, expect, it } from 'vitest';
import {
FACES, direction, faceOf, levelsFor, nodeAt, nodeBound, nodePoint, nodeRect, selectSphereNodes, sphereNodeKey, type SphereNode, type SphereTreeParams,
} from '../src/terrain/sphere';
const planet: SphereTreeParams = { radius: 4000, minHeight: -30, maxHeight: 200, leafSize: 48, range0: 180 };
const levels = levelsFor(planet.radius, planet.leafSize);
/** A reproducible stream of directions all over the sphere. */
function* directions(count: number): Generator<[number, number, number]> {
let a = 12345;
const next = () => { a = (Math.imul(a, 1664525) + 1013904223) >>> 0; return a / 4294967296; };
for (let i = 0; i < count; i++) {
const z = next() * 2 - 1, t = next() * Math.PI * 2, r = Math.sqrt(1 - z * z);
yield [r * Math.cos(t), r * Math.sin(t), z];
}
}
describe('a planet as a cube', () => {
it('has right-handed faces whose normals point out', () => {
for (const f of FACES) {
const cross = [f.a[1] * f.b[2] - f.a[2] * f.b[1], f.a[2] * f.b[0] - f.a[0] * f.b[2], f.a[0] * f.b[1] - f.a[1] * f.b[0]];
cross.forEach((c, i) => expect(c).toBeCloseTo(f.normal[i]!, 12));
}
});
it('names a direction by a face and a place on it, and the place names the direction back', () => {
for (const d of directions(2000)) {
const { face, u, v } = faceOf(d[0], d[1], d[2]);
expect(Math.abs(u)).toBeLessThanOrEqual(1 + 1e-9);
expect(Math.abs(v)).toBeLessThanOrEqual(1 + 1e-9);
const back = direction(face, u, v);
expect(Math.hypot(back[0] - d[0], back[1] - d[1], back[2] - d[2])).toBeLessThan(1e-9);
}
});
it('agrees with the neighbouring face along the edge two faces share, so the ground has no seam', () => {
// The +X face's u = 1 edge and the -Z face's u = -1 edge are the same line of the cube: the same directions from either side.
for (let v = -1; v <= 1; v += 0.25) {
const a = direction(0, 1, v), b = direction(5, -1, v);
expect(Math.hypot(a[0] - b[0], a[1] - b[1], a[2] - b[2])).toBeLessThan(1e-12);
}
// And the +X face's v = 1 edge with the +Y face's u = 1 edge (the same line, t along both).
for (let t = -1; t <= 1; t += 0.25) {
const a = direction(0, t, 1), b = direction(2, 1, t);
expect(Math.hypot(a[0] - b[0], a[1] - b[1], a[2] - b[2])).toBeLessThan(1e-12);
}
});
it('spreads the squares evenly: no node is more than about 1.4 times another on the ground', () => {
const node = (face: number, ix: number, iz: number): SphereNode => ({ face, level: 0, ix, iz });
const n = 2 ** (levels - 1);
const side = (nd: SphereNode) => {
const a = nodePoint(planet, levels, nd, 0, 0.5, 0), b = nodePoint(planet, levels, nd, 1, 0.5, 0);
return Math.hypot(a[0] - b[0], a[1] - b[1], a[2] - b[2]);
};
const middle = side(node(0, n >> 1, n >> 1)), corner = side(node(0, 0, 0));
expect(Math.max(middle, corner) / Math.min(middle, corner)).toBeLessThan(1.4);
});
});
describe('the nodes drawn round an eye', () => {
const eyeOn = (d: [number, number, number], altitude: number): [number, number, number] =>
[d[0] * (planet.radius + altitude), d[1] * (planet.radius + altitude), d[2] * (planet.radius + altitude)];
it('cover every point of the planet exactly once, from the ground and from space', () => {
for (const altitude of [2, 800, 60000]) {
const eye = eyeOn([0.3, 0.8, 0.52], altitude);
const nodes = selectSphereNodes(planet, eye[0], eye[1], eye[2], levels);
for (const d of directions(600)) {
const { face, u, v } = faceOf(d[0], d[1], d[2]);
const holding = nodes.filter((n) => {
if (n.face !== face) return false;
const { u0, v0, span } = nodeRect(levels, n);
return u >= u0 && u <= u0 + span && v >= v0 && v <= v0 + span;
});
// A point on a shared edge is in two of them; anywhere else exactly one.
expect(holding.length).toBeGreaterThanOrEqual(1);
expect(holding.length).toBeLessThanOrEqual(4);
}
const area = nodes.reduce((sum, n) => sum + nodeRect(levels, n).span ** 2, 0);
expect(area).toBeCloseTo(6 * 4, 6);
}
});
it('are finest under the eye and coarsen with distance, and few when the eye is far', () => {
const ground = selectSphereNodes(planet, 0, 0, planet.radius + 2, levels);
const space = selectSphereNodes(planet, 0, 0, planet.radius * 6, levels);
expect(Math.min(...ground.map((n) => n.level))).toBe(0);
expect(Math.max(...ground.map((n) => n.level))).toBeGreaterThan(4);
expect(ground.length).toBeLessThan(500);
// From far off the whole planet is a handful of coarse nodes, none of them the finest.
expect(space.length).toBeLessThan(ground.length);
expect(Math.min(...space.map((n) => n.level))).toBeGreaterThan(Math.min(...ground.map((n) => n.level)));
});
it('have bounds that hold every point of the node at any height in the range', () => {
const nd: SphereNode = { face: 2, level: 3, ix: 5, iz: 9 };
const b = nodeBound(planet, levels, nd);
for (let s = 0; s <= 1; s += 0.25) for (let t = 0; t <= 1; t += 0.25) for (const h of [planet.minHeight, 0, planet.maxHeight]) {
const p = nodePoint(planet, levels, nd, s, t, h);
expect(Math.hypot(p[0] - b.x, p[1] - b.y, p[2] - b.z)).toBeLessThanOrEqual(b.r + 1e-6);
}
});
it('finds the node of a level that holds a place, and names nodes by a key', () => {
const { face, u, v } = faceOf(0.2, -0.9, 0.3);
const nd = nodeAt(levels, face, 2, u, v);
const { u0, v0, span } = nodeRect(levels, nd);
expect(u).toBeGreaterThanOrEqual(u0 - 1e-12);
expect(u).toBeLessThanOrEqual(u0 + span + 1e-12);
expect(v).toBeGreaterThanOrEqual(v0 - 1e-12);
expect(sphereNodeKey(nd)).toBe(`${face}:2:${nd.ix}:${nd.iz}`);
});
});
describe('a planet node\'s page', () => {
const src = (height: (d: [number, number, number]) => number) => ({
provider: {
id: 't', versions: [1], range: () => [-50, 250] as [number, number],
sample: ({ directions, count }: { directions: Float32Array; count: number }) => {
const heights = new Float32Array(count);
for (let i = 0; i < count; i++) heights[i] = height([directions[i * 3]!, directions[i * 3 + 1]!, directions[i * 3 + 2]!]);
return { heights };
},
},
world: 'w', seed: 1, version: 1, radius: planet.radius, levels, minHeight: -50, maxHeight: 250,
});
const decode = (page: { heights: Uint8Array }, k: number) => (page.heights[k * 4]! * 256 + page.heights[k * 4 + 1]!) / 65535 * 300 - 50;
it('holds the height the provider gave, over the range, and says up is up on level ground', async () => {
const { makePlanetPage } = await import('../src/terrain/planetPages');
const { PAGE_SIDE } = await import('../src/terrain/pages');
const page = await makePlanetPage(src(() => 40), { face: 2, level: 3, ix: 5, iz: 9 });
const k = Math.floor(PAGE_SIDE / 2) * PAGE_SIDE + Math.floor(PAGE_SIDE / 2);
expect(decode(page, k)).toBeCloseTo(40, 2);
expect(page.min).toBeCloseTo(40, 3);
expect(page.max).toBeCloseTo(40, 3);
// The normal is stored in the frame at the sample: x and z are the tangents, so level ground leans neither way (128 of 255).
expect(Math.abs(page.heights[k * 4 + 2]! - 128)).toBeLessThanOrEqual(1);
expect(Math.abs(page.heights[k * 4 + 3]! - 128)).toBeLessThanOrEqual(1);
});
it('leans the normal away from a rising slope, whichever face the node is on', async () => {
const { makePlanetPage } = await import('../src/terrain/planetPages');
const { PAGE_SIDE } = await import('../src/terrain/pages');
for (const face of [2, 4, 5]) {
// Ground that rises with the direction's x, steeply: on these faces x runs along u, so the normal leans in the frame's x.
const page = await makePlanetPage(src((d) => 2000 * d[0]), { face, level: 4, ix: 3, iz: 4 });
const k = Math.floor(PAGE_SIDE / 2) * PAGE_SIDE + Math.floor(PAGE_SIDE / 2);
const leanX = page.heights[k * 4 + 2]! - 128, leanZ = page.heights[k * 4 + 3]! - 128;
expect(Math.hypot(leanX, leanZ)).toBeGreaterThan(2);
}
});
});