steel_core/chunk/light/
queue.rs

1use std::iter::FusedIterator;
2
3use steel_utils::{BlockPos, Direction};
4
5use super::{MAX_LIGHT_LEVEL, PackedLightBlockPos};
6
7const QUEUE_ENTRY_LEVEL_MASK: u64 = 0b1111;
8const QUEUE_ENTRY_DIRECTIONS_MASK: u64 = 0b11_1111_0000;
9const QUEUE_ENTRY_FLAG_FROM_EMPTY_SHAPE: u64 = 1 << 10;
10const QUEUE_ENTRY_FLAG_INCREASE_FROM_EMISSION: u64 = 1 << 11;
11const LIGHT_QUEUE_MIN_CAPACITY: usize = 512;
12const PACKED_LIGHT_QUEUE_MIN_CAPACITY: usize = 16 * 16 * 16;
13const PACKED_LIGHT_QUEUE_POSITION_BITS: u64 = 28;
14const PACKED_LIGHT_QUEUE_LEVEL_BITS: u64 = 4;
15const PACKED_LIGHT_QUEUE_DIRECTION_BITS: u64 = 6;
16const PACKED_LIGHT_QUEUE_LEVEL_MASK: u64 = (1 << PACKED_LIGHT_QUEUE_LEVEL_BITS) - 1;
17const PACKED_LIGHT_QUEUE_DIRECTION_MASK: u8 = (1 << PACKED_LIGHT_QUEUE_DIRECTION_BITS) - 1;
18const PACKED_LIGHT_QUEUE_LEVEL_SHIFT: u64 = PACKED_LIGHT_QUEUE_POSITION_BITS;
19const PACKED_LIGHT_QUEUE_DIRECTIONS_SHIFT: u64 =
20    PACKED_LIGHT_QUEUE_LEVEL_SHIFT + PACKED_LIGHT_QUEUE_LEVEL_BITS;
21const PACKED_LIGHT_QUEUE_POSITION_MASK: u64 = (1_u64 << PACKED_LIGHT_QUEUE_POSITION_BITS) - 1;
22const PACKED_LIGHT_QUEUE_FLAGS_MASK: u64 = (1_u64 << 61) | (1_u64 << 62) | (1_u64 << 63);
23
24/// `ScalableLux` axis direction order used by packed light propagation queues.
25///
26/// This intentionally differs from vanilla's `Direction.ordinal()` order.
27/// `ScalableLux` stores direction bitsets as +X, -X, +Z, -Z, +Y, -Y and relies on
28/// positive directions being even so `index ^ 1` gives the opposite direction.
29#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
30pub enum LightAxisDirection {
31    /// Positive X / east.
32    PositiveX,
33    /// Negative X / west.
34    NegativeX,
35    /// Positive Z / south.
36    PositiveZ,
37    /// Negative Z / north.
38    NegativeZ,
39    /// Positive Y / up.
40    PositiveY,
41    /// Negative Y / down.
42    NegativeY,
43}
44
45impl LightAxisDirection {
46    /// All directions in `ScalableLux` propagation order.
47    pub const ALL: [Self; 6] = [
48        Self::PositiveX,
49        Self::NegativeX,
50        Self::PositiveZ,
51        Self::NegativeZ,
52        Self::PositiveY,
53        Self::NegativeY,
54    ];
55
56    /// Horizontal directions in `ScalableLux` propagation order.
57    pub const HORIZONTAL: [Self; 4] = [
58        Self::PositiveX,
59        Self::NegativeX,
60        Self::PositiveZ,
61        Self::NegativeZ,
62    ];
63
64    /// Converts a vanilla direction into `ScalableLux`'s axis-direction order.
65    #[must_use]
66    pub const fn from_direction(direction: Direction) -> Self {
67        match direction {
68            Direction::East => Self::PositiveX,
69            Direction::West => Self::NegativeX,
70            Direction::South => Self::PositiveZ,
71            Direction::North => Self::NegativeZ,
72            Direction::Up => Self::PositiveY,
73            Direction::Down => Self::NegativeY,
74        }
75    }
76
77    /// Returns the `ScalableLux` axis direction for a direction-bit index.
78    #[must_use]
79    pub const fn from_bit_index(bit_index: u8) -> Option<Self> {
80        match bit_index {
81            0 => Some(Self::PositiveX),
82            1 => Some(Self::NegativeX),
83            2 => Some(Self::PositiveZ),
84            3 => Some(Self::NegativeZ),
85            4 => Some(Self::PositiveY),
86            5 => Some(Self::NegativeY),
87            _ => None,
88        }
89    }
90
91    /// Returns the vanilla direction represented by this axis direction.
92    #[must_use]
93    pub const fn direction(self) -> Direction {
94        match self {
95            Self::PositiveX => Direction::East,
96            Self::NegativeX => Direction::West,
97            Self::PositiveZ => Direction::South,
98            Self::NegativeZ => Direction::North,
99            Self::PositiveY => Direction::Up,
100            Self::NegativeY => Direction::Down,
101        }
102    }
103
104    /// Returns the block-coordinate offset for this axis direction.
105    #[must_use]
106    pub const fn offset(self) -> (i32, i32, i32) {
107        match self {
108            Self::PositiveX => (1, 0, 0),
109            Self::NegativeX => (-1, 0, 0),
110            Self::PositiveZ => (0, 0, 1),
111            Self::NegativeZ => (0, 0, -1),
112            Self::PositiveY => (0, 1, 0),
113            Self::NegativeY => (0, -1, 0),
114        }
115    }
116
117    /// Returns the opposite `ScalableLux` axis direction.
118    #[must_use]
119    pub const fn opposite(self) -> Self {
120        match self {
121            Self::PositiveX => Self::NegativeX,
122            Self::NegativeX => Self::PositiveX,
123            Self::PositiveZ => Self::NegativeZ,
124            Self::NegativeZ => Self::PositiveZ,
125            Self::PositiveY => Self::NegativeY,
126            Self::NegativeY => Self::PositiveY,
127        }
128    }
129
130    /// Returns this direction's `ScalableLux` bit index.
131    #[must_use]
132    pub const fn bit_index(self) -> u8 {
133        match self {
134            Self::PositiveX => 0,
135            Self::NegativeX => 1,
136            Self::PositiveZ => 2,
137            Self::NegativeZ => 3,
138            Self::PositiveY => 4,
139            Self::NegativeY => 5,
140        }
141    }
142
143    const fn bit(self) -> u8 {
144        1 << self.bit_index()
145    }
146}
147
148/// `ScalableLux` propagation direction bitset.
149#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
150pub struct LightDirectionSet(u8);
151
152impl LightDirectionSet {
153    /// Creates an empty direction set.
154    #[must_use]
155    pub const fn empty() -> Self {
156        Self(0)
157    }
158
159    /// Creates a direction set containing all six axis directions.
160    #[must_use]
161    pub const fn all() -> Self {
162        Self(PACKED_LIGHT_QUEUE_DIRECTION_MASK)
163    }
164
165    /// Creates a direction set from raw `ScalableLux` direction bits.
166    #[must_use]
167    pub const fn from_raw(raw: u8) -> Self {
168        Self(raw & PACKED_LIGHT_QUEUE_DIRECTION_MASK)
169    }
170
171    /// Creates a direction set containing exactly one axis direction.
172    #[must_use]
173    pub const fn only(direction: LightAxisDirection) -> Self {
174        Self(direction.bit())
175    }
176
177    /// Returns this set with one additional direction.
178    #[must_use]
179    pub const fn with(self, direction: LightAxisDirection) -> Self {
180        Self(self.0 | direction.bit())
181    }
182
183    /// Creates a direction set containing all directions except one.
184    #[must_use]
185    pub const fn all_except(direction: LightAxisDirection) -> Self {
186        Self(PACKED_LIGHT_QUEUE_DIRECTION_MASK & !direction.bit())
187    }
188
189    /// Creates a direction set containing all directions except the opposite of one direction.
190    #[must_use]
191    pub const fn all_except_opposite(direction: LightAxisDirection) -> Self {
192        Self::all_except(direction.opposite())
193    }
194
195    /// Returns the raw `ScalableLux` direction bits.
196    #[must_use]
197    pub const fn raw(self) -> u8 {
198        self.0
199    }
200
201    /// Returns true when this set contains the selected axis direction.
202    #[must_use]
203    pub const fn contains(self, direction: LightAxisDirection) -> bool {
204        self.0 & direction.bit() != 0
205    }
206
207    /// Iterates selected directions in `ScalableLux`'s propagation order.
208    #[must_use]
209    pub const fn directions(self) -> LightDirectionSetIter {
210        LightDirectionSetIter { remaining: self.0 }
211    }
212}
213
214/// Iterator over a `LightDirectionSet` in `ScalableLux` propagation order.
215#[derive(Debug, Clone)]
216pub struct LightDirectionSetIter {
217    remaining: u8,
218}
219
220impl Iterator for LightDirectionSetIter {
221    type Item = LightAxisDirection;
222
223    fn next(&mut self) -> Option<Self::Item> {
224        if self.remaining == 0 {
225            return None;
226        }
227
228        let bit_index = self.remaining.trailing_zeros() as u8;
229        self.remaining &= self.remaining - 1;
230        LightAxisDirection::from_bit_index(bit_index)
231    }
232
233    fn size_hint(&self) -> (usize, Option<usize>) {
234        let len = self.remaining.count_ones() as usize;
235        (len, Some(len))
236    }
237}
238
239impl ExactSizeIterator for LightDirectionSetIter {}
240
241impl FusedIterator for LightDirectionSetIter {}
242
243/// `ScalableLux` state flags stored in the top three queue-entry bits.
244#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
245pub struct LightQueueFlags(u64);
246
247impl LightQueueFlags {
248    /// No queue state flags.
249    pub const EMPTY: Self = Self(0);
250    /// The increase pass should write the entry's level before propagating.
251    pub const WRITE_LEVEL: Self = Self(1_u64 << 61);
252    /// The increase pass should confirm the current level still matches.
253    pub const RECHECK_LEVEL: Self = Self(1_u64 << 62);
254    /// Propagation must account for sided transparent block shapes.
255    pub const HAS_SIDED_TRANSPARENT_BLOCKS: Self = Self(1_u64 << 63);
256
257    /// Creates flags from raw queue bits.
258    #[must_use]
259    pub const fn from_raw(raw: u64) -> Self {
260        Self(raw & PACKED_LIGHT_QUEUE_FLAGS_MASK)
261    }
262
263    /// Returns the raw queue flag bits.
264    #[must_use]
265    pub const fn raw(self) -> u64 {
266        self.0
267    }
268
269    /// Returns a set with `flag` included.
270    #[must_use]
271    pub const fn with(self, flag: Self) -> Self {
272        Self(self.0 | flag.0)
273    }
274
275    /// Returns true when all bits in `flag` are present.
276    #[must_use]
277    pub const fn contains(self, flag: Self) -> bool {
278        self.0 & flag.0 == flag.0
279    }
280}
281
282/// `ScalableLux` packed light-propagation queue entry.
283///
284/// The lower 28 bits store `PackedLightBlockPos`, followed by a 4-bit light
285/// level and a 6-bit `LightDirectionSet`. Bits 61, 62, and 63 carry
286/// `LightQueueFlags`; the middle 23 bits are intentionally unused to preserve
287/// `ScalableLux`'s layout.
288#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
289pub struct PackedLightQueueEntry(u64);
290
291impl PackedLightQueueEntry {
292    /// Creates a packed queue entry from typed `ScalableLux` parts.
293    #[must_use]
294    pub const fn from_parts(
295        block_pos: PackedLightBlockPos,
296        level: u8,
297        directions: LightDirectionSet,
298        flags: LightQueueFlags,
299    ) -> Self {
300        Self(
301            block_pos.raw() as u64
302                | ((level as u64 & PACKED_LIGHT_QUEUE_LEVEL_MASK)
303                    << PACKED_LIGHT_QUEUE_LEVEL_SHIFT)
304                | ((directions.raw() as u64) << PACKED_LIGHT_QUEUE_DIRECTIONS_SHIFT)
305                | flags.raw(),
306        )
307    }
308
309    /// Creates a packed queue entry from raw `ScalableLux` queue bits.
310    #[must_use]
311    pub const fn from_raw(raw: u64) -> Self {
312        Self(raw)
313    }
314
315    /// Returns the raw `ScalableLux` queue entry.
316    #[must_use]
317    pub const fn raw(self) -> u64 {
318        self.0
319    }
320
321    /// Returns the packed block position stored in this queue entry.
322    #[must_use]
323    pub const fn block_pos(self) -> PackedLightBlockPos {
324        PackedLightBlockPos::from_raw((self.0 & PACKED_LIGHT_QUEUE_POSITION_MASK) as u32)
325    }
326
327    /// Returns the propagated light level.
328    #[must_use]
329    pub const fn level(self) -> u8 {
330        ((self.0 >> PACKED_LIGHT_QUEUE_LEVEL_SHIFT) & PACKED_LIGHT_QUEUE_LEVEL_MASK) as u8
331    }
332
333    /// Returns the propagation direction set.
334    #[must_use]
335    pub const fn directions(self) -> LightDirectionSet {
336        LightDirectionSet::from_raw(
337            ((self.0 >> PACKED_LIGHT_QUEUE_DIRECTIONS_SHIFT)
338                & PACKED_LIGHT_QUEUE_DIRECTION_MASK as u64) as u8,
339        )
340    }
341
342    /// Returns the top-bit state flags.
343    #[must_use]
344    pub const fn flags(self) -> LightQueueFlags {
345        LightQueueFlags::from_raw(self.0)
346    }
347
348    /// Returns true when the increase pass should write this entry's level.
349    #[must_use]
350    pub const fn should_write_level(self) -> bool {
351        self.flags().contains(LightQueueFlags::WRITE_LEVEL)
352    }
353
354    /// Returns true when the increase pass should confirm the current level.
355    #[must_use]
356    pub const fn should_recheck_level(self) -> bool {
357        self.flags().contains(LightQueueFlags::RECHECK_LEVEL)
358    }
359
360    /// Returns true when propagation must account for sided transparent shapes.
361    #[must_use]
362    pub const fn has_sided_transparent_blocks(self) -> bool {
363        self.flags()
364            .contains(LightQueueFlags::HAS_SIDED_TRANSPARENT_BLOCKS)
365    }
366}
367
368/// Array-backed FIFO used for `ScalableLux` packed light propagation entries.
369#[derive(Debug)]
370pub struct PackedLightPropagationQueue {
371    entries: Vec<PackedLightQueueEntry>,
372    read_index: usize,
373}
374
375impl PackedLightPropagationQueue {
376    /// Creates an empty `ScalableLux` packed propagation queue.
377    #[must_use]
378    pub fn new() -> Self {
379        Self {
380            entries: Vec::with_capacity(PACKED_LIGHT_QUEUE_MIN_CAPACITY),
381            read_index: 0,
382        }
383    }
384
385    /// Returns true when no packed queued work remains.
386    #[must_use]
387    pub const fn is_empty(&self) -> bool {
388        self.read_index >= self.entries.len()
389    }
390
391    /// Returns the number of packed entries that have not been dequeued yet.
392    #[must_use]
393    pub const fn len(&self) -> usize {
394        self.entries.len() - self.read_index
395    }
396
397    /// Adds packed propagation work to the back of the queue.
398    pub fn enqueue(&mut self, entry: PackedLightQueueEntry) {
399        self.entries.push(entry);
400    }
401
402    /// Removes packed propagation work from the front of the queue.
403    pub fn dequeue(&mut self) -> Option<PackedLightQueueEntry> {
404        if self.is_empty() {
405            self.clear();
406            return None;
407        }
408
409        let entry = self.entries[self.read_index];
410        self.read_index += 1;
411        if self.is_empty() {
412            self.clear();
413        }
414
415        Some(entry)
416    }
417
418    /// Removes all queued packed work while keeping allocated storage for reuse.
419    pub fn clear(&mut self) {
420        self.entries.clear();
421        self.read_index = 0;
422    }
423}
424
425impl Default for PackedLightPropagationQueue {
426    fn default() -> Self {
427        Self::new()
428    }
429}
430
431/// `ScalableLux`'s separate packed increase and decrease propagation queues.
432#[derive(Debug, Default)]
433pub struct PackedLightPropagationQueues {
434    increase: PackedLightPropagationQueue,
435    decrease: PackedLightPropagationQueue,
436}
437
438impl PackedLightPropagationQueues {
439    /// Creates empty packed increase and decrease queues.
440    #[must_use]
441    pub fn new() -> Self {
442        Self::default()
443    }
444
445    /// Returns true when either packed propagation queue contains work.
446    #[must_use]
447    pub const fn has_work(&self) -> bool {
448        !self.increase.is_empty() || !self.decrease.is_empty()
449    }
450
451    /// Enqueues packed decrease propagation work.
452    pub fn enqueue_decrease(&mut self, entry: PackedLightQueueEntry) {
453        self.decrease.enqueue(entry);
454    }
455
456    /// Enqueues packed increase propagation work.
457    pub fn enqueue_increase(&mut self, entry: PackedLightQueueEntry) {
458        self.increase.enqueue(entry);
459    }
460
461    /// Dequeues packed decrease propagation work.
462    pub fn dequeue_decrease(&mut self) -> Option<PackedLightQueueEntry> {
463        self.decrease.dequeue()
464    }
465
466    /// Dequeues packed increase propagation work.
467    pub fn dequeue_increase(&mut self) -> Option<PackedLightQueueEntry> {
468        self.increase.dequeue()
469    }
470
471    /// Removes all packed increase and decrease work.
472    pub fn clear(&mut self) {
473        self.increase.clear();
474        self.decrease.clear();
475    }
476}
477
478/// Vanilla's packed light-propagation queue entry.
479///
480/// `LightEngine.QueueEntry` stores the source level in bits 0..3, one
481/// propagation bit per vanilla `Direction.ordinal()` in bits 4..9, and two
482/// increase flags in bits 10 and 11.
483#[derive(Debug, Clone, Copy, PartialEq, Eq)]
484pub struct LightQueueEntry(u64);
485
486impl LightQueueEntry {
487    /// Creates a decrease entry that propagates to all directions except one.
488    #[must_use]
489    pub const fn decrease_skip_one_direction(
490        old_from_level: u8,
491        skip_direction: Direction,
492    ) -> Self {
493        Self::with_level(
494            Self::without_direction(QUEUE_ENTRY_DIRECTIONS_MASK, skip_direction),
495            old_from_level,
496        )
497    }
498
499    /// Creates a decrease entry that propagates to all directions.
500    #[must_use]
501    pub const fn decrease_all_directions(old_from_level: u8) -> Self {
502        Self::with_level(QUEUE_ENTRY_DIRECTIONS_MASK, old_from_level)
503    }
504
505    /// Creates an increase entry sourced from a block's light emission.
506    #[must_use]
507    pub const fn increase_light_from_emission(new_from_level: u8, from_empty_shape: bool) -> Self {
508        let mut entry = QUEUE_ENTRY_DIRECTIONS_MASK | QUEUE_ENTRY_FLAG_INCREASE_FROM_EMISSION;
509        if from_empty_shape {
510            entry |= QUEUE_ENTRY_FLAG_FROM_EMPTY_SHAPE;
511        }
512
513        Self::with_level(entry, new_from_level)
514    }
515
516    /// Creates an increase entry that propagates to all directions except one.
517    #[must_use]
518    pub const fn increase_skip_one_direction(
519        new_from_level: u8,
520        from_empty_shape: bool,
521        skip_direction: Direction,
522    ) -> Self {
523        let mut entry = Self::without_direction(QUEUE_ENTRY_DIRECTIONS_MASK, skip_direction);
524        if from_empty_shape {
525            entry |= QUEUE_ENTRY_FLAG_FROM_EMPTY_SHAPE;
526        }
527
528        Self::with_level(entry, new_from_level)
529    }
530
531    /// Creates an increase entry that propagates to exactly one direction.
532    #[must_use]
533    pub const fn increase_only_one_direction(
534        new_from_level: u8,
535        from_empty_shape: bool,
536        direction: Direction,
537    ) -> Self {
538        let mut entry = 0;
539        if from_empty_shape {
540            entry |= QUEUE_ENTRY_FLAG_FROM_EMPTY_SHAPE;
541        }
542
543        Self::with_level(Self::with_direction(entry, direction), new_from_level)
544    }
545
546    /// Creates a sky-source increase entry for selected directions.
547    #[must_use]
548    pub fn increase_sky_source_in_directions(directions: &[Direction]) -> Self {
549        let mut entry = u64::from(MAX_LIGHT_LEVEL);
550        for &direction in directions {
551            entry = Self::with_direction(entry, direction);
552        }
553
554        Self(entry)
555    }
556
557    /// Creates a queue entry from vanilla's packed representation.
558    #[must_use]
559    pub const fn from_raw(raw: u64) -> Self {
560        Self(raw)
561    }
562
563    /// Returns vanilla's packed representation.
564    #[must_use]
565    pub const fn raw(self) -> u64 {
566        self.0
567    }
568
569    /// Returns the source light level stored in this entry.
570    #[must_use]
571    pub const fn level(self) -> u8 {
572        (self.0 & QUEUE_ENTRY_LEVEL_MASK) as u8
573    }
574
575    /// Returns true if propagation starts from an empty occlusion shape.
576    #[must_use]
577    pub const fn is_from_empty_shape(self) -> bool {
578        self.0 & QUEUE_ENTRY_FLAG_FROM_EMPTY_SHAPE != 0
579    }
580
581    /// Returns true if this increase came from block light emission.
582    #[must_use]
583    pub const fn is_increase_from_emission(self) -> bool {
584        self.0 & QUEUE_ENTRY_FLAG_INCREASE_FROM_EMISSION != 0
585    }
586
587    /// Returns true if this entry propagates in `direction`.
588    #[must_use]
589    pub const fn should_propagate_in_direction(self, direction: Direction) -> bool {
590        self.0 & Self::direction_bit(direction) != 0
591    }
592
593    const fn with_level(entry: u64, level: u8) -> Self {
594        Self(entry & !QUEUE_ENTRY_LEVEL_MASK | (level as u64 & QUEUE_ENTRY_LEVEL_MASK))
595    }
596
597    const fn with_direction(entry: u64, direction: Direction) -> u64 {
598        entry | Self::direction_bit(direction)
599    }
600
601    const fn without_direction(entry: u64, direction: Direction) -> u64 {
602        entry & !Self::direction_bit(direction)
603    }
604
605    const fn direction_bit(direction: Direction) -> u64 {
606        1 << (Self::vanilla_direction_index(direction) + 4)
607    }
608
609    const fn vanilla_direction_index(direction: Direction) -> u64 {
610        match direction {
611            Direction::Down => 0,
612            Direction::Up => 1,
613            Direction::North => 2,
614            Direction::South => 3,
615            Direction::West => 4,
616            Direction::East => 5,
617        }
618    }
619}
620
621/// One typed light propagation queue item.
622#[derive(Debug, Clone, Copy, PartialEq, Eq)]
623pub struct QueuedLightUpdate {
624    /// Block position whose light should propagate.
625    pub block_pos: BlockPos,
626    /// Packed vanilla propagation metadata.
627    pub entry: LightQueueEntry,
628}
629
630/// Array-backed FIFO used for vanilla light propagation work.
631///
632/// Vanilla stores alternating packed block positions and `QueueEntry` longs in
633/// `LongArrayFIFOQueue`. Steel keeps typed records instead, while preserving
634/// the FIFO ordering and packed queue-entry semantics that propagation depends
635/// on.
636#[derive(Debug)]
637pub struct LightPropagationQueue {
638    entries: Vec<QueuedLightUpdate>,
639    read_index: usize,
640}
641
642impl LightPropagationQueue {
643    /// Creates an empty propagation queue.
644    #[must_use]
645    pub fn new() -> Self {
646        Self {
647            entries: Vec::with_capacity(LIGHT_QUEUE_MIN_CAPACITY),
648            read_index: 0,
649        }
650    }
651
652    /// Returns true when no queued work remains.
653    #[must_use]
654    pub const fn is_empty(&self) -> bool {
655        self.read_index >= self.entries.len()
656    }
657
658    /// Returns the number of queued items that have not been dequeued yet.
659    #[must_use]
660    pub const fn len(&self) -> usize {
661        self.entries.len() - self.read_index
662    }
663
664    /// Adds propagation work to the back of the queue.
665    pub fn enqueue(&mut self, block_pos: BlockPos, entry: LightQueueEntry) {
666        self.entries.push(QueuedLightUpdate { block_pos, entry });
667    }
668
669    /// Removes propagation work from the front of the queue.
670    pub fn dequeue(&mut self) -> Option<QueuedLightUpdate> {
671        if self.is_empty() {
672            self.clear();
673            return None;
674        }
675
676        let update = self.entries[self.read_index];
677        self.read_index += 1;
678        if self.is_empty() {
679            self.clear();
680        }
681
682        Some(update)
683    }
684
685    /// Removes all queued work while keeping allocated storage for reuse.
686    pub fn clear(&mut self) {
687        self.entries.clear();
688        self.read_index = 0;
689    }
690}
691
692impl Default for LightPropagationQueue {
693    fn default() -> Self {
694        Self::new()
695    }
696}
697
698/// Vanilla's separate increase and decrease propagation queues.
699#[derive(Debug, Default)]
700pub struct LightPropagationQueues {
701    increase: LightPropagationQueue,
702    decrease: LightPropagationQueue,
703}
704
705impl LightPropagationQueues {
706    /// Creates empty increase and decrease queues.
707    #[must_use]
708    pub fn new() -> Self {
709        Self::default()
710    }
711
712    /// Returns true when either propagation queue contains work.
713    #[must_use]
714    pub const fn has_work(&self) -> bool {
715        !self.increase.is_empty() || !self.decrease.is_empty()
716    }
717
718    /// Enqueues decrease propagation work.
719    pub fn enqueue_decrease(&mut self, block_pos: BlockPos, entry: LightQueueEntry) {
720        self.decrease.enqueue(block_pos, entry);
721    }
722
723    /// Enqueues increase propagation work.
724    pub fn enqueue_increase(&mut self, block_pos: BlockPos, entry: LightQueueEntry) {
725        self.increase.enqueue(block_pos, entry);
726    }
727
728    /// Dequeues decrease propagation work.
729    pub fn dequeue_decrease(&mut self) -> Option<QueuedLightUpdate> {
730        self.decrease.dequeue()
731    }
732
733    /// Dequeues increase propagation work.
734    pub fn dequeue_increase(&mut self) -> Option<QueuedLightUpdate> {
735        self.increase.dequeue()
736    }
737
738    /// Removes all increase and decrease work.
739    pub fn clear(&mut self) {
740        self.increase.clear();
741        self.decrease.clear();
742    }
743}
744
745#[cfg(test)]
746mod tests {
747    use super::*;
748
749    fn packed_entry(level: u8) -> PackedLightQueueEntry {
750        PackedLightQueueEntry::from_parts(
751            PackedLightBlockPos::from_raw(u32::from(level)),
752            level,
753            LightDirectionSet::all(),
754            LightQueueFlags::EMPTY,
755        )
756    }
757
758    #[test]
759    fn light_axis_direction_matches_scalable_lux_order() {
760        assert_eq!(
761            LightAxisDirection::ALL,
762            [
763                LightAxisDirection::PositiveX,
764                LightAxisDirection::NegativeX,
765                LightAxisDirection::PositiveZ,
766                LightAxisDirection::NegativeZ,
767                LightAxisDirection::PositiveY,
768                LightAxisDirection::NegativeY,
769            ]
770        );
771        assert_eq!(
772            LightAxisDirection::HORIZONTAL,
773            [
774                LightAxisDirection::PositiveX,
775                LightAxisDirection::NegativeX,
776                LightAxisDirection::PositiveZ,
777                LightAxisDirection::NegativeZ,
778            ]
779        );
780
781        assert_eq!(LightAxisDirection::PositiveX.bit_index(), 0);
782        assert_eq!(LightAxisDirection::NegativeX.bit_index(), 1);
783        assert_eq!(LightAxisDirection::PositiveZ.bit_index(), 2);
784        assert_eq!(LightAxisDirection::NegativeZ.bit_index(), 3);
785        assert_eq!(LightAxisDirection::PositiveY.bit_index(), 4);
786        assert_eq!(LightAxisDirection::NegativeY.bit_index(), 5);
787    }
788
789    #[test]
790    fn light_axis_direction_maps_to_steel_direction() {
791        assert_eq!(
792            LightAxisDirection::from_direction(Direction::East),
793            LightAxisDirection::PositiveX
794        );
795        assert_eq!(
796            LightAxisDirection::from_direction(Direction::West),
797            LightAxisDirection::NegativeX
798        );
799        assert_eq!(
800            LightAxisDirection::from_direction(Direction::South),
801            LightAxisDirection::PositiveZ
802        );
803        assert_eq!(
804            LightAxisDirection::from_direction(Direction::North),
805            LightAxisDirection::NegativeZ
806        );
807        assert_eq!(
808            LightAxisDirection::from_direction(Direction::Up),
809            LightAxisDirection::PositiveY
810        );
811        assert_eq!(
812            LightAxisDirection::from_direction(Direction::Down),
813            LightAxisDirection::NegativeY
814        );
815
816        assert_eq!(LightAxisDirection::PositiveX.direction(), Direction::East);
817        assert_eq!(LightAxisDirection::NegativeX.direction(), Direction::West);
818        assert_eq!(LightAxisDirection::PositiveZ.direction(), Direction::South);
819        assert_eq!(LightAxisDirection::NegativeZ.direction(), Direction::North);
820        assert_eq!(LightAxisDirection::PositiveY.direction(), Direction::Up);
821        assert_eq!(LightAxisDirection::NegativeY.direction(), Direction::Down);
822
823        assert_eq!(LightAxisDirection::PositiveX.offset(), (1, 0, 0));
824        assert_eq!(LightAxisDirection::NegativeX.offset(), (-1, 0, 0));
825        assert_eq!(LightAxisDirection::PositiveZ.offset(), (0, 0, 1));
826        assert_eq!(LightAxisDirection::NegativeZ.offset(), (0, 0, -1));
827        assert_eq!(LightAxisDirection::PositiveY.offset(), (0, 1, 0));
828        assert_eq!(LightAxisDirection::NegativeY.offset(), (0, -1, 0));
829    }
830
831    #[test]
832    fn light_axis_direction_opposites_flip_low_bit() {
833        for direction in LightAxisDirection::ALL {
834            assert_eq!(direction.opposite().bit_index(), direction.bit_index() ^ 1);
835            assert_eq!(direction.opposite().opposite(), direction);
836        }
837    }
838
839    #[test]
840    fn light_direction_set_matches_scalable_lux_masks() {
841        assert_eq!(LightDirectionSet::empty().raw(), 0);
842        assert_eq!(LightDirectionSet::all().raw(), 0b11_1111);
843        assert_eq!(LightDirectionSet::from_raw(u8::MAX).raw(), 0b11_1111);
844        assert_eq!(
845            LightDirectionSet::only(LightAxisDirection::PositiveZ).raw(),
846            0b00_0100
847        );
848        assert_eq!(
849            LightDirectionSet::all_except(LightAxisDirection::PositiveZ).raw(),
850            0b11_1011
851        );
852        assert_eq!(
853            LightDirectionSet::all_except_opposite(LightAxisDirection::PositiveZ).raw(),
854            0b11_0111
855        );
856
857        let set = LightDirectionSet::from_raw(0b10_0101);
858        assert!(set.contains(LightAxisDirection::PositiveX));
859        assert!(set.contains(LightAxisDirection::PositiveZ));
860        assert!(set.contains(LightAxisDirection::NegativeY));
861        assert!(!set.contains(LightAxisDirection::NegativeX));
862        assert!(!set.contains(LightAxisDirection::NegativeZ));
863        assert!(!set.contains(LightAxisDirection::PositiveY));
864    }
865
866    #[test]
867    fn light_direction_set_iterates_in_scalable_lux_order() {
868        let mut directions = LightDirectionSet::from_raw(0b10_1101).directions();
869
870        assert_eq!(directions.len(), 4);
871        assert_eq!(directions.next(), Some(LightAxisDirection::PositiveX));
872        assert_eq!(directions.next(), Some(LightAxisDirection::PositiveZ));
873        assert_eq!(directions.len(), 2);
874        assert_eq!(directions.next(), Some(LightAxisDirection::NegativeZ));
875        assert_eq!(directions.next(), Some(LightAxisDirection::NegativeY));
876        assert_eq!(directions.next(), None);
877        assert_eq!(directions.next(), None);
878    }
879
880    #[test]
881    fn light_queue_flags_match_scalable_lux_top_bits() {
882        assert_eq!(LightQueueFlags::WRITE_LEVEL.raw(), 1_u64 << 61);
883        assert_eq!(LightQueueFlags::RECHECK_LEVEL.raw(), 1_u64 << 62);
884        assert_eq!(
885            LightQueueFlags::HAS_SIDED_TRANSPARENT_BLOCKS.raw(),
886            1_u64 << 63
887        );
888
889        let flags = LightQueueFlags::EMPTY
890            .with(LightQueueFlags::WRITE_LEVEL)
891            .with(LightQueueFlags::HAS_SIDED_TRANSPARENT_BLOCKS);
892        assert!(flags.contains(LightQueueFlags::WRITE_LEVEL));
893        assert!(!flags.contains(LightQueueFlags::RECHECK_LEVEL));
894        assert!(flags.contains(LightQueueFlags::HAS_SIDED_TRANSPARENT_BLOCKS));
895        assert_eq!(
896            LightQueueFlags::from_raw(u64::MAX).raw(),
897            LightQueueFlags::WRITE_LEVEL
898                .with(LightQueueFlags::RECHECK_LEVEL)
899                .with(LightQueueFlags::HAS_SIDED_TRANSPARENT_BLOCKS)
900                .raw()
901        );
902    }
903
904    #[test]
905    fn packed_light_queue_entry_matches_scalable_lux_bit_layout() {
906        let position = PackedLightBlockPos::from_raw(0x0abc_def0);
907        let directions = LightDirectionSet::from_raw(0b10_1011);
908        let flags = LightQueueFlags::EMPTY
909            .with(LightQueueFlags::WRITE_LEVEL)
910            .with(LightQueueFlags::HAS_SIDED_TRANSPARENT_BLOCKS);
911        let entry = PackedLightQueueEntry::from_parts(position, 31, directions, flags);
912
913        assert_eq!(entry.block_pos(), position);
914        assert_eq!(entry.level(), 15);
915        assert_eq!(entry.directions(), directions);
916        assert_eq!(entry.flags(), flags);
917        assert!(entry.should_write_level());
918        assert!(!entry.should_recheck_level());
919        assert!(entry.has_sided_transparent_blocks());
920        assert_eq!(entry.raw() & ((1_u64 << 28) - 1), u64::from(position.raw()));
921        assert_eq!((entry.raw() >> 28) & 0x0f, 15);
922        assert_eq!((entry.raw() >> 32) & 0x3f, u64::from(directions.raw()));
923        assert_eq!(entry.raw() & (1_u64 << 61), 1_u64 << 61);
924        assert_eq!(entry.raw() & (1_u64 << 62), 0);
925        assert_eq!(entry.raw() & (1_u64 << 63), 1_u64 << 63);
926    }
927
928    #[test]
929    fn packed_light_queue_entry_reads_raw_scalable_lux_values() {
930        let raw = u64::MAX;
931        let entry = PackedLightQueueEntry::from_raw(raw);
932
933        assert_eq!(entry.raw(), raw);
934        assert_eq!(entry.block_pos().raw(), (1 << 28) - 1);
935        assert_eq!(entry.level(), 15);
936        assert_eq!(entry.directions(), LightDirectionSet::all());
937        assert!(entry.should_write_level());
938        assert!(entry.should_recheck_level());
939        assert!(entry.has_sided_transparent_blocks());
940    }
941
942    #[test]
943    fn packed_light_propagation_queue_preserves_fifo_order() {
944        let first = packed_entry(1);
945        let second = packed_entry(2);
946        let third = packed_entry(3);
947        let mut queue = PackedLightPropagationQueue::new();
948
949        assert!(queue.is_empty());
950        queue.enqueue(first);
951        queue.enqueue(second);
952        assert_eq!(queue.len(), 2);
953        assert_eq!(queue.dequeue(), Some(first));
954
955        queue.enqueue(third);
956        assert_eq!(queue.len(), 2);
957        assert_eq!(queue.dequeue(), Some(second));
958        assert_eq!(queue.dequeue(), Some(third));
959        assert_eq!(queue.dequeue(), None);
960        assert!(queue.is_empty());
961    }
962
963    #[test]
964    fn packed_light_propagation_queues_keep_increase_and_decrease_work_separate() {
965        let decrease_entry = packed_entry(6);
966        let increase_entry = packed_entry(7);
967        let mut queues = PackedLightPropagationQueues::new();
968
969        assert!(!queues.has_work());
970        queues.enqueue_decrease(decrease_entry);
971        queues.enqueue_increase(increase_entry);
972        assert!(queues.has_work());
973
974        assert_eq!(queues.dequeue_increase(), Some(increase_entry));
975        assert_eq!(queues.dequeue_increase(), None);
976        assert!(queues.has_work());
977
978        assert_eq!(queues.dequeue_decrease(), Some(decrease_entry));
979        assert_eq!(queues.dequeue_decrease(), None);
980        assert!(!queues.has_work());
981    }
982
983    #[test]
984    fn light_queue_entry_decrease_entries_match_vanilla_bits() {
985        let all = LightQueueEntry::decrease_all_directions(7);
986
987        assert_eq!(all.raw(), 0b11_1111_0000 | 7);
988        assert_eq!(all.level(), 7);
989        for direction in Direction::ALL {
990            assert!(all.should_propagate_in_direction(direction));
991        }
992        assert!(!all.is_from_empty_shape());
993        assert!(!all.is_increase_from_emission());
994
995        let skip_north = LightQueueEntry::decrease_skip_one_direction(7, Direction::North);
996        assert_eq!(skip_north.raw(), 951);
997        assert!(!skip_north.should_propagate_in_direction(Direction::North));
998        assert!(skip_north.should_propagate_in_direction(Direction::South));
999    }
1000
1001    #[test]
1002    fn light_queue_entry_increase_entries_match_vanilla_bits() {
1003        let emission = LightQueueEntry::increase_light_from_emission(15, true);
1004        assert_eq!(emission.raw(), 4095);
1005        assert_eq!(emission.level(), 15);
1006        assert!(emission.is_from_empty_shape());
1007        assert!(emission.is_increase_from_emission());
1008
1009        let skip_up = LightQueueEntry::increase_skip_one_direction(10, false, Direction::Up);
1010        assert_eq!(skip_up.raw(), 986);
1011        assert!(!skip_up.is_from_empty_shape());
1012        assert!(!skip_up.is_increase_from_emission());
1013        assert!(!skip_up.should_propagate_in_direction(Direction::Up));
1014        assert!(skip_up.should_propagate_in_direction(Direction::Down));
1015
1016        let east_only = LightQueueEntry::increase_only_one_direction(4, true, Direction::East);
1017        assert_eq!(east_only.raw(), 1540);
1018        assert!(east_only.is_from_empty_shape());
1019        assert!(east_only.should_propagate_in_direction(Direction::East));
1020        assert!(!east_only.should_propagate_in_direction(Direction::West));
1021    }
1022
1023    #[test]
1024    fn light_queue_entry_sky_source_entry_selects_horizontal_and_down_directions() {
1025        let entry = LightQueueEntry::increase_sky_source_in_directions(&[
1026            Direction::Down,
1027            Direction::North,
1028            Direction::West,
1029        ]);
1030
1031        assert_eq!(entry.raw(), 351);
1032        assert_eq!(entry.level(), 15);
1033        assert!(entry.should_propagate_in_direction(Direction::Down));
1034        assert!(!entry.should_propagate_in_direction(Direction::Up));
1035        assert!(entry.should_propagate_in_direction(Direction::North));
1036        assert!(!entry.should_propagate_in_direction(Direction::South));
1037        assert!(entry.should_propagate_in_direction(Direction::West));
1038        assert!(!entry.should_propagate_in_direction(Direction::East));
1039    }
1040
1041    #[test]
1042    fn light_queue_entry_masks_levels_like_vanilla() {
1043        let entry = LightQueueEntry::increase_light_from_emission(31, false);
1044
1045        assert_eq!(entry.level(), 15);
1046        assert_eq!(entry.raw(), 0b11_1111_0000 | 0b1000_0000_0000 | 15);
1047    }
1048
1049    #[test]
1050    fn light_propagation_queue_preserves_fifo_order() {
1051        let first_pos = BlockPos::new(1, 2, 3);
1052        let second_pos = BlockPos::new(4, 5, 6);
1053        let first_entry = LightQueueEntry::decrease_all_directions(3);
1054        let second_entry =
1055            LightQueueEntry::increase_skip_one_direction(12, false, Direction::North);
1056        let mut queue = LightPropagationQueue::new();
1057
1058        queue.enqueue(first_pos, first_entry);
1059        queue.enqueue(second_pos, second_entry);
1060
1061        assert_eq!(queue.len(), 2);
1062        assert_eq!(
1063            queue.dequeue(),
1064            Some(QueuedLightUpdate {
1065                block_pos: first_pos,
1066                entry: first_entry,
1067            })
1068        );
1069        assert_eq!(
1070            queue.dequeue(),
1071            Some(QueuedLightUpdate {
1072                block_pos: second_pos,
1073                entry: second_entry,
1074            })
1075        );
1076        assert_eq!(queue.dequeue(), None);
1077        assert!(queue.is_empty());
1078    }
1079
1080    #[test]
1081    fn light_propagation_queues_keep_increase_and_decrease_work_separate() {
1082        let decrease_pos = BlockPos::new(1, 2, 3);
1083        let increase_pos = BlockPos::new(4, 5, 6);
1084        let decrease_entry = LightQueueEntry::decrease_all_directions(4);
1085        let increase_entry = LightQueueEntry::increase_only_one_direction(9, true, Direction::East);
1086        let mut queues = LightPropagationQueues::new();
1087
1088        assert!(!queues.has_work());
1089
1090        queues.enqueue_decrease(decrease_pos, decrease_entry);
1091        queues.enqueue_increase(increase_pos, increase_entry);
1092
1093        assert!(queues.has_work());
1094        assert_eq!(
1095            queues.dequeue_increase(),
1096            Some(QueuedLightUpdate {
1097                block_pos: increase_pos,
1098                entry: increase_entry,
1099            })
1100        );
1101        assert!(queues.has_work());
1102        assert_eq!(
1103            queues.dequeue_decrease(),
1104            Some(QueuedLightUpdate {
1105                block_pos: decrease_pos,
1106                entry: decrease_entry,
1107            })
1108        );
1109        assert!(!queues.has_work());
1110    }
1111}
steel_core/chunk/light/queue.rs

steel_core/chunk/light/
queue.rs
