树(简单应用-四叉树).pptVIP

树的简单应用,四叉树,问题提出,请看这幅图,问题,在上面的这幅图中，总共有1000个小球在做随机移动。如何检测其两两之间是否相撞？,用两重循环，将每个小球取出做检测，如果有1000个小球，没有优化的情况下意味着每帧要做1000 * 1000 = 1000000次碰撞检测，效率低了点！ 那么怎样解决这个问题？,四叉树,四叉树是一种树状数据结构在每一个节点上会有四个子区块. 四叉树常应用于二维空间资料的分析与分类. 将资料区分成为四个象限. 资料范围可以是方形或矩形或其他任意形状 这种数据结构是由 拉斐尔芬科尔(Raphael Finkel) 与 J.L. Bentley 在1974年发展出来 . 类似的资料分割方法也称为 Q-tree. 所有的四叉树有共同之特点:,可分解成为各自的区块 每一个区块可持续分解直到资料无法分解为止 树状数据结构依造四叉树法加以区分 如下图,在游戏中应用四叉树,为什么在游戏中我们要用4叉树代替一般的遍历查找呢?它的优越性主要在于能在大规模对象队列中快速的查找到你想要的内容。其实现的原理是分治，把游戏中的对象按照一定的规则划分成一小块一小块有组织的集合，这样就把大规模的问题划分成遍历每一小块区域的问题，从而提高了速度。,下面我们采用四叉树来解决前面所提到的问题。 在使用四叉树之前，一种方法是事先在内存中把四叉树建好，其创建的原则是屏幕区域按照坐标系划分成四个象限。 然后对每个象限在做递归的划分。 如下图,当递归到足够的层次，建树的过程就完成了。 当四叉树建立好了后，就可以将屏幕上的小球划归到对应的结点中。 如果建树的层次恰当，那么每个叶子结点所包含的小球树相对较少，一般25个。 一般是在同一个叶子节点中的小球才能发生碰撞，而每个叶子节点检查是相对较快，如果按平均2个小球算，一个叶节点就只需要2x2 =4 次，假设树有5层，那么总共会有1024个节点，那么检查碰撞的次数是 1024 x 4 = 4096，比前面的1000000次检测要少很多。 当然四叉树还有其它的消耗，比如，小球移动，就涉及到小球需要重新划归到某个叶子节点的操作，但是其总体效率还是比循环检查要高出许多。,创建四叉树,如何编写一个四叉树类CQuadTree来创建、管理四叉树，请大家思考。,一般情况下，树的存储采用链式存储，四叉树也不例外。 那么，链式存储时，首先考虑的是结点的定义，通过分析，我们可以定义节点如下：,struct TreeNode vector listSprites;/存储Item TreeNode *pChildren4; bool hasChildren; RECT rect; ;,下面考虑定义CQuadTree类来管理四叉树。 CQuadTree要实现的功能，不外乎是： 创建树 增加Item 删除Item 更新树 检测碰撞 所以CQuadTree类可以定义如下：,class CQuadTree public: CQuadTree(void); public: CQuadTree(void); public: void CreateTree(TreeNode *pRoot,RECT ,private: int nLevel; /当前层 const int nLevels; /总计多少层 RECT rect; /顶层矩形范围 TreeNode *pRoot; /根结点 int nCount; /记录碰撞的小球数目 list listLeaves; /记录所有的叶子节点 vector vecSprites; /记录所有精灵 ;,创建树,此处创建的四叉树是一棵平衡的四叉树，除了叶结点外，其余每个节点都有4棵子树。请思考，如何创建这样一棵四叉树。,这里可以采用层次遍历的方法来创建这棵四叉树。使用层次遍历时，将用到队列帮助我们创建树。 其伪代码如下：,void CQuadTree:CreateTree(TreeNode * pRoot,RECT 将根节点入对 while(q非空) TreeNode *pParent = 队头节点,依次为pParent创建4个子节点 为每个子结点设置好它们各成员（特别是rect) 将每个子结点入队列 nCount += 4; if (nCount = 该层的结点数) nLevel +; nCount = 0; pParent-hasChildren = true; ,增加Item,增加Item的过程是从根据Item所在的矩形范围从根结点递归到相应叶子结点的过程。 其伪代码如下：,bool CQuadTree:AddItem(TreeNode *pNode,CSprite *pSprite) if （pSprite 在这个结点所持有的矩形范围里） if (是叶子结点) 将Item添加到该结点的数据数组中 return true; else ,/递归查询四个子结点是否可以添加该Item for(int i=0;i4;i+) if (子结点添加Item成功) return true; return false; ,删除Item,删除Item的方法和增加Item方法类似，都需要递归到相应的子结点，删除相应的条目,更新树,更新树的操作是发生在小球移动的时候。因为小球的移动导致它可能不在原来的叶节点上，而到了其他叶结点。因为这里所有的小球都在移动，所以需要更新所有的小球。 其伪代码如下：,int CQuadTree:Update() 用于存储小球的容器vecSprites清零 循环遍历所有叶子节点 将每个叶子结点的Item放入vecSprites; 将每个叶子结点的listSprites清零 循环取vecSprites容器中的每个Item 调用AddItem函数将其放入到合适叶结点中 返回更新了的Item个数 ,碰撞检测,碰撞检测一般发生在叶子结点内部，所以碰撞检测的方法是将每个叶子结点中的Item取出做两两比较 其伪