alex/beta-minecraft-rust
Minecraft Beta 1.7.3 Rewrite
BRANCH main
SNAPSHOT Draw terrain GPU-driven from packed per-section buffers with GPU occlusion culling, add a render distance slider (2-128) with a quad/disk shape, cut chunk bookkeeping at high render distances, and fix a light underflow at y=0
DOWNLOAD
root crates common src world light.rs
use std::ops::Range;
use std::sync::{Arc, LazyLock};
use rustc_hash::{FxHashMap, FxHashSet};
use super::chunk::{self, HEIGHT, Nibbles, VOLUME, WIDTH};
use super::{Block, Chunk, ChunkPos};
/// Loaded chunks the light engine works on.
pub trait ChunkMap {
fn chunk(&self, pos: ChunkPos) -> Option<&Chunk>;
fn chunk_mut(&mut self, pos: ChunkPos) -> Option<&mut Chunk>;
}
impl ChunkMap for rustc_hash::FxHashMap<ChunkPos, Box<Chunk>> {
fn chunk(&self, pos: ChunkPos) -> Option<&Chunk> {
self.get(&pos).map(Box::as_ref)
}
fn chunk_mut(&mut self, pos: ChunkPos) -> Option<&mut Chunk> {
self.get_mut(&pos).map(Box::as_mut)
}
}
/// Shared chunks, copied on their first change.
impl ChunkMap for rustc_hash::FxHashMap<ChunkPos, Arc<Chunk>> {
fn chunk(&self, pos: ChunkPos) -> Option<&Chunk> {
self.get(&pos).map(Arc::as_ref)
}
fn chunk_mut(&mut self, pos: ChunkPos) -> Option<&mut Chunk> {
self.get_mut(&pos).map(Arc::make_mut)
}
}
/// Mirrors `EnumSkyBlock`.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum LightKind {
Sky,
Block,
}
/// Deferred light updates, the counterpart of `World.scheduleLightingUpdate`.
///
/// The original relaxes queued boxes with `MetadataChunkBlock.updateLight` under per-tick
/// budgets, which can leave stale light behind. This settles every queued position and
/// everything it affects to the rule `max(source, max(neighbors) - max(opacity, 1))`. With
/// opacity at least 1 that fixed point is unique.
#[derive(Default)]
pub struct LightQueue {
sky: Vec<(i32, i32, i32)>,
block: Vec<(i32, i32, i32)>,
/// Chunks whose borders are checked on both sides.
borders: Vec<ChunkPos>,
/// Chunks holding queued positions or borders, possibly repeated.
chunks: Vec<ChunkPos>,
}
/// How many chunks around [`LightQueue::chunks`] a run may read or write: light spreads at most
/// 15 blocks from what it checks, which includes the rows next to a border, and refills read one
/// block beyond.
pub const REACH: i32 = 2;
impl LightQueue {
fn touch(&mut self, x: i32, z: i32) {
let pos = ChunkPos::containing(x, z);
if self.chunks.last() != Some(&pos) {
self.chunks.push(pos);
}
}
/// Queues a changed block: its own light sources and opacity changed.
pub fn push_block(&mut self, x: i32, y: i32, z: i32) {
self.sky.push((x, y, z));
self.block.push((x, y, z));
self.touch(x, z);
}
/// Queues sky light written directly into a column, together with every neighbor.
pub fn push_column(&mut self, x: i32, z: i32, ys: Range<usize>) {
let (low, high) = (ys.start as i32 - 1, ys.end as i32);
let sides = [(0, 0), (-1, 0), (1, 0), (0, -1), (0, 1)];
for y in low..=high {
for (dx, dz) in sides {
self.sky.push((x + dx, y, z + dz));
}
}
for (dx, dz) in sides {
self.touch(x + dx, z + dz);
}
}
/// Queues a freshly loaded chunk, which only has column sky light, and both sides of its borders.
pub fn push_chunk(&mut self, chunk: &Chunk) {
let (base_x, base_z) = (chunk.pos.min_block_x(), chunk.pos.min_block_z());
let emission = &TABLES.emission;
for x in 0..WIDTH {
for z in 0..WIDTH {
let (bx, bz) = (base_x + x as i32, base_z + z as i32);
// The top of a column capped at 127 sees the sky but has column light below 15
for y in 0..=chunk.height(x, z) {
self.sky.push((bx, y as i32, bz));
}
let column = chunk::index(x, 0, z);
for y in 0..HEIGHT {
if emission[usize::from(chunk.blocks().get(column + y).0)] > 0 {
self.block.push((bx, y as i32, bz));
}
}
}
}
self.push_borders(chunk);
}
/// Queues both sides of a chunk's borders, where light may cross into or out of it.
pub fn push_borders(&mut self, chunk: &Chunk) {
self.borders.push(chunk.pos);
self.touch(chunk.pos.min_block_x(), chunk.pos.min_block_z());
}
/// The chunks holding queued positions, with repeats. A run stays within [`REACH`] of them.
pub fn chunks(&self) -> &[ChunkPos] {
&self.chunks
}
pub fn is_empty(&self) -> bool {
self.sky.is_empty() && self.block.is_empty() && self.borders.is_empty()
}
/// Settles all queued positions. Returns the 16³ sections whose light, or a neighbor's
/// light next to them, changed, as section coordinates.
pub fn process(&mut self, chunks: &mut impl ChunkMap) -> FxHashSet<[i32; 3]> {
let mut engine = Engine::new(chunks);
engine.run(SKY, &mut self.sky, &self.borders);
engine.run(BLOCK, &mut self.block, &self.borders);
self.borders.clear();
self.chunks.clear();
engine.finish()
}
}
const SKY: usize = 0;
const BLOCK: usize = 1;
/// Per block id: `max(opacity, 1)`, the light lost entering it, and its light emission.
struct Tables {
cost: [u8; 256],
emission: [u8; 256],
}
static TABLES: LazyLock<Tables> = LazyLock::new(|| Tables {
cost: std::array::from_fn(|id| Block(id as u8).light_opacity().max(1)),
emission: std::array::from_fn(|id| Block(id as u8).light_emission()),
});
const UNRESOLVED: u32 = u32::MAX;
const MISSING: u32 = u32::MAX - 1;
/// No direction to skip.
const ALL: u8 = 6;
/// A chunk taking part in a run. The arrays are shared with the chunk until written, and packed
/// block ids are unpacked for quick access.
struct Slot {
pos: ChunkPos,
blocks: Arc<[Block; VOLUME]>,
heights: [u8; WIDTH * WIDTH],
has_sky: bool,
light: [Nibbles; 2],
/// Written sections per kind, as bits of their section y.
written: [u8; 2],
/// Slots of the chunks at -x, +x, -z and +z, resolved on first use.
neighbors: [u32; 4],
/// Changed sections as bits `((dx + 1) * 3 + dz + 1) * 10 + sy + 1`, relative to this column.
changed: u128,
}
/// A position with the light it carries and the direction it was reached through, which
/// cannot be affected in turn.
#[derive(Clone, Copy)]
struct Entry {
slot: u32,
index: u16,
level: u8,
from: u8,
}
/// Flood fill in the manner of Starlight: queued positions are checked once, then light spreads
/// breadth first from increases, and decreases clear what they lit before the surrounding
/// light refills it.
struct Engine<'a, C: ChunkMap> {
chunks: &'a mut C,
slots: Vec<Slot>,
index: FxHashMap<ChunkPos, u32>,
increases: Vec<Entry>,
decreases: Vec<Entry>,
tables: &'static Tables,
}
impl<'a, C: ChunkMap> Engine<'a, C> {
fn new(chunks: &'a mut C) -> Self {
Self {
chunks,
slots: Vec::new(),
index: FxHashMap::default(),
increases: Vec::new(),
decreases: Vec::new(),
tables: &TABLES,
}
}
/// The slot of a chunk, or [`MISSING`].
fn slot(&mut self, pos: ChunkPos) -> u32 {
let Self {
chunks,
slots,
index,
..
} = self;
*index.entry(pos).or_insert_with(|| {
let Some(chunk) = chunks.chunk(pos) else {
return MISSING;
};
chunk.heat.add(VOLUME as u32);
slots.push(Slot {
pos,
blocks: chunk.blocks().dense(),
heights: *chunk.height_map(),
has_sky: chunk.has_sky,
light: [chunk.sky_light.clone(), chunk.block_light.clone()],
written: [0; 2],
neighbors: [UNRESOLVED; 4],
changed: 0,
});
slots.len() as u32 - 1
})
}
fn neighbor(&mut self, slot: u32, side: usize) -> u32 {
let neighbor = self.slots[slot as usize].neighbors[side];
if neighbor != UNRESOLVED {
return neighbor;
}
let [dx, dz] = [[-1, 0], [1, 0], [0, -1], [0, 1]][side];
let neighbor = self.slot(self.slots[slot as usize].pos.offset(dx, dz));
self.slots[slot as usize].neighbors[side] = neighbor;
neighbor
}
/// The position one step in direction `dir` (-x, +x, -y, +y, -z, +z), if it is loaded.
#[inline(always)]
fn step(&mut self, slot: u32, index: usize, dir: u8) -> Option<(u32, usize)> {
let across = |engine: &mut Self, side, index| {
let neighbor = engine.neighbor(slot, side);
(neighbor != MISSING).then_some((neighbor, index))
};
match dir {
0 if index >> 11 == 0 => across(self, 0, index + (15 << 11)),
0 => Some((slot, index - (1 << 11))),
1 if index >> 11 == 15 => across(self, 1, index - (15 << 11)),
1 => Some((slot, index + (1 << 11))),
2 => (index & 127 != 0).then(|| (slot, index - 1)),
3 => (index & 127 != 127).then_some((slot, index + 1)),
4 if index >> 7 & 15 == 0 => across(self, 2, index + (15 << 7)),
4 => Some((slot, index - (1 << 7))),
5 if index >> 7 & 15 == 15 => across(self, 3, index - (15 << 7)),
_ => Some((slot, index + (1 << 7))),
}
}
fn light(&self, kind: usize, slot: u32, index: usize) -> u8 {
self.slots[slot as usize].light[kind].get(index)
}
/// Whether the engine may light this slot: sky light only exists under a sky.
fn lit(&self, kind: usize, slot: u32) -> bool {
kind == BLOCK || self.slots[slot as usize].has_sky
}
/// The light, source and cost of a position.
fn state(&self, kind: usize, slot: u32, index: usize) -> (u8, u8, u8) {
let data = &self.slots[slot as usize];
let block = usize::from(data.blocks[index].0);
let source = if kind == BLOCK {
self.tables.emission[block]
} else if index & 127 >= usize::from(data.heights[(index >> 7 & 15) << 4 | index >> 11]) {
15
} else {
0
};
(data.light[kind].get(index), source, self.tables.cost[block])
}
fn cost(&self, slot: u32, index: usize) -> u8 {
self.tables.cost[usize::from(self.slots[slot as usize].blocks[index].0)]
}
fn set(&mut self, kind: usize, slot: u32, index: usize, value: u8) {
let slot = &mut self.slots[slot as usize];
slot.light[kind].set(index, value);
slot.written[kind] |= 1 << ((index & 127) >> 4);
for dx in sections((index >> 11) as i32) {
for dz in sections((index >> 7 & 15) as i32) {
for sy in sections((index & 127) as i32) {
slot.changed |= 1 << (((dx + 1) * 3 + dz + 1) * 10 + sy + 1);
}
}
}
}
/// Checks the queued positions and borders against their neighbors, then spreads what
/// changed.
fn run(&mut self, kind: usize, queue: &mut Vec<(i32, i32, i32)>, borders: &[ChunkPos]) {
// Each side of a border is a row of columns at x = 0, x = 15, z = 0 or z = 15: two in the
// chunk, two in its neighbors. Rows shared by queued neighbors are checked once
let mut checked: Vec<u8> = Vec::new();
for &pos in borders {
for (dx, dz, row) in [
(-1, 0, 1),
(0, 0, 0),
(0, 0, 1),
(1, 0, 0),
(0, -1, 3),
(0, 0, 2),
(0, 0, 3),
(0, 1, 2),
] {
let slot = self.slot(pos.offset(dx, dz));
if slot == MISSING || !self.lit(kind, slot) {
continue;
}
checked.resize(self.slots.len(), 0);
let rows = &mut checked[slot as usize];
if *rows & 1 << row != 0 {
continue;
}
*rows |= 1 << row;
let edge = if row % 2 == 0 { 0 } else { 15 };
for i in 0..WIDTH {
let (x, z) = if row < 2 { (edge, i) } else { (i, edge) };
let column = chunk::index(x, 0, z);
for index in column..column + HEIGHT {
self.check(kind, slot, index);
}
}
}
}
let mut last = (ChunkPos::new(i32::MAX, i32::MAX), MISSING);
for (x, y, z) in queue.drain(..) {
if !(0..HEIGHT as i32).contains(&y) {
continue;
}
let pos = ChunkPos::containing(x, z);
if pos != last.0 {
last = (pos, self.slot(pos));
}
let slot = last.1;
if slot == MISSING || !self.lit(kind, slot) {
continue;
}
let index = chunk::index((x & 15) as usize, y as usize, (z & 15) as usize);
self.check(kind, slot, index);
}
let mut next = 0;
while let Some(&entry) = self.decreases.get(next) {
next += 1;
self.decrease(kind, entry);
}
self.decreases.clear();
let mut next = 0;
while let Some(&entry) = self.increases.get(next) {
next += 1;
self.increase(kind, entry);
}
self.increases.clear();
}
fn check(&mut self, kind: usize, slot: u32, index: usize) {
let (current, source, cost) = self.state(kind, slot, index);
let expected = if cost >= 15 && source == 0 {
0
} else if cost >= 15 - source {
source
} else {
let (x, y, z) = (index >> 11, index & 127, index >> 7 & 15);
let brightest = if (1..15).contains(&x) && (1..15).contains(&z) && (1..127).contains(&y)
{
let light = &self.slots[slot as usize].light[kind];
[2048, 1, 128]
.into_iter()
.map(|offset| light.get(index - offset).max(light.get(index + offset)))
.max()
.unwrap_or(0)
} else {
// `saved_light`: above and below the world reads the position itself, missing
// chunks read dark
(0..6)
.map(|dir| match self.step(slot, index, dir) {
Some((slot, index)) => self.light(kind, slot, index),
None if dir == 2 || dir == 3 => current,
None => 0,
})
.max()
.unwrap_or(0)
};
brightest.saturating_sub(cost).max(source)
};
let entry = |level| Entry {
slot,
index: index as u16,
level,
from: ALL,
};
if expected > current {
self.set(kind, slot, index, expected);
self.increases.push(entry(expected));
} else if expected < current {
self.set(kind, slot, index, source);
self.decreases.push(entry(current));
if source > 0 {
self.increases.push(entry(source));
}
}
}
/// Lights the neighbors that `entry` makes brighter.
fn increase(&mut self, kind: usize, entry: Entry) {
let index = usize::from(entry.index);
if self.light(kind, entry.slot, index) != entry.level {
return;
}
for dir in 0..6 {
if dir == entry.from {
continue;
}
let Some((slot, index)) = self.step(entry.slot, index, dir) else {
continue;
};
let target = entry.level.saturating_sub(self.cost(slot, index));
if target > self.light(kind, slot, index) && self.lit(kind, slot) {
self.set(kind, slot, index, target);
self.increases.push(Entry {
slot,
index: index as u16,
level: target,
from: dir ^ 1,
});
}
}
}
/// Clears the neighbors that `entry`'s former light may have lit, and queues the brighter
/// ones to refill the cleared space.
fn decrease(&mut self, kind: usize, entry: Entry) {
let index = usize::from(entry.index);
for dir in 0..6 {
if dir == entry.from {
continue;
}
let Some((slot, index)) = self.step(entry.slot, index, dir) else {
continue;
};
let (current, source, cost) = self.state(kind, slot, index);
if current == 0 || !self.lit(kind, slot) {
continue;
}
let neighbor = |level, from| Entry {
slot,
index: index as u16,
level,
from,
};
if current <= entry.level.saturating_sub(cost) && source < current {
self.set(kind, slot, index, source);
self.decreases.push(neighbor(current, dir ^ 1));
if source > 0 {
self.increases.push(neighbor(source, ALL));
}
} else {
self.increases.push(neighbor(current, ALL));
}
}
}
/// Writes the new light back into the chunks.
fn finish(self) -> FxHashSet<[i32; 3]> {
let mut changed = FxHashSet::default();
for slot in self.slots {
let [mut sky, mut block] = slot.light;
if slot.written == [0; 2] {
continue;
}
for bit in (0..90).filter(|bit| slot.changed >> bit & 1 != 0) {
let (column, sy) = (bit / 10, bit % 10 - 1);
let (dx, dz) = (column / 3 - 1, column % 3 - 1);
changed.insert([slot.pos.x + dx, sy, slot.pos.z + dz]);
}
let chunk = self
.chunks
.chunk_mut(slot.pos)
.unwrap_or_else(|| unreachable!());
if slot.written[SKY] != 0 {
sky.compact(slot.written[SKY]);
chunk.sky_light = sky;
}
if slot.written[BLOCK] != 0 {
block.compact(slot.written[BLOCK]);
chunk.block_light = block;
}
}
changed
}
}
/// The sections a coordinate within a column belongs to or borders on, as section offsets
/// (or section y).
fn sections(v: i32) -> std::ops::RangeInclusive<i32> {
let s = v >> 4;
match v & 15 {
0 => s - 1..=s,
15 => s..=s + 1,
_ => s..=s,
}
}
/// `WorldProvider.generateLightBrightnessTable`: the brightness of each light level, which never
/// gets fully dark, and less so in the Nether.
pub fn brightness_table(has_sky: bool) -> [f32; 16] {
let minimum = if has_sky { 0.05 } else { 0.1 };
std::array::from_fn(|level| {
let darkness = 1.0 - level as f32 / 15.0;
(1.0 - darkness) / (darkness * 3.0 + 1.0) * (1.0 - minimum) + minimum
})
}
/// `World.getSavedLightValue`: y is clamped into the world, missing chunks read as dark.
pub fn saved_light(chunks: &impl ChunkMap, kind: LightKind, x: i32, y: i32, z: i32) -> u8 {
let y = y.clamp(0, HEIGHT as i32 - 1) as usize;
chunks.chunk(ChunkPos::containing(x, z)).map_or(0, |chunk| {
light_array(chunk, kind).get(chunk::index((x & 15) as usize, y, (z & 15) as usize))
})
}
pub fn light_array(chunk: &Chunk, kind: LightKind) -> &Nibbles {
match kind {
LightKind::Sky => &chunk.sky_light,
LightKind::Block => &chunk.block_light,
}
}