Ruby Spatial Hash

spatial-hash-bitwise.rb

# This is an experiment with using bit fields to store AABB values
# It is currently a little slower in general than the array based approach but is more stable
# It could be a good fit if doing a lot of position comparisons or the other version is causing too much stutter

# max value for Fixnum is 2**62-1 so using a 60-bit field
AABB_MASK   = 0b000000000000000000000000000000000000000000000000000000000000
MIN_X_MASK  = 0b000000000000000000000000000000000000000000000111111111111111 # 0x7FFF
MIN_X_SHIFT = 0
MIN_Y_MASK  = 0b000000000000000000000000000000111111111111111000000000000000 # 0x3FFF8000
MIN_Y_SHIFT = 15
MAX_X_MASK  = 0b000000000000000111111111111111000000000000000000000000000000 # 0x1FFFC0000000
MAX_X_SHIFT = 30
MAX_Y_MASK  = 0b111111111111111000000000000000000000000000000000000000000000 # 0xFFFE00000000000
MAX_Y_SHIFT = 45

class SpatialHash
  attr_accessor(:cell_shift)

  def initialize(cell_shift = 6)
    # 6 = 64x64, 5 = 32x32, 4 = 16x16
    @cell_shift = cell_shift

    # positions are indexed with a pairing function of x and y that has a maximum range of -32,768, 32,767
    # only slight overall CPU usage reduction vs [[x, y]] but exhibits far less stutter
    @cells = Hash.new { |hash, key| hash[key] = [] }

    # temporary structures to reduce memory allocations
    @set = {}
  end

  def add(entity, position = find_position(entity))
    min_x = (position & 0x7FFF)
    min_y = (position & 0x3FFF8000) >> 15
    max_x = (position & 0x1FFFC0000000) >> 30
    max_y = (position & 0xFFFE00000000000) >> 45

    x = min_x
    y = min_y
    while x <= max_x
      while y <= max_y
        @cells[x << 16 | y] << entity
        y += 1
      end
      y = min_y
      x += 1
    end
  end

  def remove(entity, position = find_position(entity))
    min_x = (position & 0x7FFF)
    min_y = (position & 0x3FFF8000) >> 15
    max_x = (position & 0x1FFFC0000000) >> 30
    max_y = (position & 0xFFFE00000000000) >> 45

    x = min_x
    y = min_y
    while x <= max_x
      while y <= max_y
        @cells[x << 16 | y].delete(entity)
        y += 1
      end
      y = min_y
      x += 1
    end
  end

  def move(entity, x, y)
    position = find_position(entity)
    new_position = find_position_for(x, y, entity.w, entity.h)

    if new_position == position
      entity.x = x
      entity.y = y
      return
    end

    remove(entity, position)
    entity.x = x
    entity.y = y
    add(entity, new_position)
  end

  def at(entity, position = find_position(entity))
    min_x, min_y, max_x, max_y = position
    @set.clear

    x = min_x
    y = min_y
    while x <= max_x
      while y <= max_y
        cell = @cells[x << 16 | y]
        num_entities = cell.length
        i = 0
        while i < num_entities
          @set[cell.at(i)] = true
          i += 1
        end
        y += 1
      end
      y = min_y
      x += 1
    end

    @set.keys
  end

  def find_position(entity)
    (0x7FFF & (entity.x >> @cell_shift)) |
      (0x3FFF8000 & (entity.y >> @cell_shift) << 15) |
      (0x1FFFC0000000 & (entity.x + entity.w >> @cell_shift) << 30) |
      (0xFFFE00000000000 & (entity.y + entity.h >> @cell_shift) << 45)
  end

  def find_position_for(x, y, w, h)
    (0x7FFF & (x >> @cell_shift)) |
      (0x3FFF8000 & (y >> @cell_shift) << 15) |
      (0x1FFFC0000000 & (x + w >> @cell_shift) << 30) |
      (0xFFFE00000000000 & (y + h >> @cell_shift) << 45)
  end
end

spatial-hash.rb

