最近公司要做一个类似于球球大作战的项目，游戏运行中会不断进行大量的碰撞检测，需要适合的碰撞检测方案，所以在网上搜索了一下资料。下面是找到的几种方案。
方案一：循环遍历：
- 在游戏场景运行期间，会每帧调用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
网友评论