1 files changed, 22 insertions, 19 deletions

diff --git a/pixel-client/src/game.rs b/pixel-client/src/game.rs
index 5a06ad30..29b1ba30 100644
--- a/pixel-client/src/game.rs
+++ b/pixel-client/src/game.rs
@@ -25,7 +25,7 @@ use crate::{
     tilemap::Tilemap,
     State,
 };
-use hurrycurry_client_lib::network::sync::Network;
+use hurrycurry_client_lib::{network::sync::Network, spatial_index::SpatialIndex};
 use hurrycurry_protocol::{
     glam::{IVec2, Vec2},
     movement::MovementBase,
@@ -44,9 +44,9 @@ pub struct Game {
     data: ClientGamedata,
     tiles: HashMap<IVec2, Tile>,
     tilemap: Tilemap,
-    collision_map: HashSet<IVec2>,
+    walkable: HashSet<IVec2>,
     players: HashMap<PlayerID, Player>,
-    player_ids: HashSet<PlayerID>,
+    players_spatial_index: SpatialIndex<PlayerID>,
     items_removed: Vec<Item>,
     my_id: PlayerID,
 
@@ -95,14 +95,14 @@ impl Game {
             tilemap: Tilemap::default(),
             my_id: PlayerID(0),
             data: ClientGamedata::default(),
-            collision_map: HashSet::new(),
+            walkable: HashSet::new(),
             movement_send_cooldown: 0.,
             misc_textures: MiscTextures::init(layout),
             item_sprites: Vec::new(),
             items_removed: Vec::new(),
             interacting: false,
             score: Score::default(),
-            player_ids: HashSet::new(),
+            players_spatial_index: SpatialIndex::default(),
             camera_center: Vec2::ZERO,
         }
     }
@@ -161,7 +161,7 @@ impl Game {
 
         if let Some(player) = self.players.get_mut(&self.my_id) {
             player.movement.input(direction, boost);
-            player.movement.update(&self.collision_map, dt);
+            player.movement.update(&self.walkable, dt);
 
             if send_movement {
                 self.network
@@ -177,16 +177,20 @@ impl Game {
             self.camera_center.exp_to(player.movement.position, dt * 5.);
         }
 
-        for p1 in &self.player_ids {
-            for p2 in &self.player_ids {
-                if p1 != p2 {
-                    if let Some([p1, p2]) = self.players.get_many_mut([p1, p2]) {
-                        p1.movement.collide(&mut p2.movement, dt);
-                    }
-                }
-            }
+        for (&pid, player) in &mut self.players {
+            player.movement.update(&self.walkable, dt);
+            self.players_spatial_index
+                .update_entry(pid, player.movement.position);
         }
 
+        self.players_spatial_index.all(|p1, pos1| {
+            self.players_spatial_index.query(pos1, 2., |p2, _pos2| {
+                if let Some([a, b]) = self.players.get_many_mut([&p1, &p2]) {
+                    a.movement.collide(&mut b.movement, dt)
+                }
+            })
+        });
+
         for player in self.players.values_mut() {
             if let Some(item) = &mut player.item {
                 item.parent_position = player.movement.position;
@@ -244,13 +248,13 @@ impl Game {
                         },
                     );
                     if self.data.tile_collide[kind.0] {
-                        self.collision_map.remove(&tile);
+                        self.walkable.remove(&tile);
                     } else {
-                        self.collision_map.insert(tile);
+                        self.walkable.insert(tile);
                     }
                 } else {
                     self.tiles.remove(&tile);
-                    self.collision_map.remove(&tile);
+                    self.walkable.remove(&tile);
                 }
                 self.tilemap.set(tile, kind, neighbors);
             }
@@ -280,11 +284,10 @@ impl Game {
                         },
                     },
                 );
-                self.player_ids.insert(id);
             }
             PacketC::RemovePlayer { id } => {
                 info!("remove player {}", id.0);
-                self.player_ids.remove(&id);
+                self.players_spatial_index.remove_entry(id);
                 self.players.remove(&id);
             }
             PacketC::Movement {