Building on Voxel Terrain in Babylon.js · Part 3 of 10 in the series
Part 3: Walking on Blocks
Make the blocks solid for the player: the signed distance to a box, the nearest surface among the terrain and the blocks, a way out of a wall that leads into the open, and no blocks where the player stands.
Quest objectives
- Work out the signed distance from a point to a block
- Find the nearest surface of the terrain and the blocks together
- Push a point out of a block only where no other block is
- Let the player collide with that surface, unchanged otherwise
- Keep new blocks out of the player
The player of the terrain series walks right through the blocks: it only knows the terrain's density. It needs no physics engine, and it needs none now either. Its two balls, one at the feet and one at the head, ask a single question: how far is the nearest surface, and which way is out? It was answered by the density over its gradient. Blocks can answer it too.
The distance to a box
A signed distance is the distance from a point to the nearest point of a shape, below 0 inside it. For a box it is short to write. Measure the point from the box's middle and fold it into one corner with abs(): the box is the same in all eight. Then, per axis, subtract half the box's size. That says how far outside the box's slab the point is along that axis, below 0 if it is inside the slab.
If some of the three are above 0, the point is outside. The distance is the length of those parts: straight out from a side, or diagonally out from an edge or a corner.
If all three are below 0, the point is inside. The nearest side is the one whose number is closest to 0.
The way out, the normal, points from the box's nearest point to the point.
Out of a wall
One case needs care: a point inside a block that is part of a wall. The nearest side of that block may be the one it shares with the next block, and pushing out through it only pushes into the neighbor, which pushes back. So a point leaves a block only through a side that is open: one that no other block covers. The mesher of part 1 already knows which sides are covered. In src/blockMesher.ts, export Side and covered(), so that others can ask.
Inside, a side's plane is dir × p[axis] − half away, below 0. The largest of the open sides' numbers wins. If none is open, deep in a big structure, the way out is up.
All the solids
The nearest surface of the terrain is the one the player used so far: the density over the steepness of the gradient, about the distance in meters. The blocks are looked up in the cells within reach of the point, each block once, and the nearest surface of all wins. Create src/solids.ts:
import { CELL, type Block, type BlockStore } from './blocks.ts';
import { covered, SIDES } from './blockMesher.ts';
import type { Field } from './field.ts';
/** The nearest surface to a point: how far away it is, and which way is out. */
export interface Surface {
/** Meters from the point to the surface, below 0 inside a solid. */
distance: number;
/** One meter long, pointing out of the solid. */
normal: [number, number, number];
}
/**
* The distance from a point to a block, below 0 inside it: a signed distance. Each axis
* says how far the point is outside the block's slab along it; outside the box, the
* distance is the length of those that are above 0, inside it the largest of them.
* Inside, the way out is through the nearest side for which `isOpen(side)` says yes,
* by the side's number in SIDES.
*/
export function blockDistance(
block: Block,
x: number,
y: number,
z: number,
isOpen: (side: number) => boolean = () => true,
): Surface {
const half = (block.size * CELL) / 2;
// From the block's middle.
const p = [x - block.x * CELL - half, y - block.y * CELL - half, z - block.z * CELL - half];
const q = p.map((c) => Math.abs(c) - half);
const outside = q.map((c) => Math.max(c, 0));
const length = Math.hypot(...outside);
if (length > 0) {
// Out from the nearest point of the box.
const normal = outside.map((c, axis) => (c / length) * Math.sign(p[axis]));
return { distance: length, normal: normal as Surface['normal'] };
}
// Inside: out through the nearest open side, or up (side 3) if none is open. Each
// side's plane is dir × p[axis] - half away, below 0 since the point is inside.
let side = 3;
let distance = -Infinity;
SIDES.forEach(({ axis, dir }, s) => {
const d = dir * p[axis] - half;
if (d > distance && isOpen(s)) {
side = s;
distance = d;
}
});
if (distance === -Infinity) distance = p[1] - half;
const normal: Surface['normal'] = [0, 0, 0];
normal[SIDES[side].axis] = SIDES[side].dir;
return { distance, normal };
}
/** Everything solid: the terrain and the blocks. */
export class Solids {
private readonly field: Field;
private readonly store: BlockStore;
constructor(field: Field, store: BlockStore) {
this.field = field;
this.store = store;
}
/** The nearest surface to a point, if one is within `reach` meters. */
nearest(x: number, y: number, z: number, reach: number): Surface | null {
let nearest: Surface | null = null;
// The terrain: its density over how fast the density changes is about the distance
// to its surface, as the player worked it out so far.
const { density, gradient } = this.field.probe(x, y, z);
const steepness = Math.hypot(...gradient);
if (steepness > 0 && -density / steepness < reach) {
const normal = gradient.map((g) => -g / steepness) as Surface['normal'];
nearest = { distance: -density / steepness, normal };
}
// The blocks with a cell within reach, each once.
const seen = new Set<Block>();
const from = (c: number) => Math.floor((c - reach) / CELL);
const to = (c: number) => Math.floor((c + reach) / CELL);
for (let k = from(z); k <= to(z); k += 1) {
for (let j = from(y); j <= to(y); j += 1) {
for (let i = from(x); i <= to(x); i += 1) {
const block = this.store.at(i, j, k);
if (!block || seen.has(block)) continue;
seen.add(block);
// Out of a block only where no other block fills the cells beyond.
const surface = blockDistance(block, x, y, z, (side) => !covered(this.store, block, SIDES[side]));
if (surface.distance < reach && (!nearest || surface.distance < nearest.distance)) nearest = surface;
}
}
}
return nearest;
}
}Outside the blocks, the nearest of their distances is exactly the distance to all of them together. That's a property of signed distances: the distance to a union is the smallest of the distances. Inside, it isn't, which is why the way out needs the open sides.
The player
The player keeps everything it did: the speed, the jump, the steps down a slope. Only its question changes. It gets Solids instead of the terrain's Field, and asks for the nearest surface within its radius. In src/player.ts, export the size of the body:
/** The body: two balls of this radius, one at the feet and one at the head. */
export const RADIUS = 0.4;
export const HEIGHT = 1.8;Replace the head of the class, and replace the import of Field with one of Solids from ./solids.ts:
/** A body that walks on the terrain and the blocks, with no physics engine. */
export class Player {
/** Where the feet are. */
readonly position: Vector3;
readonly velocity = new Vector3();
grounded = false;
private readonly solids: Solids;
constructor(solids: Solids, feet: Vector3) {
this.solids = solids;
this.position = feet.clone();
}Replace collide():
/** Pushes both balls out of the ground and the blocks. */
private collide(): void {
this.grounded = false;
for (let pass = 0; pass < 3; pass += 1) {
for (const height of [RADIUS, HEIGHT - RADIUS]) {
const surface = this.solids.nearest(
this.position.x,
this.position.y + height,
this.position.z,
RADIUS,
);
if (!surface) continue;
const depth = RADIUS - surface.distance;
const normal = new Vector3(...surface.normal);
if (normal.y > WALKABLE) {
// Ground: straight up, so that the player doesn't slide down a slope.
this.position.y += depth / normal.y;
this.velocity.y = Math.max(this.velocity.y, 0);
this.grounded = true;
} else {
// A wall or a ceiling: back out along the normal, and stop moving into it.
this.position.addInPlace(normal.scale(depth));
const into = Vector3.Dot(this.velocity, normal);
if (into < 0) this.velocity.subtractInPlace(normal.scale(into));
}
}
}
}The surface's distance takes the place of the density over the steepness, and its normal the place of the gradient. A block's top is ground, since its normal points straight up; its side is a wall. Near an edge the normal leans, and the player slides off the edge as off a rounded one.
Not in the player
A block put where the player stands would trap it. The tool asks before it places one. In src/buildTool.ts, add a field to BlockTool:
/** Whether a block may go somewhere, besides fitting between the other blocks. */
canPlace: (block: Block) => boolean = () => true;And ask it in update(), where the tool checks whether the block fits:
const fits = this.store.fits(block.x, block.y, block.z, block.size) && this.canPlace(block);In src/main.ts, hand the player the solids. The import of Field stays, and Solids and blockDistance come from ./solids.ts, RADIUS and HEIGHT from ./player.ts:
const player = new Player(new Solids(new Field(world.edits), blocks.store), feet);And after the tools are made, tell the block tool where the player is. Three balls along the body, at the feet, the middle and the head, cover it well enough:
// A block may not go where the player stands: balls at the feet, the middle and the head
// must stay clear of it. Flying, the camera goes through anything.
blockTool.canPlace = (block) => {
if (mode === 'fly') return true;
const { x, y, z } = player.position;
return [RADIUS, HEIGHT / 2, HEIGHT - RADIUS].every(
(height) => blockDistance(block, x, y + height, z).distance >= RADIUS,
);
};Try it
Build a low wall and walk into it: you stop. Jump on it and walk along the top. Put a block in front of your feet: the ghost turns red when it would reach into you. Build a tower, step off its edge, and fall down beside it. Then fly up with F, put a block where your feet will be, and land: the player is pushed out of it, through the nearest side nothing covers.