四叉树 - 碰撞检测算法 Lua版

1、工具方法

深拷贝clone与类方法class

-- 深拷贝 保护原数据
function clone(object)
    local lookup_table = {}
    local function _copy(object)
        if type(object) ~= "table" then
            return object
        elseif lookup_table[object] then
            return lookup_table[object]
        end
        local newObject = {}
        lookup_table[object] = newObject
        for key, value in pairs(object) do
            newObject[_copy(key)] = _copy(value)
        end
        return setmetatable(newObject, getmetatable(object))
    end
    return _copy(object)
end

--定义一个类对象
[email protected]	#string		className	类名
[email protected]	#table		super		父类
[email protected]	#table	类
function class(className, super, isUserData)
	local cls = {
		name = className,
		ctor = false,		
		init = false,
		__cccreator = false,
		__cccreatorSelf = false,
		instanceIndexT = {},  	--存储需要继承的方法跟属性
	}

	local superType = type(super)
	if "table" == superType then
		cls.super = super

		cls.__cccreator = super.__cccreator
		cls.__cccreatorSelf = super.__cccreatorSelf
	end

	--该类所生成实例用于索引的元表
	local instanceIndexT = cls.instanceIndexT	
	if cls.super then
		for k, v in pairs(cls.super.instanceIndexT) do
			instanceIndexT[k] = v
		end
	end

	function cls.new(...)
		local instance = { __cname = cls.name }
		local mt = { 
			__index = instanceIndexT,
		}

		setmetatable(instance, mt)

		cls.runCtor(instance, ...)
		cls.runInit(instance, ...)
		--限制只能在构造函数执行完之前定义类变量
		mt.__newindex = errorNewIndex

		return instance
	end

	--执行构造函数
	function cls.runCtor(this, ...)
		local function ctor(c, ...)
			--递归调用父类的构造函数
			if c.super then
				ctor(c.super, ...)
			end

			if c.ctor then
				c.ctor(this, ...)
			end
		end
		ctor(cls, ...)
	end
	--执行构造后的初始化函数
	function cls.runInit(this, ...)
		local function init(c, ...)
			--递归调用父类的构造函数
			if c.super then
				init(c.super, ...)
			end

			if c.init then
				c.init(this, ...)
			end
		end
		init(cls, ...)
	end

	--将类方法copy到指定对象上，主要给ccclass用
	function cls.copyFuncs(this)
		for k, v in pairs(instanceIndexT) do
			this[k] = v
		end
	end

	--用在有时候想要调用某个类的方法，但又不需要创建类的实例
	--被调用方法里面的self不能是cls以及instanceIndexT, 因为这两个是会被继承的
	function cls.staticCall(funcName, ...)
		return instanceIndexT[funcName](nil, ...)
	end

	setmetatable(cls, {		
		__newindex = function(_, k, v)
			instanceIndexT[k] = v
		end
	})

	if super then
		return cls,super.instanceIndexT
	else
		return cls
	end
end

2、四叉树算法

1、简介

通过四叉树算法 解决2D游戏物体的碰撞检测
算法核心：
    添加游戏物体
    1、一定范围内存在超过规定数量的物体时，对此范围进行四等分切割
    2、对各物体进行新的象限所属计算
    3、添加物体重复1、2步骤
    4、直至所有物体添加完毕

    碰撞检测
    1、遍历所有物体
    2、对同一深度象限及其递归子象限的物体进行碰撞计算

2、创建并初始化类

此处需要对分割进行条件判断，应用中根据实际情况来设置。

local MAX_DEPTH = 99  	-- 四叉树的最大深度
local MAX_OBJ_NUM = 9 	-- 每个节点（象限）所能包含物体的最大数量
local MIN_WIDTH = 50	-- 象限最小宽度
local MIN_HEIGHT = 50	-- 象限最小高度

