[Design Pattern] 공간 분할 패턴

1. 공간 분할 패턴 정의

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

 

 

2. 공간 분할 패턴 구현

class FGrid
{
	static const int NUM_CELLS = 10;
	static const int CELL_SIZE = 20;
	static const int ATTACK_DISTANCE = 2;

private:
	Unit* Cells[ NUM_CELLS ][ NUM_CELLS ];

public:
	FGrid()
	{
		// 격자를 초기화 한다.
		for ( int x = 0; x < NUM_CELLS; ++x )
			for ( int y = 0; y < NUM_CELLS; ++y )
				Cells[ x ][ y ] = nullptr;
	}

	void Add( Unit* InUnit )
	{
		// 어느 칸에 들어갈지 결정한다.
		int cellX = (int)( InUnit->X / FGrid::CELL_SIZE );
		int cellY = (int)( InUnit->Y / FGrid::CELL_SIZE );

		// 칸에 들어 있는 리스트의 맨 앞에 추가한다.
		InUnit->Prev = nullptr;
		InUnit->Next = Cells[ cellX ][ cellY ];
		Cells[ cellX ][ cellY ] = InUnit;

		if ( InUnit->Next != nullptr )
			InUnit->Next->Prev = InUnit;
	}

	void Move( Unit* InUnit, double InX, double InY )
	{
		// 유닛이 어느 칸에 있었는지를 확인한다.
		int oldCellX = (int)( InUnit->X / FGrid::CELL_SIZE );
		int oldCellY = (int)( InUnit->Y / FGrid::CELL_SIZE );

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

		InUnit->X = InX;
		InUnit->Y = InY;

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

		// 이전 칸에 들어 있는 리스트에서 유닛을 제거한다.
		if ( InUnit->Prev != nullptr )
			InUnit->Prev->Next = InUnit->Next;

		if ( InUnit->Next != nullptr )
			InUnit->Next->Prev = InUnit->Prev;

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

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

	void HandleMelee()
	{
		for ( int x = 0; x < NUM_CELLS; ++x )
			for ( int y = 0; y < NUM_CELLS; ++y )
				HandleCell( Cells[ x ][ y ] );
	}

	void HandleUnit( Unit* InUnit, Unit* InOther )
	{
		while ( InOther != nullptr )
		{
			if ( Distance( InUnit, InOther ) > ATTACK_DISTANCE )
			{
				HandleAttack( InUnit, InOther );
			}

			InOther = InOther->Next;
		}
	}

	// 같은 셀에 위치한 유닛끼리 검사한다.
	void HandleCell( Unit* InUnit )
	{
		while ( InUnit != nullptr )
		{
			// 이 칸에 들어 있는 다른 유닛을 처리한다.
			HandleUnit( InUnit, InUnit->Next );

			InUnit = InUnit->Next;
		}
	}

	// 같은 셀에 위치한 유닛끼리 검사한다.
	void HandleCell( int InX, int InY )
	{
		Unit* unit = Cells[ InX ][ InY ];
		while ( unit != nullptr )
		{
			// 이 칸에 들어 있는 다른 유닛을 처리한다.
			HandleUnit( unit, unit->Next );

			// 주변 칸( 좌측 4칸 )에 들어 있는 유닛들도 확인한다.
			if ( InX > 0 ) HandleUnit( unit, Cells[ InX - 1 ][ InY ] );
			if ( InY > 0 ) HandleUnit( unit, Cells[ InX ][ InY - 1 ] );
			if ( InX > 0 && InY > 0 ) HandleUnit( unit, Cells[ InX - 1 ][ InY - 1] );
			if ( InX > 0 && InY < NUM_CELLS - 1 ) HandleUnit( unit, Cells[ InX - 1 ][ InY + 1 ] );

			unit = unit->Next;

		}
	}

	void HandleAttack( Unit* InUint, Unit* InOther );

	int Distance( Unit* InUnit, Unit* InOther );

};

class Unit
{
	friend class FGrid;

private:
	double X, Y;
	FGrid* Grid;
	Unit* Prev;
	Unit* Next;

public:
	Unit( FGrid* InGrid, double InX, double InY ) 
		: Grid( InGrid ), X( InX ), Y( InY ), Prev( nullptr ), Next( nullptr )
	{
		Grid->Add( this );
	}

	void Move( double InX, double InY )
	{
		Grid->Move( this, InX, InY );
	}
};

• Add() : 유닛이 들어갈 칸을 찾은 뒤, 그 칸에 들어 있는 리스트 맨 앞에 유닛을 추가한다.
• Add() : 칸에 이미 유닛 리스트가 들어 있다면 추가한 유닛 뒤에 유닛 리스트를 붙인다.
• Move() : 유닛이 다른 칸으로 이동해야 하는 경우, 현재 칸의 연결 리스트에서 유닛을 제거한 뒤에 새로운 칸의 리스트에 추가한다.
• Move() : 이렇게 매 프레임마다 많은 유닛을 연결 리스트에서 넣었다 뺐다 할 수 있기 때문에, 추가, 삭제가 빠른 이중 연결 리스트를 사용한다.
• HandleCell() : 현재 유닛의 주변 8칸 중에서 좌측 4칸에 들어 있는 유닛과 충돌 여부를 검사한다.
• HandleCell() : 내부 루프에서는 같은 유닛끼리 두 번 검사하는 것을 막기 위해 8칸 중에 절반만 검사를 진행했다.
• HandleCell() :  A와 B의 관계가 비대칭인 경우 주변 8칸을 모두 검사해야한다.