Grid traversal

grid.lua

local grid = {}

local function grid_toCell(cellSize, x, y)
  return math.floor(x / cellSize) + 1, math.floor(y / cellSize) + 1
end

-- grid_traverse* functions are based on "A Fast Voxel Traversal Algorithm for Ray Tracing",
-- by John Amanides and Andrew Woo - http://www.cse.yorku.ca/~amana/research/grid.pdf
-- It has been modified to include both cells when the ray "touches a grid corner",
-- and with a different exit condition

local function grid_traverse_initStep(cellSize, ct, t1, t2)
  local v = t2 - t1
  if     v > 0 then
    return  1,  cellSize / v, ((ct + v) * cellSize - t1) / v
  elseif v < 0 then
    return -1, -cellSize / v, ((ct + v - 1) * cellSize - t1) / v
  else
    return 0, math.huge, math.huge
  end
end

grid.traverse = function(cellSize, x1,y1,x2,y2, f)
  local cx1,cy1        = grid_toCell(cellSize, x1,y1)
  local cx2,cy2        = grid_toCell(cellSize, x2,y2)
  local stepX, dx, tx  = grid_traverse_initStep(cellSize, cx1, x1, x2)
  local stepY, dy, ty  = grid_traverse_initStep(cellSize, cy1, y1, y2)
  local cx,cy          = cx1,cy1
  local ncx, ncy

  f(cx, cy)

  -- The default implementation had an infinite loop problem when
  -- approaching the last cell in some occassions. We finish iterating
  -- when we are *next* to the last cell
  while math.abs(cx - cx2) + math.abs(cy - cy2) > 1 do
    if tx < ty then
      tx, cx = tx + dx, cx + stepX
      f(cx, cy)
    else
      -- Addition: include both cells when going through corners
      if tx == ty then f(cx + stepX, cy) end
      ty, cy = ty + dy, cy + stepY
      f(cx, cy)
    end
  end

  -- If we have not arrived to the last cell, use it
  if cx ~= cx2 or cy ~= cy2 then f(cx2, cy2) end

end

return grid

main.lua

local grid = require 'grid'

local gridSize = 20

local values= {}

local x1,y1,x2,y2= 90,64,60,460

function love.draw()
  for cy,row in pairs(values) do
    for cx,val in pairs(row) do
      local x,y = (cx-1)* gridSize, (cy-1)*gridSize
      love.graphics.rectangle('line', x,y, gridSize, gridSize)
      love.graphics.print(val, x+2,y+2)
    end
  end
  love.graphics.line(x1,y1,x2,y2)

  love.graphics.print(("{%d,%d} - {%d,%d}"):format(x1,y1,x2,y2), 10,10 )
end

function love.update(dt)
  x2,y2 = love.mouse.getPosition()

  values = {}
  local count = 0

  grid.traverse(gridSize, x1,y1,x2,y2, function(cx, cy)
    count = count + 1
    values[cy] = values[cy] or {}
    values[cy][cx] = count
  end)
end

function love.mousepressed(x,y)
  x1,y1 = x,y
end

function love.keypressed()
  love.event.quit()
end