bworld/client/workers/lighting.ts

// minecraft's lighting: every block has a sky light and a block light level from 0 to 15.
// sky light starts at 15 above the world and goes straight down without getting weaker until it hits
// something that isn't fully clear, block light starts at blocks that give off light. both spread to
// neighbors losing max(1, the neighbor's opacity) per step.
//
// minecraft stores light and updates it as blocks change. here it's worked out from scratch for the
// 3x3 chunks around the chunk being meshed, which gives the same result: light reaches at most 15
// blocks, so nothing outside those chunks can light the middle one or its border

import { AIR, CHUNK_AREA, CHUNK_HEIGHT, CHUNK_SIZE, ID_MASK } from "$/common/constants.ts";

export const REGION_SIZE = CHUNK_SIZE * 3;
export const REGION_LAYER = REGION_SIZE * REGION_SIZE;
export const REGION_VOLUME = REGION_LAYER * CHUNK_HEIGHT;
// what unloaded chunks and the space below the world are made of: opaque, dark, never shown
export const REGION_VOID = ID_MASK;

// by numeric block id
export interface LightTables {
	opacity: Uint8Array;
	emission: Uint8Array;
}

export class LightRegion {
	// block ids without their state bits, indexed y * REGION_LAYER + z * REGION_SIZE + x
	blocks = new Uint16Array(REGION_VOLUME);
	sky = new Uint8Array(REGION_VOLUME);
	block_light = new Uint8Array(REGION_VOLUME);

	// the lowest y that still sees the sky, per column
	#heights = new Int32Array(REGION_LAYER);
	#queue = new Int32Array(1 << 18);
	#queue_length = 0;

	// the 3x3 chunks around the one being meshed, going +x then +z, starting at -x -z. missing ones are void
	fill(chunks: (Uint32Array | null)[]) {
		for (let i = 0; i < 9; i++) {
			const source = chunks[i];
			const origin = Math.floor(i / 3) * CHUNK_SIZE * REGION_SIZE + (i % 3) * CHUNK_SIZE;
			for (let y = 0; y < CHUNK_HEIGHT; y++) {
				for (let z = 0; z < CHUNK_SIZE; z++) {
					const to = y * REGION_LAYER + origin + z * REGION_SIZE;
					if (!source) {
						this.blocks.fill(REGION_VOID, to, to + CHUNK_SIZE);
						continue;
					}
					const from = y * CHUNK_AREA + z * CHUNK_SIZE;
					for (let x = 0; x < CHUNK_SIZE; x++) {
						this.blocks[to + x] = source[from + x] & ID_MASK;
					}
				}
			}
		}
	}

	compute(tables: LightTables) {
		this.#compute_sky(tables);
		this.#compute_block_light(tables);
	}

	#compute_sky({ opacity }: LightTables) {
		const { blocks, sky } = this;
		sky.fill(0);
		this.#queue_length = 0;

		// straight down from the top, until something isn't fully clear
		for (let column = 0; column < REGION_LAYER; column++) {
			let y = CHUNK_HEIGHT - 1;
			while (y >= 0 && opacity[blocks[y * REGION_LAYER + column]] === 0) {
				sky[y * REGION_LAYER + column] = 15;
				y--;
			}
			this.#heights[column] = y + 1;
		}

		// only the lit cells next to a darker one can spread: the bottom of each column's sunlight,
		// and the part of it that's beside a neighbor column's shade
		for (let z = 0; z < REGION_SIZE; z++) {
			for (let x = 0; x < REGION_SIZE; x++) {
				const column = z * REGION_SIZE + x;
				const height = this.#heights[column];
				let highest_neighbor = height;
				if (x > 0) highest_neighbor = Math.max(highest_neighbor, this.#heights[column - 1]);
				if (x < REGION_SIZE - 1) highest_neighbor = Math.max(highest_neighbor, this.#heights[column + 1]);
				if (z > 0) highest_neighbor = Math.max(highest_neighbor, this.#heights[column - REGION_SIZE]);
				if (z < REGION_SIZE - 1) {
					highest_neighbor = Math.max(highest_neighbor, this.#heights[column + REGION_SIZE]);
				}
				const top = Math.min(CHUNK_HEIGHT - 1, Math.max(height, highest_neighbor - 1));
				for (let y = height; y <= top; y++) {
					this.#push(y * REGION_LAYER + column);
				}
			}
		}

		this.#propagate(sky, opacity, true);
	}

	#compute_block_light({ opacity, emission }: LightTables) {
		const { blocks, block_light } = this;
		block_light.fill(0);
		this.#queue_length = 0;

		for (let i = 0; i < REGION_VOLUME; i++) {
			const level = emission[blocks[i]];
			if (level > 0) {
				block_light[i] = level;
				this.#push(i);
			}
		}

		this.#propagate(block_light, opacity, false);
	}

	#push(index: number) {
		if (this.#queue_length === this.#queue.length) {
			const bigger = new Int32Array(this.#queue.length * 2);
			bigger.set(this.#queue);
			this.#queue = bigger;
		}
		this.#queue[this.#queue_length++] = index;
	}

	// breadth first from everything queued. a cell can be queued again when a brighter path reaches it
	#propagate(light: Uint8Array, opacity: Uint8Array, is_sky: boolean) {
		const blocks = this.blocks;

		const spread = (to: number, level: number, down: boolean) => {
			const block_opacity = opacity[blocks[to]];
			const next = is_sky && down && level === 15 && block_opacity === 0
				? 15
				: level - Math.max(1, block_opacity);
			if (next > light[to]) {
				light[to] = next;
				this.#push(to);
			}
		};

		for (let head = 0; head < this.#queue_length; head++) {
			const index = this.#queue[head];
			const level = light[index];
			if (level <= 1) continue;

			const y = Math.floor(index / REGION_LAYER);
			const rest = index - y * REGION_LAYER;
			const z = Math.floor(rest / REGION_SIZE);
			const x = rest - z * REGION_SIZE;

			if (y > 0) spread(index - REGION_LAYER, level, true);
			if (y < CHUNK_HEIGHT - 1) spread(index + REGION_LAYER, level, false);
			if (x > 0) spread(index - 1, level, false);
			if (x < REGION_SIZE - 1) spread(index + 1, level, false);
			if (z > 0) spread(index - REGION_SIZE, level, false);
			if (z < REGION_SIZE - 1) spread(index + REGION_SIZE, level, false);
		}
		this.#queue_length = 0;
	}
}

// what a cell looks like to the mesher, including above and below the world
export function region_block(region: LightRegion, index: number, y: number) {
	if (y >= CHUNK_HEIGHT) return AIR;
	if (y < 0) return REGION_VOID;
	return region.blocks[index];
}

export function region_sky(region: LightRegion, index: number, y: number) {
	if (y >= CHUNK_HEIGHT) return 15;
	if (y < 0) return 0;
	return region.sky[index];
}

export function region_block_light(region: LightRegion, index: number, y: number) {
	if (y >= CHUNK_HEIGHT || y < 0) return 0;
	return region.block_light[index];
}