-- 四叉树节点包含：
-- - objects: 用于存储物体对象
-- - nodes: 存储四个子节点
-- - depth: 该节点的深度，根节点的默认深度为0
-- - bounds: 该节点对应的象限在屏幕上的范围，bounds是一个矩形
-- x1:左下横坐标 y1:左下纵坐标 cx:中心点横坐标 cy:中心点纵坐标

local QuadTree = class("QuadTree")
-- 初始化构造
function QuadTree:init(bounds, depth, index)
	if not bounds or not next(bounds) or not depth or type(depth) ~= "number" then
		print("Error：参数错误！！！")
		return
	end
	self.index = index or 1
	self.objects = {}
	self.nodes = {}
	self.depth = depth or 0
	if bounds and next(bounds) then
		self.bounds = {x1 = bounds[1], y1 = bounds[2], cx = bounds[3], cy = bounds[4]}
	else 
		self.bounds = {x1 = 0, y1 = 0, cx = 600, cy = 600}
	end
end

3、获取所在象限方法

--[[
  获取物体对应的象限序号，以屏幕中心为界限，切割屏幕:
  - 右上：象限一 index:1
  - 左上：象限二	index:2
  - 左下：象限三	index:3
  - 右下：象限四	index:4
  - 物体表示
  rect = {
	x, y, width, height
  }
]]

function QuadTree:getIndex(rect)
	local bounds = self.bounds
	local onTop = rect.y >= bounds.cy
	local onBottom = rect.y + rect.height <= bounds.cy
	local onRight = rect.x >= bounds.cx
	local onLeft = rect.x + rect.width <= bounds.cx
	local index = -1

	if onTop then
		if onRight then
			index = 1
		elseif onLeft then
			index = 2
		end
	elseif onBottom then
		if onLeft then
			index = 3
		elseif onRight then
			index = 4
		end
	end

	return index
end

4、拆分方法

-- 拆分为四个象限
function QuadTree:split()
	local depth = self.depth
	local bounds = self.bounds
	local x = bounds.x1
	local y = bounds.y1
	local cx = bounds.cx
	local cy = bounds.cy
	local width = (cx - x)/2
	local height = (cy - y)/2

	-- print("==拆分为四个象限=split==")
	self.nodes = {
		QuadTree.new({cx, cy, cx+width, cy+height}, depth+1, 1),
		QuadTree.new({x, cy, x+width, cy+height}, depth+1, 2),
		QuadTree.new({x, y, x+width, y+height}, depth+1, 3),
		QuadTree.new({cx, y, cx+width, y+height}, depth+1, 4),
	}

	-- 待优化
	-- 剔除多余的节点 ###
end

5、辅助方法

