veloren_common_systems/phys/
collision.rs

1use common::{
2    comp::{
3        CharacterState, Collider, Mass, Ori, PhysicsState, Pos, PreviousPhysCache, Scale, Vel,
4        body::ship::figuredata::VoxelCollider,
5        fluid_dynamics::{Fluid, LiquidKind},
6    },
7    consts::FRIC_GROUND,
8    outcome::Outcome,
9    resources::DeltaTime,
10    terrain::{Block, BlockKind},
11    uid::Uid,
12    vol::{BaseVol, ReadVol},
13};
14use specs::Entity;
15use std::ops::Range;
16use vek::*;
17
18use super::PhysicsRead;
19
20#[expect(clippy::too_many_lines)]
21pub(super) fn box_voxel_collision<T: BaseVol<Vox = Block> + ReadVol>(
22    cylinder: (f32, f32, f32), // effective collision cylinder
23    terrain: &T,
24    entity: Entity,
25    pos: &mut Pos,
26    tgt_pos: Vec3<f32>,
27    vel: &mut Vel,
28    physics_state: &mut PhysicsState,
29    dt: &DeltaTime,
30    was_on_ground: bool,
31    block_snap: bool,
32    climbing: bool,
33    mut land_on_ground: impl FnMut(Entity, Vel, Vec3<f32>),
34    read: &PhysicsRead,
35    ori: &Ori,
36    // Get the proportion of surface friction that should be applied based on the current velocity
37    friction_factor: impl Fn(Vec3<f32>) -> f32,
38) {
39    // We cap out scale at 10.0 to prevent an enormous amount of lag
40    let scale = read.scales.get(entity).map_or(1.0, |s| s.0.min(10.0));
41
42    //prof_span!("box_voxel_collision");
43
44    // Convience function to compute the player aabb
45    fn player_aabb(pos: Vec3<f32>, radius: f32, z_range: Range<f32>) -> Aabb<f32> {
46        Aabb {
47            min: pos + Vec3::new(-radius, -radius, z_range.start),
48            max: pos + Vec3::new(radius, radius, z_range.end),
49        }
50    }
51
52    // Convience function to translate the near_aabb into the world space
53    fn move_aabb(aabb: Aabb<i32>, pos: Vec3<f32>) -> Aabb<i32> {
54        Aabb {
55            min: aabb.min + pos.map(|e| e.floor() as i32),
56            max: aabb.max + pos.map(|e| e.floor() as i32),
57        }
58    }
59
60    // Function for determining whether the player at a specific position collides
61    // with blocks with the given criteria
62    fn collision_with<T: BaseVol<Vox = Block> + ReadVol>(
63        pos: Vec3<f32>,
64        terrain: &T,
65        near_aabb: Aabb<i32>,
66        radius: f32,
67        z_range: Range<f32>,
68        move_dir: Vec3<f32>,
69    ) -> bool {
70        let player_aabb = player_aabb(pos, radius, z_range);
71
72        // Calculate the world space near aabb
73        let near_aabb = move_aabb(near_aabb, pos);
74
75        let mut collision = false;
76        // TODO: could short-circuit here
77        terrain.for_each_in(near_aabb, |block_pos, block| {
78            if block.is_solid() {
79                let block_aabb = Aabb {
80                    min: block_pos.map(|e| e as f32),
81                    max: block_pos.map(|e| e as f32) + Vec3::new(1.0, 1.0, block.solid_height()),
82                };
83                if player_aabb.collides_with_aabb(block_aabb)
84                    && block.valid_collision_dir(player_aabb, block_aabb, move_dir)
85                {
86                    collision = true;
87                }
88            }
89        });
90
91        collision
92    }
93
94    let (radius, z_min, z_max) = (Vec3::from(cylinder) * scale).into_tuple();
95
96    // Probe distances
97    let hdist = radius.ceil() as i32;
98
99    // Neighbouring blocks Aabb
100    let near_aabb = Aabb {
101        min: Vec3::new(
102            -hdist,
103            -hdist,
104            1 - Block::MAX_HEIGHT.ceil() as i32 + z_min.floor() as i32,
105        ),
106        max: Vec3::new(hdist, hdist, z_max.ceil() as i32),
107    };
108
109    let z_range = z_min..z_max;
110
111    // Setup values for the loop below
112    physics_state.on_ground = None;
113    physics_state.on_ceiling = false;
114
115    let mut on_ground = None::<Block>;
116    let mut on_ceiling = false;
117    // Don't loop infinitely here
118    let mut attempts = 0;
119
120    let mut pos_delta = tgt_pos - pos.0;
121
122    // Don't jump too far at once
123    const MAX_INCREMENTS: usize = 100; // The maximum number of collision tests per tick
124    let min_step = (radius / 2.0).min(z_max - z_min).clamped(0.01, 0.3);
125    let increments = ((pos_delta.map(|e| e.abs()).reduce_partial_max() / min_step).ceil() as usize)
126        .clamped(1, MAX_INCREMENTS);
127    let old_pos = pos.0;
128    for _ in 0..increments {
129        //prof_span!("increment");
130        const MAX_ATTEMPTS: usize = 16;
131        pos.0 += pos_delta / increments as f32;
132
133        let vel2 = *vel;
134        let try_colliding_block = |pos: &Pos| {
135            //prof_span!("most colliding check");
136            // Calculate the player's AABB
137            let player_aabb = player_aabb(pos.0, radius, z_range.clone());
138
139            // Determine the block that we are colliding with most
140            // (based on minimum collision axis)
141            // (if we are colliding with one)
142            let mut most_colliding = None;
143            // Calculate the world space near aabb
144            let near_aabb = move_aabb(near_aabb, pos.0);
145            let player_overlap = |block_aabb: Aabb<f32>| {
146                (block_aabb.center() - player_aabb.center() - Vec3::unit_z() * 0.5)
147                    .map(f32::abs)
148                    .sum()
149            };
150
151            terrain.for_each_in(near_aabb, |block_pos, block| {
152                // Make sure the block is actually solid
153                if block.is_solid() {
154                    // Calculate block AABB
155                    let block_aabb = Aabb {
156                        min: block_pos.map(|e| e as f32),
157                        max: block_pos.map(|e| e as f32)
158                            + Vec3::new(1.0, 1.0, block.solid_height()),
159                    };
160
161                    // Determine whether the block's AABB collides with the player's AABB
162                    if player_aabb.collides_with_aabb(block_aabb)
163                        && block.valid_collision_dir(player_aabb, block_aabb, vel2.0)
164                    {
165                        match &most_colliding {
166                            // Select the minimum of the value from `player_overlap`
167                            Some((_, other_block_aabb, _))
168                                if player_overlap(block_aabb)
169                                    >= player_overlap(*other_block_aabb) => {},
170                            _ => most_colliding = Some((block_pos, block_aabb, block)),
171                        }
172                    }
173                }
174            });
175
176            most_colliding
177        };
178
179        // While the player is colliding with the terrain...
180        while let Some((_block_pos, block_aabb, block)) = (attempts < MAX_ATTEMPTS)
181            .then(|| try_colliding_block(pos))
182            .flatten()
183        {
184            // Calculate the player's AABB
185            let player_aabb = player_aabb(pos.0, radius, z_range.clone());
186
187            // Find the intrusion vector of the collision
188            let dir = player_aabb.collision_vector_with_aabb(block_aabb);
189
190            // Determine an appropriate resolution vector (i.e: the minimum distance
191            // needed to push out of the block)
192            let max_axis = dir.map(|e| e.abs()).reduce_partial_min();
193            let resolve_dir = -dir.map(|e| {
194                if e.abs().to_bits() == max_axis.to_bits() {
195                    e
196                } else {
197                    0.0
198                }
199            });
200
201            // When the resolution direction is pointing upwards, we must be on the
202            // ground
203            /* if resolve_dir.z > 0.0 && vel.0.z <= 0.0 { */
204            if resolve_dir.z > 0.0 {
205                on_ground = Some(block);
206            } else if resolve_dir.z < 0.0 && vel.0.z >= 0.0 {
207                on_ceiling = true;
208            }
209
210            // When the resolution direction is non-vertical, we must be colliding
211            // with a wall
212            //
213            // If we're being pushed out horizontally...
214            if resolve_dir.z == 0.0
215            // ...and the vertical resolution direction is sufficiently great...
216            && dir.z < -0.1
217            // ...and the space above is free...
218            && {
219                //prof_span!("space above free");
220                !collision_with(
221                    Vec3::new(pos.0.x, pos.0.y, (pos.0.z + 0.1).ceil()),
222                    &terrain,
223                    near_aabb,
224                    radius,
225                    z_range.clone(),
226                    vel.0,
227                )
228            }
229            // ...and there is a collision with a block beneath our current hitbox...
230            && {
231                //prof_span!("collision beneath");
232                collision_with(
233                    pos.0 + resolve_dir - Vec3::unit_z() * 1.25,
234                    &terrain,
235                    near_aabb,
236                    radius,
237                    z_range.clone(),
238                    vel.0,
239                )
240            } {
241                // ...block-hop!
242                pos.0.z = pos.0.z.max(block_aabb.max.z);
243
244                // Apply fall damage, in the vertical axis, and correct velocity
245                land_on_ground(entity, *vel, Vec3::unit_z());
246                vel.0.z = vel.0.z.max(0.0);
247
248                // Push the character on to the block very slightly
249                // to avoid jitter due to imprecision
250                if (vel.0 * resolve_dir).xy().magnitude_squared() < 1.0_f32.powi(2) {
251                    pos.0 -= resolve_dir.normalized() * 0.05;
252                }
253                on_ground = Some(block);
254                break;
255            }
256
257            // If not, correct the velocity, applying collision damage as we do
258            if resolve_dir.magnitude_squared() > 0.0 {
259                land_on_ground(entity, *vel, resolve_dir.normalized());
260            }
261            vel.0 = vel.0.map2(
262                resolve_dir,
263                |e, d| {
264                    if d * e.signum() < 0.0 { 0.0 } else { e }
265                },
266            );
267
268            pos_delta *= resolve_dir.map(|e| if e == 0.0 { 1.0 } else { 0.0 });
269
270            // Resolve the collision normally
271            pos.0 += resolve_dir;
272
273            attempts += 1;
274        }
275
276        if attempts == MAX_ATTEMPTS {
277            vel.0 = Vec3::zero();
278            pos.0 = old_pos;
279            break;
280        }
281    }
282
283    // Report on_ceiling state
284    if on_ceiling {
285        physics_state.on_ceiling = true;
286    }
287
288    if on_ground.is_some() {
289        physics_state.on_ground = on_ground;
290    // If the space below us is free, then "snap" to the ground
291    } else if vel.0.z <= 0.0
292        && was_on_ground
293        && block_snap
294        && physics_state.in_liquid().is_none()
295        && {
296            //prof_span!("snap check");
297            collision_with(
298                pos.0 - Vec3::unit_z() * 1.1,
299                &terrain,
300                near_aabb,
301                radius,
302                z_range.clone(),
303                vel.0,
304            )
305        }
306    {
307        //prof_span!("snap!!");
308        let snap_height = terrain
309            .get(Vec3::new(pos.0.x, pos.0.y, pos.0.z - 0.1).map(|e| e.floor() as i32))
310            .ok()
311            .filter(|block| block.is_solid())
312            .map_or(0.0, Block::solid_height);
313        vel.0.z = 0.0;
314        pos.0.z = (pos.0.z - 0.1).floor() + snap_height;
315        physics_state.on_ground = terrain
316            .get(Vec3::new(pos.0.x, pos.0.y, pos.0.z - 0.01).map(|e| e.floor() as i32))
317            .ok()
318            .copied();
319    }
320
321    // Find liquid immersion and wall collision all in one round of iteration
322    let player_aabb = player_aabb(pos.0, radius, z_range.clone());
323    // Calculate the world space near_aabb
324    let near_aabb = move_aabb(near_aabb, pos.0);
325
326    let dirs = [
327        Vec3::unit_x(),
328        Vec3::unit_y(),
329        -Vec3::unit_x(),
330        -Vec3::unit_y(),
331    ];
332
333    // Compute a list of aabbs to check for collision with nearby walls
334    let player_wall_aabbs = dirs.map(|dir| {
335        let pos = pos.0 + dir * 0.01;
336        Aabb {
337            min: pos + Vec3::new(-radius, -radius, z_range.start),
338            max: pos + Vec3::new(radius, radius, z_range.end),
339        }
340    });
341
342    let mut liquid = None::<(LiquidKind, f32)>;
343    let mut wall_dir_collisions = [false; 4];
344    //prof_span!(guard, "liquid/walls");
345    terrain.for_each_in(near_aabb, |block_pos, block| {
346        // Check for liquid blocks
347        if let Some(block_liquid) = block.liquid_kind() {
348            let liquid_aabb = Aabb {
349                min: block_pos.map(|e| e as f32),
350                // The liquid part of a liquid block always extends 1 block high.
351                max: block_pos.map(|e| e as f32) + Vec3::one(),
352            };
353            if player_aabb.collides_with_aabb(liquid_aabb) {
354                liquid = match liquid {
355                    Some((kind, max_liquid_z)) => Some((
356                        // TODO: merging of liquid kinds and max_liquid_z are done
357                        // independently which allows mix and
358                        // matching them
359                        kind.merge(block_liquid),
360                        max_liquid_z.max(liquid_aabb.max.z),
361                    )),
362                    None => Some((block_liquid, liquid_aabb.max.z)),
363                };
364            }
365        }
366
367        // Check for walls
368        if block.is_solid() {
369            let block_aabb = Aabb {
370                min: block_pos.map(|e| e as f32),
371                max: block_pos.map(|e| e as f32) + Vec3::new(1.0, 1.0, block.solid_height()),
372            };
373
374            for dir in 0..4 {
375                if player_wall_aabbs[dir].collides_with_aabb(block_aabb)
376                    && block.valid_collision_dir(player_wall_aabbs[dir], block_aabb, vel.0)
377                {
378                    wall_dir_collisions[dir] = true;
379                }
380            }
381        }
382    });
383    //drop(guard);
384
385    // Use wall collision results to determine if we are against a wall
386    let mut on_wall = None;
387    for dir in 0..4 {
388        if wall_dir_collisions[dir] {
389            on_wall = Some(match on_wall {
390                Some(acc) => acc + dirs[dir],
391                None => dirs[dir],
392            });
393        }
394    }
395
396    physics_state.on_wall = on_wall;
397    let fric_mod = read.stats.get(entity).map_or(1.0, |s| s.friction_modifier);
398
399    physics_state.in_fluid = liquid
400        .map(|(kind, max_z)| {
401            // NOTE: assumes min_z == 0.0
402            let depth = max_z - pos.0.z;
403
404            // This is suboptimal because it doesn't check for true depth,
405            // so it can cause problems for situations like swimming down
406            // a river and spawning or teleporting in(/to) water
407            let new_depth = physics_state.in_liquid().map_or(depth, |old_depth| {
408                (old_depth + old_pos.z - pos.0.z).max(depth)
409            });
410
411            // TODO: Change this at some point to allow entities to be moved by liquids?
412            let vel = Vel::zero();
413
414            if depth > 0.0 {
415                physics_state.ground_vel = vel.0;
416            }
417
418            Fluid::Liquid {
419                kind,
420                depth: new_depth,
421                vel,
422            }
423        })
424        .or_else(|| match physics_state.in_fluid {
425            Some(Fluid::Liquid { .. }) | None => Some(Fluid::Air {
426                elevation: pos.0.z,
427                vel: Vel::default(),
428            }),
429            fluid => fluid,
430        });
431
432    // skating (ski)
433    if !vel.0.xy().is_approx_zero()
434        && physics_state
435            .on_ground
436            .is_some_and(|g| physics_state.footwear.can_skate_on(g.kind()))
437    {
438        const DT_SCALE: f32 = 1.0; // other areas use 60.0???
439        const POTENTIAL_TO_KINETIC: f32 = 8.0; // * 2.0 * GRAVITY;
440
441        let kind = physics_state.on_ground.map_or(BlockKind::Air, |g| g.kind());
442        let (longitudinal_friction, lateral_friction) = physics_state.footwear.get_friction(kind);
443        // the amount of longitudinal speed preserved
444        let longitudinal_friction_factor_squared =
445            (1.0 - longitudinal_friction).powf(dt.0 * DT_SCALE * 2.0);
446        let lateral_friction_factor = (1.0 - lateral_friction).powf(dt.0 * DT_SCALE);
447        let groundplane_velocity = vel.0.xy();
448        let mut longitudinal_dir = ori.look_vec().xy();
449        if longitudinal_dir.is_approx_zero() {
450            // fall back to travelling dir (in case we look up)
451            longitudinal_dir = groundplane_velocity;
452        }
453        let longitudinal_dir = longitudinal_dir.normalized();
454        let lateral_dir = Vec2::new(longitudinal_dir.y, -longitudinal_dir.x);
455        let squared_velocity = groundplane_velocity.magnitude_squared();
456        // if we crossed an edge up or down accelerate in travelling direction,
457        // as potential energy is converted into kinetic energy we compare it with the
458        // square of velocity
459        let vertical_difference = physics_state.skating_last_height - pos.0.z;
460        // might become negative when skating slowly uphill
461        let height_factor_squared = if vertical_difference != 0.0 {
462            // E=½mv², we scale both energies by ½m
463            let kinetic = squared_velocity;
464            // positive accelerate, negative decelerate, ΔE=mgΔh
465            let delta_potential = vertical_difference.clamp(-1.0, 2.0) * POTENTIAL_TO_KINETIC;
466            let new_energy = kinetic + delta_potential;
467            physics_state.skating_last_height = pos.0.z;
468            new_energy / kinetic
469        } else {
470            1.0
471        };
472
473        // we calculate these squared as we need to combined them Euclidianly anyway,
474        // skiing: separate speed into longitudinal and lateral component
475        let long_speed = groundplane_velocity.dot(longitudinal_dir);
476        let lat_speed = groundplane_velocity.dot(lateral_dir);
477        let long_speed_squared = long_speed.powi(2);
478
479        // lateral speed is reduced by lateral_friction,
480        let new_lateral = lat_speed * lateral_friction_factor;
481        let lateral_speed_reduction = lat_speed - new_lateral;
482        // we convert this reduction partically (by the cosine of the angle) into
483        // longitudinal (elastic collision) and the remainder into heat
484        let cosine_squared_aoa = long_speed_squared / squared_velocity;
485        let converted_lateral_squared = cosine_squared_aoa * lateral_speed_reduction.powi(2);
486        let new_longitudinal_squared = longitudinal_friction_factor_squared
487            * (long_speed_squared + converted_lateral_squared)
488            * height_factor_squared;
489        let new_longitudinal =
490            new_longitudinal_squared.signum() * new_longitudinal_squared.abs().sqrt();
491        let new_ground_speed = new_longitudinal * longitudinal_dir + new_lateral * lateral_dir;
492        physics_state.skating_active = true;
493        vel.0 = Vec3::new(new_ground_speed.x, new_ground_speed.y, 0.0);
494    } else {
495        let ground_fric = if physics_state.in_liquid().is_some() {
496            // HACK:
497            // If we're in a liquid, radically reduce ground friction (i.e: assume that
498            // contact force is negligible due to buoyancy) Note that this might
499            // not be realistic for very dense entities (currently no entities in Veloren
500            // are sufficiently negatively buoyant for this to matter). We
501            // should really make friction be proportional to net downward force, but
502            // that means taking into account buoyancy which is a bit difficult to do here
503            // for now.
504            0.1
505        } else {
506            1.0
507        } * physics_state
508            .on_ground
509            .map(|b| b.get_friction())
510            .unwrap_or(0.0)
511            * friction_factor(vel.0);
512        let wall_fric = if physics_state.on_wall.is_some() && climbing {
513            FRIC_GROUND
514        } else {
515            0.0
516        };
517        let fric = ground_fric.max(wall_fric);
518        if fric > 0.0 {
519            vel.0 *= (1.0 - fric.min(1.0) * fric_mod).powf(dt.0 * 60.0);
520            physics_state.ground_vel = Vec3::zero();
521        }
522        physics_state.skating_active = false;
523    }
524}
525
526pub(super) fn point_voxel_collision(
527    entity: Entity,
528    pos: &mut Pos,
529    pos_delta: Vec3<f32>,
530    vel: &mut Vel,
531    physics_state: &mut PhysicsState,
532    sticky: bool,
533    outcomes: &mut Vec<Outcome>,
534    read: &PhysicsRead,
535) {
536    // TODO: If the velocity is exactly 0,
537    // a raycast may not pick up the current block.
538    //
539    // Handle this.
540    let (dist, block) = if let Some(block) = read
541        .terrain
542        .get(pos.0.map(|e| e.floor() as i32))
543        .ok()
544        .filter(|b| b.is_solid())
545    {
546        (0.0, Some(block))
547    } else {
548        let (dist, block) = read
549            .terrain
550            .ray(pos.0, pos.0 + pos_delta)
551            .until(|block: &Block| block.is_solid())
552            .ignore_error()
553            .cast();
554        // Can't fail since we do ignore_error above
555        (dist, block.unwrap())
556    };
557
558    pos.0 += pos_delta.try_normalized().unwrap_or_else(Vec3::zero) * dist;
559
560    // TODO: Not all projectiles should count as sticky!
561    if sticky
562        && let Some((projectile, body)) = read
563            .projectiles
564            .get(entity)
565            .filter(|_| vel.0.magnitude_squared() > 1.0 && block.is_some())
566            .zip(read.bodies.get(entity).copied())
567    {
568        outcomes.push(Outcome::ProjectileHit {
569            pos: pos.0 + pos_delta * dist,
570            body,
571            vel: vel.0,
572            source: projectile.owner,
573            target: None,
574        });
575    }
576
577    if block.is_some() {
578        let block_center = pos.0.map(|e| e.floor()) + 0.5;
579        let block_rpos = (pos.0 - block_center)
580            .try_normalized()
581            .unwrap_or_else(Vec3::zero);
582
583        // See whether we're on the top/bottom of a block,
584        // or the side
585        if block_rpos.z.abs() > block_rpos.xy().map(|e| e.abs()).reduce_partial_max() {
586            if block_rpos.z > 0.0 {
587                physics_state.on_ground = block.copied();
588            } else {
589                physics_state.on_ceiling = true;
590            }
591            vel.0.z = 0.0;
592        } else {
593            physics_state.on_wall = Some(if block_rpos.x.abs() > block_rpos.y.abs() {
594                vel.0.x = 0.0;
595                Vec3::unit_x() * -block_rpos.x.signum()
596            } else {
597                vel.0.y = 0.0;
598                Vec3::unit_y() * -block_rpos.y.signum()
599            });
600        }
601
602        // Sticky things shouldn't move
603        if sticky {
604            vel.0 = physics_state.ground_vel;
605        }
606    }
607
608    physics_state.in_fluid = read
609        .terrain
610        .get(pos.0.map(|e| e.floor() as i32))
611        .ok()
612        .and_then(|vox| {
613            vox.liquid_kind().map(|kind| Fluid::Liquid {
614                kind,
615                depth: 1.0,
616                vel: Vel::zero(),
617            })
618        })
619        .or_else(|| match physics_state.in_fluid {
620            Some(Fluid::Liquid { .. }) | None => Some(Fluid::Air {
621                elevation: pos.0.z,
622                vel: Vel::default(),
623            }),
624            fluid => fluid,
625        });
626}
627
628pub(super) fn voxel_collider_bounding_sphere(
629    voxel_collider: &VoxelCollider,
630    pos: &Pos,
631    ori: &Ori,
632    scale: Option<&Scale>,
633) -> Sphere<f32, f32> {
634    let origin_offset = voxel_collider.translation;
635    use common::vol::SizedVol;
636    let lower_bound = voxel_collider.volume().lower_bound().map(|e| e as f32);
637    let upper_bound = voxel_collider.volume().upper_bound().map(|e| e as f32);
638    let center = (lower_bound + upper_bound) / 2.0;
639    // Compute vector from the origin (where pos value corresponds to) and the model
640    // center
641    let center_offset = center + origin_offset;
642    // Rotate
643    let oriented_center_offset = ori.local_to_global(center_offset);
644    // Add to pos to get world coordinates of the center
645    let wpos_center = oriented_center_offset + pos.0;
646
647    // Note: to not get too fine grained we use a 2D grid for now
648    const SPRITE_AND_MAYBE_OTHER_THINGS: f32 = 4.0;
649    let radius = ((upper_bound - lower_bound) / 2.0
650        + Vec3::broadcast(SPRITE_AND_MAYBE_OTHER_THINGS))
651    .magnitude();
652
653    Sphere {
654        center: wpos_center,
655        radius: radius * scale.map_or(1.0, |s| s.0),
656    }
657}
658
659pub(super) struct ColliderData<'a> {
660    pub pos: &'a Pos,
661    pub previous_cache: &'a PreviousPhysCache,
662    pub z_limits: (f32, f32),
663    pub collider: &'a Collider,
664    pub mass: Mass,
665}
666
667/// Returns whether interesction between entities occured
668#[expect(clippy::too_many_arguments)]
669pub(super) fn resolve_e2e_collision(
670    // utility variables for our entity
671    collision_registered: &mut bool,
672    entity_entity_collisions: &mut u64,
673    factor: f32,
674    physics: &mut PhysicsState,
675    char_state_maybe: Option<&CharacterState>,
676    vel_delta: &mut Vec3<f32>,
677    step_delta: f32,
678    // physics flags
679    is_mid_air: bool,
680    is_sticky: bool,
681    is_immovable: bool,
682    is_projectile: bool,
683    // entity we colliding with
684    other: Uid,
685    // symetrical collider context
686    our_data: ColliderData,
687    other_data: ColliderData,
688    vel: &Vel,
689    is_riding: bool,
690) -> bool {
691    // Find the distance betwen our collider and
692    // collider we collide with and get vector of pushback.
693    //
694    // If we aren't colliding, just skip step.
695
696    // Get positions
697    let pos = our_data.pos.0 + our_data.previous_cache.velocity_dt * factor;
698    let pos_other = other_data.pos.0 + other_data.previous_cache.velocity_dt * factor;
699
700    // Compare Z ranges
701    let (z_min, z_max) = our_data.z_limits;
702    let ceiling = pos.z + z_max * our_data.previous_cache.scale;
703    let floor = pos.z + z_min * our_data.previous_cache.scale;
704
705    let (z_min_other, z_max_other) = other_data.z_limits;
706    let ceiling_other = pos_other.z + z_max_other * other_data.previous_cache.scale;
707    let floor_other = pos_other.z + z_min_other * other_data.previous_cache.scale;
708
709    let in_z_range = ceiling >= floor_other && floor <= ceiling_other;
710
711    if !in_z_range {
712        return false;
713    }
714
715    let ours = ColliderContext {
716        pos,
717        previous_cache: our_data.previous_cache,
718    };
719    let theirs = ColliderContext {
720        pos: pos_other,
721        previous_cache: other_data.previous_cache,
722    };
723    let (diff, collision_dist) = projection_between(ours, theirs);
724    let in_collision_range = diff.magnitude_squared() <= collision_dist.powi(2);
725
726    if !in_collision_range {
727        return false;
728    }
729
730    // If entities have not yet collided this tick (but just did) and if entity
731    // is either in mid air or is not sticky, then mark them as colliding with
732    // the other entity.
733    if !*collision_registered && (is_mid_air || !is_sticky) {
734        physics.touch_entities.insert(other, pos);
735        *entity_entity_collisions += 1;
736    }
737
738    // Don't apply e2e pushback to entities that are in a forced movement state
739    // (e.g. roll, leapmelee).
740    //
741    // This allows leaps to work properly (since you won't get pushed away
742    // before delivering the hit), and allows rolling through an enemy when
743    // trapped (e.g. with minotaur).
744    //
745    // This allows using e2e pushback to gain speed by jumping out of a roll
746    // while in the middle of a collider, this is an intentional combat mechanic.
747    let forced_movement =
748        matches!(char_state_maybe, Some(cs) if cs.is_forced_movement()) || is_riding;
749
750    // Don't apply repulsive force to projectiles,
751    // or if we're colliding with a terrain-like entity,
752    // or if we are a terrain-like entity.
753    //
754    // Don't apply force when entity is immovable, or a sticky which is on the
755    // ground (or on the wall).
756    if !forced_movement
757        && (!is_sticky || is_mid_air)
758        && diff.magnitude_squared() > 0.0
759        && !is_projectile
760        && !is_immovable
761        && !other_data.collider.is_voxel()
762        && !our_data.collider.is_voxel()
763    {
764        const ELASTIC_FORCE_COEFFICIENT: f32 = 400.0;
765        let mass_coefficient = other_data.mass.0 / (our_data.mass.0 + other_data.mass.0);
766        let distance_coefficient = collision_dist - diff.magnitude();
767        let force = ELASTIC_FORCE_COEFFICIENT * distance_coefficient * mass_coefficient;
768
769        let diff = diff.normalized();
770
771        *vel_delta += Vec3::from(diff)
772            * force
773            * step_delta
774            * vel
775                .0
776                .xy()
777                .try_normalized()
778                .map_or(1.0, |dir| diff.dot(-dir).max(0.025));
779    }
780
781    *collision_registered = true;
782
783    true
784}
785
786struct ColliderContext<'a> {
787    pos: Vec3<f32>,
788    previous_cache: &'a PreviousPhysCache,
789}
790
791/// Find pushback vector and collision_distance we assume between this
792/// colliders.
793fn projection_between(c0: ColliderContext, c1: ColliderContext) -> (Vec2<f32>, f32) {
794    const DIFF_THRESHOLD: f32 = f32::EPSILON;
795    let our_radius = c0.previous_cache.neighborhood_radius;
796    let their_radius = c1.previous_cache.neighborhood_radius;
797    let collision_dist = our_radius + their_radius;
798
799    let we = c0.pos.xy();
800    let other = c1.pos.xy();
801
802    let (p0_offset, p1_offset) = match c0.previous_cache.origins {
803        Some(origins) => origins,
804        // fallback to simpler model
805        None => return capsule2cylinder(c0, c1),
806    };
807    let segment = LineSegment2 {
808        start: we + p0_offset,
809        end: we + p1_offset,
810    };
811
812    let (p0_offset_other, p1_offset_other) = match c1.previous_cache.origins {
813        Some(origins) => origins,
814        // fallback to simpler model
815        None => return capsule2cylinder(c0, c1),
816    };
817    let segment_other = LineSegment2 {
818        start: other + p0_offset_other,
819        end: other + p1_offset_other,
820    };
821
822    let (our, their) = closest_points(segment, segment_other);
823    let diff = our - their;
824
825    if diff.magnitude_squared() < DIFF_THRESHOLD {
826        capsule2cylinder(c0, c1)
827    } else {
828        (diff, collision_dist)
829    }
830}
831
832/// Returns the points on line segments n and m respectively that are the
833/// closest to one-another. If the lines are parallel, an arbitrary,
834/// unspecified pair of points that sit on the line segments will be chosen.
835fn closest_points(n: LineSegment2<f32>, m: LineSegment2<f32>) -> (Vec2<f32>, Vec2<f32>) {
836    // TODO: Rewrite this to something reasonable, if you have faith
837    let a = n.start;
838    let b = n.end - n.start;
839    let c = m.start;
840    let d = m.end - m.start;
841
842    // Check to prevent div by 0.0 (produces NaNs) and minimize precision
843    // loss from dividing by small values.
844    // If both d.x and d.y are 0.0 then the segment is a point and we are fine
845    // to fallback to the end point projection.
846    let t = if d.x > d.y {
847        (d.y / d.x * (c.x - a.x) + a.y - c.y) / (b.x * d.y / d.x - b.y)
848    } else {
849        (d.x / d.y * (c.y - a.y) + a.x - c.x) / (b.y * d.x / d.y - b.x)
850    };
851    let u = if d.y > d.x {
852        (a.y + t * b.y - c.y) / d.y
853    } else {
854        (a.x + t * b.x - c.x) / d.x
855    };
856
857    // Check to see whether the lines are parallel
858    if !t.is_finite() || !u.is_finite() {
859        [
860            (n.projected_point(m.start), m.start),
861            (n.projected_point(m.end), m.end),
862            (n.start, m.projected_point(n.start)),
863            (n.end, m.projected_point(n.end)),
864        ]
865        .into_iter()
866        .min_by_key(|(a, b)| ordered_float::OrderedFloat(a.distance_squared(*b)))
867        .expect("Lines had non-finite elements")
868    } else {
869        let t = t.clamped(0.0, 1.0);
870        let u = u.clamped(0.0, 1.0);
871
872        let close_n = a + b * t;
873        let close_m = c + d * u;
874
875        let proj_n = n.projected_point(close_m);
876        let proj_m = m.projected_point(close_n);
877
878        if proj_n.distance_squared(close_m) < proj_m.distance_squared(close_n) {
879            (proj_n, close_m)
880        } else {
881            (close_n, proj_m)
882        }
883    }
884}
885
886/// Find pushback vector and collision_distance we assume between this
887/// colliders assuming that only one of them is capsule prism.
888fn capsule2cylinder(c0: ColliderContext, c1: ColliderContext) -> (Vec2<f32>, f32) {
889    // "Proper" way to do this would be handle the case when both our colliders
890    // are capsule prisms by building origins from p0, p1 offsets and our
891    // positions and find some sort of projection between line segments of
892    // both colliders.
893    // While it's possible, it's not a trivial operation especially
894    // in the case when they are intersect. Because in such case,
895    // even when you found intersection and you should push entities back
896    // from each other, you get then difference between them is 0 vector.
897    //
898    // Considering that we won't fully simulate collision of capsule prism.
899    // As intermediate solution, we would assume that bigger collider
900    // (with bigger scaled_radius) is capsule prism (cylinder is special
901    // case of capsule prism too) and smaller collider is cylinder (point is
902    // special case of cylinder).
903    // So in the end our model of collision and pushback vector is simplified
904    // to checking distance of the point between segment of capsule.
905    //
906    // NOTE: no matter if we consider our collider capsule prism or cylinder
907    // we should always build pushback vector to have direction
908    // of motion from our target collider to our collider.
909    //
910    let we = c0.pos.xy();
911    let other = c1.pos.xy();
912    let calculate_projection_and_collision_dist = |our_radius: f32,
913                                                   their_radius: f32,
914                                                   origins: Option<(Vec2<f32>, Vec2<f32>)>,
915                                                   start_point: Vec2<f32>,
916                                                   end_point: Vec2<f32>,
917                                                   coefficient: f32|
918     -> (Vec2<f32>, f32) {
919        let collision_dist = our_radius + their_radius;
920
921        let (p0_offset, p1_offset) = match origins {
922            Some(origins) => origins,
923            None => return (we - other, collision_dist),
924        };
925        let segment = LineSegment2 {
926            start: start_point + p0_offset,
927            end: start_point + p1_offset,
928        };
929
930        let projection = coefficient * (segment.projected_point(end_point) - end_point);
931
932        (projection, collision_dist)
933    };
934
935    if c0.previous_cache.scaled_radius > c1.previous_cache.scaled_radius {
936        calculate_projection_and_collision_dist(
937            c0.previous_cache.neighborhood_radius,
938            c1.previous_cache.scaled_radius,
939            c0.previous_cache.origins,
940            we,
941            other,
942            1.0,
943        )
944    } else {
945        calculate_projection_and_collision_dist(
946            c0.previous_cache.scaled_radius,
947            c1.previous_cache.neighborhood_radius,
948            c1.previous_cache.origins,
949            other,
950            we,
951            -1.0,
952        )
953    }
954}