From 96ea1a53696d78b4990f14ea708da48bbcbb81cb Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Sun, 1 Oct 2023 02:26:51 -0700 Subject: [PATCH] add 3D voxels game --- lib/console.c | 11 + rust_voxels_game/.gitignore | 7 + rust_voxels_game/Cargo.lock | 26 ++ rust_voxels_game/Cargo.toml | 25 ++ rust_voxels_game/Makefile | 52 ++++ rust_voxels_game/README.md | 55 +++++ rust_voxels_game/Xargo.toml | 4 + rust_voxels_game/build.rs | 79 ++++++ rust_voxels_game/head.S | 107 ++++++++ rust_voxels_game/powerpc.lds | 13 + rust_voxels_game/src/console.rs | 156 ++++++++++++ rust_voxels_game/src/fixed.rs | 254 +++++++++++++++++++ rust_voxels_game/src/lib.rs | 135 ++++++++++ rust_voxels_game/src/main.rs | 9 + rust_voxels_game/src/screen.rs | 65 +++++ rust_voxels_game/src/sin_cos.rs | 105 ++++++++ rust_voxels_game/src/take_once.rs | 37 +++ rust_voxels_game/src/vec.rs | 162 ++++++++++++ rust_voxels_game/src/world.rs | 396 ++++++++++++++++++++++++++++++ scripts/bin2hex.py | 17 +- 20 files changed, 1703 insertions(+), 12 deletions(-) create mode 100644 rust_voxels_game/.gitignore create mode 100644 rust_voxels_game/Cargo.lock create mode 100644 rust_voxels_game/Cargo.toml create mode 100644 rust_voxels_game/Makefile create mode 100644 rust_voxels_game/README.md create mode 100644 rust_voxels_game/Xargo.toml create mode 100644 rust_voxels_game/build.rs create mode 100644 rust_voxels_game/head.S create mode 100644 rust_voxels_game/powerpc.lds create mode 100644 rust_voxels_game/src/console.rs create mode 100644 rust_voxels_game/src/fixed.rs create mode 100644 rust_voxels_game/src/lib.rs create mode 100644 rust_voxels_game/src/main.rs create mode 100644 rust_voxels_game/src/screen.rs create mode 100644 rust_voxels_game/src/sin_cos.rs create mode 100644 rust_voxels_game/src/take_once.rs create mode 100644 rust_voxels_game/src/vec.rs create mode 100644 rust_voxels_game/src/world.rs diff --git a/lib/console.c b/lib/console.c index 0750190..f9bc9fd 100644 --- a/lib/console.c +++ b/lib/console.c @@ -5,7 +5,9 @@ #include "microwatt_soc.h" #include "io.h" +#ifndef UART_BAUDS #define UART_BAUDS 115200 +#endif /* * Core UART functions to implement for a port @@ -148,6 +150,15 @@ int getchar(void) } } +bool console_havechar(void) +{ + if (uart_is_std) { + return !std_uart_rx_empty(); + } else { + return !potato_uart_rx_empty(); + } +} + int putchar(int c) { if (uart_is_std) { diff --git a/rust_voxels_game/.gitignore b/rust_voxels_game/.gitignore new file mode 100644 index 0000000..0618625 --- /dev/null +++ b/rust_voxels_game/.gitignore @@ -0,0 +1,7 @@ +*.o +*.elf +*.hex +*.bin +compile_commands.json +.cache +target diff --git a/rust_voxels_game/Cargo.lock b/rust_voxels_game/Cargo.lock new file mode 100644 index 0000000..2852db3 --- /dev/null +++ b/rust_voxels_game/Cargo.lock @@ -0,0 +1,26 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "libc" +version = "0.2.148" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9cdc71e17332e86d2e1d38c1f99edcb6288ee11b815fb1a4b049eaa2114d369b" + +[[package]] +name = "termios" +version = "0.3.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "411c5bf740737c7918b8b1fe232dca4dc9f8e754b8ad5e20966814001ed0ac6b" +dependencies = [ + "libc", +] + +[[package]] +name = "rust_voxels_game" +version = "0.0.0" +dependencies = [ + "libc", + "termios", +] diff --git a/rust_voxels_game/Cargo.toml b/rust_voxels_game/Cargo.toml new file mode 100644 index 0000000..c6da8e5 --- /dev/null +++ b/rust_voxels_game/Cargo.toml @@ -0,0 +1,25 @@ +[package] +name = "rust_voxels_game" +version = "0.0.0" +edition = "2021" +publish = false +license = "LGPL-3.0+" + +[profile.dev] +panic = "abort" + +[dependencies] +termios = { version = "0.3.3", optional = true } +libc = { version = "0.2", optional = true } + +[features] +embedded = [] +hosted = ["dep:termios", "dep:libc"] +default = ["hosted"] + +[profile.release] +panic = "abort" +codegen-units = 1 # better optimizations +opt-level = 'z' # Optimize for size. +debug = true # symbols are nice and they don't increase the size on Flash +lto = true # better optimizations \ No newline at end of file diff --git a/rust_voxels_game/Makefile b/rust_voxels_game/Makefile new file mode 100644 index 0000000..162e6ff --- /dev/null +++ b/rust_voxels_game/Makefile @@ -0,0 +1,52 @@ +.PHONY: all run size dump emu clean + +ARCH = $(shell uname -m) +ifneq ("$(ARCH)", "ppc64") +ifneq ("$(ARCH)", "ppc64le") + CROSS_COMPILE ?= powerpc64le-linux-gnu- +endif +endif + +CC = $(CROSS_COMPILE)gcc +LD = $(CROSS_COMPILE)ld +OBJCOPY = $(CROSS_COMPILE)objcopy + +CFLAGS = -Os -g -Wall -std=c99 -msoft-float -mno-string -mno-multiple -mno-vsx -mno-altivec -mlittle-endian -fno-stack-protector -mstrict-align -ffreestanding -fdata-sections -ffunction-sections -I../include +ASFLAGS = $(CFLAGS) +LDFLAGS = -T powerpc.lds --gc-sections + +RUST_BIN = $(abspath target/powerpc64le-unknown-linux-gnu/release/rust_voxels_game) +RUST_BIN_DEP = $(abspath target/powerpc64le-unknown-linux-gnu/release/rust_voxels_game.d) + +all: rust_voxels_game.hex rust_voxels_game.bin + +run: rust_voxels_game.bin + -ln -sf rust_voxels_game.bin main_ram.bin + ../core_tb > /dev/null + +$(RUST_BIN) $(RUST_BIN_DEP): Cargo.toml Cargo.lock Xargo.toml + RUSTFLAGS="-C target-feature=-vsx,-altivec,-hard-float" UART_BAUDS=1000000 xargo build --bin rust_voxels_game --release --target=powerpc64le-unknown-linux-gnu --features=embedded --no-default-features && touch -c "$(RUST_BIN)" + +include $(RUST_BIN_DEP) + +size: rust_voxels_game.elf + size rust_voxels_game.elf + +dump: rust_voxels_game.elf + powerpc64le-linux-gnu-objdump -S rust_voxels_game.elf | less + +rust_voxels_game.elf: $(RUST_BIN) + cp "$(RUST_BIN)" rust_voxels_game.elf + +rust_voxels_game.bin: rust_voxels_game.elf + $(OBJCOPY) -O binary $^ $@ + +rust_voxels_game.hex: rust_voxels_game.bin + ../scripts/bin2hex.py $^ > $@ + +emu: + cargo run + +clean: + cargo clean + @rm -f *.o rust_voxels_game.elf rust_voxels_game.bin rust_voxels_game.hex diff --git a/rust_voxels_game/README.md b/rust_voxels_game/README.md new file mode 100644 index 0000000..9298383 --- /dev/null +++ b/rust_voxels_game/README.md @@ -0,0 +1,55 @@ +# 3D Voxels Game + +# Tools you'll need: + +Install Rust using [`rustup`](https://rustup.rs/). + +Then run: +```bash +rustup default nightly +rustup target add powerpc64le-unknown-linux-gnu +rustup component add rust-src +cargo install xargo +``` + +# Run without FPGA/hardware-simulation + +Resize your terminal to be at least 100x76. + +Building: +```bash +cd rust_voxels_game +cargo build +``` + +Running: +```bash +cd rust_voxels_game +cargo run +``` + +# Run on OrangeCrab v0.2.1 + +Set the OrangeCrab into firmware upload mode by plugging it in to USB while the button is pressed, then run the following commands: + +Building/Flashing: +```bash +make -C rust_voxels_game +sudo make FPGA_TARGET=ORANGE-CRAB-0.21 dfuprog DOCKER=1 LITEDRAM_GHDL_ARG=-gUSE_LITEDRAM=false RAM_INIT_FILE=rust_voxels_game/rust_voxels_game.hex MEMORY_SIZE=$((3<<16)) +``` + +Connect a 3.3v USB serial adaptor to the OrangeCrab's TX/RX pins: + +pins going from the corner closest to the button: + +| Silkscreen Label | Purpose | Connect to on serial adaptor | +|------------------|---------|------------------------------| +| GND | Ground | Ground | +| 1 | UART RX | TX | +| 2 | UART TX | RX | + +Then, in a separate terminal that you've resized to be at least 100x76, run +(replacing ttyUSB0 with whatever serial device the OrangeCrab is connected to): +```bash +sudo tio --baudrate=1000000 /dev/ttyUSB0 +``` diff --git a/rust_voxels_game/Xargo.toml b/rust_voxels_game/Xargo.toml new file mode 100644 index 0000000..eb56903 --- /dev/null +++ b/rust_voxels_game/Xargo.toml @@ -0,0 +1,4 @@ +[target.powerpc64le-unknown-linux-gnu.dependencies] + +[dependencies.alloc] +features = ["compiler-builtins-mem"] diff --git a/rust_voxels_game/build.rs b/rust_voxels_game/build.rs new file mode 100644 index 0000000..16ab0de --- /dev/null +++ b/rust_voxels_game/build.rs @@ -0,0 +1,79 @@ +use std::{env, io, path::Path, process::Command}; + +const CFLAGS: &[&str] = &[ + "-Os", + "-g", + "-Wall", + "-std=c99", + "-msoft-float", + "-mno-string", + "-mno-multiple", + "-mno-vsx", + "-mno-altivec", + "-mlittle-endian", + "-fno-stack-protector", + "-mstrict-align", + "-ffreestanding", + "-fdata-sections", + "-ffunction-sections", + "-I../include", +]; + +fn prefix() -> &'static str { + if env::var("HOST").unwrap() != "powerpc64le-linux-gnu" { + "powerpc64le-linux-gnu-" + } else { + "" + } +} + +fn uart_bauds() -> u32 { + let s = env::var_os("UART_BAUDS").unwrap_or_else(|| "115200".into()); + s.to_str().unwrap().parse().unwrap() +} + +fn gcc(source: impl AsRef) -> io::Result<()> { + let source = source.as_ref(); + println!("cargo:rerun-if-changed={}", source.display()); + let target = source.with_extension("o"); + let target = Path::new(target.file_name().unwrap()); + println!("cargo:rustc-link-arg={}", target.display()); + if !Command::new(format!("{}gcc", prefix())) + .args(CFLAGS) + .arg(format!("-DUART_BAUDS={}", uart_bauds())) + .arg("-c") + .arg("-o") + .arg(&target) + .arg(source) + .status()? + .success() + { + Err(io::Error::new( + io::ErrorKind::Other, + format!("failed to compile: {}", source.display()), + )) + } else { + Ok(()) + } +} + +fn embedded() -> io::Result<()> { + gcc("head.S")?; + gcc("../lib/console.c")?; + println!("cargo:rustc-link-arg=-T"); + println!("cargo:rustc-link-arg=powerpc.lds"); + println!("cargo:rerun-if-changed=powerpc.lds"); + println!("cargo:rustc-link-arg=-nostartfiles"); + println!("cargo:rustc-link-arg=-static"); + Ok(()) +} + +#[cfg(feature = "embedded")] +fn main() -> io::Result<()> { + embedded() +} + +#[cfg(feature = "hosted")] +fn main() { + let _ = embedded; +} diff --git a/rust_voxels_game/head.S b/rust_voxels_game/head.S new file mode 100644 index 0000000..a5643dc --- /dev/null +++ b/rust_voxels_game/head.S @@ -0,0 +1,107 @@ +/* Copyright 2013-2014 IBM Corp. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + * implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#define STACK_TOP 0x30000 + +#define FIXUP_ENDIAN \ + tdi 0,0,0x48; /* Reverse endian of b . + 8 */ \ + b 191f; /* Skip trampoline if endian is good */ \ + .long 0xa600607d; /* mfmsr r11 */ \ + .long 0x01006b69; /* xori r11,r11,1 */ \ + .long 0x05009f42; /* bcl 20,31,$+4 */ \ + .long 0xa602487d; /* mflr r10 */ \ + .long 0x14004a39; /* addi r10,r10,20 */ \ + .long 0xa64b5a7d; /* mthsrr0 r10 */ \ + .long 0xa64b7b7d; /* mthsrr1 r11 */ \ + .long 0x2402004c; /* hrfid */ \ +191: + + +/* Load an immediate 64-bit value into a register */ +#define LOAD_IMM64(r, e) \ + lis r,(e)@highest; \ + ori r,r,(e)@higher; \ + rldicr r,r, 32, 31; \ + oris r,r, (e)@h; \ + ori r,r, (e)@l; + + .section ".head","ax" + + /* + * Microwatt currently enters in LE mode at 0x0, so we don't need to + * do any endian fix ups> + */ + . = 0 +.global _start +_start: + b boot_entry + + /* QEMU enters at 0x10 */ + . = 0x10 + FIXUP_ENDIAN + b boot_entry + + . = 0x100 + FIXUP_ENDIAN + b boot_entry + +.global boot_entry +boot_entry: + /* setup stack */ + LOAD_IMM64(%r1, STACK_TOP - 0x100) + LOAD_IMM64(%r12, main) + mtctr %r12, + bctrl + b . + +#define EXCEPTION(nr) \ + .= nr ;\ + b . + + /* More exception stubs */ + EXCEPTION(0x300) + EXCEPTION(0x380) + EXCEPTION(0x400) + EXCEPTION(0x480) + EXCEPTION(0x500) + EXCEPTION(0x600) + EXCEPTION(0x700) + EXCEPTION(0x800) + EXCEPTION(0x900) + EXCEPTION(0x980) + EXCEPTION(0xa00) + EXCEPTION(0xb00) + EXCEPTION(0xc00) + EXCEPTION(0xd00) + EXCEPTION(0xe00) + EXCEPTION(0xe20) + EXCEPTION(0xe40) + EXCEPTION(0xe60) + EXCEPTION(0xe80) + EXCEPTION(0xf00) + EXCEPTION(0xf20) + EXCEPTION(0xf40) + EXCEPTION(0xf60) + EXCEPTION(0xf80) +#if 0 + EXCEPTION(0x1000) + EXCEPTION(0x1100) + EXCEPTION(0x1200) + EXCEPTION(0x1300) + EXCEPTION(0x1400) + EXCEPTION(0x1500) + EXCEPTION(0x1600) +#endif diff --git a/rust_voxels_game/powerpc.lds b/rust_voxels_game/powerpc.lds new file mode 100644 index 0000000..c2e5881 --- /dev/null +++ b/rust_voxels_game/powerpc.lds @@ -0,0 +1,13 @@ +SECTIONS +{ + . = 0; + .head : { + KEEP(*(.head)) + } + . = 0x1000; + .text : { *(.text) } + .data : { *(.data) } + .rodata : { *(.rodata) } + .bss : { *(.bss) } + /DISCARD/ : { *(.note.gnu.build-id) } +} diff --git a/rust_voxels_game/src/console.rs b/rust_voxels_game/src/console.rs new file mode 100644 index 0000000..4f418fe --- /dev/null +++ b/rust_voxels_game/src/console.rs @@ -0,0 +1,156 @@ +use crate::take_once::{AlreadyTaken, TakeOnce}; +use core::{cell::UnsafeCell, ffi::c_int, fmt}; + +#[cfg(feature = "embedded")] +extern "C" { + fn console_init(); + fn getchar() -> c_int; + fn console_havechar() -> bool; + fn putchar(c: c_int) -> c_int; +} + +/// Safety: must only be called once +#[cfg(feature = "hosted")] +unsafe fn console_init() { + use std::sync::Mutex; + + static ORIG_TIOS: Mutex> = Mutex::new(None); + + extern "C" fn handle_exit() { + let Some(tios) = *ORIG_TIOS.lock().unwrap() else { + return; + }; + let _ = termios::tcsetattr(libc::STDIN_FILENO, libc::TCSADRAIN, &tios); + } + + extern "C" fn handle_signal(sig: c_int) { + unsafe { + libc::signal(sig, libc::SIG_DFL); + handle_exit(); + libc::raise(sig); + } + } + + if let Ok(mut tios) = termios::Termios::from_fd(libc::STDIN_FILENO) { + *ORIG_TIOS.lock().unwrap() = Some(tios); + termios::cfmakeraw(&mut tios); + tios.c_lflag |= termios::ISIG; + termios::tcsetattr(libc::STDIN_FILENO, libc::TCSADRAIN, &tios).unwrap(); + libc::atexit(handle_exit); + if libc::signal(libc::SIGINT, handle_signal as libc::sighandler_t) == libc::SIG_IGN { + libc::signal(libc::SIGINT, libc::SIG_IGN); + } + if libc::signal(libc::SIGTERM, handle_signal as libc::sighandler_t) == libc::SIG_IGN { + libc::signal(libc::SIGTERM, libc::SIG_IGN); + } + } + let flags = libc::fcntl(libc::STDIN_FILENO, libc::F_GETFL); + assert!(flags >= 0); + assert!(libc::fcntl(libc::STDIN_FILENO, libc::F_SETFL, flags | libc::O_NONBLOCK) >= 0); +} + +#[cfg(feature = "embedded")] +fn console_try_read() -> Option { + unsafe { + if console_havechar() { + Some(getchar() as u8) + } else { + None + } + } +} + +#[cfg(feature = "hosted")] +fn console_try_read() -> Option { + use std::io::Read; + + let mut retval = [0u8]; + match std::io::stdin().read(&mut retval) { + Ok(1) => Some(retval[0]), + _ => None, + } +} + +#[cfg(feature = "embedded")] +fn console_write(b: u8) { + unsafe { + putchar(b as c_int); + } +} + +#[cfg(feature = "hosted")] +fn console_write(b: u8) { + use core::{ + sync::atomic::{AtomicU32, Ordering}, + time::Duration, + }; + use std::{io::Write, sync::Mutex, thread::sleep, time::Instant}; + + const CHECK_PERIOD: u32 = 1024; + const SIMULATED_BYTES_PER_SEC: f64 = 1000000.0 / 8.0; + + static SLEEP_COUNTER: AtomicU32 = AtomicU32::new(CHECK_PERIOD); + + if SLEEP_COUNTER.fetch_add(1, Ordering::Relaxed) >= CHECK_PERIOD { + struct SleepState { + last_sleep: Option, + } + static SLEEP_STATE: Mutex = Mutex::new(SleepState { last_sleep: None }); + let mut state = SLEEP_STATE.lock().unwrap(); + let sleep_counter = SLEEP_COUNTER.load(Ordering::Relaxed); + let now = Instant::now(); + let last_sleep = state.last_sleep.get_or_insert(now); + let target = last_sleep + .checked_add(Duration::from_secs(sleep_counter as u64).div_f64(SIMULATED_BYTES_PER_SEC)) + .unwrap(); + if let Some(sleep_duration) = target.checked_duration_since(now) { + sleep(sleep_duration); + } + *last_sleep = target; + SLEEP_COUNTER.fetch_sub(sleep_counter, Ordering::Relaxed); + } + + let _ = std::io::stdout().write_all(&[b]); +} + +pub struct Console(()); + +impl Console { + fn try_take() -> Result<&'static mut Console, AlreadyTaken> { + static CONSOLE: TakeOnce = TakeOnce::new(Console(())); + let retval = CONSOLE.take()?; + unsafe { + console_init(); + } + Ok(retval) + } + + pub fn take() -> &'static mut Console { + Self::try_take().expect("console already taken") + } + + #[cfg(feature = "embedded")] + pub(crate) unsafe fn emergency_console() -> &'static mut Console { + struct EmergencyConsole(UnsafeCell); + + unsafe impl Sync for EmergencyConsole {} + static EMERGENCY_CONSOLE: EmergencyConsole = EmergencyConsole(UnsafeCell::new(Console(()))); + Self::try_take().unwrap_or_else(|_| unsafe { &mut *EMERGENCY_CONSOLE.0.get() }) + } + + pub fn try_read(&mut self) -> Option { + console_try_read() + } +} + +impl fmt::Write for Console { + fn write_str(&mut self, s: &str) -> fmt::Result { + for b in s.bytes() { + if b == b'\n' { + console_write(b'\r'); + } + console_write(b); + } + Ok(()) + } +} diff --git a/rust_voxels_game/src/fixed.rs b/rust_voxels_game/src/fixed.rs new file mode 100644 index 0000000..fc20794 --- /dev/null +++ b/rust_voxels_game/src/fixed.rs @@ -0,0 +1,254 @@ +#[cfg(feature = "hosted")] +use core::fmt; +use core::ops::{ + Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Rem, RemAssign, Shl, ShlAssign, Shr, + ShrAssign, Sub, SubAssign, +}; + +macro_rules! impl_assign_op { + ($AssignOp:ident::$assign_fn:ident => $Op:ident::$op_fn:ident) => { + impl $AssignOp for Fix64 + where + Self: $Op, + { + fn $assign_fn(&mut self, rhs: Rhs) { + *self = self.$op_fn(rhs); + } + } + }; +} + +#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Default)] +pub struct Fix64(i64); + +#[cfg(feature = "hosted")] +impl fmt::Display for Fix64 { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let frac_digits = (Fix64::FRAC_BITS + 3) / 4; + let v = self.0.unsigned_abs(); + if self.0 < 0 { + write!(f, "-")?; + } + let trunc = v >> Self::FRAC_BITS; + let fract = v as u128 & Self::FRAC_MASK as u128; + let fract = (fract << 4 * frac_digits) >> Fix64::FRAC_BITS; + write!( + f, + "0x{trunc:x}.{fract:0digits$x}", + digits = frac_digits as usize, + ) + } +} + +#[cfg(feature = "hosted")] +impl fmt::Debug for Fix64 { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Display::fmt(self, f) + } +} + +impl Fix64 { + pub const FRAC_BITS: u32 = 24; + pub const INT_MASK: i64 = (!0i64) << Self::FRAC_BITS; + pub const FRAC_MASK: i64 = !Self::INT_MASK; + pub const fn from_bits(v: i64) -> Self { + Self(v) + } + pub const fn as_bits(self) -> i64 { + self.0 + } + pub const fn from_int(v: i64) -> Self { + Self(v << Self::FRAC_BITS) + } + pub const fn from_rat(num: i64, denom: i64) -> Self { + Self((((num as i128) << Self::FRAC_BITS) / denom as i128) as i64) + } + #[cfg(feature = "hosted")] + pub fn from_f32(v: f32) -> Self { + Self((v * (1u64 << Self::FRAC_BITS) as f32) as i64) + } + #[cfg(feature = "hosted")] + pub fn to_f32(self) -> f32 { + self.0 as f32 * (1.0 / (1u64 << Self::FRAC_BITS) as f32) + } + #[cfg(feature = "hosted")] + pub fn from_f64(v: f64) -> Self { + Self((v * (1u64 << Self::FRAC_BITS) as f64) as i64) + } + #[cfg(feature = "hosted")] + pub fn to_f64(self) -> f64 { + self.0 as f64 * (1.0 / (1u64 << Self::FRAC_BITS) as f64) + } + pub const fn floor_fract(self) -> Self { + Self(self.0 & Self::FRAC_MASK) + } + pub const fn floor(self) -> i64 { + self.0 >> Self::FRAC_BITS + } + pub const fn round(self) -> i64 { + Self(self.0 + Self::from_rat(1, 2).0).floor() + } + pub const fn ceil(self) -> i64 { + (self.0 + Self::FRAC_MASK) >> Self::FRAC_BITS + } + pub const fn trunc(self) -> i64 { + self.0 / Self::from_int(1).0 + } + pub const fn abs(self) -> Self { + Self(self.0.abs()) + } + pub const fn is_zero(self) -> bool { + self.0 == 0 + } + pub const fn is_negative(self) -> bool { + self.0 < 0 + } + pub const fn is_positive(self) -> bool { + self.0 > 0 + } + pub const fn signum(self) -> i64 { + self.0.signum() + } + /// Computes `(self * a) + b)` rounding once at the end + pub const fn mul_add(self, a: Self, b: Self) -> Self { + let prod = self.0 as i128 * a.0 as i128; + let sum = prod + ((b.0 as i128) << Self::FRAC_BITS); + Self((sum >> Self::FRAC_BITS) as i64) + } +} + +#[cfg(feature = "hosted")] +impl From for f32 { + fn from(value: Fix64) -> Self { + value.to_f32() + } +} + +#[cfg(feature = "hosted")] +impl From for f64 { + fn from(value: Fix64) -> Self { + value.to_f64() + } +} + +#[cfg(feature = "hosted")] +impl From for Fix64 { + fn from(value: f32) -> Self { + Self::from_f32(value) + } +} + +#[cfg(feature = "hosted")] +impl From for Fix64 { + fn from(value: f64) -> Self { + Self::from_f64(value) + } +} + +impl From for Fix64 { + fn from(value: i64) -> Self { + Self::from_int(value) + } +} + +impl Add for Fix64 { + type Output = Self; + + fn add(self, rhs: Fix64) -> Self::Output { + Fix64(self.0 + rhs.0) + } +} + +impl_assign_op!(AddAssign::add_assign => Add::add); + +impl Sub for Fix64 { + type Output = Self; + + fn sub(self, rhs: Fix64) -> Self::Output { + Fix64(self.0 - rhs.0) + } +} + +impl_assign_op!(SubAssign::sub_assign => Sub::sub); + +impl Mul for Fix64 { + type Output = Self; + + fn mul(self, rhs: Fix64) -> Self::Output { + Fix64((self.0 as i128 * rhs.0 as i128 >> Self::FRAC_BITS) as i64) + } +} + +impl_assign_op!(MulAssign::mul_assign => Mul::mul); + +impl Div for Fix64 { + type Output = Self; + + fn div(self, rhs: Fix64) -> Self::Output { + Fix64((((self.0 as i128) << Self::FRAC_BITS) / rhs.0 as i128) as i64) + } +} + +impl_assign_op!(DivAssign::div_assign => Div::div); + +impl Rem for Fix64 { + type Output = Self; + + fn rem(self, rhs: Fix64) -> Self::Output { + Fix64(self.0 % rhs.0) + } +} + +impl_assign_op!(RemAssign::rem_assign => Rem::rem); + +impl Shl for Fix64 +where + i64: Shl, +{ + type Output = Self; + + fn shl(self, rhs: Rhs) -> Self::Output { + Fix64(self.0 << rhs) + } +} + +impl_assign_op!(ShlAssign::shl_assign => Shl::shl); + +impl Shr for Fix64 +where + i64: Shr, +{ + type Output = Self; + + fn shr(self, rhs: Rhs) -> Self::Output { + Fix64(self.0 >> rhs) + } +} + +impl_assign_op!(ShrAssign::shr_assign => Shr::shr); + +impl Neg for Fix64 { + type Output = Self; + + fn neg(self) -> Self::Output { + Fix64(-self.0) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_fix64_display() { + assert_eq!( + Fix64::from_bits(0x123456789abcdef).to_string(), + "0x123456789.abcdef" + ); + assert_eq!( + Fix64::from_bits(-0x123456789abcdef).to_string(), + "-0x123456789.abcdef" + ); + assert_eq!(Fix64::from_bits(-0x3C00001).to_string(), "-0x3.c00001"); + } +} diff --git a/rust_voxels_game/src/lib.rs b/rust_voxels_game/src/lib.rs new file mode 100644 index 0000000..84cdd35 --- /dev/null +++ b/rust_voxels_game/src/lib.rs @@ -0,0 +1,135 @@ +#![cfg_attr(all(feature = "embedded", not(test)), no_std)] + +use crate::{ + fixed::Fix64, + sin_cos::sin_cos_pi, + vec::Vec3D, + world::{Block, World}, +}; +use core::fmt::Write; +#[cfg(feature = "hosted")] +use std::process::exit; + +mod console; +mod fixed; +mod screen; +mod sin_cos; +mod take_once; +mod vec; +mod world; + +#[cfg(feature = "embedded")] +#[panic_handler] +fn panic_handler(info: &core::panic::PanicInfo) -> ! { + use core::sync::atomic::{AtomicBool, Ordering}; + + static PANICKED: AtomicBool = AtomicBool::new(false); + + if PANICKED.swap(true, Ordering::Relaxed) { + loop {} + } + let console = unsafe { console::Console::emergency_console() }; + loop { + let _ = writeln!(console, "{info}"); + } +} + +#[cfg(feature = "embedded")] +fn exit(code: i32) -> ! { + panic!("exited code={code}"); +} + +#[cfg_attr(feature = "embedded", no_mangle)] +pub extern "C" fn main() -> ! { + let console = console::Console::take(); + console.write_str("starting...\n").unwrap(); + let screen = screen::Screen::take(); + let world = World::take(); + let mut pos = Vec3D { + x: Fix64::from(0i64), + y: Fix64::from(0i64), + z: Fix64::from(0i64), + }; + let mut theta_over_pi = Fix64::from(0i64); + let mut phi_over_pi = Fix64::from(0i64); + let mut blink_counter = 0; + let blink_period = 6; + loop { + blink_counter = (blink_counter + 1) % blink_period; + let (sin_theta, cos_theta) = sin_cos_pi(theta_over_pi); + let (sin_phi, cos_phi) = sin_cos_pi(phi_over_pi); + let forward0 = Vec3D { + x: Fix64::from(sin_theta), + y: Fix64::from(0i64), + z: Fix64::from(cos_theta), + }; + let right = Vec3D { + x: Fix64::from(cos_theta), + y: Fix64::from(0i64), + z: Fix64::from(-sin_theta), + }; + let down0 = Vec3D { + x: Fix64::from(0i64), + y: Fix64::from(-1i64), + z: Fix64::from(0i64), + }; + let forward = forward0 * cos_phi - down0 * sin_phi; + let down = forward0 * sin_phi + down0 * cos_phi; + let mut restore_cursor = None; + let (_prev_pos, hit_pos) = world.get_hit_pos(pos, forward); + if blink_counter * 2 < blink_period { + restore_cursor = hit_pos.map(|hit_pos| { + let block = world.get_mut(hit_pos).unwrap(); + let old = *block; + block.color.0 = block.color.0.wrapping_add(100); + if *block == Block::default() { + block.color.0 = block.color.0.wrapping_add(1); + } + move |world: &mut World| *world.get_mut(hit_pos).unwrap() = old + }); + } + world.render(screen, pos, forward, right, down); + restore_cursor.map(|f| f(world)); + screen.display(console); + writeln!(console, "Press WASD to move, IJKL to change look dir, 0-9 to place a block, - to delete a block, ESC to exit.").unwrap(); + loop { + let (prev_pos, hit_pos) = world.get_hit_pos(pos, forward); + let mut new_pos = pos; + let Some(b) = console.try_read() else { + break; + }; + match b { + b'w' | b'W' => new_pos = pos + forward * Fix64::from_rat(1, 4), + b's' | b'S' => new_pos = pos - forward * Fix64::from_rat(1, 4), + b'd' | b'D' => new_pos = pos + right * Fix64::from_rat(1, 4), + b'a' | b'A' => new_pos = pos - right * Fix64::from_rat(1, 4), + b'i' | b'I' => phi_over_pi += Fix64::from_rat(1, 32), + b'k' | b'K' => phi_over_pi -= Fix64::from_rat(1, 32), + b'l' | b'L' => theta_over_pi += Fix64::from_rat(1, 32), + b'j' | b'J' => theta_over_pi -= Fix64::from_rat(1, 32), + b'0'..=b'9' => { + if let Some(prev_pos) = prev_pos { + if prev_pos != pos.map(Fix64::floor) { + world.get_mut(prev_pos).unwrap().color.0 = 1 + b - b'0'; + } + } + } + b'\x08' | b'-' => { + if let Some(hit_pos) = hit_pos { + *world.get_mut(hit_pos).unwrap() = Block::default(); + } + } + b'\x1B' => { + writeln!(console).unwrap(); + exit(0); + } + _ => {} + } + theta_over_pi %= Fix64::from(2i64); + phi_over_pi = phi_over_pi.clamp(Fix64::from_rat(-1, 2), Fix64::from_rat(1, 2)); + if world.get(new_pos.map(Fix64::floor)) == Some(&Block::default()) { + pos = new_pos; + } + } + } +} diff --git a/rust_voxels_game/src/main.rs b/rust_voxels_game/src/main.rs new file mode 100644 index 0000000..e47a589 --- /dev/null +++ b/rust_voxels_game/src/main.rs @@ -0,0 +1,9 @@ +#![cfg_attr(feature = "embedded", no_std)] +#![cfg_attr(feature = "embedded", no_main)] + +extern crate rust_voxels_game; + +#[cfg(feature = "hosted")] +fn main() { + rust_voxels_game::main() +} diff --git a/rust_voxels_game/src/screen.rs b/rust_voxels_game/src/screen.rs new file mode 100644 index 0000000..412a672 --- /dev/null +++ b/rust_voxels_game/src/screen.rs @@ -0,0 +1,65 @@ +use crate::{console::Console, fixed::Fix64, take_once::TakeOnce}; +use core::fmt::Write; + +#[derive(Copy, Clone, Debug, PartialEq, Eq)] +pub struct Color(pub u8); + +impl Color { + pub const fn default() -> Color { + Color(0) + } +} + +impl Console { + pub fn set_background_color(&mut self, color: Color) { + write!(self, "\x1B[48;5;{}m", color.0).unwrap(); + } + pub fn set_foreground_color(&mut self, color: Color) { + write!(self, "\x1B[38;5;{}m", color.0).unwrap(); + } +} + +pub struct Screen { + pub pixels: [[Color; Self::X_SIZE]; Self::Y_SIZE], +} + +impl Screen { + pub const X_SIZE: usize = 80; + pub const Y_SIZE: usize = 50; + pub fn pixel_dimensions(&self) -> (Fix64, Fix64) { + (Fix64::from(1), Fix64::from(1)) + } + pub fn take() -> &'static mut Screen { + static SCREEN: TakeOnce = TakeOnce::new(Screen { + pixels: [[Color(0); Screen::X_SIZE]; Screen::Y_SIZE], + }); + SCREEN.take().expect("screen already taken") + } + pub fn display(&self, console: &mut Console) { + let mut last_bg = Color::default(); + let mut last_fg = Color::default(); + write!(console, "\x1B[H").unwrap(); + for y in (0..Self::Y_SIZE).step_by(2) { + console.set_background_color(last_bg); + console.set_foreground_color(last_fg); + for x in 0..Self::X_SIZE { + let fg = self.pixels[y][x]; + let bg = self + .pixels + .get(y + 1) + .map(|row| row[x]) + .unwrap_or(Color::default()); + if fg != last_fg { + console.set_foreground_color(fg); + last_fg = fg; + } + if bg != last_bg { + console.set_background_color(bg); + last_bg = bg; + } + write!(console, "\u{2580}").unwrap(); // upper half block + } + writeln!(console, "\x1B[m").unwrap(); + } + } +} diff --git a/rust_voxels_game/src/sin_cos.rs b/rust_voxels_game/src/sin_cos.rs new file mode 100644 index 0000000..4a24eb2 --- /dev/null +++ b/rust_voxels_game/src/sin_cos.rs @@ -0,0 +1,105 @@ +use crate::fixed::Fix64; + +const SIN_PI_OVER_2_POLY_COEFFS: &[Fix64] = &[ + Fix64::from_rat(26353589, 16777216), // x^1 + Fix64::from_rat(-10837479, 16777216), // x^3 + Fix64::from_rat(334255, 4194304), // x^5 + Fix64::from_rat(-78547, 16777216), // x^7 + Fix64::from_rat(673, 4194304), // x^9 +]; + +fn sin_pi_over_2_poly(x: Fix64) -> Fix64 { + let x_sq = x * x; + let mut retval = Fix64::from(0); + for coeff in SIN_PI_OVER_2_POLY_COEFFS.iter().rev() { + retval = retval.mul_add(x_sq, *coeff); + } + retval * x +} + +const COS_PI_OVER_2_POLY_COEFFS: &[Fix64] = &[ + Fix64::from_rat(1, 1), // x^0 + Fix64::from_rat(-20698061, 16777216), // x^2 + Fix64::from_rat(1063967, 4194304), // x^4 + Fix64::from_rat(-350031, 16777216), // x^6 + Fix64::from_rat(15423, 16777216), // x^8 +]; + +fn cos_pi_over_2_poly(x: Fix64) -> Fix64 { + let x_sq = x * x; + let mut retval = Fix64::from(0); + for coeff in COS_PI_OVER_2_POLY_COEFFS.iter().rev() { + retval = retval.mul_add(x_sq, *coeff); + } + retval +} + +pub fn sin_cos_pi(mut x: Fix64) -> (Fix64, Fix64) { + x >>= 1; + x = x.floor_fract(); + x <<= 2; + let xi = x.round(); + x -= Fix64::from(xi); + match xi & 3 { + 0 => (sin_pi_over_2_poly(x), cos_pi_over_2_poly(x)), + 1 => (cos_pi_over_2_poly(x), -sin_pi_over_2_poly(x)), + 2 => (-sin_pi_over_2_poly(x), -cos_pi_over_2_poly(x)), + 3 => (-cos_pi_over_2_poly(x), sin_pi_over_2_poly(x)), + _ => unreachable!(), + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_sincospi() { + #[derive(Debug, Copy, Clone)] + #[allow(dead_code)] + struct Error { + v: Fix64, + fv: f64, + fsin: f64, + fcos: f64, + sin: Fix64, + cos: Fix64, + eps: f64, + sin_dist: f64, + cos_dist: f64, + max_dist: f64, + } + let mut worst_error = None; + for i in (Fix64::from(-4i64).as_bits()..=Fix64::from(4i64).as_bits()).step_by(12345) { + let v = Fix64::from_bits(i); + let fv = v.to_f64(); + let (fsin, fcos) = (fv * std::f64::consts::PI).sin_cos(); + let (sin, cos) = sin_cos_pi(v); + let eps = Fix64::from_bits(5).to_f64(); + let sin_dist = (sin.to_f64() - fsin).abs(); + let cos_dist = (cos.to_f64() - fcos).abs(); + let max_dist = sin_dist.max(cos_dist); + match worst_error { + Some(Error { max_dist: d, .. }) if d > max_dist => {} + _ => { + worst_error = Some(Error { + v, + fv, + fsin, + fcos, + sin, + cos, + eps, + sin_dist, + cos_dist, + max_dist, + }) + } + } + } + let Some(worst_error @ Error { eps, max_dist, .. }) = worst_error else { + return; + }; + assert!(max_dist < eps, "{worst_error:?}"); + } +} diff --git a/rust_voxels_game/src/take_once.rs b/rust_voxels_game/src/take_once.rs new file mode 100644 index 0000000..69af801 --- /dev/null +++ b/rust_voxels_game/src/take_once.rs @@ -0,0 +1,37 @@ +use core::{ + cell::UnsafeCell, + fmt, + sync::atomic::{AtomicBool, Ordering}, +}; + +pub struct TakeOnce { + value: UnsafeCell, + taken: AtomicBool, +} + +unsafe impl Sync for TakeOnce {} + +#[derive(Debug)] +pub struct AlreadyTaken; + +impl fmt::Display for AlreadyTaken { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.write_str("value already taken") + } +} + +impl TakeOnce { + pub const fn new(value: T) -> Self { + TakeOnce { + value: UnsafeCell::new(value), + taken: AtomicBool::new(false), + } + } + pub fn take(&self) -> Result<&mut T, AlreadyTaken> { + if self.taken.swap(true, Ordering::AcqRel) { + Err(AlreadyTaken) + } else { + Ok(unsafe { &mut *self.value.get() }) + } + } +} diff --git a/rust_voxels_game/src/vec.rs b/rust_voxels_game/src/vec.rs new file mode 100644 index 0000000..d9e2006 --- /dev/null +++ b/rust_voxels_game/src/vec.rs @@ -0,0 +1,162 @@ +use core::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign}; + +macro_rules! impl_assign_op { + ($AssignOp:ident::$assign_fn:ident => $Op:ident::$op_fn:ident) => { + impl $AssignOp for Vec3D + where + Self: $Op + Clone, + { + fn $assign_fn(&mut self, rhs: R) { + *self = self.clone().$op_fn(rhs); + } + } + }; +} + +#[derive(Copy, Clone, PartialEq, Eq, Debug)] +pub struct Vec3D { + pub x: T, + pub y: T, + pub z: T, +} + +impl Vec3D { + pub fn map R>(self, mut f: F) -> Vec3D { + Vec3D { + x: f(self.x), + y: f(self.y), + z: f(self.z), + } + } + pub fn as_ref(&self) -> Vec3D<&T> { + let Vec3D { x, y, z } = self; + Vec3D { x, y, z } + } + pub fn zip(self, rhs: Vec3D) -> Vec3D<(T, R)> { + Vec3D { + x: (self.x, rhs.x), + y: (self.y, rhs.y), + z: (self.z, rhs.z), + } + } + pub fn into_array(self) -> [T; 3] { + [self.x, self.y, self.z] + } + pub fn from_array(v: [T; 3]) -> Self { + let [x, y, z] = v; + Self { x, y, z } + } + pub fn dot(self, rhs: Vec3D) -> R + where + R: Add, + T: Mul, + { + self.x * rhs.x + self.y * rhs.y + self.z * rhs.z + } + pub fn abs_sq(self) -> R + where + R: Add, + T: Mul + Clone, + { + let rhs = self.clone(); + self.dot(rhs) + } +} + +impl Vec3D { + pub const fn sub_const(self, r: Self) -> Self { + Vec3D { + x: self.x - r.x, + y: self.y - r.y, + z: self.z - r.z, + } + } + pub const fn dot_const(self, rhs: Vec3D) -> i64 { + self.x * rhs.x + self.y * rhs.y + self.z * rhs.z + } + pub const fn abs_sq_const(self) -> i64 { + self.dot_const(self) + } +} + +impl Neg for Vec3D { + type Output = Vec3D; + + fn neg(self) -> Self::Output { + Vec3D { + x: -self.x, + y: -self.y, + z: -self.z, + } + } +} + +impl Add> for Vec3D +where + L: Add, +{ + type Output = Vec3D; + + fn add(self, r: Vec3D) -> Self::Output { + Vec3D { + x: self.x + r.x, + y: self.y + r.y, + z: self.z + r.z, + } + } +} + +impl_assign_op!(AddAssign::add_assign => Add::add); + +impl Sub> for Vec3D +where + L: Sub, +{ + type Output = Vec3D; + + fn sub(self, r: Vec3D) -> Self::Output { + Vec3D { + x: self.x - r.x, + y: self.y - r.y, + z: self.z - r.z, + } + } +} + +impl_assign_op!(SubAssign::sub_assign => Sub::sub); + +impl Mul for Vec3D +where + L: Mul, + R: Clone, +{ + type Output = Vec3D; + + fn mul(self, r: R) -> Self::Output { + Vec3D { + x: self.x * r.clone(), + y: self.y * r.clone(), + z: self.z * r, + } + } +} + +impl_assign_op!(MulAssign::mul_assign => Mul::mul); + +impl Div for Vec3D +where + L: Div, + R: Clone, +{ + type Output = Vec3D; + + fn div(self, r: R) -> Self::Output { + Vec3D { + x: self.x / r.clone(), + y: self.y / r.clone(), + z: self.z / r, + } + } +} + +impl_assign_op!(DivAssign::div_assign => Div::div); diff --git a/rust_voxels_game/src/world.rs b/rust_voxels_game/src/world.rs new file mode 100644 index 0000000..7bfc135 --- /dev/null +++ b/rust_voxels_game/src/world.rs @@ -0,0 +1,396 @@ +use crate::{ + fixed::Fix64, + screen::{Color, Screen}, + take_once::TakeOnce, + vec::Vec3D, +}; +use core::ops::ControlFlow; + +#[derive(Copy, Clone, PartialEq, Eq)] +pub struct Block { + pub color: Color, +} + +impl Block { + pub const fn is_empty(&self) -> bool { + self.color.0 == Color::default().0 + } + pub const fn default() -> Self { + Block { + color: Color::default(), + } + } +} + +pub struct World { + pub blocks: [[[Block; Self::SIZE]; Self::SIZE]; Self::SIZE], +} + +struct RayCastDimension { + next_pos: i64, + next_t: Fix64, + t_step: Fix64, + pos_step: i64, +} + +impl RayCastDimension { + fn new(start: Fix64, dir: Fix64) -> Option { + let pos_step = dir.signum(); + if pos_step == 0 { + return None; + } + let inv_dir = Fix64::from(1) / dir; + let next_pos = start.floor() + pos_step; + let target = if pos_step > 0 { + Fix64::from(next_pos) + } else { + Fix64::from(next_pos) + Fix64::from(1) + }; + let next_t = (target - start) * inv_dir; + + let retval = RayCastDimension { + next_pos, + next_t, + t_step: inv_dir.abs(), + pos_step, + }; + + Some(retval) + } + fn step(&mut self) { + self.next_t += self.t_step; + self.next_pos += self.pos_step; + } +} + +impl World { + pub const SIZE: usize = 40; + pub const ARRAY_AXIS_ORIGIN: i64 = Self::SIZE as i64 / -2; + pub const ARRAY_ORIGIN: Vec3D = Vec3D { + x: Self::ARRAY_AXIS_ORIGIN, + y: Self::ARRAY_AXIS_ORIGIN, + z: Self::ARRAY_AXIS_ORIGIN, + }; + const fn init_block(pos: Vec3D) -> Block { + let mut block = Block { + color: Color((pos.x * 157 + pos.y * 246 + pos.z * 43 + 123) as u8), + }; + const SPHERES: &[(Vec3D, i64, Color)] = &[ + (Vec3D { x: 0, y: 0, z: 0 }, 10 * 10, Color::default()), + ( + Vec3D { + x: -5, + y: -5, + z: -5, + }, + 3 * 3, + Color(3), + ), + ( + Vec3D { + x: -5, + y: 5, + z: 5, + }, + 3 * 3, + Color(6), + ), + ( + Vec3D { + x: 5, + y: 5, + z: -5, + }, + 3 * 3, + Color(5), + ), + ( + Vec3D { + x: 5, + y: -5, + z: 5, + }, + 3 * 3, + Color(7), + ), + ]; + let mut sphere_idx = 0; + while sphere_idx < SPHERES.len() { + let (sphere_pos, r_sq, sphere_color) = SPHERES[sphere_idx]; + if pos.sub_const(sphere_pos).abs_sq_const() <= r_sq { + block.color = sphere_color; + } + sphere_idx += 1; + } + block + } + const fn new() -> World { + let mut retval = Self { + blocks: [[[Block::default(); Self::SIZE]; Self::SIZE]; Self::SIZE], + }; + let mut array_pos = Vec3D { x: 0, y: 0, z: 0 }; + while array_pos.x < Self::SIZE { + array_pos.y = 0; + while array_pos.y < Self::SIZE { + array_pos.z = 0; + while array_pos.z < Self::SIZE { + let pos = Self::from_array_pos(array_pos); + retval.blocks[array_pos.z][array_pos.y][array_pos.x] = Self::init_block(pos); + array_pos.z += 1; + } + array_pos.y += 1; + } + array_pos.x += 1; + } + retval + } + pub fn take() -> &'static mut World { + #[allow(long_running_const_eval)] + static WORLD: TakeOnce = TakeOnce::new(World::new()); + WORLD.take().expect("world already taken") + } + /// out-of-range inputs produce wrapping outputs + pub const fn from_array_pos(array_pos: Vec3D) -> Vec3D { + Vec3D { + x: (array_pos.x as i64).wrapping_add(Self::ARRAY_ORIGIN.x), + y: (array_pos.y as i64).wrapping_add(Self::ARRAY_ORIGIN.y), + z: (array_pos.z as i64).wrapping_add(Self::ARRAY_ORIGIN.z), + } + } + /// out-of-range inputs produce wrapping outputs + pub fn array_pos(pos: Vec3D) -> Vec3D { + pos.zip(Self::ARRAY_ORIGIN) + .map(|(pos, ao)| pos.wrapping_sub(ao) as usize) + } + pub fn get_array_mut(&mut self, array_pos: Vec3D) -> Option<&mut Block> { + self.blocks + .get_mut(array_pos.z)? + .get_mut(array_pos.y)? + .get_mut(array_pos.x) + } + pub fn get_array(&self, array_pos: Vec3D) -> Option<&Block> { + self.blocks + .get(array_pos.z)? + .get(array_pos.y)? + .get(array_pos.x) + } + pub fn get_mut(&mut self, pos: Vec3D) -> Option<&mut Block> { + let array_pos = Self::array_pos(pos); + self.get_array_mut(array_pos) + } + pub fn get(&self, pos: Vec3D) -> Option<&Block> { + let array_pos = Self::array_pos(pos); + self.get_array(array_pos) + } + pub fn array_positions() -> impl Iterator> { + (0..Self::SIZE).flat_map(|x| { + (0..Self::SIZE).flat_map(move |y| (0..Self::SIZE).map(move |z| Vec3D { x, y, z })) + }) + } + pub fn positions() -> impl Iterator> { + Self::array_positions().map(Self::from_array_pos) + } + fn cast_ray_impl( + &self, + start: Vec3D, + dir: Vec3D, + mut f: impl FnMut(Vec3D, &Block) -> ControlFlow<()>, + ) -> ControlFlow<()> { + let mut f = move |pos| { + let Some(block) = self.get(pos) else { + return ControlFlow::Break(()); + }; + f(pos, block) + }; + let mut pos = start.map(Fix64::floor).into_array(); + let mut ray_casters = start + .zip(dir) + .map(|(start, dir)| RayCastDimension::new(start, dir)) + .into_array(); + loop { + f(Vec3D::from_array(pos))?; + let mut min_index = None; + let mut min_t = Fix64::from_bits(i64::MAX); + for (index, ray_caster) in ray_casters.iter().enumerate() { + let Some(ray_caster) = ray_caster else { + continue; + }; + if ray_caster.next_t < min_t { + min_t = ray_caster.next_t; + min_index = Some(index); + } + } + let Some(min_index) = min_index else { + return ControlFlow::Break(()); + }; + let ray_caster = ray_casters[min_index].as_mut().unwrap(); + pos[min_index] = ray_caster.next_pos; + ray_caster.step(); + } + } + pub fn cast_ray( + &self, + start: Vec3D, + dir: Vec3D, + f: impl FnMut(Vec3D, &Block) -> ControlFlow<()>, + ) { + let _ = self.cast_ray_impl(start, dir, f); + } + pub fn get_hit_pos( + &self, + start: Vec3D, + forward: Vec3D, + ) -> (Option>, Option>) { + let mut prev_pos = None; + let mut hit_pos = None; + self.cast_ray(start, forward, |pos, block| { + if block.is_empty() { + prev_pos = Some(pos); + ControlFlow::Continue(()) + } else { + hit_pos = Some(pos); + ControlFlow::Break(()) + } + }); + (prev_pos, hit_pos) + } + pub fn render( + &self, + screen: &mut Screen, + start: Vec3D, + forward: Vec3D, + right: Vec3D, + down: Vec3D, + ) { + let (pixel_x_dim, pixel_y_dim) = screen.pixel_dimensions(); + let screen_x_size = Fix64::from(Screen::X_SIZE as i64); + let screen_y_size = Fix64::from(Screen::Y_SIZE as i64); + let screen_x_center = screen_x_size / Fix64::from(2i64); + let screen_y_center = screen_y_size / Fix64::from(2i64); + let screen_x_dim = pixel_x_dim * screen_x_size; + let screen_y_dim = pixel_y_dim * screen_y_size; + let screen_min_dim = screen_x_dim.min(screen_y_dim); + let screen_x_factor = screen_x_dim / screen_min_dim; + let screen_y_factor = screen_y_dim / screen_min_dim; + let right_factor_inc = Fix64::from(2) * screen_x_factor / screen_x_size; + let down_factor_inc = Fix64::from(2) * screen_y_factor / screen_y_size; + for (y, row) in screen.pixels.iter_mut().enumerate() { + for (x, pixel) in row.iter_mut().enumerate() { + let right_factor = (Fix64::from(x as i64) - screen_x_center) * right_factor_inc; + let down_factor = (Fix64::from(y as i64) - screen_y_center) * down_factor_inc; + let dir = forward + right * right_factor + down * down_factor; + let mut color = Color::default(); + self.cast_ray(start, dir, |_pos, block| { + if block.is_empty() { + ControlFlow::Continue(()) + } else { + color = block.color; + ControlFlow::Break(()) + } + }); + *pixel = color; + } + } + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_ray_cast() { + let world = World::new(); + let valid_steps = &[ + Vec3D { x: -1, y: 0, z: 0 }, + Vec3D { x: 1, y: 0, z: 0 }, + Vec3D { x: 0, y: -1, z: 0 }, + Vec3D { x: 0, y: 1, z: 0 }, + Vec3D { x: 0, y: 0, z: -1 }, + Vec3D { x: 0, y: 0, z: 1 }, + ]; + let check_cast_ray = |dir, expected_visited: &[_]| { + let mut visited = Vec::new(); + world.cast_ray( + Vec3D { + x: Fix64::from(0.0), + y: Fix64::from(0.0), + z: Fix64::from(0.0), + }, + dir, + |pos, _block| { + visited.push(pos); + ControlFlow::Continue(()) + }, + ); + assert_eq!(expected_visited, &*visited, "dir={dir:?}"); + for i in visited.windows(2) { + let diff = i[0] - i[1]; + assert!(valid_steps.contains(&diff), "diff={diff:?} dir={dir:?}"); + } + }; + check_cast_ray( + Vec3D { + x: Fix64::from(-1.0 / 8.0), + y: Fix64::from(0.0), + z: Fix64::from(1.0), + }, + &[ + Vec3D { x: 0, y: 0, z: 0 }, + Vec3D { x: -1, y: 0, z: 0 }, + Vec3D { x: -1, y: 0, z: 1 }, + Vec3D { x: -1, y: 0, z: 2 }, + Vec3D { x: -1, y: 0, z: 3 }, + Vec3D { x: -1, y: 0, z: 4 }, + Vec3D { x: -1, y: 0, z: 5 }, + Vec3D { x: -1, y: 0, z: 6 }, + Vec3D { x: -1, y: 0, z: 7 }, + Vec3D { x: -2, y: 0, z: 7 }, + Vec3D { x: -2, y: 0, z: 8 }, + Vec3D { x: -2, y: 0, z: 9 }, + Vec3D { x: -2, y: 0, z: 10 }, + Vec3D { x: -2, y: 0, z: 11 }, + Vec3D { x: -2, y: 0, z: 12 }, + Vec3D { x: -2, y: 0, z: 13 }, + Vec3D { x: -2, y: 0, z: 14 }, + Vec3D { x: -2, y: 0, z: 15 }, + Vec3D { x: -3, y: 0, z: 15 }, + Vec3D { x: -3, y: 0, z: 16 }, + Vec3D { x: -3, y: 0, z: 17 }, + Vec3D { x: -3, y: 0, z: 18 }, + Vec3D { x: -3, y: 0, z: 19 }, + ], + ); + check_cast_ray( + Vec3D { + x: Fix64::from(1.0 / 8.0), + y: Fix64::from(0.0), + z: Fix64::from(1.0), + }, + &[ + Vec3D { x: 0, y: 0, z: 0 }, + Vec3D { x: 0, y: 0, z: 1 }, + Vec3D { x: 0, y: 0, z: 2 }, + Vec3D { x: 0, y: 0, z: 3 }, + Vec3D { x: 0, y: 0, z: 4 }, + Vec3D { x: 0, y: 0, z: 5 }, + Vec3D { x: 0, y: 0, z: 6 }, + Vec3D { x: 0, y: 0, z: 7 }, + Vec3D { x: 1, y: 0, z: 7 }, + Vec3D { x: 1, y: 0, z: 8 }, + Vec3D { x: 1, y: 0, z: 9 }, + Vec3D { x: 1, y: 0, z: 10 }, + Vec3D { x: 1, y: 0, z: 11 }, + Vec3D { x: 1, y: 0, z: 12 }, + Vec3D { x: 1, y: 0, z: 13 }, + Vec3D { x: 1, y: 0, z: 14 }, + Vec3D { x: 1, y: 0, z: 15 }, + Vec3D { x: 2, y: 0, z: 15 }, + Vec3D { x: 2, y: 0, z: 16 }, + Vec3D { x: 2, y: 0, z: 17 }, + Vec3D { x: 2, y: 0, z: 18 }, + Vec3D { x: 2, y: 0, z: 19 }, + ], + ); + } +} diff --git a/scripts/bin2hex.py b/scripts/bin2hex.py index cd732cb..5c19022 100755 --- a/scripts/bin2hex.py +++ b/scripts/bin2hex.py @@ -1,17 +1,10 @@ #!/usr/bin/python3 import sys -import subprocess -import struct with open(sys.argv[1], "rb") as f: - while True: - word = f.read(8) - if len(word) == 8: - print("%016x" % struct.unpack('