게임 디자인 패턴 15. 공간 분할 패턴 (Spatial Partition Pattern)

---

공간 분할 패턴

주의점

공간 분할을 위해 사용할 수 있는 자료구조

---

다음의 게시글의 코드를 함께 참고하였습니다.

Game programming patterns in Unity with C# - Spatial Partition Pattern | Habrador

This is a tutorial on game programming patterns in Unity with C# code. Another name for the same thing is software design patterns. You will learn the following programming patterns: command pattern, and much more. This section is all about the spatial partition pattern.

https://www.habrador.com/tutorials/programming-patterns/19-spatial-partition-pattern/

게임 안에서 가까이 있는 물체들로부터만 소리가 들린다거나, 서로 붙어 있는 유저들끼리만 채팅이 가능하다던지, 주변의 객체들하고만 상호작용하기 위해서 주변에 어떤 객체들이 있는지를 알아야 할 필요가 있다.

이걸 매 프레임마다 확인한다면?

매우 큰 수준의 성능 병목이 일어날 수 밖에 없는 것이다.

검사 방법도 마찬가지다.

모든 오브젝트들의 서로 간의 거리를 일일히 계산한다면?

GameObject FindClosestEnemySlow(GameObject soldier)
{
	GameObject closestEnemy = null;

	float bestDistSqr = Mathf.Infinity;

	//Loop through all enemies
	for (int i = 0; i < enemySoldiers.Count; i++)
	{
		//The distance sqr between the soldier and this enemy
		float distSqr = (soldier.transform.position - enemySoldiers[i].transform.position).sqrMagnitude;

		//If this distance is better than the previous best distance, then we have found an enemy that's closer
		if (distSqr < bestDistSqr)
		{
			bestDistSqr = distSqr;

			closestEnemy = enemySoldiers[i];
		}
	}

	return closestEnemy;
}

벌써 O(n^2)의 확인을 매번마다 해줘야 한다는 답답한 상황이 나온다.

그래서 공간 분할 패턴에서는 이러한 객체들의 위치에 따라 객체들을 정렬하여 보관해놓는다.

정확히 어떻게 하는 것인지 알아보자.

---

공간 분할 패턴

공간 분할 패턴에서는 공간 자료구조라는 것을 따로 두고, 객체들의 위치에 따라 자료구조를 업데이트 해준다.

보통은 2차원의 공간을 그리드로 나누어 각각의 셀에 어떤 오브젝트가 있는지를 관리하게 된다.

void Start() 
{
    //Create a new grid
    grid = new Grid((int)mapWidth, cellSize);
    
    //Add random enemies and friendly and store them in a list
    for (int i = 0; i < numberOfSoldiers; i++)
    {
        //Give the enemy a random position
        Vector3 randomPos = new Vector3(Random.Range(0f, mapWidth), 0.5f, Random.Range(0f, mapWidth));

        //Create a new enemy
        GameObject newEnemy = Instantiate(enemyObj, randomPos, Quaternion.identity) as GameObject;

        //Add the enemy to a list
        enemySoldiers.Add(new Enemy(newEnemy, mapWidth, grid));

        //Parent it
        newEnemy.transform.parent = enemyParent;


        //Give the friendly a random position
        randomPos = new Vector3(Random.Range(0f, mapWidth), 0.5f, Random.Range(0f, mapWidth));

        //Create a new friendly
        GameObject newFriendly = Instantiate(friendlyObj, randomPos, Quaternion.identity) as GameObject;

        //Add the friendly to a list
        friendlySoldiers.Add(new Friendly(newFriendly, mapWidth));

        //Parent it 
        newFriendly.transform.parent = friendlyParent;
    }
}


void Update() 
{
    //Move the enemies
    for (int i = 0; i < enemySoldiers.Count; i++)
    {
        enemySoldiers[i].Move();
    }

    //Reset material of the closest enemies
    for (int i = 0; i < closestEnemies.Count; i++)
    {
        closestEnemies[i].soldierMeshRenderer.material = enemyMaterial;
    }

    //Reset the list with closest enemies
    closestEnemies.Clear();

    //For each friendly, find the closest enemy and change its color and chase it
    for (int i = 0; i < friendlySoldiers.Count; i++)
    {
        //Soldier closestEnemy = FindClosestEnemySlow(friendlySoldiers[i]);

        //The fast version with spatial partition
        Soldier closestEnemy = grid.FindClosestEnemy(friendlySoldiers[i]);

        //If we found an enemy
        if (closestEnemy != null)
        {
            //Change material
            closestEnemy.soldierMeshRenderer.material = closestEnemyMaterial;

            closestEnemies.Add(closestEnemy);

            //Move the friendly in the direction of the enemy
            friendlySoldiers[i].Move(closestEnemy);
        }
    }
}

---

주의점

공간 분할을 해서 내가 과연 성능 상의 이득을 얻을 수 있는 지를 잘 고민해봐야 한다.

기본적으로는 O(n^2)보다 나은 수준의 공간 탐색을 구현하겠다는 것인데, n의 크기가 충분히 작다면 그냥 그대로 쓰는 것이 더 나을 수도 있다는 것이다.

또한 객체가 소속된 공간이 변경될 때마다 이 위치 변경을 처리하기가 더 어려워지기 때문에 코드가 더 복잡해진다.

또한 자료구조를 통해 객체들의 소속 위치를 저장하기 때문에 추가적인 메모리가 필요하다.

CPU 성능 최적화보다 메모리 최적화가 더 필요한 상황이라면? 안쓰는게 더 나을수도 있다는 것이다.

---

공간 분할을 위해 사용할 수 있는 자료구조

공간을 분할하고, 그것을 자료구조에 저장할 때, 사용할 수 있는 것들은 다음과 같다.

• 격자

• 쿼드트리

• 이진 공간 분할 (BSP)

• k-d 트리

• 경계 볼륨 계층 구조 (BVH)

보통 1차원 자료구조를 다차원으로 확장한 것에 지나지 않기 때문에, 한 번 간단하게 살펴보고 내 상황에 맞는 자료구조를 선택해보자.

Uploaded by N2T