Part 7: Streaming an Endless World

import type { Material, Mesh, Scene, Vector3 } from '@babylonjs/core/pure';
import { chunkKey, type ChunkPosition } from './chunks.ts';
import { CHUNK_SIZE } from './grid.ts';
import { createMesh, type MeshData } from './meshData.ts';
import type { MesherName } from './meshers.ts';
import { highestGround } from './terrain.ts';
import type { ChunkWorkers } from './workers.ts';

/** How far around the camera chunks are loaded, in chunks. */
export const VIEW_RADIUS = 8;
/** The lowest layer of chunks: below it the world is solid. */
const LOWEST_LAYER = -2;
/** Milliseconds per frame for handing new meshes to the graphics card. */
const SHOW_BUDGET = 4;

interface Chunk {
  position: ChunkPosition;
  mesh: Mesh | null;
  /** Counts up whenever the chunk has to be built again. */
  version: number;
  /** The version the chunk's mesh shows; -1 before it has one. */
  shown: number;
  /** The version a worker builds, or that waits to be shown; -1 when there is none. */
  pending: number;
}

interface Finished {
  chunk: Chunk;
  version: number;
  data: MeshData | null;
}

/** The chunks around the camera: which to load, build, show and drop. */
export class World {
  mesher: MesherName = 'marching-cubes';
  private readonly chunks = new Map<string, Chunk>();
  /** The highest layer of chunks that can hold ground, per column. */
  private readonly tops = new Map<string, number>();
  private readonly finished: Finished[] = [];
  private focus = { x: 0, y: 0, z: 0 };
  private readonly scene: Scene;
  private readonly material: Material;
  private readonly workers: ChunkWorkers;

  constructor(scene: Scene, material: Material, workers: ChunkWorkers) {
    this.scene = scene;
    this.material = material;
    this.workers = workers;
  }

  /** Switches the mesher. Every chunk is built again and keeps its mesh until then. */
  setMesher(mesher: MesherName): void {
    this.mesher = mesher;
    for (const chunk of this.chunks.values()) chunk.version += 1;
  }

  /** Once a frame: follows the camera at `focus`. */
  update(focus: Vector3): void {
    this.focus = { x: focus.x, y: focus.y, z: focus.z };
    this.dropFar();
    this.startJobs();
    this.showFinished();
  }

  /** How many chunks are loaded, and how many of them wait for a mesh. */
  get counts(): { loaded: number; waiting: number } {
    let waiting = 0;
    for (const chunk of this.chunks.values()) if (chunk.shown !== chunk.version) waiting += 1;
    return { loaded: this.chunks.size, waiting };
  }

  /** The column of chunks the camera is in. */
  private get center(): { x: number; z: number } {
    return { x: Math.floor(this.focus.x / CHUNK_SIZE), z: Math.floor(this.focus.z / CHUNK_SIZE) };
  }

  private dropFar(): void {
    const center = this.center;
    // A little beyond the view radius, so that chunks at the edge are not dropped and
    // loaded again while the camera moves back and forth.
    const limit = (VIEW_RADIUS + 1.5) ** 2;
    for (const [key, chunk] of this.chunks) {
      if ((chunk.position.x - center.x) ** 2 + (chunk.position.z - center.z) ** 2 <= limit) continue;
      chunk.mesh?.dispose();
      this.chunks.delete(key);
    }
    for (const key of this.tops.keys()) {
      const [x, z] = key.split(',').map(Number);
      if ((x - center.x) ** 2 + (z - center.z) ** 2 > limit) this.tops.delete(key);
    }
  }

  /** Gives every free worker the nearest chunk that needs building. */
  private startJobs(): void {
    if (this.workers.free === 0) return;
    const center = this.center;
    const wanted: { position: ChunkPosition; distance: number }[] = [];
    for (let dz = -VIEW_RADIUS; dz <= VIEW_RADIUS; dz += 1) {
      for (let dx = -VIEW_RADIUS; dx <= VIEW_RADIUS; dx += 1) {
        if (dx * dx + dz * dz > VIEW_RADIUS * VIEW_RADIUS) continue;
        const x = center.x + dx;
        const z = center.z + dz;
        for (let y = LOWEST_LAYER; y <= this.top(x, z); y += 1) {
          const chunk = this.chunks.get(chunkKey({ x, y, z }));
          if (chunk && (chunk.pending >= 0 || chunk.shown === chunk.version)) continue;
          const distance = Math.hypot(
            (x + 0.5) * CHUNK_SIZE - this.focus.x,
            (y + 0.5) * CHUNK_SIZE - this.focus.y,
            (z + 0.5) * CHUNK_SIZE - this.focus.z,
          );
          wanted.push({ position: { x, y, z }, distance });
        }
      }
    }
    wanted.sort((a, b) => a.distance - b.distance);

    for (const { position } of wanted.slice(0, this.workers.free)) {
      const key = chunkKey(position);
      let chunk = this.chunks.get(key);
      if (!chunk) {
        chunk = { position, mesh: null, version: 0, shown: -1, pending: -1 };
        this.chunks.set(key, chunk);
      }
      const job = chunk;
      const version = chunk.version;
      job.pending = version;
      this.workers.run({ chunk: position, mesher: this.mesher }).then((result) => {
        this.finished.push({ chunk: job, version, data: result.mesh });
        // The worker is free again: no need to wait for the next frame.
        this.startJobs();
      });
    }
  }

