最近公司要做一个类似于球球大作战的项目，游戏运行中会不断进行大量的碰撞检测，需要适合的碰撞检测方案，所以在网上搜索了一下资料。下面是找到的几种方案。

方案一：循环遍历：

• 在游戏场景运行期间，会每帧调用update()，在update函数中循环遍历场景中所有的物体，通过计算物体中心点的距离来判断物体是否碰撞。
• 试想如果场景中有N个物体，对每两个物体都进行碰撞检测，那时间复杂度就有N^2，效率低。而且实际上一个位于场景左下角的物体与一个位于场景右上角的物体明显不可能发生碰撞，

方案二：使用cocos2dx自带的chipmunk物理引擎：

• 可以在scene添加物理世界，将所有的物体都设置成物理刚体，通过chipmunk的碰撞回调实现碰撞检测
• 之前做游戏遇到过刚体速度太快出现碰撞穿透现象，所以此次不采用此方案。

方案三：四叉树优化碰撞检测：

• 使用四叉树空间索引，减少需要遍历的物体数量，大大减少了计算量。
  说得太多主要还是因为我没有使用过四叉树~ 想尝试一下~

四叉树原理

---

网上可以查到许多关于四叉树的资料。四叉树是一个每个父节点都具有四个子节点的树状数据结构。我们将屏幕划分为四个区域，用于区分处于不同位置的物体，四叉树的四个节点正合适表示这四个区域。
方便起见将四块区域命名为象限一、二、三、四。

image.png

我们将完全处于某一个象限的物体存储在该象限对应的子节点下，当然，也存在跨越多个象限的物体，我们将它们存在父节点中，如下图所示：

image.png

如果某个象限内的物体的数量过多，它会同样会分裂成四个子象限，以此类推：

image.png

lua实现四叉树

---

local QuadTree = {}
QuadTree.__index = QuadTree

QuadTree.MAX_OBJECTS = 10
QuadTree.MAX_LEVELS = 5

local function checkbounds(quadrant, box)
    local list = {
        cc.p(box.x + box.width, box.y + box.height),
        cc.p(box.x + box.width, box.y + box.height),
        cc.p(box.x + box.width, box.y + box.height),
        cc.p(box.x + box.width, box.y + box.height),
    }
    for _, pos in pairs(list) do
        if not (pos.x >= quadrant.x and pos.x <= quadrant.x + quadrant.width and pos.y >= quadrant.y and pos.y <= quadrant.y + quadrant.height) then
            return false
        end
    end
    
    return true
end

--bounds 屏幕范围
--level 四叉树层级
function QuadTree:new(bounds, level)
    local o = {}
    o = setmetatable(o,QuadTree)
    o.objects = {}
    o.nodes = {}
    o.level = level and level or 0
    o.bounds = bounds
    return o
end

--   获取物体对应的象限序号，以屏幕中心为界限，切割屏幕:
--   - 右上：象限一
--   - 左上：象限二
--   - 左下：象限三
--   - 右下：象限四
function QuadTree:getIndex(node)
    local rect = node:getBoundingBox()
    if not checkbounds(self.bounds, rect) then
        return nil
    end
    
    local x = self.bounds.x
    local y = self.bounds.y
    local width = self.bounds.width / 2
    local height = self.bounds.height / 2
    
    local quadrant1 = cc.rect(x + width, y + height, width, height)
    local quadrant2 = cc.rect(x, y + height, width, height)
    local quadrant3 = cc.rect(x, y, width, height)
    local quadrant4 = cc.rect(x + width, y, width, height)
    
    if checkbounds(quadrant1, rect) then
        return 1
    elseif checkbounds(quadrant2, rect) then
        return 2
    elseif checkbounds(quadrant3, rect) then
        return 3
    elseif checkbounds(quadrant4, rect) then
        return 4
    end
    
    --如果物体跨越多个象限，则放回-1
    return - 1
end

function QuadTree:split()
    if #self.nodes > 0 then
        return
    end
    
    local x = self.bounds.x
    local y = self.bounds.y
    local width = self.bounds.width / 2
    local height = self.bounds.height / 2
    
    local tree1 = QuadTree:new(cc.rect(x + width, y + height, width, height), self.level + 1)
    local tree2 = QuadTree:new(cc.rect(x, y + height, width, height), self.level + 1)
    local tree3 = QuadTree:new(cc.rect(x, y, width, height), self.level + 1)
    local tree4 = QuadTree:new(cc.rect(x + width, y, width, height), self.level + 1)
    
    table.insert(self.nodes, tree1)
    table.insert(self.nodes, tree2)
    table.insert(self.nodes, tree3)
    table.insert(self.nodes, tree4)
end

