1 files changed, 205 insertions, 0 deletions
diff --git a/src/phys/world.odin b/src/phys/world.odin
new file mode 100644
index 0000000..eac3d5c
--- /dev/null
+++ b/src/phys/world.odin
@@ -0,0 +1,205 @@
+package phys
+
+import "core:log"
+import "core:math"
+
+import sapp "shared:sokol/app"
+
+BIN_COUNT :: 2056
+BIN_SIZE :: 64
+
+Body_Handle :: u32
+
+World :: struct {
+  handles: [dynamic]u32,
+  unused_handles: [dynamic]Body_Handle,
+  bodies: [dynamic]Body,
+  bins: [BIN_COUNT][dynamic]Body_Handle,
+}
+
+destroy_world :: proc(w: World) {
+  for bin in w.bins {
+    delete(bin)
+  }
+}
+
+@(private="file")
+hash_bin :: proc(x: i32, y: i32) -> u32 {
+  return transmute(u32)((x * 73856093) ~ (y * 19349663))
+}
+
+@(private="file")
+world_to_bin :: proc(point: Vec2) -> (i32, i32) {
+  return \
+    i32(math.floor(point.x / BIN_SIZE)), 
+    i32(math.floor(point.y / BIN_SIZE))
+}
+
+@(private="file")
+get_surrounding_bins :: proc(
+  w: ^World,
+  pos: Vec2,
+  allocator := context.temp_allocator,
+) -> []^[dynamic]Body_Handle {
+  neighbors := make([]^[dynamic]Body_Handle, 9, allocator)
+
+  center_x, center_y := world_to_bin(pos)
+
+  idx := 0
+
+  for offset_x in -1..=1 {
+    for offset_y in -1..=1 {
+      bin_idx := hash_bin(center_x + i32(offset_x), center_y + i32(offset_y))
+      bin := &w.bins[bin_idx % BIN_COUNT]
+      neighbors[idx] = bin
+      idx += 1
+    }
+  }
+
+  return neighbors
+}
+
+@(private="file")
+find_bin :: proc(w: ^World, b: Body) -> ^[dynamic]Body_Handle {
+  bin_x, bin_y := world_to_bin(b.pos + b.rect.start)
+  return &w.bins[hash_bin(bin_x, bin_y) % BIN_COUNT]
+}
+
+@(private="file")
+add_to_bins :: proc(w: ^World, b: Body) {
+  bin := find_bin(w, b)
+  idx := i32(len(bin))
+  append(bin, b.handle)
+  w.bodies[bin[idx]].bin_idx = idx
+}
+
+@(private="file")
+remove_from_bins :: proc(w: ^World, b: Body) {
+  bin := find_bin(w, b)
+
+  assert(bin[b.bin_idx] == b.handle)
+
+  last := pop(bin)
+  if last != b.handle {
+    bin[b.bin_idx] = last
+    w.bodies[last].bin_idx = b.bin_idx
+  }
+}
+
+get_body :: proc(w: World, h: Body_Handle) -> ^Body {
+  return &w.bodies[w.handles[h]]
+}
+
+add_body :: proc(w: ^World, b: Body) -> (Body_Handle, ^Body) {
+  handle: Body_Handle
+
+  if b.rect.size.x > BIN_SIZE || b.rect.size.y > BIN_SIZE {
+    log.warnf("Body size is too big (%vx%v)", b.rect.size.x, b.rect.size.y)
+  }
+
+  if len(w.unused_handles) > 0 {
+    handle = pop(&w.unused_handles)
+  } else {
+    handle = cast(Body_Handle)len(w.handles)
+    append(&w.handles, 0)
+  }
+
+  w.handles[handle] = u32(len(w.bodies))
+  append(&w.bodies, b)
+
+  body := &w.bodies[w.handles[handle]]
+  body.handle = handle
+
+  add_to_bins(w, body^)
+
+  return handle, body
+}
+
+remove_body :: proc(w: ^World, h: Body_Handle) {
+  b := get_body(w^, h)
+
+  remove_from_bins(w, b^)
+
+  last := pop(&w.bodies)
+  if last.handle != h {
+    w.bodies[h] = last
+    w.handles[last.handle] = w.handles[h]
+  }
+
+  append(&w.unused_handles, b.handle)
+}
+
+update_body :: proc(w: ^World, h: Body_Handle) {
+  dt := f32(sapp.frame_duration())
+
+  b := get_body(w^, h)
+
+  res_pos := b.pos + b.vel * dt
+
+  rect := b.rect
+  rect.start += b.pos
+
+  res_rect := b.rect
+  res_rect.start += res_pos
+
+  bin_list := get_surrounding_bins(w, res_rect.start)
+
+  b.collisions = {}
+
+  total_len := 0
+
+  for bin in bin_list {
+    total_len += len(bin)
+
+    for c_h in bin {
+      if c_h == h {
+        continue
+      }
+
+      c := get_body(w^, c_h)
+
+      c_rect := c.rect
+      c_rect.start += c.pos
+
+      if aabb(res_rect, c_rect) {
+        if aabb_hori(rect, c_rect) {
+          if b.vel.y > 0 {
+            res_pos.y = c_rect.start.y - b.rect.size.y - b.rect.start.y
+            b.collisions += {.DOWN}
+          } else {
+            res_pos.y = c_rect.start.y + c_rect.size.y - b.rect.start.y
+            b.collisions += {.UP}
+          }
+          b.collisions += {.VERTICAL}
+        } else if aabb_vert(rect, c.rect) {
+          if b.vel.x > 0 {
+            res_pos.x = c_rect.start.x - b.rect.size.x - b.rect.start.x
+            b.collisions += {.LEFT}
+          } else {
+            res_pos.x = c_rect.start.x + c_rect.size.x - b.rect.start.x
+            b.collisions += {.RIGHT}
+          }
+          b.collisions += {.HORIZONTAL}
+        }
+      }
+    }
+  }
+
+  if .HORIZONTAL in b.collisions {
+    b.vel.x = 0
+  }
+  if .VERTICAL in b.collisions {
+    b.vel.y = 0
+  }
+
+  b.pos = res_pos
+
+  prev_bin := hash_bin(world_to_bin(b.pos + b.rect.start))
+  res_bin := hash_bin(world_to_bin(res_pos + b.rect.start))
+
+  if prev_bin != res_bin {
+    remove_from_bins(w, b^)
+    add_to_bins(w, b^)
+  }
+}
+