  /** The highest layer of chunks in a column that can hold ground. */
  private top(x: number, z: number): number {
    const key = `${x},${z}`;
    let top = this.tops.get(key);
    if (top === undefined) {
      top = Math.floor(highestGround(x * CHUNK_SIZE, z * CHUNK_SIZE, CHUNK_SIZE) / CHUNK_SIZE);
      this.tops.set(key, top);
    }
    return top;
  }

  /** Shows the meshes the workers made, as many as fit into the frame's budget. */
  private showFinished(): void {
    const started = performance.now();
    while (this.finished.length > 0 && performance.now() - started < SHOW_BUDGET) {
      const { chunk, version, data } = this.finished.shift()!;
      chunk.pending = -1;
      // Dropped while it was being built: the chunk is gone.
      if (this.chunks.get(chunkKey(chunk.position)) !== chunk) continue;
      chunk.mesh?.dispose();
      chunk.mesh = data ? this.createChunkMesh(chunk.position, data) : null;
      chunk.shown = version;
    }
  }

  private createChunkMesh(position: ChunkPosition, data: MeshData): Mesh {
    const mesh = createMesh(`chunk ${chunkKey(position)}`, data, this.scene);
    mesh.position.set(position.x * CHUNK_SIZE, position.y * CHUNK_SIZE, position.z * CHUNK_SIZE);
    mesh.material = this.material;
    // The chunk never moves: Babylon.js can stop working out its world matrix.
    mesh.freezeWorldMatrix();
    return mesh;
  }
}

/**
 * A height that no ground in the square from (x, z) to (x + size, z + size) rises above:
 * the highest of 5 × 5 heights in it, plus the overhangs and some room for a peak
 * between the samples.
 */
export function highestGround(x: number, z: number, size: number): number {
  let highest = -Infinity;
  for (let i = 0; i <= 4; i += 1) {
    for (let j = 0; j <= 4; j += 1) {
      highest = Math.max(highest, surfaceHeight(x + (i * size) / 4, z + (j * size) / 4));
    }
  }
  return highest + MOST_BEND + 16;
}

import {
  Color3,
  Color4,
  DirectionalLight,
  Engine,
  HemisphericLight,
  RegisterStandardEngineExtensions,
  RegisterStandardMaterial,
  Scene,
  StandardMaterial,
  UniversalCamera,
  Vector3,
} from '@babylonjs/core/pure';
import { CHUNK_SIZE } from './grid.ts';
import { MESHERS, otherMesher } from './meshers.ts';
import { surfaceHeight } from './terrain.ts';
import { ChunkWorkers } from './workers.ts';
import { VIEW_RADIUS, World } from './world.ts';
import './style.css';

RegisterStandardEngineExtensions();
RegisterStandardMaterial();

const canvas = document.querySelector<HTMLCanvasElement>('#game')!;
const hud = document.querySelector<HTMLElement>('#hud')!;

const engine = new Engine(canvas, true, {}, true);
const scene = new Scene(engine);
scene.clearColor = Color4.FromHexString('#2a1150ff');

// Fog hides the edge of the loaded chunks: it ends a little before the view radius.
const viewDistance = VIEW_RADIUS * CHUNK_SIZE;
scene.fogMode = Scene.FOGMODE_LINEAR;
scene.fogColor = Color3.FromHexString('#2a1150');
scene.fogStart = viewDistance * 0.5;
scene.fogEnd = viewDistance * 0.95;

// A cool light from the sky and a warm, low sun.
const sky = new HemisphericLight('sky', new Vector3(0, 1, 0), scene);
sky.intensity = 0.6;
sky.diffuse = Color3.FromHexString('#c4b5fd');
sky.groundColor = Color3.FromHexString('#3b1676');
const sun = new DirectionalLight('sun', new Vector3(0.5, -0.65, -0.55), scene);
sun.intensity = 1.1;
sun.diffuse = Color3.FromHexString('#ffd8a8');

const material = new StandardMaterial('ground', scene);
material.diffuseColor = Color3.FromHexString('#d9a066');
material.specularColor = Color3.Black();

const world = new World(scene, material, new ChunkWorkers());

// A flying camera: WASD to move, Q and E for down and up, drag the mouse to look.
const start = new Vector3(0, surfaceHeight(0, 40) + 25, 40);
const camera = new UniversalCamera('camera', start, scene);
camera.setTarget(new Vector3(0, surfaceHeight(0, -200) + 20, -200));
camera.keysUp = [87];
camera.keysDown = [83];
camera.keysLeft = [65];
camera.keysRight = [68];
camera.keysDownward = [81];
camera.keysUpward = [69];
camera.speed = 1;
camera.minZ = 0.1;
camera.maxZ = viewDistance * 1.2;
camera.attachControl();

window.addEventListener('keydown', (event) => {
  if (event.code === 'KeyL') material.wireframe = !material.wireframe;
  if (event.code === 'KeyM') world.setMesher(otherMesher(world.mesher));
  // Shift flies faster.
  if (event.key === 'Shift') camera.speed = 4;
});
window.addEventListener('keyup', (event) => {
  if (event.key === 'Shift') camera.speed = 1;
});

scene.onBeforeRenderObservable.add(() => {
  world.update(camera.position);
  const { loaded, waiting } = world.counts;
  const { x, y, z } = camera.position;
  hud.textContent =
    `${MESHERS[world.mesher].label}: ${loaded} chunks, ${waiting} waiting\n` +
    `x ${x.toFixed(0)}, y ${y.toFixed(0)}, z ${z.toFixed(0)}\n` +
    `${engine.getFps().toFixed(0)} fps`;
});

engine.runRenderLoop(() => scene.render());
window.addEventListener('resize', () => engine.resize());