-- 将两个table合并为数组形式
local function tableMerge(tb1, tb2)
	local ret = {}
	tb1 = tb1 or {}
	tb2 = tb2 or {}
	for _,v in pairs(tb1) do
		ret[#ret+1] = v
	end
	for _,v in pairs(tb2) do
		ret[#ret+1] = v
	end
	return ret
end

-- 象限分割矩形
local function rectCarve(rect, bounds)
	local arr = {}
	local x = rect.x
	local y = rect.y
	local index = rect.index
	local width = rect.width
	local height = rect.height
	local cx = bounds.cx
	local cy = bounds.cy
	local spx
	local spy

	if cx > x and cx < x + width then
		spx = cx
	end
	if cy > y and cy < y + height then
		spy = cy
	end

	if spx then
		if spy then
			arr = {
				{index = index, x = x, y = y, width = spx - x, height = spy - y},
				{index = index, x = cx, y = y, width = width - spx + x, height = spy - y},
				{index = index, x = x, y = cy, width = spx - x, height = height - spy + y},
				{index = index, x = cx, y = cy, width = width - spx + x, height = height - spy + y},
			}
		else
			arr = {
				{index = index, x = x, y = y, width = spx - x, height = height},
				{index = index, x = cx, y = y, width = width - spx + x, height = height},
			}
		end
	else
		if spy then
			arr = {
				{index = index, x = x, y = y, width = width, height = spy - y},
				{index = index, x = x, y = cy, width = width, height = height - spy + y},
			}
		end
	end

	return arr
end

-- 获取table长度
local function getTableLen(tb)
	local count = 0
	for _,_ in pairs(tb) do
		count = count + 1
	end
	return count
end

6、插入方法

-- 插入节点
--[[
  插入功能：
    - 如果当前节点[ 存在 ]子节点，则检查物体到底属于哪个子节点，如果能匹配到子节点，则将该物体插入到该子节点中
    - 如果当前节点[ 不存在 ]子节点，将该物体存储在当前节点。
    	随后，检查当前节点的存储数量，如果超过了最大存储数量，则对当前节点进行划分，划分完成后，将当前节点存储的物体重新分配到四个子节点中。
]]
function QuadTree:insert(rect)
	local index
	self.objects[rect.index] = rect

	local function _insert()
		-- print("======insert:" .. self.depth .. "  " .. self.index)
		for i,_rect in pairs(self.objects) do
			index = self:getIndex(_rect)
			if index ~= -1 then
				self.nodes[index]:insert(_rect)
				self.objects[i] = nil
			else
				-- 同时处于多个象限 切割矩形 仅用于计算  
				local subArr = rectCarve(_rect, self.bounds)
				for _,__rect in pairs(subArr) do
					index = self:getIndex(__rect)
					self.nodes[index]:insert(__rect)
				end
				self.objects[i] = nil
			end
		end
	end

	-- 若存在子节点
	if next(self.nodes) then
		_insert()
		return
	end

	-- 如果当前节点存储的数量超过了MAX_OBJECTS 划分为四象限
	if getTableLen(self.objects) > MAX_OBJ_NUM 
		and self.depth < MAX_DEPTH 
		and self.bounds.cx - self.bounds.x1 > MIN_WIDTH
		and self.bounds.cy - self.bounds.y1 > MIN_HEIGHT then
		self:split()
		_insert()
	end
end

7、检索方法

.

--[[
  检索功能：
    给出一个物体对象，该函数负责将该物体可能发生碰撞的所有物体选取出来。
    该函数先查找物体所属的象限，该象限下的物体都是有可能发生碰撞的，然后再递归地查找子象限...
]]

function QuadTree:retrieve(rect)
	local result = {}
	local nodes = self.nodes
	local index
	local indexL = {}

	-- 若存在子节点
	if next(nodes) then
		index = self:getIndex(rect)
		-- print("getIndex", index)
		if index ~= -1 then
			table.insert(indexL, index)
			result = tableMerge(result, nodes[index]:retrieve(rect))
		else
			-- 同时处于多个象限 切割矩形 仅用于计算
			local subArr = rectCarve(rect, self.bounds)
			for _,_rect in pairs(subArr) do
				index = self:getIndex(_rect)
				table.insert(indexL, index)
				result = tableMerge(result, nodes[index]:retrieve(_rect))
			end
		end
	end 

	-- 可优化部分，对于在中间节点上，横跨多个象限的节点可以进行具体的条件
	local objs = clone(self.objects)
	local cx = self.bounds.cx
	local cy = self.bounds.cy
	for _, _index in ipairs(indexL) do
		if _index == 1 then
			for k,v in pairs(objs) do
				if v.x + v.width < cx or v.y + v.height < cy then
					objs[k] = nil
				end
			end
		elseif _index == 2 then
			for k,v in pairs(objs) do
				if v.x > cx or v.y + v.height < cy then
					objs[k] = nil
				end
			end
		elseif _index == 3 then
			for k,v in pairs(objs) do
				if v.x > cx or v.y > cy then
					objs[k] = nil
				end
			end
		elseif _index == 4 then
			for k,v in pairs(objs) do
				if v.x + v.width < cx or v.y > cy then
					objs[k] = nil
				end
			end
		end
	end
	result = tableMerge(result, objs)

	return result
end

3、测试应用

1、矩形相交判断方法

-- 判断两个矩形是否相交
-- true为相交，false不相交  
-- 顶点或边重合视为 不相交 
	-- 1、不影响物理计算
	-- 2、方便四叉树象限划分 
		-- 1 节省内存空间
		-- 2 减少象限划分时的计算量
local count_times = 0
local function isCollision(rect1, rect2)
	count_times = count_times + 1
	return not(rect1.x >= rect2.x + rect2.width
		or rect1.y >= rect2.y + rect2.height
		or rect2.x >= rect1.x + rect1.width
		or rect2.y >= rect1.y + rect1.height)
end

2、应用

-- 屏幕size
local SCREEN_WIDTH = 1200
local SCREEN_HEIGHT = 1200

-- 1、初始化根节点
local quadTree = QuadTree.new({0, 0, SCREEN_WIDTH/2, SCREEN_HEIGHT/2}, 0)
local rect_list = {}

-- 随机初始化
math.randomseed(os.time())
for i=1,500 do
	local rect = {
		index = i,
		width = math.random(10, i>10 and i or 15),
		height = math.random(15, i>15 and i or 20),
		x = math.random(1, SCREEN_WIDTH),
		y = math.random(1, SCREEN_HEIGHT),
	}
	table.insert(rect_list, rect)
end

-- 2、添加游戏物体
for i,v in ipairs(rect_list) do
	quadTree:insert(v)
end

-- 3、循环检测所有可能的碰撞
print("------全部遍历----")

local function calCollsition(answer)
	local collisionCount = 0
	count_times = 0
	print("\n=========方法" .. answer)
	if answer == 2 then
		-- 2) 遍历四叉树象限
		-- 思路一 插入矩形划分象限时，对跨多个象限的矩形特殊处理
			-- 优点：节省内存空间
			-- 缺点：花费较多的时间

		-- 思路二 插入矩形划分象限时，考虑直接将跨多个象限的矩形同时划分至其子象限  2020.07.14 采用此方案
			-- 优点：易理解，查询碰撞省时间
			-- 缺点：花费更多内存空间
		local recordDict = {}
		local function chechCollision(quadTree)
			if next(quadTree.nodes) then
				for i,v in pairs(quadTree.nodes) do
					-- print("递归循环\ndepth：" .. v.depth)
					-- print("index：" .. i)
					chechCollision(v, quadTree.objects)
				end
			else
				local ret = {}
				for k,v in pairs(quadTree.objects) do
					ret[#ret+1] = v
				end
				for _index=1,#ret do
					local rect = ret[_index]
					for __index=_index+1,#ret do
						local otherRect = ret[__index]
						local index1 = rect.index
						local index2 = otherRect.index

						if (recordDict[index1] and recordDict[index1][index2]) or 
							(recordDict[index2] and recordDict[index2][index1]) then
						else
							if isCollision(rect, otherRect) then
								if isPrint then
									print("\t" .. rect.index .. "与" .. otherRect.index .. "相交")
								end
								collisionCount = collisionCount + 1
								if recordDict[index1] then
									recordDict[index1][index2] = true
								else
									recordDict[index1] = {}
									recordDict[index1][index2] = true
								end
							end
						end
					end
				end
			end
		end
		chechCollision(quadTree)

	elseif answer == 3 then
		-- 3) 全部遍历
		for index=1,#rect_list do
			local rect = rect_list[index]
			for _index=index+1,#rect_list do		
				local otherRect = rect_list[_index]
				if isCollision(rect, otherRect) then
					if isPrint then
						print("\t" .. rect.index .. "与" .. otherRect.index .. "相交")
					end
					collisionCount = collisionCount + 1
				end
			end
		end
	end

	print("计算次数：" .. count_times)
	print("相交次数：" .. collisionCount)
end

calCollsition(2)
calCollsition(3)

3、结果比较

------全部遍历----

=========方法2
计算次数：10123
相交次数：5453

=========方法3
计算次数：124750
相交次数：5453

4、待写

1、复杂度比较

2、复杂度优化

3、游戏中每帧计算与动态更新

……