RTS游戏开发：基于四叉树的平面管理系统【加源码】

目录

为什么要有四叉树？

四叉树的思路。

四叉树源码。

为什么要有四叉树？

有一个算法名为flocking算法，作用是让一群单位模拟群行为的，这意味着每一个单位都需要获取周围邻居的信息，这里我们可以很容易地想到两重for循环来遍历，但是这样的时间复杂度是o(n^2)，是我们接受不了的，所以我们就迫切需要一种数据结构来优化这一情景，很显然四叉树可以胜任，他可以用o(2*logn)的时间复杂度来寻找邻居对象和删除指定对象，用o(2*n*logn)的时间复杂度来为一群对象构建树，用o(n)的时间复杂度clear；

四叉树的思路。

 我们可以看上面这副图，可以发现，我们将一个区域划分4等分，并对其中一部分划分出来的区间再进行划分，形成一个递归过程。

我们将一个区域划分成多个子区域，并在子区域中存储对象，一个区域的对象只与存储该对象的长辈区域【包含该区域的区域被称为该区域的长辈区域】和本区域以及晚辈区域【被该区域包含的区域被成为该区域的晚辈区域】的对象进行距离比较，如果距离满足，那么我们就视为其为邻居对象；

经过这么一个区域划分，我们可以忽略掉大部分不可能成为该对象的邻居对象的对象，因为是采用了二分的思路，所以查询效率是非常高的；

四叉树在游戏中的运用主要是获取某一片区域中的对象，比如RTS游戏中的框选单位；

四叉树的源码解析。

实现我们先定义节点

