Class: RGame::Engine::SpatialHash

Inherits:
Object
  • Object
show all
Defined in:
lib/rgame/engine/spatial_hash.rb

Overview

A uniform-grid spatial hash for broadphase collision: bucket colliders into fixed-size cells, then test only candidates that share a cell instead of every pair. Pure logic; no graphics.

Typical per-frame use: clear, insert every collider of the static set (here: rocks), then query around each moving collider (bullets, the ship).

hash.clear
rocks.each { |r| hash.insert(r, *r.aabb) }
hash.query(*bullet.aabb) { |rock| ...narrowphase... }

Constant Summary collapse

OFFSET =

Cell (col, row) → one integer key. The offset keeps negative cells (objects off-screen / mid-wrap) non-negative; the stride keeps pairs unique. Both are sized to keep every packed key inside a tagged Fixnum, so keying allocates nothing on the query path (CLAUDE.md: never allocate on the per-frame path).

The ceiling that sizes them is Windows, not Linux/macOS: CRuby's immediate Fixnum range comes from a C long, which is 64 bits on LP64 (Linux, macOS) but stays 32 bits on Windows' LLP64 even in a 64-bit process — so a value comfortably inside Fixnum range on Linux (this packing used to run up to ~242) silently becomes a heap-allocated Bignum on Windows instead, one allocation per cell per query. OFFSET/STRIDE here keep the largest possible packed key (both coordinates at the far corner) under 228 — well inside Windows' ~2**30 Fixnum ceiling — while still allowing cell coordinates out to +/-8192, i.e. a world some sixteen million pixels wide at this file's own cell_size: 64 example. A game whose world exceeds that wraps into a neighbouring cell's key instead of raising; see #each_cell below.

1 << 13
STRIDE = 
1 << 14

Instance Method Summary collapse

Constructor Details

#initialize(cell_size:) ⇒ SpatialHash

Returns a new instance of SpatialHash.



35
36
37
38
 
# File 'lib/rgame/engine/spatial_hash.rb', line 35

def initialize(cell_size:)
  @cell_size = cell_size
  @buckets = Hash.new { |h, key| h[key] = [] }
end

Instance Method Details

#clear ⇒ Object

Reuse the bucket arrays across frames (clear contents, keep capacity).



41
42
43
 
# File 'lib/rgame/engine/spatial_hash.rb', line 41

def clear
  @buckets.each_value(&:clear)
end

#insert(item, x, y, w, h) ⇒ Object 



45
46
47
 
# File 'lib/rgame/engine/spatial_hash.rb', line 45

def insert(item, x, y, w, h)
  each_cell(x, y, w, h) { |key| @buckets[key] << item }
end

#query(x, y, w, h) ⇒ Object

Yield every item whose buckets overlap the region. Dedup contract: an item spanning several cells may be yielded more than once. Narrowphase callers must already guard with next if a.dead? || b.dead? to make hits idempotent, so we skip a per-query visited set and stay allocation-free.



53
54
55
56
57
58
 
# File 'lib/rgame/engine/spatial_hash.rb', line 53

def query(x, y, w, h, &)
  each_cell(x, y, w, h) do |key|
    bucket = @buckets[key]
    bucket.each(&) unless bucket.empty?
  end
end

#query_circle(cx, cy, r) ⇒ Object

Broadphase a circle: yield every item bucketed in a cell the circle's bounding box covers — the radial counterpart to #query, for range/nearest lookups. Same dedup contract (an item may be yielded more than once; the narrowphase caller refines by true distance). Allocation-free.



64
65
66
67
 
# File 'lib/rgame/engine/spatial_hash.rb', line 64

def query_circle(cx, cy, r, &)
  d = r * 2
  query(cx - r, cy - r, d, d, &)
end