200字范文 > 四叉树 - 碰撞检测算法 Lua版

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

时间：2021-07-02 05:53:39

相关推荐

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

1、工具方法

深拷贝clone与类方法class

-- 深拷贝保护原数据function clone(object)local lookup_table = {}local function _copy(object)if type(object) ~= "table" thenreturn objectelseif lookup_table[object] thenreturn lookup_table[object]endlocal newObject = {}lookup_table[object] = newObjectfor key, value in pairs(object) donewObject[_copy(key)] = _copy(value)endreturn setmetatable(newObject, getmetatable(object))endreturn _copy(object)end--定义一个类对象--@param#stringclassName类名--@param#tablesuper父类--@return#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 thencls.super = supercls.__cccreator = super.__cccreatorcls.__cccreatorSelf = super.__cccreatorSelfend--该类所生成实例用于索引的元表local instanceIndexT = cls.instanceIndexTif cls.super thenfor k, v in pairs(cls.super.instanceIndexT) doinstanceIndexT[k] = vendendfunction cls.new(...)local instance = { __cname = cls.name }local mt = { __index = instanceIndexT,}setmetatable(instance, mt)cls.runCtor(instance, ...)cls.runInit(instance, ...)--限制只能在构造函数执行完之前定义类变量mt.__newindex = errorNewIndexreturn instanceend--执行构造函数function cls.runCtor(this, ...)local function ctor(c, ...)--递归调用父类的构造函数if c.super thenctor(c.super, ...)endif c.ctor thenc.ctor(this, ...)endendctor(cls, ...)end--执行构造后的初始化函数function cls.runInit(this, ...)local function init(c, ...)--递归调用父类的构造函数if c.super theninit(c.super, ...)endif c.init thenc.init(this, ...)endendinit(cls, ...)end--将类方法copy到指定对象上，主要给ccclass用function cls.copyFuncs(this)for k, v in pairs(instanceIndexT) dothis[k] = vendend--用在有时候想要调用某个类的方法，但又不需要创建类的实例--被调用方法里面的self不能是cls以及instanceIndexT, 因为这两个是会被继承的function cls.staticCall(funcName, ...)return instanceIndexT[funcName](nil, ...)endsetmetatable(cls, {__newindex = function(_, k, v)instanceIndexT[k] = vend})if super thenreturn cls,super.instanceIndexTelsereturn clsendend

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" thenprint("Error：参数错误！！！")returnendself.index = index or 1self.objects = {}self.nodes = {}self.depth = depth or 0if bounds and next(bounds) thenself.bounds = {x1 = bounds[1], y1 = bounds[2], cx = bounds[3], cy = bounds[4]}else self.bounds = {x1 = 0, y1 = 0, cx = 600, cy = 600}endend

3、获取所在象限方法

--[[获取物体对应的象限序号，以屏幕中心为界限，切割屏幕:- 右上：象限一 index:1- 左上：象限二index:2- 左下：象限三index:3- 右下：象限四index:4- 物体表示rect = {x, y, width, height}]]function QuadTree:getIndex(rect)local bounds = self.boundslocal onTop = rect.y >= bounds.cylocal onBottom = rect.y + rect.height <= bounds.cylocal onRight = rect.x >= bounds.cxlocal onLeft = rect.x + rect.width <= bounds.cxlocal index = -1if onTop thenif onRight thenindex = 1elseif onLeft thenindex = 2endelseif onBottom thenif onLeft thenindex = 3elseif onRight thenindex = 4endendreturn indexend

4、拆分方法

