Building on Voxel Terrain in Babylon.js · Part 6 of 10 in the series
Part 6: What Holds a Block
Decide which blocks stand: a block holds while a chain of blocks touching by a side or an edge leads to one the ground holds. Search groups lowest block first after a break or a dig, show in orange what would fall with the block you aim at, and build a little scene to try it on.
Quest objectives
- Know when two blocks hold each other, and when the ground holds a block
- Find the groups nothing holds, searching downward first with a heap
- Search only where a block was broken or the ground was dug
- Show what would fall with the block you aim at, before you break it
- Build a scene from code that stands on uneven ground
So far a block stays wherever you leave it, in the air if need be. That's how many block games work, and it makes building easy, but it also means nothing can ever fall down. This series wants buildings that come apart, so a block needs something to hold it. This part decides what holds a block, and finds the blocks that lost their hold. For now they simply vanish; part 7 lets them fall.
The rules
The ground holds a block when there is solid ground within 20 cm of its box: below it, but also beside it, against a cliff, or above it, on a cave's ceiling. A block sunk halfway into a slope is held, and so is one dug into the side of a hill. The test asks the terrain's density at a point just outside the middle of each cell on each side of the block.
Blocks hold each other when they touch by a side or by an edge. A side is the obvious case: a block on top of another. An edge matters for diagonals: a staircase of blocks, each one a step up and a step over, touches only by edges, and should stand. Blocks that meet only at a corner point don't hold each other: that would be too thin to believe.
A block holds while a chain of touching blocks leads from it to a block the ground holds. There is no strength, no weight, no balance: a beam of a hundred blocks stands on one corner, as in a block game. Simple rules are easy to see through when you build. Part 9 brings strength into it, in another way.
Groups
The blocks that touch each other form groups. Either a group has a block the ground holds, and all of it holds, or it hasn't, and all of it is loose. A loose group comes down as one piece, which is what part 7 needs.
To find out whether a group holds, search it from any of its blocks: visit the block's touching neighbors, theirs, and so on, until a block the ground holds turns up, or the group runs out. The order matters for speed. The ground is below, so the search looks at the lowest block it knows of first. In a tall building, a search from the roof goes straight down the nearest wall to the ground and stops there, without visiting the other rooms. The waiting blocks are kept in a binary heap, which hands out the lowest in a few steps however many are waiting.
Where to look
Searching every building after every change would be a waste. A group can only lose its hold when something under it goes, so the search starts from seeds: the blocks that touched a block when it was taken away, and the blocks near ground that was dug. A seed whose group still holds costs a search down to the ground; a loose one is found whole.
The store needs to tell when a block goes, after it is gone, and to count its changes for the preview below. In src/blocks.ts, add to the fields of 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 = () => {};Count up in add() and reshape() too, with this.revision += 1; before onChange. Replace 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);
}The world tells when the terrain changes. In src/world.ts, add a field to World, and call it in edit() right after this.workers.broadcast(edit);, as this.onEdit(box);, and import the type SampleBox from ./edits.ts:
/** Called after every edit, with the samples it changed. */
onEdit: (box: SampleBox) => void = () => {};Now the support. Create src/support.ts:
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()walks the cells around a block, one out on each side. For each it counts on how many axes the cell lies beside the block: one is a side, two an edge, three only a corner.groundHolds()tests the points just outside each side's cells. The density comes from the terrain'sField, which reads the edits too, so a hole dug under a block counts.LowestFirstis the heap: a list in which each block is no higher than the two below it, so the lowest is always first.looseGroups()searches each seed's group, unless an earlier search has already judged it. A held group stops at its first held block; only a loose group is searched whole, and comes back.Supportcollects seeds and works the groups out once a frame. It keeps the ground's answer per block, until the ground changes.
What would fall
Before you break a block, you want to know what comes down with it. The same search answers that: take the block's neighbors as seeds, count the block as gone, and every group that turns up loose would fall. wouldFall() keeps its answer while the blocks and the ground stay the same, so aiming at the same block costs nothing.
The answer is shown as an orange tint over those blocks: a see-through mesh made by the same mesher, a little in front of the blocks so that it isn't lost in their surfaces. Create src/tint.ts:
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, the block tool asks what would fall, and shows it. Add to its fields:
/** 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;Add a private fallTint: Tint, made in the constructor with this.fallTint = new Tint(scene, '#f97316');, and import Tint. hide() hides the tint too:
hide(): void {
this.ghost.isVisible = false;
this.target.isVisible = false;
this.fallTint.hide();
this.falling = 0;
}But update() no longer calls hide() each frame: the tint would be built again every frame. It hides the boxes itself, and the tint only when the aim leaves the blocks. Replace 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);
}Something to try it on
The rules are easier to see on something already built. A small scene stands in front of the player: a tall stone pillar, 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. It is built in code, on the ground as it is. Each column starts at the first whole meter above the highest ground under it, with one block sunk into the ground beneath, so that nothing floats on uneven ground. Create src/sample.ts:
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, the field gets a name of its own, the support is made, the scene built, and the store and the world report their changes. Replace the player's line:
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);After the tools are made, the block tool learns to ask:
// Aiming at a block shows what would fall with it.
blockTool.wouldFall = (block) => support.wouldFall(block);In the frame, after the tools, the loose groups go:
// For now, loose blocks just vanish.
for (const group of support.update()) for (const block of group) blocks.store.remove(block);And the HUD counts what would fall:
blocks:
`Blocks: ${MATERIALS[blockTool.material].name}, ${blockTool.size * CELL} m, ${blocks.store.count} placed` +
(blockTool.falling > 0 ? `\nBreaking this drops ${blockTool.falling} more` : ''),Import Support from ./support.ts and buildSample from ./sample.ts.
Try it
Aim at the block of the beam next to the pillar: the rest of the beam and the ball light up in orange, and the HUD says three more would drop. Break it, and they're gone. Aim at the pillar's lowest block above the ground: the whole pillar above it lights up, with the beam and the ball, since nothing else holds them. Build a tower on the meadow and dig under it with the terrain tool: when the hole is deep enough that its lowest block no longer touches the ground, the tower vanishes. Build a staircase of blocks touching only by their edges: it stands.
