Detecting Collisions Between Objects on a Grid in Ruby

This is the first of a number of posts I plan on writing that share some of the things I have learned while building Book'd. Some of the posts I share will be technical, some business/startup related, and others perhaps just anecdotal. Hopefully they'll all be fun for someone. :) Enjoy.

This first post is a technical post. For most programmers, this is CS101 kinda stuff, but I thought I'd share anyway because it's fun. It is a simple algorithm in Ruby for detecting collisions between 2D objects on a grid. I have greatly simplified this in order to keep it short and just get the idea across.

So imagine you have a collection of objects you want to lay out on a plane within a confined width. Every object has a defined top and bottom, but its width should take up as much space as possible so long as there is not another object that overlaps with it. Here's how you would do it in Ruby:

# Call this for each block in a collection of blocks if you 
# want to position the blocks on a grid without them overlapping.
# Returns the array [top, left_offset, height, width] for a single block
def get_coordinates(block, blocks)
  y1 = block.top
  h1 = block.top - block.bottom
  
  collisions = 0
  colliders = [block]

  # this part checks for collisions and adds colliders to an array

  blocks.each do |b|
    if block != b     
      y2 = b.top
      vOverlap = h1 - (y2-y1).abs
          
      if vOverlap > 0 
        collisions += 1
        colliders << b
      end
    end
  end

  # if there are collisions, then you need to set the width 
  # and offset from the left of the block
  if collisions > 0

    # get the percentage of total width to take up
    w1 = 100/(collisions+1)
    
    # You need to decide what order the blocks appear in order to 
    # set the offset from the left. Therefore, you need some 
    # variable by which to sort them that will be consistent each 
    # time you call this for a block.  Could be a creation date 
    # or a custom field.
    colliders.sort!{|x,y| x.sort_field <=> y.sort_field } 

    # now that you know the width and the order of the blocks, 
    # you can then set the left offset
    l1 = "#{colliders.index(block) * w1}%" 

    # return the original height, number of units offset from 
    # left, the original height, and the width
    [y1,l1,h1,"#{w1}%"]

  else #there are no collisions

    # return original top, 0 units offset from the left, 
    # original height, and 100% width
    [y1,0,h1,"100%"] 
  end
  
end

That's it.