-- 拆分为四个象限function QuadTree:split()local depth = self.depthlocal bounds = self.boundslocal x = bounds.x1local y = bounds.y1local cx = bounds.cxlocal cy = bounds.cylocal width = (cx - x)/2local 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) doret[#ret+1] = vendfor _,v in pairs(tb2) doret[#ret+1] = vendreturn retend-- 象限分割矩形local function rectCarve(rect, bounds)local arr = {}local x = rect.xlocal y = rect.ylocal index = rect.indexlocal width = rect.widthlocal height = rect.heightlocal cx = bounds.cxlocal cy = bounds.cylocal spxlocal spyif cx > x and cx < x + width thenspx = cxendif cy > y and cy < y + height thenspy = cyendif spx thenif spy thenarr = {{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},}elsearr = {{index = index, x = x, y = y, width = spx - x, height = height},{index = index, x = cx, y = y, width = width - spx + x, height = height},}endelseif spy thenarr = {{index = index, x = x, y = y, width = width, height = spy - y},{index = index, x = x, y = cy, width = width, height = height - spy + y},}endendreturn arrend-- 获取table长度local function getTableLen(tb)local count = 0for _,_ in pairs(tb) docount = count + 1endreturn countend

6、插入方法

-- 插入节点--[[插入功能：- 如果当前节点[ 存在 ]子节点，则检查物体到底属于哪个子节点，如果能匹配到子节点，则将该物体插入到该子节点中- 如果当前节点[ 不存在 ]子节点，将该物体存储在当前节点。随后，检查当前节点的存储数量，如果超过了最大存储数量，则对当前节点进行划分，划分完成后，将当前节点存储的物体重新分配到四个子节点中。]]function QuadTree:insert(rect)local indexself.objects[rect.index] = rectlocal function _insert()-- print("======insert:" .. self.depth .. " " .. self.index)for i,_rect in pairs(self.objects) doindex = self:getIndex(_rect)if index ~= -1 thenself.nodes[index]:insert(_rect)self.objects[i] = nilelse-- 同时处于多个象限切割矩形仅用于计算 local subArr = rectCarve(_rect, self.bounds)for _,__rect in pairs(subArr) doindex = self:getIndex(__rect)self.nodes[index]:insert(__rect)endself.objects[i] = nilendendend-- 若存在子节点if next(self.nodes) then_insert()returnend-- 如果当前节点存储的数量超过了MAX_OBJECTS 划分为四象限if getTableLen(self.objects) > MAX_OBJ_NUM and self.depth < MAX_DEPTH and self.bounds.cx - self.bounds.x1 > MIN_WIDTHand self.bounds.cy - self.bounds.y1 > MIN_HEIGHT thenself:split()_insert()endend

7、检索方法

--[[检索功能：给出一个物体对象，该函数负责将该物体可能发生碰撞的所有物体选取出来。该函数先查找物体所属的象限，该象限下的物体都是有可能发生碰撞的，然后再递归地查找子象限...]]function QuadTree:retrieve(rect)local result = {}local nodes = self.nodeslocal indexlocal indexL = {}-- 若存在子节点if next(nodes) thenindex = self:getIndex(rect)-- print("getIndex", index)if index ~= -1 thentable.insert(indexL, index)result = tableMerge(result, nodes[index]:retrieve(rect))else-- 同时处于多个象限切割矩形仅用于计算local subArr = rectCarve(rect, self.bounds)for _,_rect in pairs(subArr) doindex = self:getIndex(_rect)table.insert(indexL, index)result = tableMerge(result, nodes[index]:retrieve(_rect))endendend -- 可优化部分，对于在中间节点上，横跨多个象限的节点可以进行具体的条件local objs = clone(self.objects)local cx = self.bounds.cxlocal cy = self.bounds.cyfor _, _index in ipairs(indexL) doif _index == 1 thenfor k,v in pairs(objs) doif v.x + v.width < cx or v.y + v.height < cy thenobjs[k] = nilendendelseif _index == 2 thenfor k,v in pairs(objs) doif v.x > cx or v.y + v.height < cy thenobjs[k] = nilendendelseif _index == 3 thenfor k,v in pairs(objs) doif v.x > cx or v.y > cy thenobjs[k] = nilendendelseif _index == 4 thenfor k,v in pairs(objs) doif v.x + v.width < cx or v.y > cy thenobjs[k] = nilendendendendresult = tableMerge(result, objs)return resultend

3、测试应用

1、矩形相交判断方法

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

2、应用

-- 屏幕sizelocal SCREEN_WIDTH = 1200local 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 dolocal 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) doquadTree:insert(v)end-- 3、循环检测所有可能的碰撞print("------全部遍历----")local function calCollsition(answer)local collisionCount = 0count_times = 0print("\n=========方法" .. answer)if answer == 2 then-- 2) 遍历四叉树象限-- 思路一插入矩形划分象限时，对跨多个象限的矩形特殊处理-- 优点：节省内存空间-- 缺点：花费较多的时间-- 思路二插入矩形划分象限时，考虑直接将跨多个象限的矩形同时划分至其子象限 .07.14 采用此方案-- 优点：易理解，查询碰撞省时间-- 缺点：花费更多内存空间local recordDict = {}local function chechCollision(quadTree)if next(quadTree.nodes) thenfor i,v in pairs(quadTree.nodes) do-- print("递归循环\ndepth：" .. v.depth)-- print("index：" .. i)chechCollision(v, quadTree.objects)endelselocal ret = {}for k,v in pairs(quadTree.objects) doret[#ret+1] = vendfor _index=1,#ret dolocal rect = ret[_index]for __index=_index+1,#ret dolocal otherRect = ret[__index]local index1 = rect.indexlocal index2 = otherRect.indexif (recordDict[index1] and recordDict[index1][index2]) or (recordDict[index2] and recordDict[index2][index1]) thenelseif isCollision(rect, otherRect) thenif isPrint thenprint("\t" .. rect.index .. "与" .. otherRect.index .. "相交")endcollisionCount = collisionCount + 1if recordDict[index1] thenrecordDict[index1][index2] = trueelserecordDict[index1] = {}recordDict[index1][index2] = trueendendendendendendendchechCollision(quadTree)elseif answer == 3 then-- 3) 全部遍历for index=1,#rect_list dolocal rect = rect_list[index]for _index=index+1,#rect_list dolocal otherRect = rect_list[_index]if isCollision(rect, otherRect) thenif isPrint thenprint("\t" .. rect.index .. "与" .. otherRect.index .. "相交")endcollisionCount = collisionCount + 1endendendendprint("计算次数：" .. count_times)print("相交次数：" .. collisionCount)endcalCollsition(2)calCollsition(3)