树(简单应用-四叉树)

《树(简单应用-四叉树)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树的简单应用四叉树问题提出请看这幅图问题在上面的这幅图中，总共有1000个小球在做随机移动。如何检测其两两之间是否相撞？用两重循环，将每个小球取出做检测，如果有1000个小球，没有优化的情况下意味着每帧要做1000*1000=1000000次碰撞检测，效率低了点！那么怎样解决这个问题？四叉树四叉树是一种树状数据结构在每一个节点上会有四个子区块.四叉树常应用于二维空间资料的分析与分类.将资料区分成为四个象限.资料范围可以是方形或矩形或其他任意形状这种数据结构是由拉斐尔·芬科尔(RaphaelFinkel)与J.L.Bentley在1974年发展出来.类似的资料分割方法也称为Q-tre

2、e.所有的四叉树有共同之特点:可分解成为各自的区块每一个区块可持续分解直到资料无法分解为止树状数据结构依造四叉树法加以区分如下图在游戏中应用四叉树为什么在游戏中我们要用4叉树代替一般的遍历查找呢?它的优越性主要在于能在大规模对象队列中快速的查找到你想要的内容。其实现的原理是分治，把游戏中的对象按照一定的规则划分成一小块一小块有组织的集合，这样就把大规模的问题划分成遍历每一小块区域的问题，从而提高了速度。下面我们采用四叉树来解决前面所提到的问题。在使用四叉树之前，一种方法是事先在内存中把四叉树建好，其创建的原则是屏幕区域按照坐标系划分成四个象限。然后对每个象限在做递归的划分。如下图当

3、递归到足够的层次，建树的过程就完成了。当四叉树建立好了后，就可以将屏幕上的小球划归到对应的结点中。如果建树的层次恰当，那么每个叶子结点所包含的小球树相对较少，一般2~5个。一般是在同一个叶子节点中的小球才能发生碰撞，而每个叶子节点检查是相对较快，如果按平均2个小球算，一个叶节点就只需要2x2=4次，假设树有5层，那么总共会有1024个节点，那么检查碰撞的次数是1024x4=4096，比前面的1000000次检测要少很多。当然四叉树还有其它的消耗，比如，小球移动，就涉及到小球需要重新划归到某个叶子节点的操作，但是其总体效率还是比循环检查要高出许多。创建四叉树如何编写一个四叉树类CQu

4、adTree来创建、管理四叉树，请大家思考。一般情况下，树的存储采用链式存储，四叉树也不例外。那么，链式存储时，首先考虑的是结点的定义，通过分析，我们可以定义节点如下：structTreeNode{vectorlistSprites;//存储ItemTreeNode*pChildren[4];boolhasChildren;RECTrect;};下面考虑定义CQuadTree类来管理四叉树。CQuadTree要实现的功能，不外乎是：创建树增加Item删除Item更新树检测碰撞所以CQuadTree类可以定义如下：classCQuadTree{public:CQu

5、adTree(void);public:~CQuadTree(void);public:voidCreateTree(TreeNode*pRoot,RECT&rect);boolAddItem(TreeNode*pNode,CSprite*pSprite);boolRemoveItem(TreeNode*pNode,CSprite*pSprite);intCollisionDetection();intUpdate();private:intnLevel;//当前层constintnLevels;//总计多少层RECTrect;//顶层矩形范围TreeNode*pRoot;//根结

6、点intnCount;//记录碰撞的小球数目listlistLeaves;//记录所有的叶子节点vectorvecSprites;//记录所有精灵};创建树此处创建的四叉树是一棵平衡的四叉树，除了叶结点外，其余每个节点都有4棵子树。请思考，如何创建这样一棵四叉树。这里可以采用层次遍历的方法来创建这棵四叉树。使用层次遍历时，将用到队列帮助我们创建树。其伪代码如下：voidCQuadTree::CreateTree(TreeNode*pRoot,RECT&rect){if(pRoot==NULL){return;}this->pRoot=pRo

7、ot;nLevel=1;nCount=0;定义队列q;将根节点入对while(q非空){TreeNode*pParent=队头节点依次为pParent创建4个子节点为每个子结点设置好它们各成员（特别是rect)将每个子结点入队列nCount+=4;if(nCount>=该层的结点数){nLevel++;nCount=0;}pParent->hasChildren=true;}}增加Item增加Item的过程是从根据Item所在的矩形范围从根结点递归到相应叶子结点的过程