Physics (#11)

* Put physics module in azalea-entity

* port aabb

* add more stuff to PositionXYZ

* azalea-physics

* important collision things

* more physics stuff

* backup because i'm about to delete shapes

* more shape stuff

* CubeVoxelShape

* no compile errors???

insane

* impl VoxelShape for ArrayVoxelShape

* Shapes stuff

* collide_x but it doesn't work yet

* binary_search

* it compiles

* Entity has bounding box

* Update discrete_voxel_shape.rs

* Entity::make_bounding_box

* ok i'm about to merge az-entity and az-world

might be a terrible idea which is why i'm committing first

* ok so i moved entity to world

* on_pos and move_entity compiles

* add send_position

* move collision stuff to collision module in az-physics

* dimension is no longer an Option

* start trying to do collision for the client

* collision works :tada:

* start adding palette resizing

* get_and_set (pain)

* it compiles but probably won't work

* add a test

* remove printlns

* add more tests for palette stuff

* ClientboundMoveVec3Packet -> ClientboundMoveEntityPosPacket

i think i changed this on accident once

* palette resizing works

todo: remove the printlns

* Remove printlns in palette.rs

* fix issues from merge

* fixes + work a bit more on physics

* Better entities (#19)

* well it compiles

* add tests to entity storage

* add suggestions in azalea-brigadier

* this probably causes ub

* fix brigadiersuggestions

* get rid of entityid

* test From<EntityMut> for EntityRef

* don't mention other libraries since there's too many

* fix warnings

* do todos in brigadier suggestions

* work on physics

* more physics stuff

* remove trait feature on az-block

i think rust gets confused and compiles the macro without the feature

* bump ahash

* aes tests in az-crypto

* optimize aes's deps

* fix crashes

* fix section_index for negative numbers and test

* fix BlockPos protocol implementation

* remove some debug prints

* prepare to add ai_step

* make ai step work

* clippy

5 files changed, 947 insertions, 0 deletions

diff --git a/azalea-physics/src/collision/dimension_collisions.rs b/azalea-physics/src/collision/dimension_collisions.rs
new file mode 100644
index 00000000..59514fda
--- /dev/null
+++ b/azalea-physics/src/collision/dimension_collisions.rs
@@ -0,0 +1,137 @@
+use crate::collision::{VoxelShape, AABB};
+use azalea_block::BlockState;
+use azalea_core::{ChunkPos, ChunkSectionPos, Cursor3d, CursorIterationType, EPSILON};
+use azalea_world::entity::EntityData;
+use azalea_world::{Chunk, Dimension};
+use std::sync::{Arc, Mutex};
+
+pub trait CollisionGetter {
+    fn get_block_collisions<'a>(
+        &'a self,
+        entity: Option<&EntityData>,
+        aabb: AABB,
+    ) -> BlockCollisions<'a>;
+}
+
+impl CollisionGetter for Dimension {
+    fn get_block_collisions<'a>(
+        &'a self,
+        entity: Option<&EntityData>,
+        aabb: AABB,
+    ) -> BlockCollisions<'a> {
+        BlockCollisions::new(self, entity, aabb)
+    }
+}
+
+pub struct BlockCollisions<'a> {
+    pub dimension: &'a Dimension,
+    // context: CollisionContext,
+    pub aabb: AABB,
+
+    pub cursor: Cursor3d,
+    pub only_suffocating_blocks: bool,
+}
+
+impl<'a> BlockCollisions<'a> {
+    pub fn new(dimension: &'a Dimension, _entity: Option<&EntityData>, aabb: AABB) -> Self {
+        let origin_x = (aabb.min_x - EPSILON) as i32 - 1;
+        let origin_y = (aabb.min_y - EPSILON) as i32 - 1;
+        let origin_z = (aabb.min_z - EPSILON) as i32 - 1;
+
+        let end_x = (aabb.max_x + EPSILON) as i32 + 1;
+        let end_y = (aabb.max_y + EPSILON) as i32 + 1;
+        let end_z = (aabb.max_z + EPSILON) as i32 + 1;
+
+        let cursor = Cursor3d::new(origin_x, origin_y, origin_z, end_x, end_y, end_z);
+
+        Self {
+            dimension,
+            aabb,
+            cursor,
+            only_suffocating_blocks: false,
+        }
+    }
+
+    fn get_chunk(&self, block_x: i32, block_z: i32) -> Option<&Arc<Mutex<Chunk>>> {
+        let chunk_x = ChunkSectionPos::block_to_section_coord(block_x);
+        let chunk_z = ChunkSectionPos::block_to_section_coord(block_z);
+        let chunk_pos = ChunkPos::new(chunk_x, chunk_z);
+
+        // TODO: minecraft caches chunk here
+        // int chunkX = SectionPos.blockToSectionCoord(blockX);
+        // int chunkZ = SectionPos.blockToSectionCoord(blockZ);
+        // long chunkPosLong = ChunkPos.asLong(chunkX, chunkZ);
+        // if (this.cachedBlockGetter != null && this.cachedBlockGetterPos == var5) {
+        //    return this.cachedBlockGetter;
+        // } else {
+        //    BlockGetter var7 = this.collisionGetter.getChunkForCollisions(chunkX, chunkZ);
+        //    this.cachedBlockGetter = var7;
+        //    this.cachedBlockGetterPos = chunkPosLong;
+        //    return var7;
+        // }
+
+        self.dimension[&chunk_pos].as_ref()
+    }
+}
+
+impl<'a> Iterator for BlockCollisions<'a> {
+    type Item = Box<dyn VoxelShape>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        while let Some(item) = self.cursor.next() {
+            if item.iteration_type == CursorIterationType::Corner {
+                continue;
+            }
+
+            let chunk = self.get_chunk(item.pos.x, item.pos.z);
+            let chunk = match chunk {
+                Some(chunk) => chunk,
+                None => continue,
+            };
+            let chunk_lock = chunk.lock().unwrap();
+
+            let pos = item.pos;
+            println!("getting block at {:?}", pos);
+            let block_state: BlockState = chunk_lock.get(&(&pos).into(), self.dimension.min_y());
+            // let block: Box<dyn Block> = block_state.into();
+
+            // TODO: continue if self.only_suffocating_blocks and the block is not suffocating
+
+            let block_shape = if block_state == BlockState::Air {
+                crate::collision::empty_shape()
+            } else {
+                crate::collision::block_shape()
+            };
+            // let block_shape = block.get_collision_shape();
+            // if block_shape == Shapes::block() {
+            if true {
+                // TODO: this can be optimized
+                if !self.aabb.intersects_aabb(&AABB {
+                    min_x: item.pos.x as f64,
+                    min_y: item.pos.y as f64,
+                    min_z: item.pos.z as f64,
+                    max_x: (item.pos.x + 1) as f64,
+                    max_y: (item.pos.y + 1) as f64,
+                    max_z: (item.pos.z + 1) as f64,
+                }) {
+                    continue;
+                }
+
+                return Some(block_shape.move_relative(
+                    item.pos.x as f64,
+                    item.pos.y as f64,
+                    item.pos.z as f64,
+                ));
+            }
+
+            // let block_shape = block_shape.move_relative(item.pos.x, item.pos.y, item.pos.z);
+            // if (!Shapes.joinIsNotEmpty(block_shape, this.entityShape, BooleanOp.AND)) {
+            //     continue;
+            // }
+
+            // return block_shape;
+        }
+
+        None
+    }
+}
diff --git a/azalea-physics/src/collision/discrete_voxel_shape.rs b/azalea-physics/src/collision/discrete_voxel_shape.rs
new file mode 100644
index 00000000..6eb425ce
--- /dev/null
+++ b/azalea-physics/src/collision/discrete_voxel_shape.rs
@@ -0,0 +1,156 @@
+use azalea_core::{Axis, AxisCycle, BitSet};
+
+// TODO: every impl of DiscreteVoxelShape could be turned into a single enum as an optimization
+
+pub trait DiscreteVoxelShape {
+    fn size(&self, axis: Axis) -> u32;
+
+    fn first_full_x(&self) -> u32;
+    fn first_full_y(&self) -> u32;
+    fn first_full_z(&self) -> u32;
+
+    fn last_full_x(&self) -> u32;
+    fn last_full_y(&self) -> u32;
+    fn last_full_z(&self) -> u32;
+
+    fn is_empty(&self) -> bool {
+        if self.first_full_x() >= self.last_full_x() {
+            return true;
+        }
+        if self.first_full_y() >= self.last_full_y() {
+            return true;
+        }
+        if self.first_full_x() >= self.last_full_x() {
+            return true;
+        }
+        false
+    }
+
+    fn is_full_wide(&self, x: u32, y: u32, z: u32) -> bool {
+        (x < self.size(Axis::X) && y < self.size(Axis::Y) && z < self.size(Axis::Z))
+            && (self.is_full(x, y, z))
+    }
+    fn is_full_wide_axis_cycle(&self, axis_cycle: AxisCycle, x: u32, y: u32, z: u32) -> bool {
+        self.is_full_wide(
+            axis_cycle.cycle_xyz(x, y, z, Axis::X),
+            axis_cycle.cycle_xyz(x, y, z, Axis::Y),
+            axis_cycle.cycle_xyz(x, y, z, Axis::Z),
+        )
+    }
+
+    fn is_full(&self, x: u32, y: u32, z: u32) -> bool;
+
+    // i don't know how to do this properly
+    fn clone(&self) -> Box<dyn DiscreteVoxelShape>;
+}
+
+#[derive(Default, Clone)]
+pub struct BitSetDiscreteVoxelShape {
+    x_size: u32,
+    y_size: u32,
+    z_size: u32,
+
+    storage: BitSet,
+    x_min: u32,
+    y_min: u32,
+    z_min: u32,
+    x_max: u32,
+    y_max: u32,
+    z_max: u32,
+}
+
+impl BitSetDiscreteVoxelShape {
+    // public BitSetDiscreteVoxelShape(int var1, int var2, int var3) {
+    // 	super(var1, var2, var3);
+    // 	this.storage = new BitSet(var1 * var2 * var3);
+    // 	this.xMin = var1;
+    // 	this.yMin = var2;
+    // 	this.zMin = var3;
+    // }
+    pub fn new(x_min: u32, y_min: u32, z_min: u32) -> Self {
+        BitSetDiscreteVoxelShape {
+            x_size: x_min,
+            y_size: y_min,
+            z_size: z_min,
+
+            storage: BitSet::new((x_min * y_min * z_min).try_into().unwrap()),
+            x_min,
+            y_min,
+            z_min,
+            x_max: 0,
+            y_max: 0,
+            z_max: 0,
+        }
+    }
+
+    // private void fillUpdateBounds(int var1, int var2, int var3, boolean var4) {
+    // 	this.storage.set(this.getIndex(var1, var2, var3));
+    // 	if (var4) {
+    // 	   this.xMin = Math.min(this.xMin, var1);
+    // 	   this.yMin = Math.min(this.yMin, var2);
+    // 	   this.zMin = Math.min(this.zMin, var3);
+    // 	   this.xMax = Math.max(this.xMax, var1 + 1);
+    // 	   this.yMax = Math.max(this.yMax, var2 + 1);
+    // 	   this.zMax = Math.max(this.zMax, var3 + 1);
+    // 	}
+    // }
+    fn fill_update_bounds(&mut self, x: u32, y: u32, z: u32, update: bool) {
+        self.storage.set(self.get_index(x, y, z));
+        if update {
+            self.x_min = std::cmp::min(self.x_min, x);
+            self.y_min = std::cmp::min(self.y_min, y);
+            self.z_min = std::cmp::min(self.z_min, z);
+            self.x_max = std::cmp::max(self.x_max, x + 1);
+            self.y_max = std::cmp::max(self.y_max, y + 1);
+            self.z_max = std::cmp::max(self.z_max, z + 1);
+        }
+    }
+
+    // public void fill(int var1, int var2, int var3) {
+    // 	this.fillUpdateBounds(var1, var2, var3, true);
+    // }
+    pub fn fill(&mut self, x: u32, y: u32, z: u32) {
+        self.fill_update_bounds(x, y, z, true);
+    }
+
+    // protected int getIndex(int var1, int var2, int var3) {
+    //     return (var1 * this.ySize + var2) * this.zSize + var3;
+    // }
+    fn get_index(&self, x: u32, y: u32, z: u32) -> usize {
+        ((x * self.y_size + y) * self.z_size + z) as usize
+    }
+}
+
+impl DiscreteVoxelShape for BitSetDiscreteVoxelShape {
+    fn size(&self, axis: Axis) -> u32 {
+        axis.choose(self.x_size, self.y_size, self.z_size)
+    }
+
+    fn first_full_x(&self) -> u32 {
+        self.x_min
+    }
+    fn first_full_y(&self) -> u32 {
+        self.y_min
+    }
+    fn first_full_z(&self) -> u32 {
+        self.z_min
+    }
+
+    fn last_full_x(&self) -> u32 {
+        self.x_max
+    }
+    fn last_full_y(&self) -> u32 {
+        self.y_max
+    }
+    fn last_full_z(&self) -> u32 {
+        self.z_max
+    }
+
+    fn clone(&self) -> Box<dyn DiscreteVoxelShape> {
+        Box::new(Clone::clone(self))
+    }
+
+    fn is_full(&self, x: u32, y: u32, z: u32) -> bool {
+        self.storage.index(self.get_index(x, y, z))
+    }
+}
diff --git a/azalea-physics/src/collision/mod.rs b/azalea-physics/src/collision/mod.rs
new file mode 100644
index 00000000..465698b2
--- /dev/null
+++ b/azalea-physics/src/collision/mod.rs
@@ -0,0 +1,273 @@
+mod dimension_collisions;
+mod discrete_voxel_shape;
+mod shape;
+
+use azalea_core::{Axis, PositionXYZ, Vec3, AABB, EPSILON};
+use azalea_world::entity::{EntityData, EntityMut};
+use azalea_world::{Dimension, MoveEntityError};
+use dimension_collisions::CollisionGetter;
+pub use discrete_voxel_shape::*;
+pub use shape::*;
+
+pub enum MoverType {
+    Own,
+    Player,
+    Piston,
+    ShulkerBox,
+    Shulker,
+}
+
+pub trait HasCollision {
+    fn collide(&self, movement: &Vec3, entity: &EntityData) -> Vec3;
+}
+
+pub trait MovableEntity {
+    fn move_colliding(
+        &mut self,
+        mover_type: &MoverType,
+        movement: &Vec3,
+    ) -> Result<(), MoveEntityError>;
+}
+
+impl HasCollision for Dimension {
+    // private Vec3 collide(Vec3 var1) {
+    //     AABB var2 = this.getBoundingBox();
+    //     List var3 = this.level.getEntityCollisions(this, var2.expandTowards(var1));
+    //     Vec3 var4 = var1.lengthSqr() == 0.0D ? var1 : collideBoundingBox(this, var1, var2, this.level, var3);
+    //     boolean var5 = var1.x != var4.x;
+    //     boolean var6 = var1.y != var4.y;
+    //     boolean var7 = var1.z != var4.z;
+    //     boolean var8 = this.onGround || var6 && var1.y < 0.0D;
+    //     if (this.maxUpStep > 0.0F && var8 && (var5 || var7)) {
+    //        Vec3 var9 = collideBoundingBox(this, new Vec3(var1.x, (double)this.maxUpStep, var1.z), var2, this.level, var3);
+    //        Vec3 var10 = collideBoundingBox(this, new Vec3(0.0D, (double)this.maxUpStep, 0.0D), var2.expandTowards(var1.x, 0.0D, var1.z), this.level, var3);
+    //        if (var10.y < (double)this.maxUpStep) {
+    //           Vec3 var11 = collideBoundingBox(this, new Vec3(var1.x, 0.0D, var1.z), var2.move(var10), this.level, var3).add(var10);
+    //           if (var11.horizontalDistanceSqr() > var9.horizontalDistanceSqr()) {
+    //              var9 = var11;
+    //           }
+    //        }
+
+    //        if (var9.horizontalDistanceSqr() > var4.horizontalDistanceSqr()) {
+    //           return var9.add(collideBoundingBox(this, new Vec3(0.0D, -var9.y + var1.y, 0.0D), var2.move(var9), this.level, var3));
+    //        }
+    //     }
+
+    //     return var4;
+    // }
+    fn collide(&self, movement: &Vec3, entity: &EntityData) -> Vec3 {
+        let entity_bounding_box = entity.bounding_box;
+        println!("collide: entity_bounding_box: {:?}", entity_bounding_box);
+        // TODO: get_entity_collisions
+        // let entity_collisions = dimension.get_entity_collisions(self, entity_bounding_box.expand_towards(movement));
+        let entity_collisions = Vec::new();
+        if movement.length_sqr() == 0.0 {
+            *movement
+        } else {
+            collide_bounding_box(
+                Some(entity),
+                movement,
+                &entity_bounding_box,
+                self,
+                entity_collisions,
+            )
+        }
+
+        // TODO: stepping (for stairs and stuff)
+
+        // collided_movement
+    }
+}
+
+impl MovableEntity for EntityMut<'_> {
+    /// Move an entity by a given delta, checking for collisions.
+    fn move_colliding(
+        &mut self,
+        _mover_type: &MoverType,
+        movement: &Vec3,
+    ) -> Result<(), MoveEntityError> {
+        // TODO: do all these
+
+        // if self.no_physics {
+        //     return;
+        // };
+
+        // if (var1 == MoverType.PISTON) {
+        //     var2 = this.limitPistonMovement(var2);
+        //     if (var2.equals(Vec3.ZERO)) {
+        //        return;
+        //     }
+        // }
+
+        // if (this.stuckSpeedMultiplier.lengthSqr() > 1.0E-7D) {
+        //     var2 = var2.multiply(this.stuckSpeedMultiplier);
+        //     this.stuckSpeedMultiplier = Vec3.ZERO;
+        //     this.setDeltaMovement(Vec3.ZERO);
+        // }
+
+        // movement = this.maybeBackOffFromEdge(movement, moverType);
+
+        println!("move_entity {:?}", movement);
+
+        let collide_result = { self.dimension.collide(movement, self) };
+
+        let move_distance = collide_result.length_sqr();
+
+        println!("move_entity move_distance: {}", move_distance);
+
+        if move_distance > EPSILON {
+            // TODO: fall damage
+
+            let new_pos = {
+                let entity_pos = self.pos();
+                Vec3 {
+                    x: entity_pos.x + collide_result.x,
+                    y: entity_pos.y + collide_result.y,
+                    z: entity_pos.z + collide_result.z,
+                }
+            };
+
+            self.dimension.set_entity_pos(self.id, new_pos)?;
+
+            println!("move_entity set_entity_pos {:?}", new_pos)
+        }
+
+        let x_collision = movement.x != collide_result.x;
+        let z_collision = movement.z != collide_result.z;
+        let horizontal_collision = x_collision || z_collision;
+        let vertical_collision = movement.y != collide_result.y;
+        let on_ground = vertical_collision && movement.y < 0.;
+        // self.on_ground = on_ground;
+
+        println!(
+            "move_entity {} {} {}",
+            x_collision, z_collision, vertical_collision
+        );
+
+        // TODO: minecraft checks for a "minor" horizontal collision here
+
+        let block_pos_below = { self.on_pos_legacy() };
+        let _block_state_below = self
+            .dimension
+            .get_block_state(&block_pos_below)
+            .expect("Couldn't get block state below");
+
+        println!("move_entity 4");
+        // self.check_fall_damage(collide_result.y, on_ground, block_state_below, block_pos_below);
+
+        // if self.isRemoved() { return; }
+
+        if horizontal_collision {
+            let delta_movement = &self.delta;
+            self.delta = Vec3 {
+                x: if x_collision { 0. } else { delta_movement.x },
+                y: delta_movement.y,
+                z: if z_collision { 0. } else { delta_movement.z },
+            }
+        }
+
+        if vertical_collision {
+            // blockBelow.updateEntityAfterFallOn(this.level, this);
+        }
+
+        if on_ground {
+            // blockBelow.stepOn(this.level, blockPosBelow, blockStateBelow, this);
+        }
+
+        // sounds
+
+        // this.tryCheckInsideBlocks();
+
+        // float var25 = this.getBlockSpeedFactor();
+        // this.setDeltaMovement(this.getDeltaMovement().multiply((double)var25, 1.0D, (double)var25));
+        // if (this.level.getBlockStatesIfLoaded(this.getBoundingBox().deflate(1.0E-6D)).noneMatch((var0) -> {
+        //    return var0.is(BlockTags.FIRE) || var0.is(Blocks.LAVA);
+        // })) {
+        //    if (this.remainingFireTicks <= 0) {
+        //       this.setRemainingFireTicks(-this.getFireImmuneTicks());
+        //    }
+
+        //    if (this.wasOnFire && (this.isInPowderSnow || this.isInWaterRainOrBubble())) {
+        //       this.playEntityOnFireExtinguishedSound();
+        //    }
+        // }
+
+        // if (this.isOnFire() && (this.isInPowderSnow || this.isInWaterRainOrBubble())) {
+        //    this.setRemainingFireTicks(-this.getFireImmuneTicks());
+        // }
+
+        println!("move_entity 5");
+
+        Ok(())
+    }
+}
+
+fn collide_bounding_box(
+    entity: Option<&EntityData>,
+    movement: &Vec3,
+    entity_bounding_box: &AABB,
+    dimension: &Dimension,
+    entity_collisions: Vec<Box<dyn VoxelShape>>,
+) -> Vec3 {
+    let mut collision_boxes: Vec<Box<dyn VoxelShape>> =
+        Vec::with_capacity(entity_collisions.len() + 1);
+
+    if !entity_collisions.is_empty() {
+        collision_boxes.extend(entity_collisions);
+    }
+
+    // TODO: world border
+
+    let block_collisions =
+        dimension.get_block_collisions(entity, entity_bounding_box.expand_towards(movement));
+    collision_boxes.extend(block_collisions);
+    collide_with_shapes(movement, *entity_bounding_box, &collision_boxes)
+}
+
+fn collide_with_shapes(
+    movement: &Vec3,
+    mut entity_box: AABB,
+    collision_boxes: &Vec<Box<dyn VoxelShape>>,
+) -> Vec3 {
+    if collision_boxes.is_empty() {
+        return *movement;
+    }
+
+    let mut x_movement = movement.x;
+    let mut y_movement = movement.y;
+    let mut z_movement = movement.z;
+    if y_movement != 0. {
+        y_movement = Shapes::collide(&Axis::Y, &entity_box, collision_boxes, y_movement);
+        if y_movement != 0. {
+            entity_box = entity_box.move_relative(0., y_movement, 0.);
+        }
+    }
+
+    // whether the player is moving more in the z axis than x
+    // this is done to fix a movement bug, minecraft does this too
+    let more_z_movement = x_movement.abs() < z_movement.abs();
+
+    if more_z_movement && z_movement != 0. {
+        z_movement = Shapes::collide(&Axis::Z, &entity_box, collision_boxes, z_movement);
+        if z_movement != 0. {
+            entity_box = entity_box.move_relative(0., 0., z_movement);
+        }
+    }
+
+    if x_movement != 0. {
+        x_movement = Shapes::collide(&Axis::X, &entity_box, collision_boxes, x_movement);
+        if x_movement != 0. {
+            entity_box = entity_box.move_relative(x_movement, 0., 0.);
+        }
+    }
+
+    if !more_z_movement && z_movement != 0. {
+        z_movement = Shapes::collide(&Axis::Z, &entity_box, collision_boxes, z_movement);
+    }
+
+    Vec3 {
+        x: x_movement,
+        y: y_movement,
+        z: z_movement,
+    }
+}
diff --git a/azalea-physics/src/collision/shape.rs b/azalea-physics/src/collision/shape.rs
new file mode 100644
index 00000000..45822d07
--- /dev/null
+++ b/azalea-physics/src/collision/shape.rs
@@ -0,0 +1,254 @@
+use crate::collision::{BitSetDiscreteVoxelShape, DiscreteVoxelShape, AABB};
+use azalea_core::{binary_search, Axis, AxisCycle, EPSILON};
+use std::cmp;
+
+pub struct Shapes {}
+
+pub fn block_shape() -> Box<dyn VoxelShape> {
+    let mut shape = BitSetDiscreteVoxelShape::new(1, 1, 1);
+    shape.fill(0, 0, 0);
+    Box::new(CubeVoxelShape::new(Box::new(shape)))
+}
+pub fn empty_shape() -> Box<dyn VoxelShape> {
+    Box::new(ArrayVoxelShape::new(
+        Box::new(BitSetDiscreteVoxelShape::new(0, 0, 0)),
+        vec![0.],
+        vec![0.],
+        vec![0.],
+    ))
+}
+
+impl Shapes {
+    pub fn collide(
+        axis: &Axis,
+        entity_box: &AABB,
+        collision_boxes: &Vec<Box<dyn VoxelShape>>,
+        mut movement: f64,
+    ) -> f64 {
+        for shape in collision_boxes {
+            if movement.abs() < EPSILON {
+                return 0.;
+            }
+            movement = shape.collide(axis, entity_box, movement);
+        }
+        movement
+    }
+}
+
+pub trait VoxelShape {
+    fn shape(&self) -> Box<dyn DiscreteVoxelShape>;
+
+    fn get_coords(&self, axis: Axis) -> Vec<f64>;
+
+    // TODO: optimization: should this be changed to return ArrayVoxelShape?
+    // i might change the implementation of empty_shape in the future so not 100% sure
+    fn move_relative(&self, x: f64, y: f64, z: f64) -> Box<dyn VoxelShape> {
+        if self.shape().is_empty() {
+            return empty_shape();
+        }
+
+        println!(
+            "making new voxel shape {:?} {:?} {:?}",
+            self.get_coords(Axis::X),
+            self.get_coords(Axis::Y),
+            self.get_coords(Axis::Z)
+        );
+
+        Box::new(ArrayVoxelShape::new(
+            self.shape(),
+            self.get_coords(Axis::X).iter().map(|c| c + x).collect(),
+            self.get_coords(Axis::Y).iter().map(|c| c + y).collect(),
+            self.get_coords(Axis::Z).iter().map(|c| c + z).collect(),
+        ))
+    }
+
+    fn get(&self, axis: Axis, index: usize) -> f64 {
+        self.get_coords(axis)[index]
+    }
+
+    fn find_index(&self, axis: Axis, coord: f64) -> u32 {
+        binary_search(0, self.shape().size(axis) + 1, &|t| {
+            coord < self.get(axis, t as usize)
+        }) - 1
+    }
+
+    fn collide(&self, axis: &Axis, entity_box: &AABB, movement: f64) -> f64 {
+        self.collide_x(AxisCycle::between(*axis, Axis::X), entity_box, movement)
+    }
+    fn collide_x(&self, axis_cycle: AxisCycle, entity_box: &AABB, mut movement: f64) -> f64 {
+        if self.shape().is_empty() {
+            return movement;
+        }
+        if movement.abs() < EPSILON {
+            return 0.;
+        }
+
+        let inverse_axis_cycle = axis_cycle.inverse();
+
+        // probably not good names but idk what this does
+        let x_axis = inverse_axis_cycle.cycle(Axis::X);
+        let y_axis = inverse_axis_cycle.cycle(Axis::Y);
+        let z_axis = inverse_axis_cycle.cycle(Axis::Z);
+
+        // i gave up on names at this point (these are the obfuscated names from fernflower)
+        let var9 = entity_box.max(&x_axis);
+        let var11 = entity_box.min(&x_axis);
+
+        let var13 = self.find_index(x_axis, var11 + EPSILON);
+        let var14 = self.find_index(x_axis, var9 - EPSILON);
+
+        let var15 = cmp::max(
+            0,
+            self.find_index(y_axis, entity_box.min(&y_axis) + EPSILON),
+        );
+        let var16 = cmp::min(
+            self.shape().size(y_axis),
+            self.find_index(y_axis, entity_box.max(&y_axis) - EPSILON) + 1,
+        );
+
+        let var17 = cmp::max(
+            0,
+            self.find_index(z_axis, entity_box.min(&z_axis) + EPSILON),
+        );
+        let var18 = cmp::min(
+            self.shape().size(z_axis),
+            self.find_index(z_axis, entity_box.max(&z_axis) - EPSILON) + 1,
+        );
+
+        let var19 = self.shape().size(x_axis);
+
+        if movement > 0. {
+            for var20 in var14 + 1..var19 {
+                for var21 in var15..var16 {
+                    for var22 in var17..var18 {
+                        if self.shape().is_full_wide_axis_cycle(
+                            inverse_axis_cycle,
+                            var20,
+                            var21,
+                            var22,
+                        ) {
+                            let var23 = self.get(x_axis, var20 as usize) - var9;
+                            if var23 >= -EPSILON {
+                                movement = f64::min(movement, var23);
+                            }
+                            return movement;
+                        }
+                    }
+                }
+            }
+        } else if movement < 0. {
+            for var20 in (var13 - 1)..=0 {
+                for var21 in var15..var16 {
+                    for var22 in var17..var18 {
+                        if self.shape().is_full_wide_axis_cycle(
+                            inverse_axis_cycle,
+                            var20,
+                            var21,
+                            var22,
+                        ) {
+                            let var23 = self.get(x_axis, (var20 + 1) as usize) - var11;
+                            if var23 <= EPSILON {
+                                movement = f64::max(movement, var23);
+                            }
+                            return movement;
+                        }
+                    }
+                }
+            }
+        }
+
+        movement
+    }
+}
+
+pub struct ArrayVoxelShape {
+    shape: Box<dyn DiscreteVoxelShape>,
+    // TODO: check where faces is used in minecraft
+    #[allow(dead_code)]
+    faces: Option<Vec<Box<dyn VoxelShape>>>,
+
+    pub xs: Vec<f64>,
+    pub ys: Vec<f64>,
+    pub zs: Vec<f64>,
+}
+
+pub struct CubeVoxelShape {
+    shape: Box<dyn DiscreteVoxelShape>,
+    // TODO: check where faces is used in minecraft
+    #[allow(dead_code)]
+    faces: Option<Vec<Box<dyn VoxelShape>>>,
+}
+
+impl ArrayVoxelShape {
+    pub fn new(
+        shape: Box<dyn DiscreteVoxelShape>,
+        xs: Vec<f64>,
+        ys: Vec<f64>,
+        zs: Vec<f64>,
+    ) -> Self {
+        let x_size = shape.size(Axis::X) + 1;
+        let y_size = shape.size(Axis::Y) + 1;
+        let z_size = shape.size(Axis::Z) + 1;
+
+        // Lengths of point arrays must be consistent with the size of the VoxelShape.
+        assert_eq!(x_size, xs.len() as u32);
+        assert_eq!(y_size, ys.len() as u32);
+        assert_eq!(z_size, zs.len() as u32);
+
+        Self {
+            faces: None,
+            shape,
+            xs,
+            ys,
+            zs,
+        }
+    }
+}
+
+impl CubeVoxelShape {
+    pub fn new(shape: Box<dyn DiscreteVoxelShape>) -> Self {
+        Self { shape, faces: None }
+    }
+}
+
+impl VoxelShape for ArrayVoxelShape {
+    fn shape(&self) -> Box<dyn DiscreteVoxelShape> {
+        self.shape.clone()
+    }
+
+    fn get_coords(&self, axis: Axis) -> Vec<f64> {
+        axis.choose(self.xs.clone(), self.ys.clone(), self.zs.clone())
+    }
+}
+
+impl VoxelShape for CubeVoxelShape {
+    fn shape(&self) -> Box<dyn DiscreteVoxelShape> {
+        self.shape.clone()
+    }
+
+    fn get_coords(&self, axis: Axis) -> Vec<f64> {
+        let size = self.shape.size(axis);
+        let mut parts = Vec::with_capacity(size as usize);
+        for i in 0..=size {
+            parts.push(i as f64 / size as f64);
+        }
+        parts
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_block_shape() {
+        let shape = block_shape();
+        assert_eq!(shape.shape().size(Axis::X), 1);
+        assert_eq!(shape.shape().size(Axis::Y), 1);
+        assert_eq!(shape.shape().size(Axis::Z), 1);
+
+        assert_eq!(shape.get_coords(Axis::X).len(), 2);
+        assert_eq!(shape.get_coords(Axis::Y).len(), 2);
+        assert_eq!(shape.get_coords(Axis::Z).len(), 2);
+    }
+}
diff --git a/azalea-physics/src/lib.rs b/azalea-physics/src/lib.rs
new file mode 100644
index 00000000..8842727b
--- /dev/null
+++ b/azalea-physics/src/lib.rs
@@ -0,0 +1,127 @@
+pub mod collision;
+
+use azalea_block::Block;
+use azalea_core::{BlockPos, Vec3};
+use azalea_world::entity::{EntityData, EntityMut};
+use collision::{MovableEntity, MoverType};
+
+pub trait HasPhysics {
+    fn travel(&mut self, acceleration: &Vec3);
+    fn ai_step(&mut self);
+}
+
+impl HasPhysics for EntityMut<'_> {
+    /// Move the entity with the given acceleration while handling friction,
+    /// gravity, collisions, and some other stuff.
+    fn travel(&mut self, acceleration: &Vec3) {
+        // if !self.is_effective_ai() && !self.is_controlled_by_local_instance() {
+        //     // this.calculateEntityAnimation(this, this instanceof FlyingAnimal);
+        //     return;
+        // }
+
+        let gravity: f64 = 0.08;
+
+        // TODO: slow falling effect
+        // let is_falling = self.delta.y <= 0.;
+
+        // TODO: fluids
+
+        // TODO: elytra
+
+        let block_pos_below = get_block_pos_below_that_affects_movement(self);
+        let block_friction =
+            if let Some(block_state_below) = self.dimension.get_block_state(&block_pos_below) {
+                let block_below: Box<dyn Block> = block_state_below.into();
+                block_below.behavior().friction
+            } else {
+                unreachable!("Block below should be a real block.")
+            };
+
+        let inertia = if self.on_ground {
+            block_friction * 0.91
+        } else {
+            0.91
+        };
+        let mut movement =
+            handle_relative_friction_and_calculate_movement(self, acceleration, block_friction);
+
+        movement.y -= gravity;
+
+        // if (this.shouldDiscardFriction()) {
+        //     this.setDeltaMovement(movement.x, yMovement, movement.z);
+        // } else {
+        //     this.setDeltaMovement(movement.x * (double)inertia, yMovement * 0.9800000190734863D, movement.z * (double)inertia);
+        // }
+
+        // if should_discard_friction(self) {
+        if false {
+            self.delta = movement;
+        } else {
+            self.delta = Vec3 {
+                x: movement.x * inertia as f64,
+                y: movement.y * 0.98f64,
+                z: movement.z * inertia as f64,
+            };
+        }
+    }
+
+    /// applies air resistance, calls self.travel(), and some other random
+    /// stuff.
+    fn ai_step(&mut self) {
+        // vanilla does movement interpolation here, doesn't really matter much for a bot though
+
+        self.xxa *= 0.98;
+        self.zza *= 0.98;
+
+        self.travel(&Vec3 {
+            x: self.xxa as f64,
+            y: self.yya as f64,
+            z: self.zza as f64,
+        });
+        // freezing
+        // pushEntities
+        // drowning damage
+    }
+}
+
+fn get_block_pos_below_that_affects_movement(entity: &EntityData) -> BlockPos {
+    BlockPos::new(
+        entity.pos().x as i32,
+        // TODO: this uses bounding_box.min_y instead of position.y
+        (entity.pos().y - 0.5f64) as i32,
+        entity.pos().z as i32,
+    )
+}
+
+fn handle_relative_friction_and_calculate_movement(
+    entity: &mut EntityMut,
+    acceleration: &Vec3,
+    block_friction: f32,
+) -> Vec3 {
+    entity.move_relative(get_speed(&*entity, block_friction), acceleration);
+    // entity.delta = entity.handle_on_climbable(entity.delta);
+    entity
+        .move_colliding(&MoverType::Own, &entity.delta.clone())
+        .expect("Entity should exist.");
+    // let delta_movement = entity.delta;
+    //   if ((entity.horizontalCollision || entity.jumping) && (entity.onClimbable() || entity.getFeetBlockState().is(Blocks.POWDER_SNOW) && PowderSnowBlock.canEntityWalkOnPowderSnow(entity))) {
+    //      var3 = new Vec3(var3.x, 0.2D, var3.z);
+    //   }
+    // TODO: powdered snow
+
+    entity.delta
+}
+
+// private float getFrictionInfluencedSpeed(float friction) {
+//     return this.onGround ? this.getSpeed() * (0.21600002F / (friction * friction * friction)) : this.flyingSpeed;
+// }
+fn get_speed(entity: &EntityData, friction: f32) -> f32 {
+    // TODO: have speed & flying_speed fields in entity
+    if entity.on_ground {
+        let speed: f32 = 0.7;
+        speed * (0.216f32 / (friction * friction * friction))
+    } else {
+        // entity.flying_speed
+        0.02
+    }
+}