게임제작기법연구 8주차

QuadTree란.

위 사진과 같이 부모 노드가 자식 노드를 4개 씩 가지고 있는 트리구조이며, 우리가 흔히 사분면이라 부르는 2차원 직교좌표평면을 그대로 1, 2, 3, 4사분면으로 나눈 것이라 보면 된다.

 

만약 물체가 2개 이상의 사분면에 걸치지 않았을 경우에는 그 물체가 있는 사분면(예를들어 1사분면이라 해보자)을 다시 4등분으로 나누어서 2개 이상의 사분면에 걸칠 때 까지 분할한다.

 

이 트리의 장점은 내 생각엔 크기가 아무리 거대한 지형이라도 탐색하는 속도는 매우 빠를것이라고 생각한다.

(계속 4개의 자식노드로 분할하여 탐색하기 때문에)

 

QuadTree의 클래스 구조

#pragma once

enum Sect
{
	NW = 0,
	NE = 1,
	SW = 2,
	SE = 3,	
	NONE
};
class Quadtree
{
public:
	Quadtree(const Rectangle& rect) : _rect(rect) {}
	Quadtree(const Vector2& minVec, const Vector2& maxVec)
		: _rect(Rectangle(minVec, maxVec))	 {}
	~Quadtree();	
	void Insert(GameObject2D* obj, const Rectangle& rect);
	bool GetIntersectObj(const Rectangle& rect, std::vector<GameObject2D*>& obj);
	void GetWholeObj(std::vector<GameObject2D*>& obj);
	char IsRect(const Rectangle& rect);

private:
	Rectangle _rect;
	std::vector<GameObject2D*> _list;
	Quadtree* children[4] = { nullptr, nullptr, nullptr, nullptr };
};

 

1. AABB를 체크하는 IsRect함수

char Quadtree::IsRect(const Rectangle& rect)
{
	char result = NONE;

	Vector2 center = Vector2((_size.Min.X + _size.Max.X) / 2.f, (_size.Min.Y + _size.Max.Y) / 2.f);
	if (_rect.Min.Y >= center.Y)
	{
		if (_rect.Max.X <= center.X)
		{
			result = NW;
		}
		else if (_rect.Min.X >= center.X)
		{
			result = NE;
		}
	}
	else if (_rect.Max.Y <= center.Y)
	{
		if (_rect.Max.X <= center.X)
		{
			result = SW;
		}
		else if (_rect.Min.X >= center.X)
		{
			result = SE;
		}
	}
	return result;
}

2. 각 메쉬가 어느 Section에 있는지를 체크 한 뒤 삽입하는 Insert 함수

void Quadtree::Insert(GameObject2D* obj, const Rectangle& rect)
{
	if (obj->GetMesh() == nullptr)
		return;

	char sect = IsRect(rect);

	if (sect == NONE || size.GetSize() <= Vector2(50.f, 50.f))
	{
 		list.push_back(obj);
	}
	else
	{
		switch (sect)
		{
		case NW:
			if (children[NW] == nullptr)
			{
				Vector2 min = Vector2(size.Min.X, (size.Min.Y + size.Max.Y) / 2.f);
				Vector2 max = Vector2((size.Min.X + size.Max.X) / 2.f, size.Max.Y);
				children[NW] = new Quadtree(min, max);
			}
			children[NW]->Insert(obj, rect);
			return;
		case NE:
			if (children[NE] == nullptr)
			{
				Vector2 min = Vector2((size.Min.X + size.Max.X) / 2.f, (size.Min.Y + size.Max.Y) / 2.f);
				Vector2 max = Vector2(size.Max.X, size.Max.Y);
				children[NE] = new Quadtree(min, max);
			}
			children[NE]->Insert(obj, rect);
			return;
		case SW:
			if (children[SW] == nullptr)
			{
				Vector2 min = Vector2(size.Min.X, size.Min.Y);
				Vector2 max = Vector2((size.Min.X + size.Max.X) / 2.f, (size.Min.Y + size.Max.Y) / 2.f);
				children[SW] = new Quadtree(min, max);
			}
			children[SW]->Insert(obj, rect);
			return;
		case SE:
			if (children[SE] == nullptr)
			{
				Vector2 min = Vector2((size.Min.X + size.Max.X) / 2.f, size.Min.Y);
				Vector2 max = Vector2(size.Max.X, (size.Min.Y + size.Max.Y) / 2.f);
				children[SE] = new Quadtree(min, max);
			}
			children[SE]->Insert(obj, rect);
			return;
		default:
			return;
		}
	}
}

3. AABB로 GameObject를 가져오는 GetIntersectObj 함수

bool Quadtree::GetIntersectObj(const Rectangle& rect, std::vector<GameObject2D*>& obj)
{
	bool result = false;

	if (rect.Intersect(this->size))
	{
		if (list.size() > 0)
		{
			for (int i = 0; i < list.size(); ++i)
				obj.push_back(list[i]);

			for (int i = NW; i < SE+1; ++i)
			{
				if (children[i] != nullptr)
					children[i]->GetIntersectObj(rect, obj);
			}

			result = true;
		}
		else
		{
			for (int i = NW; i < SE+1; ++i)
			{
				if (children[i] != nullptr)
					if (children[i]->GetIntersectObj(rect, obj))
						result = true;
			}
		}
	}
	return result;
}

 

QuadTree를 썼을 때와 안썼을 때의 Performance를 비교하기