Bauen auf Voxel-Terrain in Babylon.js · Teil 6 von 10 der Serie
Teil 6: Was einen Block hält
Entscheide, welche Blöcke stehen: Ein Block hält, solange eine Kette sich an Seiten oder Kanten berührender Blöcke zu einem führt, den der Boden hält. Durchsuche Gruppen den untersten Block zuerst, zeig in Orange, was mit dem anvisierten Block fiele, und bau eine Szene zum Ausprobieren.
Quest-Ziele
- Wissen, wann zwei Blöcke einander halten und wann der Boden einen Block hält
- Die Gruppen finden, die nichts hält, abwärts zuerst gesucht, mit einem Heap
- Nur dort suchen, wo ein Block abgebaut oder der Boden gegraben wurde
- Zeigen, was mit dem anvisierten Block fiele, bevor du ihn abbaust
- Eine Szene in Code bauen, die auf unebenem Boden steht
Bisher bleibt ein Block, wo du ihn lässt, notfalls in der Luft. So funktionieren viele Blockspiele, und es macht das Bauen leicht, aber es heißt auch, dass nie etwas herunterfallen kann. Diese Serie will Gebäude, die auseinanderfallen, also braucht ein Block etwas, das ihn hält. Dieser Teil entscheidet, was einen Block hält, und findet die Blöcke, die ihren Halt verloren haben. Vorerst verschwinden sie einfach; Teil 7 lässt sie fallen.
Die Regeln
Der Boden hält einen Block, wenn fester Boden höchstens 20 cm von seiner Box entfernt ist: unter ihm, aber auch neben ihm, an einer Klippe, oder über ihm, an der Decke einer Höhle. Ein Block, der halb in einen Hang gesunken ist, wird gehalten, und ebenso einer, der in die Seite eines Hügels gegraben ist. Der Test fragt die Dichte des Terrains an einem Punkt knapp außerhalb der Mitte jeder Zelle auf jeder Seite des Blocks.
Blöcke halten einander, wenn sie sich an einer Seite oder einer Kante berühren. Eine Seite ist der naheliegende Fall: ein Block auf einem anderen. Eine Kante zählt für Diagonalen: Eine Treppe aus Blöcken, jeder eine Stufe hinauf und eine hinüber, berührt sich nur an Kanten und soll stehen. Blöcke, die sich nur an einem Eckpunkt treffen, halten einander nicht: Das wäre zu dünn, um es zu glauben.
Ein Block hält, solange eine Kette sich berührender Blöcke von ihm zu einem Block führt, den der Boden hält. Es gibt keine Festigkeit, kein Gewicht, kein Gleichgewicht: Ein Balken aus hundert Blöcken steht auf einer Ecke, wie in einem Blockspiel. Einfache Regeln sind beim Bauen leicht zu durchschauen. Teil 9 bringt Festigkeit ins Spiel, auf andere Art.
Gruppen
Die Blöcke, die sich berühren, bilden Gruppen. Entweder hat eine Gruppe einen Block, den der Boden hält, und sie hält ganz, oder sie hat keinen, und sie ist ganz lose. Eine lose Gruppe kommt als ein Stück herunter, und genau das braucht Teil 7.
Um herauszufinden, ob eine Gruppe hält, durchsuche sie von einem ihrer Blöcke aus: Besuche die berührenden Nachbarn des Blocks, deren Nachbarn und so weiter, bis ein Block auftaucht, den der Boden hält, oder die Gruppe zu Ende ist. Die Reihenfolge entscheidet über das Tempo. Der Boden ist unten, also schaut die Suche zuerst auf den untersten Block, den sie kennt. In einem hohen Gebäude geht eine Suche vom Dach geradewegs die nächste Wand hinunter zum Boden und hört dort auf, ohne die anderen Räume zu besuchen. Die wartenden Blöcke liegen in einem binären Heap, der den untersten in wenigen Schritten herausgibt, egal wie viele warten.
Wo suchen
Nach jeder Änderung jedes Gebäude zu durchsuchen, wäre Verschwendung. Eine Gruppe kann ihren Halt nur verlieren, wenn etwas unter ihr verschwindet, also beginnt die Suche bei Saatblöcken: den Blöcken, die einen Block berührt haben, als er weggenommen wurde, und den Blöcken nahe Boden, der gegraben wurde. Ein Saatblock, dessen Gruppe noch hält, kostet eine Suche bis zum Boden; ein loser wird ganz gefunden.
Der Speicher muss sagen, wann ein Block geht, nachdem er weg ist, und seine Änderungen für die Vorschau unten zählen. Ergänze in src/blocks.ts die Felder von BlockStore:
/** Counts up with every change. */
revision = 0;
/** Called with every block that is added, removed or reshaped. */
onChange: (block: Block) => void = () => {};
/** Called with every block that is removed, after it is gone. */
onRemove: (block: Block) => void = () => {};Zähl auch in add() und reshape() hoch, mit this.revision += 1; vor onChange. Ersetze remove():
remove(block: Block): void {
if (this.at(block.x, block.y, block.z) !== block) return;
forEachCell(block, (x, y, z) => this.cells.delete(cellKey(x, y, z)));
const region = regionOf(block.x, block.y, block.z);
this.regions.get(region)?.delete(block);
if (this.regions.get(region)?.size === 0) this.regions.delete(region);
this.count -= 1;
this.revision += 1;
this.onChange(block);
this.onRemove(block);
}Die Welt sagt, wann sich das Terrain ändert. Ergänze in src/world.ts ein Feld in World, ruf es in edit() direkt nach this.workers.broadcast(edit); als this.onEdit(box); auf, und importiere den Typ SampleBox aus ./edits.ts:
/** Called after every edit, with the samples it changed. */
onEdit: (box: SampleBox) => void = () => {};Nun der Halt. Lege src/support.ts an:
import { CELL, cellKey, type Block, type BlockStore } from './blocks.ts';
import type { SampleBox } from './edits.ts';
import type { Field } from './field.ts';
import { CHUNK_SIZE } from './grid.ts';
/** How far solid ground may be from a block's box and still hold it, in meters. */
const GROUND_REACH = 0.2;
/**
* Calls `visit` with every block that touches a block by a side or an edge, each once.
* They fill the cells around the block that lie beside it on one axis (a side) or on two
* (an edge). A cell beside it on all three axes only meets it at a corner, which holds
* nothing.
*/
export function forEachTouching(store: BlockStore, block: Block, visit: (other: Block) => void): void {
const seen = new Set<Block>([block]);
const { x, y, z, size } = block;
const beside = (c: number, low: number) => (c < low || c >= low + size ? 1 : 0);
for (let k = z - 1; k <= z + size; k += 1) {
for (let j = y - 1; j <= y + size; j += 1) {
for (let i = x - 1; i <= x + size; i += 1) {
const axes = beside(i, x) + beside(j, y) + beside(k, z);
if (axes === 0 || axes === 3) continue;
const other = store.at(i, j, k);
if (other && !seen.has(other)) {
seen.add(other);
visit(other);
}
}
}
}
}
/**
* Whether the ground holds a block: solid ground within GROUND_REACH of its box. Points
* just outside the middle of each cell on each of its sides are tested, so the ground
* holds a block from below, but also a cliff beside it or a cave's ceiling above it.
*/
export function groundHolds(block: Block, field: Field): boolean {
const meters = block.size * CELL;
const low = [block.x * CELL, block.y * CELL, block.z * CELL];
for (let axis = 0; axis < 3; axis += 1) {
const u = (axis + 1) % 3;
const v = (axis + 2) % 3;
for (const dir of [-1, 1]) {
for (let a = 0; a < block.size; a += 1) {
for (let b = 0; b < block.size; b += 1) {
const p = [0, 0, 0];
p[axis] = dir > 0 ? low[axis] + meters + GROUND_REACH : low[axis] - GROUND_REACH;
p[u] = low[u] + (a + 0.5) * CELL;
p[v] = low[v] + (b + 0.5) * CELL;
if (field.probe(p[0], p[1], p[2]).density > 0) return true;
}
}
}
}
return false;
}
/** Blocks waiting to be looked at, the lowest first: a binary heap by height. */
class LowestFirst {
private readonly heap: Block[] = [];
push(block: Block): void {
const heap = this.heap;
heap.push(block);
// Up the heap while the parent is higher.
let i = heap.length - 1;
while (i > 0) {
const parent = (i - 1) >> 1;
if (heap[parent].y <= heap[i].y) break;
[heap[parent], heap[i]] = [heap[i], heap[parent]];
i = parent;
}
}
pop(): Block | undefined {
const heap = this.heap;
const lowest = heap[0];
const last = heap.pop();
if (heap.length > 0 && last) {
// The last one goes to the top, and down while a child is lower.
heap[0] = last;
let i = 0;
for (;;) {
const left = i * 2 + 1;
const right = left + 1;
let low = i;
if (left < heap.length && heap[left].y < heap[low].y) low = left;
if (right < heap.length && heap[right].y < heap[low].y) low = right;
if (low === i) break;
[heap[low], heap[i]] = [heap[i], heap[low]];
i = low;
}
}
return lowest;
}
}
/**
* The groups of blocks that nothing holds: blocks that touch each other, none of them held
* by the ground. Only the groups the `seeds` belong to are searched, and `gone` counts as
* taken away already. A search goes lowest block first, as the ground is below, and stops
* at the first block the ground holds: then its whole group holds.
*/
export function looseGroups(
store: BlockStore,
holds: (block: Block) => boolean,
seeds: Iterable<Block>,
gone?: Block,
): Block[][] {
const held = new Set<Block>();
const loose = new Set<Block>();
const groups: Block[][] = [];
for (const seed of seeds) {
if (seed === gone || held.has(seed) || loose.has(seed)) continue;
// A seed may have been removed since it was noted.
if (store.at(seed.x, seed.y, seed.z) !== seed) continue;
const reached = new Set<Block>([seed]);
const waiting = new LowestFirst();
waiting.push(seed);
let isHeld = false;
for (let block = waiting.pop(); block; block = waiting.pop()) {
if (held.has(block) || holds(block)) {
isHeld = true;
break;
}
forEachTouching(store, block, (other) => {
if (other === gone || reached.has(other)) return;
reached.add(other);
waiting.push(other);
});
}
for (const block of reached) (isHeld ? held : loose).add(block);
if (!isHeld) groups.push([...reached]);
}
return groups;
}
/** Keeps track of which blocks may have lost their hold, and finds the loose groups. */
export class Support {
/** Blocks whose hold may have changed since the last update. */
private readonly seeds = new Set<Block>();
/** Whether the ground holds a block, worked out once per change of the ground. */
private readonly grounded = new Map<Block, boolean>();
/** Counts up whenever the ground changes. */
private groundRevision = 0;
private preview: { block: Block; revision: string; falling: Block[] } | null = null;
private readonly store: BlockStore;
private readonly field: Field;
constructor(store: BlockStore, field: Field) {
this.store = store;
this.field = field;
}
/** A block was taken away: the blocks it touched may have lost their hold. */
removed(block: Block): void {
this.grounded.delete(block);
forEachTouching(this.store, block, (other) => this.seeds.add(other));
}
/** The terrain changed: the blocks near the changed samples may have lost their hold. */
groundChanged(box: SampleBox): void {
this.grounded.clear();
this.groundRevision += 1;
// The blocks of the regions around the box, as far as their boxes reach near it.
const reach = GROUND_REACH + 1;
const first = (axis: number) => Math.floor((box.low[axis] - reach - 2) / CHUNK_SIZE);
const last = (axis: number) => Math.floor((box.high[axis] + reach) / CHUNK_SIZE);
for (let z = first(2); z <= last(2); z += 1) {
for (let y = first(1); y <= last(1); y += 1) {
for (let x = first(0); x <= last(0); x += 1) {
for (const block of this.store.inRegion(cellKey(x, y, z))) {
const low = [block.x, block.y, block.z].map((c) => c * CELL);
const meters = block.size * CELL;
const near = [0, 1, 2].every(
(axis) => low[axis] - reach <= box.high[axis] && low[axis] + meters + reach >= box.low[axis],
);
if (near) this.seeds.add(block);
}
}
}
}
}
/** The groups of blocks that lost their hold since the last update. */
update(): Block[][] {
if (this.seeds.size === 0) return [];
const groups = looseGroups(this.store, this.holds, this.seeds);
this.seeds.clear();
return groups;
}
/** The blocks that would fall if `block` were taken away. Worked out once per change. */
wouldFall(block: Block): Block[] {
const revision = `${this.store.revision} ${this.groundRevision}`;
if (this.preview?.block === block && this.preview.revision === revision) return this.preview.falling;
const seeds: Block[] = [];
forEachTouching(this.store, block, (other) => seeds.push(other));
const falling = looseGroups(this.store, this.holds, seeds, block).flat();
this.preview = { block, revision, falling };
return falling;
}
private readonly holds = (block: Block): boolean => {
let holds = this.grounded.get(block);
if (holds === undefined) {
holds = groundHolds(block, this.field);
this.grounded.set(block, holds);
}
return holds;
};
}forEachTouching()geht die Zellen um einen Block ab, eine hinaus auf jeder Seite. Für jede zählt es, auf wie vielen Achsen die Zelle neben dem Block liegt: eine ist eine Seite, zwei eine Kante, drei nur eine Ecke.groundHolds()testet die Punkte knapp außerhalb der Zellen jeder Seite. Die Dichte kommt aus demFielddes Terrains, das auch die Edits liest, also zählt ein Loch, das unter einem Block gegraben wurde.LowestFirstist der Heap: eine Liste, in der jeder Block nicht höher liegt als die beiden unter ihm, also ist der unterste immer vorn.looseGroups()durchsucht die Gruppe jedes Saatblocks, außer eine frühere Suche hat sie schon beurteilt. Eine gehaltene Gruppe hört bei ihrem ersten gehaltenen Block auf; nur eine lose Gruppe wird ganz durchsucht und zurückgegeben.Supportsammelt Saatblöcke und rechnet die Gruppen einmal pro Frame aus. Es behält die Antwort des Bodens pro Block, bis sich der Boden ändert.
Was fallen würde
Bevor du einen Block abbaust, willst du wissen, was mit ihm herunterkommt. Dieselbe Suche beantwortet das: Nimm die Nachbarn des Blocks als Saatblöcke, zähl den Block als weg, und jede Gruppe, die lose auftaucht, fiele. wouldFall() behält seine Antwort, solange Blöcke und Boden gleich bleiben, also kostet es nichts, auf denselben Block zu zielen.
Die Antwort erscheint als orange Tönung über diesen Blöcken: ein durchscheinendes Mesh vom selben Mesher, ein wenig vor den Blöcken, damit es nicht in ihren Oberflächen untergeht. Lege src/tint.ts an:
import { Color3, StandardMaterial, type Mesh, type Scene } from '@babylonjs/core/pure';
import type { Block, BlockStore } from './blocks.ts';
import { meshBlocks } from './blockMesher.ts';
import { createMesh } from './meshData.ts';
/** A see-through color laid over some blocks, built again only when they change. */
export class Tint {
private mesh: Mesh | null = null;
private shown: Block[] | null = null;
private readonly material: StandardMaterial;
private readonly scene: Scene;
constructor(scene: Scene, color: string) {
this.scene = scene;
this.material = new StandardMaterial(`tint ${color}`, scene);
this.material.emissiveColor = Color3.FromHexString(color);
this.material.disableLighting = true;
this.material.alpha = 0.5;
// Drawn a little in front of the blocks, whose surfaces it lies on.
this.material.zOffset = -2;
}
/** Lays the tint over `blocks`; the same list as last time changes nothing. */
show(blocks: Block[], store: BlockStore): void {
if (blocks === this.shown) return;
this.hide();
this.shown = blocks;
const data = meshBlocks(blocks, store);
if (!data) return;
this.mesh = createMesh('tint', data, this.scene);
this.mesh.material = this.material;
this.mesh.isPickable = false;
}
hide(): void {
this.mesh?.dispose();
this.mesh = null;
this.shown = null;
}
}In src/buildTool.ts fragt das Block-Werkzeug, was fallen würde, und zeigt es. Ergänze seine Felder:
/** The blocks that would fall with a block if it were broken. */
wouldFall: (block: Block) => Block[] = () => [];
/** How many blocks would fall with the block aimed at. */
falling = 0;Ergänze ein privates fallTint: Tint, im Konstruktor mit this.fallTint = new Tint(scene, '#f97316'); erzeugt, und importiere Tint. hide() versteckt auch die Tönung:
hide(): void {
this.ghost.isVisible = false;
this.target.isVisible = false;
this.fallTint.hide();
this.falling = 0;
}Aber update() ruft hide() nicht mehr in jedem Frame auf: Die Tönung würde jeden Frame neu gebaut. Es versteckt die Boxen selbst, und die Tönung nur, wenn das Ziel die Blöcke verlässt. Ersetze update():
update(now: number): void {
this.ghost.isVisible = false;
this.target.isVisible = false;
const aim = aimAt(this.scene, this.camera, this.store, REACH);
if (aim?.kind !== 'block') {
this.fallTint.hide();
this.falling = 0;
}
if (!aim) {
this.clicked = null;
return;
}
const block = this.placement(aim);
const fits = this.store.fits(block.x, block.y, block.z, block.size) && this.canPlace(block);
placeMarker(this.ghost, block.x, block.y, block.z, block.size);
(this.ghost.material as StandardMaterial).emissiveColor = Color3.FromHexString(fits ? '#f97316' : '#ef4444');
if (aim.kind === 'block') {
const { x, y, z, size } = aim.block;
placeMarker(this.target, x, y, z, size, 0.02);
const falling = this.wouldFall(aim.block);
this.fallTint.show(falling, this.store);
this.falling = falling.length;
}
const action = this.clicked ?? (now - this.lastEdit >= REPEAT ? this.held : null);
this.clicked = null;
if (!action) return;
this.lastEdit = now;
if (action === 'break' && aim.kind === 'block') this.store.remove(aim.block);
if (action === 'place' && fits) this.store.add(block);
}Etwas zum Ausprobieren
Die Regeln sind an etwas schon Gebautem leichter zu sehen. Eine kleine Szene steht vor der Spielfigur: eine hohe Steinsäule, ein Balken aus Brettern, der von ihrer Spitze hinausragt, eine Kupferkugel, die am Ende des Balkens hängt, und ein Tisch aus Brettern unter der Kugel. Sie wird in Code gebaut, auf dem Boden, wie er ist. Jede Säule beginnt beim ersten ganzen Meter über dem höchsten Boden unter ihr, mit einem Block darunter im Boden, damit auf unebenem Boden nichts schwebt. Lege src/sample.ts an:
import { CELL, type BlockStore } from './blocks.ts';
import type { Field } from './field.ts';
import { sideEdges } from './shapes.ts';
import { surfaceHeight } from './terrain.ts';
/** The materials, by their numbers. */
const STONE = 0;
const PLANKS = 2;
const SLATE = 4;
const COPPER = 5;
/**
* Something to try the rules on, built in front of the player: a tall stone pillar with a beam
* of planks reaching out from its top, a copper ball hanging from the beam's end, and a
* table of planks under the ball. Break the beam next to the pillar, and the ball comes
* down. All of it is 1 m blocks, around the column at (x, z).
*/
export function buildSample(store: BlockStore, field: Field, x: number, z: number): void {
// The first whole meter above the highest ground under a 1 m column, in cells.
const groundCell = (cx: number, cz: number) => {
let top = -Infinity;
for (const [dx, dz] of [[0.1, 0.1], [0.9, 0.1], [0.1, 0.9], [0.9, 0.9]]) {
let y = surfaceHeight(cx * CELL + dx, cz * CELL + dz) + 12;
while (field.probe(cx * CELL + dx, y, cz * CELL + dz).density <= 0) y -= 0.1;
top = Math.max(top, y);
}
return Math.ceil(top / CELL / 2) * 2;
};
const add = (cx: number, cy: number, cz: number, material: number, cuts = 0, slope = false) =>
store.add({ x: cx, y: cy, z: cz, size: 2, material, cuts, slope });
// A whole number of meters, in cells.
const cx = Math.floor(x / CELL / 2) * 2;
const cz = Math.floor(z / CELL / 2) * 2;
// The pillar: from a block in the ground up seven, with a pyramid of slate on top.
const ground = groundCell(cx - 4, cz);
for (let y = ground - 2; y < ground + 14; y += 2) add(cx - 4, y, cz, STONE);
const pyramid = sideEdges(1, 1).reduce((cuts, edge) => cuts | (1 << edge), 0);
add(cx - 4, ground + 14, cz, SLATE, pyramid, true);
// The beam, out from the pillar's top block, and the ball under its end: all edges rounded.
for (let bx = cx - 2; bx <= cx + 2; bx += 2) add(bx, ground + 12, cz, PLANKS);
add(cx + 2, ground + 10, cz, COPPER, 0b111111111111);
// The table under the ball, its top a meter above the highest ground under its legs.
const legs = [[cx, cz - 2], [cx + 4, cz - 2], [cx, cz + 2], [cx + 4, cz + 2]];
const tableTop = Math.max(...legs.map(([lx, lz]) => groundCell(lx, lz))) + 2;
for (const [lx, lz] of legs) {
for (let y = groundCell(lx, lz) - 2; y < tableTop; y += 2) add(lx, y, lz, PLANKS);
}
for (let tx = cx; tx <= cx + 4; tx += 2) for (let tz = cz - 2; tz <= cz + 2; tz += 2) add(tx, tableTop, tz, PLANKS);
}In src/main.ts bekommt das Feld einen eigenen Namen, der Halt wird erzeugt, die Szene gebaut, und Speicher und Welt melden ihre Änderungen. Ersetze die Zeile der Spielfigur:
const field = new Field(world.edits);
const player = new Player(new Solids(field, blocks.store), feet);
// What holds the blocks: after a block is broken or the ground dug, the blocks around
// are checked, and the groups nothing holds any more go.
const support = new Support(blocks.store, field);
// Something to try the rules on, in front of the player.
buildSample(blocks.store, field, 96, 158);
blocks.store.onRemove = (block) => support.removed(block);
world.onEdit = (box) => support.groundChanged(box);Nach dem Erzeugen der Werkzeuge lernt das Block-Werkzeug zu fragen:
// Aiming at a block shows what would fall with it.
blockTool.wouldFall = (block) => support.wouldFall(block);Im Frame, nach den Werkzeugen, verschwinden die losen Gruppen:
// For now, loose blocks just vanish.
for (const group of support.update()) for (const block of group) blocks.store.remove(block);Und das HUD zählt, was fallen würde:
blocks:
`Blocks: ${MATERIALS[blockTool.material].name}, ${blockTool.size * CELL} m, ${blocks.store.count} placed` +
(blockTool.falling > 0 ? `\nBreaking this drops ${blockTool.falling} more` : ''),Importiere Support aus ./support.ts und buildSample aus ./sample.ts.
Ausprobieren
Ziel auf den Block des Balkens neben der Säule: Der Rest des Balkens und die Kugel leuchten orange auf, und das HUD sagt, dass drei weitere fielen. Bau ihn ab, und sie sind weg. Ziel auf den untersten Block der Säule über dem Boden: Die ganze Säule darüber leuchtet auf, mit dem Balken und der Kugel, denn sonst hält sie nichts. Bau einen Turm auf der Wiese und grab mit dem Terrain-Werkzeug unter ihm: Wenn das Loch tief genug ist, dass sein unterster Block den Boden nicht mehr berührt, verschwindet der Turm. Bau eine Treppe aus Blöcken, die sich nur an ihren Kanten berühren: Sie steht.
