쿼드트리

쿼드트리는 그림에서 볼 수 있듯이 2차원(3차원) 맵을 4등분으로 나누어 트리형태로 관리하는 자료구조를 뜻합니다.

 

이것은 왜 필요할까요? 3차원상에 객체를 그리는 일은 간단하면서도 오래걸리는 작업입니다.

 

특히 광활한 맵을 그리거나 많은 객체를 그린다면 그거 나름대로 어쩔 수 없는 일이지만, 사용자 눈(PC 모니터)에 보이지 않는 영역까지 그리는데 자원을 사용한다면 비효율적입니다.

 

그렇다면 맵에 관하여 사용자 눈에 보이는 영역을 어떻게 구분할 것이며(절두체) 구분한 영역을 어떻게 계산하는 걸까요?
답은 "쿼드트리" 를 사용합니다.

 

절두체에 관한 내용은 다음에 다루기로 하고, 영역을 계산하는 것에 있어서는 위 {x} 트리구조를 따르면 됩니다.

 

처음은 광활한 맵을 4등분하여 쿼드트리 구조로 담아놓고 쿼드트리의 최상단 Root부터 최하단 Leaf까지 깊이를 높여가며 현재 보이는 영역에 해당되는지 선택만 합니다. 쉽게 말해 현재 깊이 단에 4부분의 개별적인 영역이 보이는 영역이라면 깊이를 하나 더하여 ( depth + 1 )들어가고 아니라면 멈춥니다.

 

3D에서는 맵을 그리는 유무 ( on/off ) 의 의미를 가지고 판단하지만 2D는 의미가 있을까요?
2D역시 광활한 맵 데이터를 배열에 올려두고 ( 또는 일부분만 판단하여 가져오고 ) 현재 캐릭터의 2D좌표를 기점으로 주변의 2D 맵을 쿼드트리로 관리할 수 있습니다.

 

2차원 배열 쿼드트리

#define SIZE 32

typedef struct leaf{
	int depth;
	char value;

	leaf *parent;
	leaf *child[4];
}QTREE;

bool MAP[SIZE][SIZE];

int POW(int N)
{
	int H = 1;
	for (int i = 0; i < N; i++)
		H *= 2;
	return H;
}
void MakeLeaf(leaf *CurLeaf, int &peek, char *Data)
{
	if (CurLeaf->depth == -1)
	{
		CurLeaf->depth = 0;
		CurLeaf->value = Data[peek++];
		if (CurLeaf->value == 'x')
			MakeLeaf(CurLeaf, peek, Data);
	}
	else
	{
		for (int i = 0; i < 4; i++)
		{
			leaf* t = (leaf*) malloc(sizeof(leaf));
			t->parent = CurLeaf;
			t->depth = CurLeaf->depth + 1;
			t->value = Data[peek++];
			if (t->value == 'x')
				MakeLeaf(t, peek, Data);
			CurLeaf->child[i] = t;
		}
	}
}
void PrintQTREE(leaf *ROOT)
{
	printf("%c", ROOT->value);
	if (ROOT->value == 'x')
		for (int i = 0; i < 4; i++)
		{
			if (ROOT->child[i]->value == 'x')
				PrintQTREE(ROOT->child[i]);
			else
				printf("%c", ROOT->child[i]->value);
		}

	if (ROOT->parent == NULL)
		printf("\n");
}
void FillMap(leaf* ROOT, int sX, int sY)
{
	int length = SIZE / POW(ROOT->depth);
	if (ROOT->value == 'x')
	{
		for (int i = 0; i < 4; i++)
			FillMap(ROOT->child[i], sX + (i % 2 * length / 2), sY + (i / 2 * length / 2));
	}
	else
	{
		for (int i = sY; i < sY + length; i++)
			for (int j = sX; j < sX + length; j++)
				MAP[i][j] = (ROOT->value == 'b') ? 1 : 0;
	}
}
void PrintMAP()
{
	for (int i = 0; i < SIZE; i++){
		for (int j = 0; j < SIZE; j++)
			(MAP[i][j]) ? printf("1") : printf("0");
		printf("\n");
	}
}
void ReverseMAP()
{
	for (int i = 0; i < SIZE / 2; i++)
	{
		bool BUF[SIZE];
		memcpy(BUF, MAP[i], SIZE);
		memcpy(MAP[i], MAP[SIZE - i - 1], SIZE);
		memcpy(MAP[SIZE - i - 1], BUF, SIZE);
	}
}
void MAP2QTREE(leaf* ROOT, int sX, int sY)
{
	int length = SIZE / POW(ROOT->depth) / 2;
	bool PLAG = MAP[sY][sX];

	if (MAP[sY + length][sX] == PLAG &&
		MAP[sY][sX + length] == PLAG &&
		MAP[sY + length][sX + length] == PLAG)
		ROOT->value = (PLAG) ? 'b' : 'w';
	else
	{
		ROOT->value = 'x';
		for (int i = 0; i < 4; i++)
		{
			leaf* t = (leaf*) malloc(sizeof(leaf));
			t->parent = ROOT;
			t->depth = ROOT->depth + 1;
			ROOT->child[i] = t;
			MAP2QTREE(t, sX + (i % 2 * length), sY + (i / 2 * length));
		}
	}
}
void DeleteQTree(leaf* ROOT)
{
	if (ROOT->value == 'x')
	{
		for (int i = 0; i < 4; i++)
			DeleteQTree(ROOT->child[i]);
	}
	else
		free(ROOT);
}
int main()
{
	int T;
	for (scanf("%d", &T); T > 0; T--)
	{
		char BUF[1001];
		int BUF_index = 0, peek = 0;
		QTREE *head, *head2;
		memset(MAP, 0, sizeof(MAP));

		head = (leaf*) malloc(sizeof(leaf));
		head->parent = NULL;
		head->depth = -1;

		scanf("%s", &BUF);

		MakeLeaf(head, peek, BUF);

		//PrintQTREE(&head);

		FillMap(head, 0, 0);

		//PrintMAP();
		ReverseMAP();

		head2 = (leaf*) malloc(sizeof(leaf));
		head2->parent = NULL;
		head2->depth = 0;
		MAP2QTREE(head2, 0, 0);

		PrintQTREE(head2);

		DeleteQTree(head);
		DeleteQTree(head2);
	}
	return 0;
}