Continuing the discussion from Re: Game world and implementation:
Here’s what I’ve been working on this weekend…
use std::fmt;
use std::convert::From;
use std::hash::Hash;
use std::hash::Hasher;
use std::collections::HashSet;
use std::rc::Rc;
#[derive(Debug, Hash, PartialEq)]
pub struct BlockState
{
color: Color
}
impl BlockState
{
fn get_color(&self) -> Color
{
self.color
}
}
#[derive(Hash, PartialEq)]
pub struct Color
{
red: u8,
green: u8,
blue: u8,
alpha: u8
}
impl Clone for Color
{
fn clone(&self) -> Color
{
Color
{
red: self.red,
green: self.green,
blue: self.blue,
alpha: self.alpha
}
}
}
impl Copy for Color {}
impl fmt::Debug for Color
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result
{
f.write_fmt(format_args!("Color {{ RGBA: #{:08X?} }}", u32::from(*self)))
}
}
impl From<u32> for Color
{
fn from(dw: u32) -> Color
{
let bytes: [u8; 4] = dw.to_le_bytes();
Color
{
red: bytes[0],
green: bytes[1],
blue: bytes[2],
alpha: bytes[3]
}
}
}
impl From<Color> for u32
{
fn from(color: Color) -> u32
{
color.red as u32 |
(color.green as u32 >> 8) |
(color.blue as u32 >> 16) |
(color.alpha as u32 >> 24)
}
}
enum Node
{
Branch(Color, [Rc<Node>; 8]),
Leaf(BlockState)
}
impl Node
{
fn get_color(&self) -> Color
{
match self
{
Node::Branch(color, _) => *color,
Node::Leaf(state) => state.get_color()
}
}
}
impl fmt::Debug for Node
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result
{
match self
{
Node::Branch(color, children) =>
{
// default implementation is a dump (literally)
/*f.debug_struct("Node::Branch")
.field("color", color)
.field("children", children)
.finish()*/
f.write_fmt
(
format_args!
(
"Node::Branch {{ color: {:?}, children: \
[{:?},{:?},{:?},{:?},{:?},{:?},{:?},{:?}] }}",
color,
Rc::as_ptr(&children[0]),
Rc::as_ptr(&children[1]),
Rc::as_ptr(&children[2]),
Rc::as_ptr(&children[3]),
Rc::as_ptr(&children[4]),
Rc::as_ptr(&children[5]),
Rc::as_ptr(&children[6]),
Rc::as_ptr(&children[7])
)
)
},
Node::Leaf(block_state) =>
{
f.debug_struct("Node::Leaf")
.field("block_state", &block_state)
.finish()
}
}
}
}
struct NodeKey
{
node: Rc<Node>
}
impl Eq for NodeKey {}
impl Hash for NodeKey
{
fn hash<H: Hasher>(&self, state: &mut H)
{
match &*self.node
{
Node::Branch(_, children) =>
{
Rc::as_ptr(&children[0]).hash(state);
Rc::as_ptr(&children[1]).hash(state);
Rc::as_ptr(&children[2]).hash(state);
Rc::as_ptr(&children[3]).hash(state);
Rc::as_ptr(&children[4]).hash(state);
Rc::as_ptr(&children[5]).hash(state);
Rc::as_ptr(&children[6]).hash(state);
Rc::as_ptr(&children[7]).hash(state);
},
Node::Leaf(block_state) =>
{
block_state.hash(state);
}
}
}
}
impl PartialEq for NodeKey
{
fn eq(&self, other: &Self) -> bool
{
match &*self.node
{
Node::Branch(_, children) =>
{
match &*other.node
{
Node::Branch(_, ochildren) =>
{
Rc::as_ptr(&children[0]) == Rc::as_ptr(&ochildren[0]) &&
Rc::as_ptr(&children[1]) == Rc::as_ptr(&ochildren[1]) &&
Rc::as_ptr(&children[2]) == Rc::as_ptr(&ochildren[2]) &&
Rc::as_ptr(&children[3]) == Rc::as_ptr(&ochildren[3]) &&
Rc::as_ptr(&children[4]) == Rc::as_ptr(&ochildren[4]) &&
Rc::as_ptr(&children[5]) == Rc::as_ptr(&ochildren[5]) &&
Rc::as_ptr(&children[6]) == Rc::as_ptr(&ochildren[6]) &&
Rc::as_ptr(&children[7]) == Rc::as_ptr(&ochildren[7])
},
Node::Leaf(_) => false
}
},
Node::Leaf(state) =>
{
match &*other.node
{
Node::Branch(_, _) => false,
Node::Leaf(ostate) =>
{
state == ostate
}
}
}
}
}
}
pub struct Octree
{
max_depth: usize,
root: NodeKey,
nodes: HashSet<NodeKey>
}
impl Octree
{
pub fn get_block_state(&self, x: i64, y: i64, z: i64) -> &BlockState
{
let node = self.get_node(x, y, z, Some(self.max_depth));
let key = NodeKey { node: Rc::clone(&node) };
let block_state: &BlockState = match self.nodes.get(&key)
{
Some(n) => match &*n.node
{
Node::Branch(_, _) => panic!(),
Node::Leaf(block_state) => &block_state
},
None => panic!()
};
block_state
}
pub fn get_color
(
&self,
x: i64, y: i64, z: i64,
level_of_detail: Option<usize>
) -> Color
{
self.get_node(x, y, z, level_of_detail).get_color()
}
/*
* max_depth must be between 1 and 22 inclusive.
*/
pub fn new(max_depth: usize, fill_block: Option<BlockState>) -> Octree
{
if max_depth < 1 // you want an octree, right?
{
panic!("Octree::new() requires max_depth of at least 1");
}
else if max_depth > 65 // i64 limit
{
// That still leaves over 49 cubic light years of accessible space
// assuming each leaf node represents a cubic inch
// The observable universe has a diameter of ~93 ly for reference
panic!("Octree::new() requires max_depth of no more than 65");
}
let mut nodes: HashSet<NodeKey> = HashSet::with_capacity(max_depth);
let color: Color;
let leaf: Rc<Node>;
if let Some(block_state) = fill_block
{
color = block_state.get_color();
leaf = Rc::new(Node::Leaf(block_state));
}
else
{
color = Color { red: 0, blue: 0, green: 0, alpha: 0 };
let block_state = BlockState { color };
leaf = Rc::new(Node::Leaf(block_state));
}
nodes.insert(NodeKey { node: Rc::clone(&leaf) });
let mut node = Rc::clone(&leaf);
for _ in 0..max_depth
{
let children =
[
Rc::clone(&node),
Rc::clone(&node),
Rc::clone(&node),
Rc::clone(&node),
Rc::clone(&node),
Rc::clone(&node),
Rc::clone(&node),
Rc::clone(&node)
];
node = Rc::new(Node::Branch(color, children));
nodes.insert(NodeKey { node: Rc::clone(&node) });
}
Octree { max_depth, root: NodeKey { node }, nodes }
}
pub fn set_block_state
(
&mut self,
block_state: BlockState,
x: i64, y: i64, z: i64
) -> Result<(), &str>
{
// todo: replace leaf nodes at coords, update parent nodes up the tree
Err("NYI")
}
fn get_node
(
&self,
x: i64, y: i64, z: i64,
level_of_detail: Option<usize>
) -> Rc<Node>
{
let lod: usize;
if let Some(level) = level_of_detail
{
lod = std::cmp::min(level, self.max_depth);
}
else
{
lod = self.max_depth;
}
let mut node = Rc::clone(&self.root.node);
if lod > 0
{
let mut center_x = 2_i64.pow(self.max_depth as u32 - 2);
let mut center_y = center_x;
let mut center_z = center_x;
let mut i = 0;
if x < 0 { i += 4; center_x = -center_x }
if y >= 0 { i += 1} else { center_y = -center_y }
if z < 0 { i += 2; center_z = -center_z}
node = match &*node
{
Node::Branch(_, children) =>
{
Rc::clone(&children[i])
},
_ => panic!("Malformed Octree.")
};
for depth in 0..(lod - 1)
{
i = 0;
let delta = 2_i64.pow(self.max_depth as u32 - depth as u32 - 2);
if x < center_x { i += 4; center_x -= delta }
else {center_x += delta }
if y >= center_y { i += 1; center_y += delta }
else { center_y -= delta }
if z < center_z { i += 2; center_z -= delta }
else {center_z += delta }
node = match &*node
{
Node::Branch(_, children) =>
{
Rc::clone(&children[i])
},
_ => panic!("Malformed Octree.")
};
}
}
node
}
}
#[cfg(test)]
mod tests
{
#[test]
fn new()
{
use crate::{BlockState, Color, Octree};
let max_depth = 4_usize;
let color = Color { red: 0_u8, blue: 0_u8, green: 0_u8, alpha: 0_u8 };
let block_state = BlockState { color };
let tree = Octree::new(max_depth, Some(block_state));
let block_state = BlockState { color };
let range = 2_i64.pow(max_depth as u32 - 1_u32);
for i in -range..range
{
for j in -range..range
{
for k in -range..range
{
let block_state2 = tree.get_block_state(i, j, k);
assert_eq!(block_state, *block_state2);
let color2 = tree.get_color(i, j, k, None);
assert_eq!(color, color2);
}
}
}
}
#[test]
fn set_block_state()
{
use crate::{BlockState, Color, Octree};
let max_depth = 2_usize;
let range = 2_i64.pow(max_depth as u32 - 1_u32);
let white = Color::from(0xFFFFFFFF_u32);
let black = Color::from(0x000000FF_u32);
let mut tree = Octree::new(max_depth, None);
// fill the bottom layer with black
for i in -range..range
{
for j in -range..range
{
let block_state = BlockState { color: black };
tree.set_block_state(block_state, i, j, -range).unwrap();
}
}
// add a bit of white
let block_state = BlockState { color: white };
tree.set_block_state(block_state, 0, 0, -range + 1).unwrap();
// check
let clear = Color::from(0x00000000_u32);
for i in -range..range
{
for j in -range..range
{
for k in -range..range
{
let color = tree.get_color(i, j, k, None);
if k == -range
{
assert_eq!(color, black);
}
else if i == 0 && j == 0 && k == -range + 1
{
assert_eq!(color, white);
}
else
{
assert_eq!(color, clear);
}
}
}
}
}
}
~Max
