quadtree.lua

function checkCollision(x1,y1,w1,h1, x2,y2,w2,h2)
  return x1 < x2+w2 and
         x2 < x1+w1 and
         y1 < y2+h2 and
         y2 < y1+h1
end

MAX_OBJECTS = 10
MAX_LEVELS = 5


QuadTree = {}
QuadTree_mt = {}
QuadTree_mt.__index = QuadTree
function QuadTree.new(x, y, w, h, level, color)
    return setmetatable(
    {
        x = x,
        y = y,
        w = w,
        h = h,
        children = nil,
        level = level or 0,
        objects = {},
        count = 0,
        color = color,
    }, QuadTree_mt)
end

function QuadTree:clear()
    for k,v in pairs(self.objects) do self.objects[k]=nil end
    for k,v in pairs(self.children) do
        v:clear()
        self.children[k] = nil
    end
end

function QuadTree:split()
    --print("split!")
    local sw = self.w / 2
    local sh = self.h / 2
    local x = self.x
    local y = self.y
    local slevel = self.level + 1
    self.children = {}
    self.children[1] = QuadTree.new(x + sw, y     , sw, sh, slevel,{1,0,0})
    self.children[2] = QuadTree.new(x     , y     , sw, sh, slevel,{1,0,1})
    self.children[3] = QuadTree.new(x     , y + sh, sw, sh, slevel,{0,0,1})
    self.children[4] = QuadTree.new(x + sw, y + sh, sw, sh, slevel,{0,1,0})
end

function QuadTree:getIndex(e)
    local index = -1
    local middleX = self.x + self.w / 2
    local middleY = self.y + self.h / 2
    
    local inTopQuadrant = e.y < middleY and e.y + e.h < middleY
    local inBotQuadrant = e.y > middleY
    --inleftQuadrant
    if e.x < middleX and e.x + e.w < middleX then
        if inTopQuadrant then
            index = 2
        elseif inBotQuadrant then
            index = 3
        end
    elseif e.x > middleX then--in right quadrant
        if inTopQuadrant then
            index = 1
        elseif inBotQuadrant then
            index = 4
        end
    end
    return index
end

function QuadTree:insert(e)
    --already subdivided, put it there, unless it doesnt fit
    if self.children ~= nil then
        local index = self:getIndex(e)
        --e.index = index
        if index ~= -1 then
            --print("FFFF", index)
            self.children[index]:insert(e)
            return
        end
    end
    --not subdivided yet  
    e.quad = self
    self.objects[e] = e 
    self.count = self.count + 1
    
    --this here is if a new subdivision is necessary
    if self.count > MAX_OBJECTS and self.level < MAX_LEVELS then
        if self.children == nil then
            self:split()
        end
        
        local i = 0
        --copy over current objects to children nodes
        for k, v in pairs(self.objects) do
            local index = self:getIndex(v)
            if index ~= -1 then
                self.children[index]:insert(v)
                self.objects[k] = nil
                self.count = self.count - 1
            end
        end
        
    end
end    
    
function QuadTree:retrieve(e, returnList)
    local index = self:getIndex(e)
    if index ~= -1 and self.children then
        self.children[index]:retrieve(e, returnList)
    end
    for k,v in pairs(self.objects) do
        returnList[#returnList + 1] = v
    end
    return returnList
end


local entities = {}

function newEnt(x,y,w,h,vx,vy)
    return {
        x = x,
        y = y,
        w = w,
        h = h,
        vx = vx,
        vy = vy
    }
end

function love.load()
    love.window.setMode( 1290, 800 )
    for i = 1, 100 do
        entities[#entities + 1] = newEnt(math.random(800), math.random(600), math.random(10, 30), math.random(10, 30), math.random(-40, 40), math.random(-40, 40))
    end
    entities[1].marked = true
end

function love.update(dt)
    quadtree = QuadTree.new(0,0,800,600, 0, {1,1,1})
    for _,e in ipairs(entities) do
        e.x = e.x + e.vx * dt
        e.y = e.y + e.vy * dt
        
        if e.x + e.w > 800 or e.x < 0 then
            e.vx = e.vx * -1
        end
        if e.y + e.h > 600 or e.y < 0 then
            e.vy = e.vy * -1
        end  
        
        quadtree:insert(e)
    end
    --print(quadtree.count)
    
end

local function drawChildren(quad)
    --print(#quad.objects)
    love.graphics.rectangle("line", quad.x, quad.y, quad.w, quad.h)
    if not quad.children then return end
    for k,v in ipairs(quad.children) do
        drawChildren(v)
    end
end

function love.draw()
    local qt = quadtree
    drawChildren(qt)
--[[    love.graphics.rectangle("line", qt.x, qt.y, qt.w, qt.h)
    while qt.children do
        
    end
    --while true do
        love.graphics.rectangle("line", qt.x, qt.y, qt.w, qt.h)
        --print(qt.x, qt.y, qt.w, qt.h)
        --if not qt.children then
        --    break
        --end
        if qt.children then
            print("----")
            print(qt.count)
            --print(#qt.children)
            for k,v in ipairs(qt.children) do
                print(v.count)
                --print(v.x, v.y, v.w, v.h)
                love.graphics.rectangle("line", v.x, v.y, v.w, v.h)
            end
        end
    --end
    ]]
    local ret = {}
    qt:retrieve(entities[1], ret)
    print(#ret)
    
    for _,v in pairs(ret) do
        v.marked = true
    end
    for _,e in ipairs(entities) do
        if e.quad.color then
            love.graphics.setColor(e.quad.color)
        end
        if e.marked then
            love.graphics.rectangle("fill", e.x, e.y, e.w, e.h) 
        else
            love.graphics.rectangle("line", e.x, e.y, e.w, e.h)        
        end
        e.marked = nil
        
        love.graphics.setColor(1,1,1,1)
    end
    entities[1].marked = true
    love.graphics.print(love.timer.getFPS())
end