<-- Home

四叉树与2D游戏碰撞检测

二叉查找树(BST),对一维数组的存储和查找的效率可以达到。四叉树(QuadTree)算是BST的变体,将2D空间递归划分为4个子区域,可以实现对2D空间上点的快速查找。八叉树,用于三维空间中点的快速查找。

四叉树的C++实现:

#include <vector>
#include <list>
#include <memory>

// 2D空间中的一个物体,坐标为(x,y),宽为w,高为h
struct Object {
	float x, y, w, h;
	Object(){}
	Object(float x, float y, float w, float h) {
		this->x = x;
		this->y = y;
		this->w = w;
		this->h = h;
	}
};

// 四叉树类声明
class QuadTree
{
public:
	QuadTree() {};
	QuadTree::QuadTree(float _left, float _right, float _top, float _down, int level);
	~QuadTree();
	void Add(Object& obj);
	void Clear();
	std::vector<Object> GetObjects(float x, float y);
private:
	int MAX_OBJECTS = 20;         // 单个节点存储个数超过该值就分裂出4个子空间
	int MAX_LEVELS = 5;           // 四叉树最大深度

	int level;
	bool isleaf;
	std::list<Object> objects;
	float left, right, top, down;
	std::shared_ptr<QuadTree> nodes[4];
	bool Contains(Object& obj);
	bool Contains(float x, float y);
	void CreateLeaves();
	void MoveObjectsToLeaves();
};
QuadTree::QuadTree(float _left, float _right, float _top, float _down, int _level) :
	left(_left),
	right(_right),
	top(_top),
	down(_down),
	level(_level),
	isleaf(true) {}

// 将对象加入四叉树中
void QuadTree::Add(Object& obj) {
	if (isleaf) {
		objects.push_back(obj);
		if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {
			CreateLeaves();
			MoveObjectsToLeaves();
			isleaf = false;
		}
		return;
	}
	for (auto &i : nodes) {
		if (i->Contains(obj)) {
			i->Add(obj);
			return;
		}
	}
	objects.push_back(obj);
}

// 清空四叉树
void QuadTree::Clear() {
	objects.clear();
	if (!isleaf) {
		for (auto &i : nodes) {
			i->Clear();
		}
		isleaf = true;
	}
}
 
// 分裂出4个子空间
void QuadTree::CreateLeaves() {
	nodes[0] = std::shared_ptr<QuadTree>(new QuadTree(left, (left + right) / 2, top, (top + down) / 2, level + 1));
	nodes[1] = std::shared_ptr<QuadTree>(new QuadTree((left + right) / 2, right, top, (top + down) / 2, level + 1));
	nodes[2] = std::shared_ptr<QuadTree>(new QuadTree(left, (left + right) / 2, (top + down) / 2, down, level + 1));
	nodes[3] = std::shared_ptr<QuadTree>(new QuadTree((left + right) / 2, right, (top + down) / 2, down, level + 1));
}

// 判断对象是否在该空间内
bool QuadTree::Contains(Object& obj) {
	return (obj.x >= left && obj.y >= top && (obj.x + obj.w) <= right && (obj.y + obj.h) <= down);
}

// 判定点是否在空间内
bool QuadTree::Contains(float x, float y) {
	return 	(x >= left && x <= right) && (y >= top && y <= down);
}

// 分裂,将父空间存储的对象移动到子空间,如果该对象能被子空间覆盖则存储在子空间,否则还是存储在父空间
void QuadTree::MoveObjectsToLeaves() {
	for (auto &i : nodes) {
		for (auto it = objects.begin(); it != objects.end();) {
			if (i->Contains(*it)) {
				i->Add(*it);
				it = objects.erase(it);
			}
			else {
				it++;
			}
		}
	}
}

// 根据某点的坐标返回所在的所有空间存储中的对象
std::vector<Object> QuadTree::GetObjects(float x, float y) {
	if(isleaf) {
		return std::vector<Object>(objects.begin(), objects.end());
	}

	std::vector<Object> returnedObjects;

	if (!objects.empty()) {
		returnedObjects.insert(returnedObjects.end(), objects.begin(), objects.end());
	}

	for (auto &i : nodes) {
		if (i->Contains(x, y)) {
			std::vector<Object> childObjects = i->GetObjects(x, y);
			returnedObjects.insert(returnedObjects.end(), childObjects.begin(), childObjects.end());
			break;
		}
	}
	return returnedObjects;
}
QuadTree::~QuadTree()
{

}

将2D游戏空间中的物体存入四叉树之后,进行碰撞检测时,不需要选取所有的物体进行检测,只需选取部分子空间中的物体即可,因为不同空间的物体不可能发生碰撞。

只需要判断玩家与所在矩形内的子弹是否碰撞即可。