精华内容
下载资源
问答
  • http://bbs.9ria.com/thread-243675-1-1.html 转载于:https://www.cnblogs.com/chenhongyu/p/3283165.html

    http://bbs.9ria.com/thread-243675-1-1.html

    转载于:https://www.cnblogs.com/chenhongyu/p/3283165.html

    展开全文
  • 因为蛇的碰撞使用cocos creator中自带的Collider去检测食物和蛇身体,随着游戏的进行就造成了碰撞体越来越多,变得卡顿,查阅了一些资料,了解到了四叉树碰撞检测算法,所以我将游戏整体的检测进行了一下优化。...

    最近公司的小游戏项目贪吃蛇大作战出现了一些优化问题,当游戏玩到后期蛇会变得很长很长,食物也越来越多,游戏就会变得很卡,因为蛇的碰撞使用cocos creator中自带的Collider去检测食物和蛇身体,随着游戏的进行就造成了碰撞体越来越多,变得卡顿,查阅了一些资料,了解到了四叉树碰撞检测算法,所以我将游戏整体的检测进行了一下优化。

    代码参考地址 https://github.com/timohausmann/quadtree-js

    首先研究一下四叉树算法的原理

    QuadTree四叉树顾名思义就是树状的数据结构,其每个节点有四个孩子节点,可将二维平面递归分割子区域。QuadTree常用于空间数据库索引,3D的椎体可见区域裁剪,甚至图片分析处理。QuadTree最常被游戏领域使用到的碰撞检测。采用QuadTree算法将大大减少需要测试碰撞的次数,从而提高游戏刷新性能。

    1.就是把一块2d的区域,等分成四个象限

    2.当更多的对象被添加到四叉树里时,它们最终会被分为四个子节点。将完全处于某一个象限的物体存储在该象限对应的子节点下,当然,也存在跨越多个象限的物体,我们将它们存在父节点中。如果某个象限内的物体的数量过多,它会同样会分裂成四个子象限,以此类推:

    3.上图中右下角区域当蛇(白块表示)处于当前位置,会判断此区域内蛇的矩形所在象限的食物(绿块表示),提取出当前可计算的食物(绿块),进行计算,其他区域的食物(白框格子)不计算。这样就大大减少了计算量

    代码如下:

    class Quadtree {
         
        /*
         * Quadtree Constructor
         * @param Object bounds            bounds of the node { x, y, width, height }
         * @param Integer max_objects      (optional) max objects a node can hold before splitting into 4 subnodes (default: 10)
         * @param Integer max_levels       (optional) total max levels inside root Quadtree (default: 4) 
         * @param Integer level            (optional) deepth level, required for subnodes (default: 0)
         */
        constructor (bounds, max_objects, max_levels, level) {
            
            this.max_objects    = max_objects || 10;
            this.max_levels     = max_levels || 4;
            
            this.level  = level || 0;
            this.bounds = bounds;
            
            this.objects    = [];
            this.nodes      = [];
        };
        
        
        /*
         * Split the node into 4 subnodes
         */
        split = function() {
            
            var nextLevel   = this.level + 1,
                subWidth    = this.bounds.width/2,
                subHeight   = this.bounds.height/2,
                x           = this.bounds.x,
                y           = this.bounds.y;        
         
            //top right node
            this.nodes[0] = new Quadtree({
                x       : x + subWidth, 
                y       : y, 
                width   : subWidth, 
                height  : subHeight
            }, this.max_objects, this.max_levels, nextLevel);
            
            //top left node
            this.nodes[1] = new Quadtree({
                x       : x, 
                y       : y, 
                width   : subWidth, 
                height  : subHeight
            }, this.max_objects, this.max_levels, nextLevel);
            
            //bottom left node
            this.nodes[2] = new Quadtree({
                x       : x, 
                y       : y + subHeight, 
                width   : subWidth, 
                height  : subHeight
            }, this.max_objects, this.max_levels, nextLevel);
            
            //bottom right node
            this.nodes[3] = new Quadtree({
                x       : x + subWidth, 
                y       : y + subHeight, 
                width   : subWidth, 
                height  : subHeight
            }, this.max_objects, this.max_levels, nextLevel);
        };
        
        
        /*
         * Determine which node the object belongs to
         * @param Object pRect      bounds of the area to be checked, with x, y, width, height
         * @return Array            an array of indexes of the intersecting subnodes 
         *                          (0-3 = top-right, top-left, bottom-left, bottom-right / ne, nw, sw, se)
         */
        getIndex = function(pRect) {
            
            var indexes = [],
                verticalMidpoint    = this.bounds.x + (this.bounds.width/2),
                horizontalMidpoint  = this.bounds.y + (this.bounds.height/2);    
    
            var startIsNorth = pRect.y < horizontalMidpoint,
                startIsWest  = pRect.x < verticalMidpoint,
                endIsEast    = pRect.x + pRect.width > verticalMidpoint,
                endIsSouth   = pRect.y + pRect.height > horizontalMidpoint;    
    
            //top-right quad
            if(startIsNorth && endIsEast) {
                indexes.push(0);
            }
            
            //top-left quad
            if(startIsWest && startIsNorth) {
                indexes.push(1);
            }
    
            //bottom-left quad
            if(startIsWest && endIsSouth) {
                indexes.push(2);
            }
    
            //bottom-right quad
            if(endIsEast && endIsSouth) {
                indexes.push(3);
            }
         
            return indexes;
        };
        
        
        /*
         * Insert the object into the node. If the node
         * exceeds the capacity, it will split and add all
         * objects to their corresponding subnodes.
         * @param Object pRect        bounds of the object to be added { x, y, width, height }
         */
        insert = function(pRect) {
            
            var i = 0,
                indexes;
             
            //if we have subnodes, call insert on matching subnodes
            if(this.nodes.length) {
                indexes = this.getIndex(pRect);
         
                for(i=0; i<indexes.length; i++) {
                    this.nodes[indexes[i]].insert(pRect);     
                }
                return;
            }
         
            //otherwise, store object here
            this.objects.push(pRect);
    
            //max_objects reached
            if(this.objects.length > this.max_objects && this.level < this.max_levels) {
    
                //split if we don't already have subnodes
                if(!this.nodes.length) {
                    this.split();
                }
                
                //add all objects to their corresponding subnode
                for(i=0; i<this.objects.length; i++) {
                    indexes = this.getIndex(this.objects[i]);
                    for(var k=0; k<indexes.length; k++) {
                        this.nodes[indexes[k]].insert(this.objects[i]);
                    }
                }
    
                //clean up this node
                this.objects = [];
            }
         };
         
         
        /*
         * Return all objects that could collide with the given object
         * @param Object pRect        bounds of the object to be checked { x, y, width, height }
         * @Return Array            array with all detected objects
         */
        retrieve = function(pRect) {
             
            var indexes = this.getIndex(pRect),
                returnObjects = this.objects;
                
            //if we have subnodes, retrieve their objects
            if(this.nodes.length) {
                for(var i=0; i<indexes.length; i++) {
                    returnObjects = returnObjects.concat(this.nodes[indexes[i]].retrieve(pRect));
                }
            }
    
            //remove duplicates
            returnObjects = returnObjects.filter(function(item, index) {
                return returnObjects.indexOf(item) >= index;
            });
         
            return returnObjects;
        };
        
        
        /*
         * Clear the quadtree
         */
        clear = function() {
            
            this.objects = [];
         
            for(var i=0; i < this.nodes.length; i++) {
                if(this.nodes.length) {
                    this.nodes[i].clear();
                  }
            }
    
            this.nodes = [];
        };    
    }

    使用方法:先创建一个 myFoodTree,再用 insert 方法将所有节点插入到myFoodTree中,通过 retrieve 方法传入蛇头自身的矩形信息,得到相对应的所有食物,在进行计算。

    //创建一个quadtree 初始化蛇头的矩形信息
    initQuadTree(){
        this.myFoodTree = new Quadtree({
             x: 0,
             y: 0,
             width: 1136,
             height: 640
        });
        
        this.snakeHeadRect = {
            x: 0,
            y: 0,
            width: 20,
            height: 20
        };
    
        this.foodList = [];
        for(let i = 0; i < 10; i++){
            this.foodList.push({
                x : this.random(-1136 / 2,1136 / 2),
                y : this.random(-1136 / 2,1136 / 2),
                width : this.random(4, 32),
                height : this.random(4, 32),
            })
        }
    },
    
    //随机
    random: function (min, max) {
        return Math.floor(Math.random() * (max - min + 1) + min)
    },
    
    //将所有食物插入
    insertFood(){
        for(let i = 0;i < this.foodList.length;i++){
             this.myFoodTree.insert({
                 x: foodList[i].x,
                 y: foodList[i].y,
                 width: foodList[i].width,
                 height: foodList[i].height,
             })
        }
    },
    
    //将蛇头的矩形添加参数内 获取可以计算的食物
    checkFoodCollision(){
        var candidates = this.myFoodTree.retrieve(this.snakeHeadRect);
        //TODO..
    },

     

    展开全文
  • 四叉树碰撞检测算法优化

    千次阅读 2016-09-19 16:07:06
    四叉树算法的优点是检测效率和对象数量无关,只和树的深度有关该算法广泛运用在游戏AI搜索,多物体碰撞检测等场合。建树 var levelIndex:int = 0; var columeIndex:int; var rowIndex:int; while(levelIndex ...

    先看一下效果 同屏100个对象
    这里写图片描述

    四叉树算法的优点是检测效率和对象数量无关,只和树的深度有关

    该算法广泛运用在游戏AI搜索,多物体碰撞检测等场合。

    建树

        var levelIndex:int = 0;
                var columeIndex:int;
                var rowIndex:int;
                while(levelIndex < maxTreeLevel){//遍历每一层
                    nColumeCount = 1 << levelIndex;
                    nLeavesTotal = Math.pow(4,levelIndex);//每层叶子结点数量1,4,16,64  4的N次幂
    
                    //构建一个数组,存储每一层的所有子节点  因为第一层是没有父节点的 所以用levelIndex+1
                    aryLeavesArry = treeNodeVec2[levelIndex+1] = new Vector.<QuadNode>(nLeavesTotal,true);
    
                    //节点size
                    nNodeWidth = nMapWidth >> levelIndex;
                    nNodeHeight = nMapHeight >> levelIndex;
    
                    columeIndex = 0;
                    //构建行,列 map
                    while(columeIndex < nColumeCount){
                        rowIndex = 0;
                        //行列值肯定是相等的 比如 1*1 4*4 16*16 64*64
                        while(rowIndex < nColumeCount){
                            vQuadNode = new QuadNode();
                            vQuadNode.left = rowIndex * nNodeWidth;
                            vQuadNode.right = rowIndex * nNodeWidth + nNodeWidth;
                            vQuadNode.top = columeIndex * nNodeHeight;
                            vQuadNode.bottom = columeIndex * nNodeHeight + nNodeHeight;
    
                            //最后一层不用创建子节点 没有孩子了
                            if(levelIndex < maxTreeLevel - 1){
                                vQuadNode.children = new Vector.<QuadNode>();
                            }
    
                            //有孩子的就存起来,这个index可以这样理解,第一层就一个 index = 0
                            //第二层有4个  0,1,2,3
                            //第三层有16个 4,5,6,7,,,,15 推到一下就知道怎么算了 
                            var index:int = columeIndex * nColumeCount + rowIndex; //方格子嘛!
                            vQuadNode.level = levelIndex+1;
                            vQuadNode.index = index;
                            aryLeavesArry[index] =  vQuadNode;
    
                            //关联父子节点 treeNodeVec2[0]是空的,因为第一层是没有父节点的
                            if(treeNodeVec2[levelIndex] != null){
                                var parentIndex:int = index >> 2;//除以四就能算出父节点的index来了,自己画图验证吧
                                vQuadNode.Parent = treeNodeVec2[levelIndex][parentIndex];
                                vQuadNode.Parent.children.push(vQuadNode);//太他妈巧妙了
                            }
                            rowIndex++;
                        }
                        columeIndex++;
                    }
                    levelIndex++;
                }//建树完毕
    
                trace('建树完毕');
    
                //构建个对象池
                proxyPool = new Vector.<QObjBounds>(1<<9,true);
    
                for (var i:int = 0; i < proxyPool.length; i++) 
                {
                    var obj:QObjBounds = new QObjBounds();
                    obj.id = i;
                    obj.nextId =i +1;
                    proxyPool[i] = obj;
                }
    

    优化算法部分,查找结点,采用等比缩放,异或位运算实现快速节点查找

        /**
             * 查找结点 
             * @param p
             * @return 
             * 
             */     
            private function findNode(p:QObjBounds):QuadNode
            {
                // TODO Auto Generated method stub
                //坐标映射到  节点上
                var n_left:int = p.left * m_nScaleW;
                var n_top:int = p.top * m_nScaleH;
                var n_right:int = p.right * m_nScaleW;
                var n_bottom:int = p.bottom * m_nScaleH;
    
                //异或操作  求出对现所在 节点层级  如果不理解,可以把 层级映射成二进制来表示
                var m_nXRange:int = n_left ^ n_right;
                var m_nYRange:int = n_top ^ n_bottom;
    
                var nodeLevel:int = maxTreeLevel;
                while((m_nXRange + m_nYRange) !=0){
                    m_nXRange = m_nXRange >> 1;
                    m_nYRange = m_nYRange >> 1;
                    nodeLevel -- ;
                }
                if(nodeLevel == 0){
                    trace("daddsd");
                }
    
                if(nodeLevel == 0)nodeLevel =1;
                //这里为啥要有移位,很多同学不理解,举个例子 
                //例如 一个深度是3的四叉树 上面的 top left 都是基于最高层级去算的 
                //也就是第三层,那么你算出来发现显示对象在第二层,
                //就需要我们把当前的top,left缩放到第二层的大小,
                //再根据 列数 * 维度 + 行数 求出索引,缩放多少层呢  就是下面的差
                var m_nShiftCount:int = maxTreeLevel - nodeLevel;
                n_left = n_left >> m_nShiftCount;
                n_top = n_top >> m_nShiftCount;
    
                //找到层级后,接着找具体的节点索引 
                //索引  = 列数 * 维度 + 行数    比如 3层  16个节点的树  当代理对象在第15个空间中
                // 行数 = 4 列数 = 3 维度 4*4 
                //          if(nodeLevel == 0)nodeLevel =1;
                var weishu:int = 1 << (nodeLevel - 1);
                var index:int =  n_top * weishu + n_left;
                var quadNode:QuadNode = treeNodeVec2[nodeLevel][index];
                return quadNode;
            }
    
    
    碰撞检测
    
    /**
         * 检测碰撞 
         * 
         */     
        private function checkCollision(checkObj:QObjBounds):void
        {
            // TODO Auto Generated method stub
            var vNode:QuadNode;
            var nextObj:QObjBounds;
            var preObj:QObjBounds;
    
            vNode = checkObj.node;
            var nodeLevel:int = vNode.level;
    
            //检测当前结点对象
            nextObj = checkObj.nextInNode;
            while(nextObj){
                if(checkObj.intersect(nextObj)){
                    //                  nextObj.color = 0xFFFF00FF;
                    //                  checkObj.color = 0xFFFF00FF;
                    nextObj.isCollision = checkObj.isCollision = true;
                }
                nextObj = nextObj.nextInNode;
            }
    
            //检查 跨越所有子节点
            var level:int = maxTreeLevel;
            var nLineStart:int= checkObj.left*m_nScaleW;
            var nLineEnd:int = checkObj.right*m_nScaleW;
            var nColumeStart:int = checkObj.top*m_nScaleH;
            var nColumeEnd:int = checkObj.bottom*m_nScaleH;
    
            while(level!=0){
                for (var i:int = nColumeStart; i <= nColumeEnd; i++) 
                {
                    for (var j:int = nLineStart; j <= nLineEnd; j++) 
                    {
                        var index:int =int( i * (1 << (level -1)))+j;
                        vNode = treeNodeVec2[level][index];
    
                        //检测当前结点对象
                        nextObj = vNode.proxyListHead;
                        while(nextObj){
                            if(nextObj != checkObj){//当前检测的不是原来的
                                if(checkObj.intersect(nextObj)){
                                    //                                  nextObj.color = 0xFFFF00FF;
                                    //                                  checkObj.color = 0xFFFF00FF;
                                    nextObj.isCollision = checkObj.isCollision = true;
                                }
                            }
                            nextObj = nextObj.nextInNode;
                        }
                    }
                }
                //缩小包围圈
                nLineStart>>=1;
                nLineEnd>>=1;
                nColumeStart>>=1;
                nColumeEnd>>=1;
                level --;
                if(nodeLevel == level)break;
            }
    
        }
    

    “`

    源码及问题请留言或联系作者

    展开全文
  • 四叉树优化碰撞检测

    2017-03-27 15:41:56
    游戏中碰撞检测分为两个阶段:broad phase 和 narrow phase。...在broad phase这个阶段,我们的主要任务是将屏幕上的物体进行筛选,筛选出最可能发生碰撞的物体集合。 试想想,屏幕上有N个物体,

    原文地址:http://blog.csdn.net/qq276592716/article/details/45999831

    游戏中碰撞检测分为两个阶段:broad phase 和 narrow phase。接下来要介绍的就是broad phase。在broad phase这个阶段,我们的主要任务是将屏幕上的物体进行筛选,筛选出最可能发生碰撞的物体集合。

    试想想,屏幕上有N个物体,如果我们对每两个物体都进行碰撞检测,那时间复杂度就有N^2。但实际上,在游戏画面中,并不是每两个物体都需要进行碰撞检测,比如一个在屏幕右上方的物体和一个在屏幕左上方的物体之间明显是不会发生碰撞的,所以我们不需要对这两个物体进行碰撞检测。那么,现在我们就需要一个这样的算法去将屏幕上可能和不可能发生碰撞的物体区分开来。

    四叉树原理

    正如其名,四叉树就是每个父节点都具有四个子节点的树状数据结构。由于要区分屏幕上的物体,我们要将屏幕划分为四个区域,所以四叉树的四个节点正合适表示这四个区域。

    屏幕上四个区域分别为:左上区域 + 右上区域 + 右下区域 + 左下区域,方便起见,我们分别命名为:象限1、象限2、象限3、象限4:

    屏幕向量

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

    四叉树结构

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

    子象限

    实现四叉树

    我们先定义四叉树的结构:

    /* 
      四叉树节点包含:
      - objects: 用于存储物体对象
      - nodes: 存储四个子节点
      - level: 该节点的深度,根节点的默认深度为0
      - bounds: 该节点对应的象限在屏幕上的范围,bounds是一个矩形
    */
    var QuadTree = function QuadTree(bounds, level) {
        this.objects = [];
        this.nodes = [];
        this.level = typeof level === 'undefined' ? 0 : level;
        this.bounds = bounds;
    }
    
    /*
      常量:
      - MAX_OBJECTS: 每个节点(象限)所能包含物体的最大数量
      - MAX_LEVELS: 四叉树的最大深度
    */
    QuadTree.prototype.MAX_OBJECTS = 10;
    QuadTree.prototype.MAX_LEVELS = 5;
    

    接下来,我们需要判断屏幕上的物体属于哪个象限:

    /* 
      获取物体对应的象限序号,以屏幕中心为界限,切割屏幕:
      - 右上:象限一
      - 左上:象限二
      - 左下:象限三
      - 右下:象限四
    */
    QuadTree.prototype.getIndex = function(rect) {
        var bounds = this.bounds,
            onTop = rect.y + rect.height <=  bounds.centroid.y,
            onBottom = rect.y >= bounds.centroid.y,
            onLeft = rect.x + rect.w <= bounds.centroid.x,
            onRight = rect.x >= bounds.centroid.x;
    
        if (onTop) {
            if (onRight) {
                return 0;
            } else if (onLeft) {
                return 1;
            }
        } else if (onBottom) {
            if (onLeft) {
                return 2;
            } else if (onRight) {
                return 3;
            }
        }
    
        // 如果物体跨越多个象限,则放回-1
        return -1;
    };
    

    我们知道,如果某一个象限(节点)内存储的物体数量超过了MAX_OBJECTS最大数量,则需要对这个节点进行划分,所以我们同样需要一个划分函数,它的工作就是将一个象限看作一个屏幕,将其划分为四个子象限:

    // 划分
    QuadTree.prototype.split = function() {
        var level = this.level,
            bounds = this.bounds,
            x = bounds.x,
            y = bounds.y,
            sWidth = bounds.width / 2,
            sHeight = bounds.height / 2;
    
        this.nodes.push(
            new QuadTree(new Rect(bounds.centroid.x, y, sWidth, sHeight), level + 1),
            new QuadTree(new Rect(x, y, sWidth, sHeight), level + 1),
            new QuadTree(new Rect(x, bounds.centroid.y, sWidth, sHeight), level + 1),
            new QuadTree(new Rect(bounds.centroid.x, bounds.centroid.y, sWidth, sHeight), level + 1)
        );
    };
    

    为了初始化四叉树,我们也需要实现四叉树的插入功能,用于将物体插入到四叉树中:

    /*
      插入功能:
        - 如果当前节点[ 存在 ]子节点,则检查物体到底属于哪个子节点,如果能匹配到子节点,则将该物体插入到该子节点中
        - 如果当前节点[ 不存在 ]子节点,将该物体存储在当前节点。随后,检查当前节点的存储数量,如果超过了最大存储数量,则对当前节点进行划分,划分完成后,将当前节点存储的物体重新分配到四个子节点中。
    */
    QuadTree.prototype.insert = function(rect) {
        var objs = this.objects,
            i, index;
    
        // 如果该节点下存在子节点
        if (this.nodes.length) {
            index = this.getIndex(rect);
            if (index !== -1) {
                this.nodes[index].insert(rect);
                return;
            }
        }
    
        // 否则存储在当前节点下
        objs.push(rect);
    
        // 如果当前节点存储的数量超过了MAX_OBJECTS
        if (!this.nodes.length &&
            this.objects.length > this.MAX_OBJECTS &&
            this.level < this.MAX_LEVELS) {
    
            this.split();
    
            for (i = objs.length - 1; i >= 0; i--) {
                index = this.getIndex(objs[i]);
                if (index !== -1) {
                    this.nodes[index].insert(objs.splice(i, 1)[0]);
                }
            }
        }
    };
    

    筛选功能

    重头戏来啦!现在我们已经能够初始化一个四叉树了,接下来我们要解决——如何将可能发生碰撞的物体集合选取出来:

    /*
      检索功能:
        给出一个物体对象,该函数负责将该物体可能发生碰撞的所有物体选取出来。该函数先查找物体所属的象限,该象限下的物体都是有可能发生碰撞的,然后再递归地查找子象限...
    */
    QuadTree.prototype.retrieve = function(rect) {
        var result = [],
            index;
    
        if (this.nodes.length) {
            index = this.getIndex(rect);
            if (index !== -1) {
                resutl = result.concat(this.nodes[index].retrieve(rect));
            }
        }
    
        result = result.concat(this.objects);
    
        return result;
    };
    

    咋一看,这个函数貌似没什么问题,但是我们知道,并不是所有物体都恰好完全属于某一个象限的,比如有个物体跨越了象限一和象限二:

    不属于任何象限的矩形

    一眼就能看出来,矩形6可能发生碰撞的物体集合包括:矩形1、矩形2和矩形5。而我们实现的retrive函数筛选出来的集合则是为空,显然是不正确的,我们需要改进这块代码。

    为了让跨越多个象限的物体也能递归地执行retrive函数,从而找到所有可能碰撞的物体集合,我们需要让这个物体同时属于这些象限。

    以矩形6为例,我们如何让矩形6同时属于象限二和象限三呢?我们的做法是:以象限的边界为切割线,将矩形6切割为两个子矩形。我们能够确定的是:这两个子矩形分别属于象限二和象限三,所以我们能用这两个子矩形递归的调用retrive函数,从而找到所有可能碰撞的物体集合。

    分裂递归

    改进后的retrive函数:

    // 检索
    QuadTree.prototype.retrieve = function(rect) {
        var result = [],
            arr, i, index;
    
        if (this.nodes.length) {
            index = this.getIndex(rect);
            if (index !== -1) {
                resutl = result.concat(this.nodes[index].retrieve(rect));
            } else {
    
                // 切割矩形
                arr = rect.carve(this.bounds);
    
                for (i = arr.length - 1; i >= 0; i--) {
                    index = this.getIndex(arr[i]);
                    resutl = result.concat(this.nodes[index].retrieve(rect));
    
                }
            }
        }
    
        result = result.concat(this.objects);
    
        return result;
    }
    

    动态更新

    我们已经实现了四叉树全部的功能,先介绍一下四叉树的用法。

    首先创建一个四叉树:

    var tree = new Quadtree(new Rect(0, 0, 1000, 500));
    

    接下来,我们需要初始化四叉树,我们将屏幕上的所有物体都插入到这个四叉树中:

    var rectsArr = [/* ... */];
    rectsArr.forEach(function(rect) {
        tree.insert(rect);
    });
    

    一棵四叉树已经初始化完成,我们调用retrive找出每个物体对应的碰撞物体集合,并进行下一步的narrow phase部分的碰撞检测了:

    rectsArr.forEach(function(rect) {
        var result = tree.retrive(rect);
        result.forEach(function() {
            // norrow phase部分的碰撞检测...
        });
    })
    

    我们现在知道四叉树的使用方法了,但同时我们也注意到一个问题:由于屏幕的物体是运行的,前一秒在象限一的物体可能下一秒就跑到象限二了,所以每一帧都需要重新初始化四叉树。这意味着,每16ms就要初始化一次四叉树,这个代价太大,太得不偿失了:

    var run = function run() {
        // 重新向四叉树中插入所有物体,重新初始化四叉树
        // ...
    
        // 筛选物体集合并进行碰撞检测
        // ...
    
        requestAnimationFrame(run);
    };
    
    requestAnimationFrame(run);
    

    我们想想,是不是有这样做的必要?实际上,只是部分物体从一个象限跑到另一个象限,而其他物体都是保持在原先象限中,所以我们只需要重新插入这部分物体即可,从而避免了对所有物体进行插入操作。

    我们为四叉树增添这部分的功能,其名为动态更新:

    // 判断矩形是否在象限范围内
    function isInner(rect, bounds) {
        return rect.x >= bounds.x &&
            rect.x + width <= bounds.x + bounds.width &&
            rect.y >= bounds.y &&
            rect.y + rect.height <= bounds.y + bounds.height;
    }
    
    /*
      动态更新:
        从根节点深入四叉树,检查四叉树各个节点存储的物体是否依旧属于该节点(象限)的范围之内,如果不属于,则重新插入该物体。
    */
    QuadTree.prototype.refresh = function(root) {
        var objs = this.objects,
            rect, index, i, len;
    
        root = root || this;
    
        for (i = objs.length - 1; i >= 0; i--) {
            rect = objs[i];
            index = this.getIndex(rect);
    
            // 如果矩形不属于该象限,则将该矩形重新插入
            if (!isInner(rect, this.bounds)) {
                if (this !== root) {
                    root.insert(objs.splice(i, 1)[0]);
                }
    
            // 如果矩形属于该象限 且 该象限具有子象限,则
            // 将该矩形安插到子象限中
            } else if (this.nodes.length) {
                this.nodes[index].insert(objs.splice(i, 1)[0]);
            }
        }
    
        // 递归刷新子象限
        for (i = 0, len = this.nodes.length; i < len; i++) {
            this.nodes[i].refresh(root);
        }
    }; 
    

    现在有了动态更新功能,每一帧中只需要对该四叉树进行动态更新即可:

    var run = function run() {
        // 动态更新
        tree.refresh();
    
        // 筛选物体集合并进行碰撞检测
        // ...
    
        requestAnimationFrame(run);
    };
    
    requestAnimationFrame(run);
    

    以上。


    展开全文
  • 使用四叉树优化碰撞检测

    千次阅读 2020-06-18 12:26:56
    四叉树是干什么的? 百度百科 元树又称四叉树是一种...使用四叉树就是使用分类的方法,减少碰撞节点的个数,只取出与给定碰撞体相同区域或者压在碰撞体所在区域边上的对象。 将游戏屏幕分为个区域。 插入对象
  • 这里我们学习一下使用四叉树来对碰撞检测进行优化优化的根本是碰撞检测时跳过那些明显离得很远的物体,加快检测速度。【注:这里算法的实现使用的Java语言,但算法和语言没有关系,理解了其中的原理可以应用到各种...
  • 腾讯游戏学院有一篇四叉树优化碰撞检测的文章,不过是js版本的,感觉思路写得挺清晰的,所有想翻译成lua来以备不时之需。 不过翻译过程发现挺多问题的,虽然思路很清晰,但细节照它那样写会有问题,有兴趣的人也可以...
  • Cocos Creator | 碰撞检测优化-四叉树

    千次阅读 2020-07-12 11:12:01
    首先说明下四叉树并不是一个碰撞引擎,它只是一种减少碰撞候选者的算法,所以在利用四叉树得到碰撞候选元素后,还需要去检测这些候选元素与目标元素是否发生碰撞 2D中是四叉树,3D中则对应的为八叉树 项目...
  • 【步兵 cocos2dx】四叉树碰撞算法 by EOS.四叉树碰撞网上例子不少,自己也观摩了一下,然后自己写了一个。 并不是想证明自己写的比别人好,不自己写一遍,总感觉自己不认识它。 写过之后感觉,深入了解,并且自己...
  • 碰撞检测优化-四叉树

    2021-03-24 15:20:05
    2.检索的对象比较多时,四叉树检索效率明显优于暴力检索。 3.四叉树检索增加了不少的内存开销。 演示代码 index.html <body style="margin: 0px;"> <button style="position: fixed; margin-top: 70px...
  • 直接上效果图图中: 绿色圆为玩家的位置(运行后发现是会跟随鼠标位置的) 绿色矩形为当前镜头视野 ...运行后,用鼠标控制玩家的位置源码工程IDEA的AS3四叉树源码测试工程参考场景管理:四叉树算法C++实现
  • OBB碰撞四叉树优化

    2020-04-17 13:02:30
    项目最近在移植lua,考虑到后续会用到帧同步,就自告奋勇,尝试写一下碰撞系统,原来实现过AABB的碰撞,OBB碰撞就是在AABB的碰撞上加了个旋转,可理解为有向的AABB(AABB为轴对其,可理解为在同一坐标系中,各碰撞的...
  • 四叉树-2D平面的渲染剔除、碰撞次数优化-附件资源

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,746
精华内容 1,098
关键字:

四叉树碰撞优化