use crate::entity::{Entity, EntityType, MetaValue};
use crate::store::{Entities, Fast};
const INT_PHI: i32 = 0x9E37_79B9_u32 as i32;
const DEFAULT_INITIAL_SIZE: usize = 16;
const LOAD_FACTOR: f32 = 0.75;
#[inline]
fn mix(x: i32) -> i32 {
let h = x.wrapping_mul(INT_PHI);
h ^ ((h as u32) >> 16) as i32
}
fn array_size(expected: usize, f: f32) -> usize {
let s = (expected as f32 / f).ceil() as u64;
s.next_power_of_two().max(2) as usize
}
fn max_fill(n: usize, f: f32) -> usize {
((n as f32 * f).ceil() as usize).min(n - 1)
}
#[derive(Clone, Debug)]
pub(crate) struct ClientMap {
key: Vec<i32>,
n: usize,
mask: usize,
size: usize,
max_fill: usize,
min_n: usize,
has_null: bool,
}
impl Default for ClientMap {
fn default() -> Self {
let n = array_size(DEFAULT_INITIAL_SIZE, LOAD_FACTOR);
ClientMap {
key: vec![0; n],
n,
mask: n - 1,
size: 0,
max_fill: max_fill(n, LOAD_FACTOR),
min_n: n,
has_null: false,
}
}
}
impl ClientMap {
fn find(&self, k: i32) -> Option<usize> {
if k == 0 {
return self.has_null.then_some(self.n);
}
let mut pos = (mix(k) as usize) & self.mask;
loop {
let cur = self.key[pos];
if cur == 0 {
return None;
}
if cur == k {
return Some(pos);
}
pos = (pos + 1) & self.mask;
}
}
pub(crate) fn insert(&mut self, k: i32) {
if k == 0 {
if self.has_null {
return;
}
self.has_null = true;
} else {
let mut pos = (mix(k) as usize) & self.mask;
loop {
let cur = self.key[pos];
if cur == 0 {
break;
}
if cur == k {
return;
}
pos = (pos + 1) & self.mask;
}
self.key[pos] = k;
}
let before = self.size;
self.size += 1;
if before >= self.max_fill {
self.rehash(array_size(self.size + 1, LOAD_FACTOR));
}
}
pub(crate) fn remove(&mut self, k: i32) -> bool {
if k == 0 {
if !self.has_null {
return false;
}
self.has_null = false;
} else {
let Some(pos) = self.find(k) else {
return false;
};
self.shift_keys(pos);
}
self.size -= 1;
if self.n > self.min_n && self.size < self.max_fill / 4 && self.n > DEFAULT_INITIAL_SIZE {
self.rehash(self.n / 2);
}
true
}
fn shift_keys(&mut self, mut pos: usize) {
loop {
let last = pos;
pos = (last + 1) & self.mask;
let cur = loop {
let cur = self.key[pos];
if cur == 0 {
self.key[last] = 0;
return;
}
let slot = (mix(cur) as usize) & self.mask;
let stays = if last <= pos {
last >= slot || slot > pos
} else {
last >= slot && slot > pos
};
if stays {
break cur;
}
pos = (pos + 1) & self.mask;
};
self.key[last] = cur;
}
}
fn rehash(&mut self, new_n: usize) {
let mask = new_n - 1;
let mut next = vec![0; new_n];
for i in (0..self.n).rev() {
let k = self.key[i];
if k == 0 {
continue;
}
let mut pos = (mix(k) as usize) & mask;
while next[pos] != 0 {
pos = (pos + 1) & mask;
}
next[pos] = k;
}
self.key = next;
self.n = new_n;
self.mask = mask;
self.max_fill = max_fill(new_n, LOAD_FACTOR);
}
pub(crate) fn order(&self) -> impl Iterator<Item = i32> + '_ {
self.has_null
.then_some(0)
.into_iter()
.chain(self.key.iter().rev().copied().filter(|&k| k != 0))
}
pub(crate) fn before(&self, a: i32, b: i32) -> bool {
match (self.find(a), self.find(b)) {
(Some(x), Some(y)) => x > y,
_ => false,
}
}
pub(crate) fn rank(&self, k: i32) -> Option<u32> {
self.find(k).map(|slot| (self.n - slot) as u32)
}
#[cfg(test)]
pub(crate) fn len(&self) -> usize {
self.size
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Lerp {
Living,
Boat,
Still,
}
#[derive(Clone, Debug)]
pub(crate) struct Motion {
pub(crate) pos: [f64; 3],
target: [f64; 3],
steps: u8,
lerp: Lerp,
pub(crate) bb: [f64; 6],
dims: (f32, f32),
pose: i32,
slime: i32,
stand: u8,
baby: bool,
attached: Option<[i32; 3]>,
pub(crate) dead: bool,
pub(crate) name: Option<Box<str>>,
}
pub(crate) mod ty {
pub(crate) const ARMOR_STAND: u16 = 1;
pub(crate) const BOAT: u16 = 6;
pub(crate) const MAGMA_CUBE: u16 = 44;
pub(crate) const PIGLIN: u16 = 60;
pub(crate) const SHULKER: u16 = 70;
pub(crate) const SLIME: u16 = 75;
}
fn box_at(dims: (f32, f32), p: [f64; 3]) -> [f64; 6] {
let f = f64::from(dims.0 / 2.0);
let g = f64::from(dims.1);
[p[0] - f, p[1], p[2] - f, p[0] + f, p[1] + g, p[2] + f]
}
impl Motion {
fn set_position(&mut self, p: [f64; 3]) {
self.pos = p;
self.bb = box_at(self.dims, p);
}
fn retarget(&mut self, target: [f64; 3]) {
match self.lerp {
Lerp::Living => {
self.target = target;
self.steps = 3;
}
Lerp::Boat => {
self.target = target;
self.steps = 10;
}
Lerp::Still => {}
}
}
fn resize(&mut self, e: &Entity) {
let Some(vs) = e.sizer else { return };
let Some(d) =
crate::v1_16_5::dims_with(e.ty, vs, self.pose, Some(self.slime), self.stand, self.baby)
else {
return;
};
let new = (d.width, d.height);
let old = self.dims;
self.dims = new;
if new.0 < old.0 {
let h = f64::from(new.0) / 2.0;
let [x, y, z] = self.pos;
self.bb = [x - h, y, z - h, x + h, y + f64::from(new.1), z + h];
} else {
let b = self.bb;
self.bb = [
b[0],
b[1],
b[2],
b[0] + f64::from(new.0),
b[1] + f64::from(new.1),
b[2] + f64::from(new.0),
];
}
if matches!(
e.ty,
EntityType::Registry(ty::SLIME | ty::MAGMA_CUBE | ty::ARMOR_STAND)
) {
let p = self.pos;
self.set_position(p);
}
}
}
#[derive(Clone, Debug, Default)]
pub(crate) struct Client16 {
pub(crate) map: ClientMap,
pub(crate) motion: Fast<i32, Motion>,
}
impl Client16 {
pub(crate) fn new_world(&mut self, self_id: Option<i32>) {
self.map = ClientMap::default();
self.motion.clear();
crate::store::shrink_map(&mut self.motion);
if let Some(id) = self_id {
self.map.insert(id);
}
}
pub(crate) fn add(&mut self, id: i32) {
self.map.remove(id);
self.map.insert(id);
self.motion.remove(&id);
}
pub(crate) fn remove(&mut self, id: i32) {
self.map.remove(id);
if self.motion.remove(&id).is_some() {
crate::store::shrink_map(&mut self.motion);
}
}
pub(crate) fn spawned(&mut self, e: &Entity, name: Option<Box<str>>) {
let lerp = match e.ty {
EntityType::Registry(ty::BOAT) => Lerp::Boat,
EntityType::Registry(ty::SHULKER) => Lerp::Still,
EntityType::Player => Lerp::Living,
_ if e.living => Lerp::Living,
_ => return,
};
let Some((w, h)) = e.sizer.and_then(|s| s.registered) else {
return;
};
let mut m = Motion {
pos: e.pos,
target: e.pos,
steps: 0,
lerp,
bb: [0.0; 6],
dims: (w, h),
pose: 0,
slime: 1,
stand: 0,
baby: false,
attached: None,
dead: false,
name,
};
m.set_position(e.pos);
let cap = self.motion.capacity();
self.motion.insert(e.id, m);
crate::store::after_insert(&mut self.motion, cap);
}
pub(crate) fn moved(&mut self, id: i32, target: [f64; 3]) {
if let Some(m) = self.motion.get_mut(&id) {
m.retarget(target);
}
}
pub(crate) fn looked(&mut self, id: i32) {
if let Some(m) = self.motion.get_mut(&id) {
let p = m.pos;
m.retarget(p);
}
}
pub(crate) fn data(&mut self, e: &Entity, entries: &[(u8, MetaValue)]) {
let Some(m) = self.motion.get_mut(&e.id) else {
return;
};
let id = match e.ty {
EntityType::Registry(id) => Some(id),
_ => None,
};
let baby_index = if id == Some(ty::PIGLIN) { 16 } else { 15 };
let has_baby = e.sizer.is_some_and(|s| s.baby().is_some());
for (i, v) in entries {
let resize = match (*i, v) {
(6, MetaValue::Pose(p)) => {
m.pose = *p;
true
}
(8, MetaValue::Float(h)) if e.living || e.ty == EntityType::Player => {
m.dead = h.is_nan() || *h <= 0.0;
false
}
(15, MetaValue::VarInt(n)) if matches!(id, Some(ty::SLIME | ty::MAGMA_CUBE)) => {
m.slime = *n;
true
}
(14, MetaValue::Byte(b)) if id == Some(ty::ARMOR_STAND) => {
m.stand = *b as u8;
true
}
(16, MetaValue::OptBlockPos(p)) if id == Some(ty::SHULKER) => {
m.attached = *p;
false
}
(i, MetaValue::Bool(b)) if has_baby && i == baby_index => {
m.baby = *b;
true
}
_ => false,
};
if resize {
m.resize(e);
}
}
}
pub(crate) fn tick(&mut self, store: &Entities, ticks: impl Fn(&Entity) -> bool) {
for (id, m) in &mut self.motion {
let Some(e) = store.map.get(id) else { continue };
if !ticks(e) {
continue;
}
if let Some(b) = m.attached {
let (x, y, z) = (f64::from(b[0]), f64::from(b[1]), f64::from(b[2]));
m.pos = [x + 0.5, y, z + 0.5];
m.bb = [
m.pos[0] - 0.5,
y,
m.pos[2] - 0.5,
m.pos[0] + 0.5,
y + 1.0,
m.pos[2] + 0.5,
];
continue;
}
if m.steps > 0 && m.lerp != Lerp::Still {
let n = f64::from(m.steps);
let p = [
m.pos[0] + (m.target[0] - m.pos[0]) / n,
m.pos[1] + (m.target[1] - m.pos[1]) / n,
m.pos[2] + (m.target[2] - m.pos[2]) / n,
];
m.steps -= 1;
m.set_position(p);
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn grows_and_shrinks() {
let mut m = ClientMap::default();
for k in 1..=100 {
m.insert(k * 7);
}
assert_eq!(m.len(), 100);
assert_eq!(m.n, 256);
for k in 1..=95 {
assert!(m.remove(k * 7));
}
assert_eq!(m.len(), 5);
assert!(m.n < 256);
let order: Vec<i32> = m.order().collect();
assert_eq!(order.len(), 5);
m.insert(0);
assert_eq!(m.order().next(), Some(0));
assert!(m.before(0, 96 * 7));
}
}