[게임 프로그래밍 패턴] 19. 공간 분할 패턴

객체를 효과적으로 찾기 위해 객체 위치에 따라 구성되는 자료구조에 저장한다.

#include <algorithm>

class Unit {
	friend class Grid;

public:
	Unit(Grid* grid, double x, double y)
		:grid_(grid), x_(x), y_(y),
		prev_(nullptr), next_(nullptr)
	{
		grid_->Add(this);
	}

	void Move(double x, double y) {
		grid_->Move(this, x, y);
	}

private:
	Unit* prev_;
	Unit* next_;

	Grid* grid_;
	double x_, y_;
};

class Grid {
public:
	Grid() {
		//격자를 싹 지운다.
		for (int x = 0; x < NUM_CELLS; x++)
		{
			for (int y = 0; y < NUM_CELLS; y++)
			{
				cells_[x][y] = nullptr;
			}
		}
	}

	void Add(Unit* unit);
	void HandleMelee();
	void HandleCell(int x, int y);
	void HandleUnit(Unit* unit, Unit* other);
	void Move(Unit* unit, double x, double y);

	static const int NUM_CELLS = 10;
	static const int CELL_SIZE = 20;

	static const int ATTACK_DISTANCE = 3;

private:
	//연결리스트의 머리모음
	Unit* cells_[NUM_CELLS][NUM_CELLS];
};

void Grid::Add(Unit* unit) {
	//어느 칸에 들어갈지를 결정한다.
	int cellX = (int)(unit->x_ / Grid::CELL_SIZE);
	int cellY = (int)(unit->y_ / Grid::CELL_SIZE);

	unit->prev_ = nullptr;
	// 기존에 있었던 주소 값은 뒤로 밀려남
	unit->next_ = cells_[cellX][cellY];
	// 새로운 주소값을 저장함
	cells_[cellX][cellY] = unit;

	//역참조도 가능함
	if (unit->next_ != nullptr) {
		unit->next_->prev_ = unit;
	}
}

void Grid::HandleMelee() {
	for (int x = 0; x < NUM_CELLS; x++)
	{
		for (int y = 0; y < NUM_CELLS; y++)
		{
			HandleCell(x, y);
		}
	}
}

void Grid::HandleCell(int x, int y){
	Unit* unit = cells_[x][y];
	while (unit!=nullptr)
	{
		//이 칸에 들어 있는 다른 유닛을 처리한다.
		//칸에 들어 있다고 같은 위치는 아니다. (공간을 칸으로 분할한 것임)
		HandleUnit(unit, unit->next_);

		//주변 칸에 들어 있는 유닛들도 확인한다.(주위 8칸 중에 반인 4칸만 검사한다. => 두 번 검사하는 것을 막아준다.)
		if (x > 0) HandleUnit(unit, cells_[x - 1][y]);
		if (y > 0) HandleUnit(unit, cells_[x][y - 1]);
		if (x > 0 && y > 0) HandleUnit(unit, cells_[x - 1][y - 1]);
		if (x > 0 && y < NUM_CELLS - 1) HandleUnit(unit, cells_[x - 1][y + 1]);
		unit = unit->next_;
	}
}

//지정 범위 안에 있는 유닛들이 있는지 체크한다.
void Grid::HandleUnit(Unit* unit, Unit* other) {
	while (other!=nullptr)
	{
		if (std::distance(unit, other) < ATTACK_DISTANCE) {
			HandleAttack(unit, other);
		}
		other = other->next_;
	}
}

void Grid::Move(Unit* unit, double x, double y)
{
	//유닛이 어느 칸에 있었는지를 확인한다.
	int oldCellX = (int)(unit->x_ / Grid::CELL_SIZE);
	int oldCellY = (int)(unit->y_ / Grid::CELL_SIZE);

	//유닛이 어느 칸으로 가야 하는지를 확인한다.
	int cellX = (int)(x / Grid::CELL_SIZE);
	int cellY = (int)(y / Grid::CELL_SIZE);

	unit->x_ = x;
	unit->y_ = y;

	// 칸이 바뀌지 않았다면 더 할 일이 없다.
	if (oldCellX == cellX && oldCellY == cellY) {
		return;
	}

	//이전 칸에 들어 있는 리스트에서 유닛을 제거한다.
	if (unit->prev_ != nullptr) {
		unit->prev_->next_ = unit->next_;
	}

	if (unit->next_ != nullptr) {
		unit->next_->prev_ = unit->prev_;
	}

	//유닛이 칸에 들어 있는 리스트의 머리였다면 머리를 바꿔준다.
	if (cells_[oldCellX][oldCellY] == unit) {
		cells_[oldCellX][oldCellY] = unit->next_;
	}

	//새로 들어갈 칸에 추가한다.
	Add(unit);
}