-- 插入功能：
--     - 如果当前节点[ 存在 ]子节点，则检查物体到底属于哪个子节点，如果能匹配到子节点，则将该物体插入到该子节点中
--     - 如果当前节点[ 不存在 ]子节点，将该物体存储在当前节点。随后，检查当前节点的存储数量，如果超过了最大存储数量，则对当前节点进行划分，划分完成后，将当前节点存储的物体重新分配到四个子节点中。
function QuadTree:insert(node)
    --如果该节点下存在子节点
    print("!!!!!!!!!!!!!!!!!!!!!!!!",tolua.type(node))
    if #self.nodes > 0 then
        local index = self:getIndex(node)
        if index and index ~= - 1 then
            self.nodes[index]:insert(node)
            return
        end
    end
    
    --否则存储在当前节点下
    table.insert(self.objects, node)
    
    --如果当前节点存储的数量超过了MAX_OBJECTS
    if #self.nodes <= 0 and #self.objects > QuadTree.MAX_OBJECTS
    and self.level < QuadTree.MAX_LEVELS then
        self:split()
        
        for i = #self.objects, 1, - 1 do
            local index = self:getIndex(self.objects[i])
            if index and index ~= - 1 then  
                self.nodes[index]:insert(self.objects[i])
                table.remove(self.objects, i)
            end
        end
    end
end

-- 检索功能：
--  给出一个物体对象，该函数负责将该物体可能发生碰撞的所有物体选取出来。该函数先查找物体所属的象限，该象限下的物体都是有可能发生碰撞的，然后再递归地查找子象限...
function QuadTree:retrieve(node)
    local result = {}
    
    if #self.nodes > 0 then
        local index = self:getIndex(node)
        if index and index ~= - 1 then
            local list = self.nodes[index]:retrieve(node)
            for _,value in pairs(list) do
                table.insert(result, value)
            end
        elseif index and index == - 1 then
            local x = self.bounds.x
            local y = self.bounds.y
            local width = self.bounds.width / 2
            local height = self.bounds.height / 2
            
            local quadrant1 = cc.rect(x + width, y + height, width, height)
            local quadrant2 = cc.rect(x, y + height, width, height)
            local quadrant3 = cc.rect(x, y, width, height)
            local quadrant4 = cc.rect(x + width, y, width, height)
            
            local rect = node:getBoundingBox()
            
            if checkbounds(quadrant1, rect) then
                local list = self.nodes[1]:retrieve(node)
                for _,value in pairs(list) do
                    table.insert(result, value)
                end
            end
            
            if checkbounds(quadrant2, rect) then
                local list = self.nodes[2]:retrieve(node)
                for _,value in pairs(list) do
                    table.insert(result, value)
                end
            end
            
            if checkbounds(quadrant3, rect) then
                local list = self.nodes[3]:retrieve(node)
                for _,value in pairs(list) do
                    table.insert(result, value)
                end
            end
            
            if checkbounds(quadrant4, rect) then
                local list = self.nodes[4]:retrieve(node)
                for _,value in pairs(list) do
                    table.insert(result, value)
                end
            end
        end
    end

    for _,value in pairs(self.objects) do
        table.insert(result, value)
    end
    
    return result
end

--判断矩形是否在象限范围内
function QuadTree:isInner(node, bounds)
    local rect = node:getBoundingBox()
    return rect.x >= bounds.x and rect.x + rect.width <= bounds.x + bounds.width
    and rect.y >= bounds.y and rect.y + rect.height <= bounds.y + bounds.height
end

-- 动态更新：
-- 从根节点深入四叉树，检查四叉树各个节点存储的物体是否依旧属于该节点（象限）的范围之内，如果不属于，则重新插入该物体。
function QuadTree:refresh(root)
    root = root or self
    for i = #self.objects, 1, - 1 do
        local node = self.objects[i]
        local index = self:getIndex(node)
        
        if index then
            --如果矩形不属于该象限，则将该矩形重新插入
            if not self:isInner(node, self.bounds) then
                if self ~= root then
                    root:insert(self.objects[i])
                    table.remove(self.objects, i)
                end
                
                --  如果矩形属于该象限 且 该象限具有子象限，则
                --  将该矩形安插到子象限中
            elseif #self.nodes > 0 then
                self.nodes[index]:insert(self.objects[i])
                table.remove(self.objects, i)
            end
        end
    end
    
    for i = 1, #self.nodes do
        self.nodes[i]:refresh(root)
    end
end

return QuadTree 

后期实际运用到项目里面的时候，发现还缺少了移除节点，以及清除整个四叉树的接口
四叉树中object的结构我存的是CCNODE

--移除四叉树节点中的object
function QuadTree:remove(removeNode)
    for i = #self.objects, 1, - 1 do
        local node = self.objects[i]
        if node and node:getTag() == removeNode:getTag() then
            table.remove(self.objects, i)
            return true
        end
    end
    
    for i = 1, #self.nodes do
        if self.nodes[i]:remove(removeNode) then
            return true
        end
    end
    
    return false
end

--清理四叉树
function QuadTree:clear()
    for i = #self.objects, 1, - 1 do
        table.remove(self.objects,i)
    end
    self.objects = {}

    for i = 1, #self.nodes do
        self.nodes[i]:clear()
    end
end