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 { fitRange, levelRange, parentOf, selectNodes, type QuadtreeParams, type TerrainNode } from '../src/terrain/quadtree';
import { makePage, PageTable, PAGE_SIDE } from '../src/terrain/pages';
import { NoiseSource, noised } from '../src/terrain/source';
const area: QuadtreeParams = { leafSize: 32, levels: 5, range0: 80, bounds: [-256, -256, 256, 256], minHeight: 0, maxHeight: 50 };
const covers = (nodes: TerrainNode[], x: number, z: number): number =>
nodes.filter((n) => x >= n.x0 && x < n.x0 + n.size && z >= n.z0 && z < n.z0 + n.size).length;
describe('the ground\'s quadtree', () => {
it('covers every place in the area exactly once', () => {
const nodes = selectNodes(area, 10, 20, -30);
for (let x = -250; x < 256; x += 17) for (let z = -250; z < 256; z += 19) expect(covers(nodes, x, z)).toBe(1);
});
it('is finest at the eye and coarsens with distance', () => {
const nodes = selectNodes(area, 0, 5, 0);
const at = (x: number, z: number) => nodes.find((n) => x >= n.x0 && x < n.x0 + n.size && z >= n.z0 && z < n.z0 + n.size)!;
expect(at(1, 1).level).toBe(0);
expect(at(250, 250).level).toBeGreaterThan(at(60, 60).level);
});
it('never puts two nodes more than a level apart side by side, so the morph closes every seam', () => {
const nodes = selectNodes(area, 40, 10, 70);
for (const a of nodes) for (const b of nodes) {
const touch = a.x0 <= b.x0 + b.size && b.x0 <= a.x0 + a.size && a.z0 <= b.z0 + b.size && b.z0 <= a.z0 + a.size;
if (touch) expect(Math.abs(a.level - b.level)).toBeLessThanOrEqual(1);
}
});
it('goes on round the eye for ground without end, as far as its top range', () => {
const nodes = selectNodes({ ...area, bounds: null }, 5000, 10, -9000);
expect(covers(nodes, 5000, -9000)).toBe(1);
expect(covers(nodes, 5000 + levelRange(area, 4) * 0.9, -9000)).toBe(1);
expect(nodes.every((n) => n.size === 32 * 2 ** n.level)).toBe(true);
});
it('finds a node\'s parent', () => {
expect(parentOf({ level: 0, ix: 3, iz: -1, x0: 96, z0: -32, size: 32 }, 32)).toEqual({ level: 1, ix: 1, iz: -1, x0: 64, z0: -64, size: 64 });
});
});
describe('ground without end', () => {
const ground = new NoiseSource({ seed: 4, frequency: 3, octaves: 5, persistence: 0.5, ridged: 0.3, warp: 0.3, erosion: 1, sizeX: 1000, height: 200,
rockSlope: 0.35, dirtHeight: 0.62, snowHeight: 0.88 });
it('is the same ground for the same seed anywhere, as far out as it is asked', () => {
const a = ground.height(123456.5, -98765.25), b = new NoiseSource({ ...(ground as unknown as { p: object }).p } as ConstructorParameters<typeof NoiseSource>[0]).height(123456.5, -98765.25);
expect(a).toBe(b);
expect(a).toBeGreaterThanOrEqual(0);
expect(a).toBeLessThanOrEqual(200);
});
it('has a slope that is the derivative of its noise', () => {
const e = 1e-4;
for (const [x, y] of [[0.3, 0.7], [5.5, -3.2], [-12.1, 9.9]] as const) {
const [, dx, dy] = noised(x, y, 7);
expect(dx).toBeCloseTo((noised(x + e, y, 7)[0] - noised(x - e, y, 7)[0]) / (2 * e), 4);
expect(dy).toBeCloseTo((noised(x, y + e, 7)[0] - noised(x, y - e, 7)[0]) / (2 * e), 4);
}
});
});
describe('the pages', () => {
const ground = new NoiseSource({ seed: 2, frequency: 2, octaves: 4, persistence: 0.5, ridged: 0, warp: 0, erosion: 0, sizeX: 500, height: 100,
rockSlope: 0.35, dirtHeight: 0.62, snowHeight: 0.88 });
it('hold a node\'s heights to a 65535th of the ground\'s range, with a border, and its box', async () => {
const page = await makePage(ground, 64, -32, 32);
const n = PAGE_SIDE;
// The first sample past the border is the node's corner.
const k = (1 * n + 1) * 4;
const h = ((page.heights[k]! * 256 + page.heights[k + 1]!) / 65535) * 100;
expect(h).toBeCloseTo(ground.height(64, -32), 1);
expect(page.min).toBeLessThanOrEqual(page.max);
expect(page.heights.length).toBe(n * n * 4);
});
it('give a full atlas\'s oldest page up for a new one, but not one drawn this frame', () => {
const table = new PageTable(PAGE_SIDE * 2);
expect(table.capacity).toBe(4);
for (let i = 0; i < 4; i++) expect(table.claim(`p${i}`, 0, 1)).not.toBeNull();
expect(table.claim('fresh', 0, 1)).toBeNull();
table.tick();
table.touch('p1'); table.touch('p2'); table.touch('p3');
const page = table.claim('fresh', 0, 1)!;
expect(table.get('p0')).toBeUndefined();
expect(page.slot).toBeGreaterThanOrEqual(0);
});
it('keeps a page the ground changed under, drawn as it was, until it is made again in its own slot', () => {
const table = new PageTable(PAGE_SIDE * 2);
const slot = table.claim('a', 0, 1)!.slot;
table.claim('b', 0, 1);
table.markStale((key) => key === 'a');
// Still there to draw: an edit leaves no hole while its pages are rebuilt.
expect(table.get('a')).toBeDefined();
expect(table.isStale('a')).toBe(true);
expect(table.isStale('b')).toBe(false);
const again = table.claim('a', 0.25, 2)!;
expect(again.slot).toBe(slot);
expect(again.min).toBe(0.25);
expect(again.max).toBe(2);
expect(table.isStale('a')).toBe(false);
expect(table.size).toBe(2);
});
});
describe('a tree fitted to the pages there are', () => {
// Six kilometres of ground on 1.5 m cells at a detail of 4: what a fjord's cliffs cracked at, wanting 1153 pages of 900.
const island = (share: number): QuadtreeParams => ({ leafSize: 48, levels: 8, range0: 480 * share, bounds: [-3072, -3072, 3072, 3072], minHeight: 0, maxHeight: 528 });
it('keeps its whole range where the nodes fit', () => {
const fitted = fitRange(island, -300, 119, -640, 5000);
expect(fitted.share).toBe(1);
expect(fitted.nodes).toEqual(selectNodes(island(1), -300, 119, -640));
});
it('gives up range until the nodes fit, and no more than that', () => {
expect(selectNodes(island(1), -300, 119, -640).length).toBeGreaterThan(900);
const fitted = fitRange(island, -300, 119, -640, 765);
expect(fitted.nodes.length).toBeLessThanOrEqual(765);
expect(fitted.share).toBeLessThan(1);
expect(selectNodes(island(fitted.share / 0.9), -300, 119, -640).length).toBeGreaterThan(765);
expect(fitted.nodes).toEqual(selectNodes(island(fitted.share), -300, 119, -640));
});
it('holds what it settled on, and takes range back only with room to spare', () => {
const settled = fitRange(island, -300, 119, -640, 765).share;
expect(fitRange(island, -300, 119, -640, 765, settled).share).toBe(settled);
// A budget just over what the next step up wants is not room: one far over it is.
const next = selectNodes(island(settled / 0.9), -300, 119, -640).length;
expect(fitRange(island, -300, 119, -640, next + 1, settled).share).toBe(settled);
expect(fitRange(island, -300, 119, -640, next * 2, settled).share).toBeCloseTo(settled / 0.9, 9);
});
});