# Fast spatial hash
# Limitations: cell sizes must be pow2, index range is 16-bit
class SpatialHash
  attr_accessor(:cell_shift)

  def initialize(cell_shift = 6)
    # 6 = 64x64, 5 = 32x32, 4 = 16x16
    @cell_shift = cell_shift

    # positions are indexed with a pairing function of x and y that has a maximum range of -32,768, 32,767
    # only slight overall CPU usage reduction vs [[x, y]] but exhibits far less stutter
    @cells = Hash.new { |hash, key| hash[key] = [] }
  end

  def add(entity, position = find_position(entity))
    min_x, min_y, max_x, max_y = position

    x = min_x
    y = min_y
    while x <= max_x
      while y <= max_y
        @cells[x << 16 | y] << entity
        y += 1
      end
      y = min_y
      x += 1
    end
  end

  def remove(entity, position = find_position(entity))
    min_x, min_y, max_x, max_y = position

    x = min_x
    y = min_y
    while x <= max_x
      while y <= max_y
        @cells[x << 16 | y].delete(entity)
        y += 1
      end
      y = min_y
      x += 1
    end
  end

  def move(entity, x, y)
    min_x, min_y, max_x, max_y = current_position = find_position(entity)
    new_min_x, new_min_y, new_max_x, new_max_y = new_position = find_position_for(x, y, entity.w, entity.h)

    if min_x == new_min_x && min_y == new_min_y && max_x == new_max_x && max_y == new_max_y
      entity.x = x
      entity.y = y
      return
    end

    remove(entity, current_position)
    entity.x = x
    entity.y = y
    add(entity, new_position)
  end

  def at(entity, position = find_position(entity))
    min_x, min_y, max_x, max_y = position

    set = {}

    x = min_x
    y = min_y
    while x <= max_x
      while y <= max_y
        cell = @cells[x << 16 | y]
        num_entities = cell.length
        i = 0
        while i < num_entities
          set[cell.at(i)] = true
          i += 1
        end
        y += 1
      end
      y = min_y
      x += 1
    end

    set.keys
  end

  def find_position(entity)
    [entity.x >> @cell_shift, entity.y >> @cell_shift, entity.x + entity.w >> @cell_shift, entity.y + entity.h >> @cell_shift]
  end

  def find_position_for(x, y, w, h)
    [x >> @cell_shift, y >> @cell_shift, x + w >> @cell_shift, y + h >> @cell_shift]
  end
end

v1.rb

# This is the very first version I wrote.  You probably don't want this
class SpatialHash
  def initialize
    @cell_size = CELL_SIZE
    @cells = {}
  end

  def add(object)
    min_x = (object.x / CELL_SIZE).to_i
    min_y = (object.y / CELL_SIZE).to_i
    max_x = ((object.x + object.width - 1) / CELL_SIZE).to_i
    max_y = ((object.y + object.height - 1) / CELL_SIZE).to_i

    (min_x..max_x).each do |x|
      (min_y..max_y).each do |y|
        (@cells[[x, y]] ||= []) << object
      end
    end
  end

  def remove(object)
    min_x = (object.x / CELL_SIZE).to_i
    min_y = (object.y / CELL_SIZE).to_i
    max_x = ((object.x + object.width - 1) / CELL_SIZE).to_i
    max_y = ((object.y + object.height - 1) / CELL_SIZE).to_i

    (min_x..max_x).each do |x|
      (min_y..max_y).each do |y|
        @cells[[x, y]]&.delete(object)
      end
    end
  end

  def at(object)
    min_x = (object.x / CELL_SIZE).to_i
    min_y = (object.y / CELL_SIZE).to_i
    max_x = ((object.x + object.width - 1) / CELL_SIZE).to_i
    max_y = ((object.y + object.height - 1) / CELL_SIZE).to_i

    collection = []

    (min_x..max_x).each do |x|
      (min_y..max_y).each do |y|
        @cells[[x, y]]&.each do |entity|
          collection << entity
        end
      end
    end

    collection.uniq
  end

  def clear
    @cells.clear
  end
end