[디자인 패턴]#16_공간 분할 패턴, Spatial Partition

 

[디자인 패턴] #16_공간 분할 패턴, Spatial Partition

게임 디자인 패턴 중 "최적화 패턴"에 대해 알아보겠습니다.

"게임 프로그래밍 패턴"의 20 항목, "공간 분할"에 해당하는 내용입니다.

 

---

 

Overview

1. 목적

출저: 게임 프로그래밍 패턴

• 공격 사정 범위 안에 존재하는 객체들을 찾는 등 주변 객체들을 찾는 작업은 월드 내 객체들을 순회합니다.
• 월드 내 객체의 개수가 많아질수록, 객체들을 전부 순회하는 작업은 성능 저하의 요인이 될 수 있습니다.
• 월드 내 주변 객체 탐색 성능을 최적화하기 위해 객체의 "위치 값"에 따라 구성되는 자료구조에 각 객체를 저장합니다.

 

2. 언제 사용할 것인가?

• 위치 값을 갖는 객체가 많을 때
• 위치에 따라 객체 탐색 성능에 영향을 줄 때

3. 주의할 점

1. 객체의 개수가 충분히 많을 때 공간 분할 패턴의 활용 가치가 높아집니다.
2. 객체의 위치 변경이 빈번하게 발생할 경우, 비교적 복잡한 코드가 필요합니다.
3. 객체의 위치 값을 저장할 추가적인 메모리 공간이 필요합니다.

 

코드 예제

1. Overview

• 턴제 게임, 혹은 체스 등의 격자무늬 위에서 발생하는 전략형 게임을 예제로 합니다.
• 한 칸에 들어갈 수 있는 게임 유닛을 "연결 리스트"로 관리합니다.

 

2. Unit 클래스(게임 유닛)

class Unit
{
	friend class Grid;

private:
	Grid* grid;
	float X;
	float Y;

private:
	Unit* prev;
	Unit* next;

public:
	Unit(class Grid* _grid, float x, float y)
	: grid(_grid), X(x), Y(y){}

	void Move(float x, float y)
	{
		grid->Move(this, x, y);
	}
};

 

3. Grid.h(게임 월드 클래스)

class Grid
{
public:
	Grid() {
		// 모든 격자 칸 초기화
	}

	void Add(Unit* unit)
	{
		// 리스트의 어느 위치로 들어갈지 계산
		int cellX = (int)(unit->X / Grid::CELL_SIZE);
		int cellY = (int)(unit->Y / Grid::CELL_SIZE);

		// 리스트의 맨 앞으로 게임 유닛 객체의 포인터를 추가합니다.
		unit->prev = nullptr;
		// 여기서 cells[cellX][cellY]는 한 격자 당 갖고 있는 연결 리스트를 의미합니다!
		unit->next = cells[cellX][cellY];
		cells[cellX][cellY] = unit;

		// next 즉 다음 노드가 존재하면, 다음 노드의 이전 노드 포인터를 자신으로 업데이트합니다.
		if (unit->next != nullptr)
		{
			unit->next->prev = unit;
		}
	}

	void Move(Unit* unit, float x, float y)
	{
		// 이전 위치 값
		int oldCellX = (int)(unit->X / Grid::CELL_SIZE);
		int oldCellY = (int)(unit->Y / Grid::CELL_SIZE);

		// 새로운 위치 값 
		int newCellX = (int)(x / Grid::CELL_SIZE);
		int newCellY = (int)(y / Grid::CELL_SIZE);

		// 위치 값 업데이트
		unit->X = x;
		unit->Y = y;

		// 이전 위치 값과 새로운 위치 값이 같다면 끝
		if (oldCellX == newCellX && oldCellY == newCellY)
			return;

		// 연결 리스트 업데이트
		// 1. prev 업데이트
		if (unit->prev != nullptr)
			unit->prev->next = unit->next;
		// 2. next 업데이트
		if (unit->next != nullptr)
			unit->next->prev = unit->prev;
		// 3. Head일 경우
		if (cells[oldCellX][oldCellY] == unit)
			cells[oldCellX][oldCellY] = unit->next;

		// 새로 들어갈 위치에 추가
		Add(unit);
 	}

	void HandleMelee()
	{
		for (int i = 0; i < NUM_CELLS; i++)
			for (int j = 0; j < NUM_CELLS; j++)
				HandleCell(cells[i][j]);
	}

	void HandleUnit(Unit* unit, Unit* nextUnit)
	{
		while (nextUnit != nullptr)
		{
			if(distance(unit, nextUnit) < ATTACK_DISTANCE)
				HandleAttack(unit, nextUnit);
		}
		nextUnit = nextUnit->next;
	}

	void HandleCell(Unit* unit)
	{
		while (unit != nullptr)
		{
			Unit* nextUnit = unit->next;
			
			HandleUnit(unit, nextUnit);

			// 공격 범위 안에 존재하는 주변 칸에 들어있는  연결리스트들을 체크합니다.
			//...
		
			unit = unit->next;
		}
	}

	// 1. 10 x 10 격자
	static const int NUM_CELLS = 10;
	// 2. 격자 한개 당 가질 수 있는 게임 유닛 객체의 개수
	static const int CELL_SIZE = 10;

	static const int ATTACK_DISTANCE = 3;
private:
	Unit* cells[NUM_CELLS][NUM_CELLS];
};