template<class T>
class QTreeNode {
public:QTreeNode<T>* son[4];//该节点的4个孩子节点QTreeNode<T>* Father;//该节点的父节点std::list<T*> Data;//该节点存储对象的容器SquareArea<float> Bound;//区域QTreeNode(SquareArea<float> bound):Bound(bound) {for (int i = 0; i < 4; i++) {son[i] = nullptr;}}QTreeNode(){}/*Quadrant3 20 1*/void InstantiateNode() {//将区级分裂Pair<float> P1(Bound.BottomLeft.X, Bound.BottomLeft.Y + Bound.H / 2);Pair<float> P2(Bound.BottomLeft.X + Bound.W / 2, Bound.BottomLeft.Y);Pair<float> P3(Bound.Center.X, Bound.Center.Y + Bound.H / 2);Pair<float> P4(Bound.Center.X + Bound.W / 2, Bound.Center.Y);son[0] = new QTreeNode(SquareArea<float>(P1, P2));son[1] = new QTreeNode(SquareArea<float>(Bound.Center, Bound.BottomRight));son[2] = new QTreeNode(SquareArea<float>(P3, P4));son[3] = new QTreeNode(SquareArea<float>(Bound.TopLeft, Bound.Center));}~QTreeNode() {}};

其中SquareArea是已经写好的一个矩形区域类，主要作用是描绘平面空间中的一个矩形。

然后是四茶树管理类

template<class T>
class QTree {QTreeNode<T>* Head;int MaxData;//默认为1，为1时效率高int PretreatmentDeep;//预处理深度，这里可以选择性地调用，作用是先将区间划分n次，而且这些区间不存储对象，这种行为在某些情况下可以增加效率，在某些情况下会降低效率，这里本菜没有过多的研究SquareArea<float> TreeBound;//这个四叉树所覆盖的区域，也就是头节点所代表的矩形void pushBody(QTreeNode<T>* Node, T* Data, int Deep = 0);void extractBody(QTreeNode<T>* Node,SquareArea<float>* Bound, std::list<T*>* List);void extractBody(QTreeNode<T>* Node, CircularArea<float>* Bound, std::list<T*>* List);void clearBody(QTreeNode<T>* Node);
public:void Pretreatment(int Deep = 0) {//预处理if (Deep < PretreatmentDeep && Nodes->son[0] == nullptr) {Nodes->InstantiateNode();for (int i = 0; i < 4; i++) {Pretreatment(Deep + 1);}}}QTree(SquareArea<float> Bound,int Deep);void push(T* Data) { pushBody(Head, Data, 0); }//insert operatestd::list<T*> extract(SquareArea<float>* Bound){//提取一个矩形区间的对象std::list<T*> *List = new std::list<T*>();extractBody(Head, Bound, List);return List;}std::list<T*> extract(CircularArea<float>* Bound) {//提取一个圆形区域的对象std::list<T*> *List = new std::list<T*>();extractBody(Head, Bound, List);return List;}void clear() {//清除操作clearBody(Head);Head = new QTreeNode<T>(TreeBound);}void SetTreeBound(SquareArea<float> Bound) {//设置这个树所覆盖的区间Head->Bound = Bound;TreeBound = Bound;}~QTree() { clear(); }
};

下面是具体的代码实现；

插入代码的思路如下【这里考虑的是每个节点只存储一个对象】：

1、2、3ifelse语句

1：区间的孩子节点是否是空

• 是，进入2
• 不是，检测该区间的子区间是否与该对象有交集
  • 有交集，那么我们进入该区间所代表的节点，进行1操作 
  • 无交集，查询下一个子区间，如果查询完毕，返回上一层节点

2：该区间是否满了

•  满了，将该区间进行分割，并查询子区域是否与对象有交集；
  • 有交集，那么我们进入该区间所代表的节点，进行1操作 
  • 无交集，查询下一个子区间，如果查询完毕，返回上一层节点
• 没有满，进行3

3：将对象插入该节点，并返回上一个节点

提取的思路如下【这里考虑的是每个节点只存储一个对象】；

1：将该节点的对象放入到容器中，进行2

2：该节点的子节点是否为空

• 是，返回上一个节点
• 不是，进行3

3：查询该区域的子区域是否与该对象有交集

• 有，进入该节点，进行1
• 没有，查询下一个节点，如果查询完毕，返回上一层节点

clear操作的话，就不多介绍了，就是一个dfs进行后序遍历

template<class T>
void QTree<T>::pushBody(QTreeNode<T>* Node,T* Data,int Deep) {//When the MaxDeep is reached,insert directly//这里我选择不设置深度限制，并且不考虑预处理深度if (Node->Son[i]!=nullptr) {for (int i = 0; i < 4; i++) {if (IsInterSectSS(Node->Son[i]->Bound, Data.Bound)) {pushBody(Node->Son[i], Data, Deep + 1);}}}else if (Node->Data.size() >= MaxData) {Node->InstantiateNode();for (int i = 0; i < 4; i++) {if (IsInterSectSS(Node->Son[i]->Bound, Data.Bound)) {pushBody(Node->Son[i], Data, Deep + 1);}}}else if (Node->Data.size() < MaxData) {Node->Data.push_back(Data);}}template<class T>
void QTree<T>::extractBody(QTreeNode<T>* Node,SquareArea<float>* Bound, std::list<T*>* List) {for (auto t = Node->Data.begin(); t != Node->Data.end(); t++) {List->push_back(*t);}//如果子节点是if (Node->Son[0] == nullptr) return;//看4个象限是否与之有交集，如果有交集，那么我们就进入for (int i = 0; i < 4; i++) {if (IsInterSectSS(Node->Son[i]->Bound, Bound))//如果有交集extractBody(Node->Son[i], Bound, List);}}template<class T>
void QTree<T>::extractBody(QTreeNode<T>* Node, CircularArea<float>* Bound, std::list<T*>* List) {for (auto t = Node->Data.begin(); t != Node->Data.end(); t++) {List->push_back(*t);}//如果子节点是if (Node->Son[0] == nullptr) return;//看4个象限是否与之有交集，如果有交集，那么我们就进入for (int i = 0; i < 4; i++) {if (IsInterSectSC(Node->Son[i]->Bound, Bound))//如果有交集extractBody(Node->Son[i], Bound, List);}}template<class T>
void QTree<T>::clearBody(QTreeNode<T>* Node) {if (Node == nullptr) return;for (int i = 0; i < 4; i++) {clearBody(Node->Son[i]);}delete Node;return;
}template<class T>
QTree<T>::QTree(SquareArea<float> Bound,int Deep=3) {//预处理深度，默认5TreeBound = Bound;Head = new QTreeNode<T>(Bound);MaxData = 1;PretreatmentDeep = 3;
}