RoomGenerator (1)

RoomGenerator

랜덤한 그래프를 생성하는 로직을 구현해야 하는 상황이다.

간단한 이론과 알고리즘이 있을 거라 생각했지만 그리 만만하지 않았다...

여러 이론과 방법들을 분석하며 실제로 구현해 보자.

---

 

 

 

 

 

보로노이 + 들로네 삼각 분할

보로노이는 평면을 분할하는 방법중 하나이다.

평면의 두 점을 연결하고 그에 수직하는 선분으로 평면을 나누어 나간다.

그러면 왼쪽 사진과 같이 평면이 자연스럽게 나눠진다.

이는 CG에서 땅을 부수거나 벽이 부서지는 등의 효과를 만들 때 많이 사용된다.

자연스러움이 있기 때문인 듯 하다.

들로네 삼각 분할은 점들을 연결하는 삼각형을 만들 때, 최대한 정삼각형에 가깝게 만드는 방식으로 분할하는 것이다.

그러기 위해서, 세 점으로 이루어진 삼각형의 외접원안에 다른 점이 없도록 해야 한다.

이 둘은 쌍대 관계에 있다.

즉, 하나를 얻으면 다른 하나를 구할 수 있다는 뜻이다.

 

자연스러운 랜덤 그래프를 생성하기 위해 임의의 점을 평면상에 배치하고 들로네 삼각분할을 이용하여 그래프의 연결 구조를 결정하려 했다.

하지만, 원하는 그래프의 형태를 만들기 쉽지 않다고 판단했다.

따라서, 다른 방법이 필요했다.

---

 

 

 

 

 

에르되시-레니 모델

완전 랜덤한 그래프를 만드는 모델 중 하나인 에르되시-레니 모델은 두 노드 간의 연결 관계를 특정 확률(p)에 의해 생성하는 모델이다.

이와 관련된 내용 중 적당한 이론이 있어서 이를 채택하였다.

그 내용은 확률(p)이 특정 임계점을 넘게 되면 그래프의 모양이 급격히 변화한다는 것이다.

그래프 연결성에 대한 임계점은 $log(n) / n$이라고 한다.

즉, 확률(p)이 $log(n) / n$를 넘으면 연결 그래프가 만들어질 확률이 급격히 증가한다는 뜻이다.

https://horizon.kias.re.kr/25610/

무작위 이산 구조의 문지방 현상

 

이를 이용하여 랜덤한 노드(room)를 생성하고 각각의 노드쌍을 확률에 의해 연결성을 부여한다면 연결 그래프를 만들 수 있다고 생각했다.

하지만, 구현중 문제가 발생했다.

게임에서의 룸을 만드는 작업이기 때문에 모든 노드(room)의 연결이 보장되어야 한다.

즉, 100% 연결 그래프여야 한다는 뜻이다.

아무리 확률(p)을 높게 설정한다 하더라도 무조건 연결 그래프를 만든다는 보장이 없다.

따라서, 해당 방법만으로는 적절한 구현이 힘들 것이라 판단했다.

---

 

 

 

 

 

에르되시-레니 모델 + MST

연결 그래프를 만들어 놓고 에르되시-레니 모델을 적용하여 랜덤한 연결성을 추가하면 문제를 해결할 수 있을 것이라 생각했다.

랜덤한 연결 그래프를 만드는 방법은 MST를 적절히 변형하는 것이다.

연결된 노드와 연결되지 않는 노드를 구분한다.

최초에는 시작 노드만이 연결된 노드로 분류된다.

이후, 연결된 노드에서 임의로 한 개의 노드를 선택하고 연결되지 않은 노드에서도 동일하게 선택한다.

이후, 두 개의 노드를 연결해 본다.

만약, 특정 제약에 의해 연결이 실패하면 다시 노드를 선택한다.

연결이 성공하면 연결되지 않은 노드에서 연결된 노드로 옮기는 작업을 수행한다.

모든 노드가 연결될 때까지 이를 진행하면 연결성이 보장된 그래프를 만들 수 있다.

한 가지 우려할 점은 운이 엄청 나쁘다면 계속 같은 노드를 선택할 수도 있으면 연결 불가능한 노드 조합을 계속하여 선택할 수도 있다.

하지만, 이는 확률적으로 극히 드물기 때문에 괜찮을 거라 판단했다.

//연결 그래프 생성
HashSet<Room> connectedRooms = new HashSet<Room> { _rooms[0] }; // 시작 방
HashSet<Room> remainingRooms = new HashSet<Room>();

for (var i = 1; i < _rooms.Count; i++)
{
    remainingRooms.Add(_rooms[i]);
}

// 모든 방이 연결될 때까지 반복
while (connectedRooms.Count < _rooms.Count)
{
    // 이미 연결된 방 중 하나를 무작위로 선택
    int connectedRoomIdx = Random.Range(0, connectedRooms.Count);
    var connectedRoom = connectedRooms.ElementAt(connectedRoomIdx);

    // 아직 연결되지 않은 방 중 하나를 무작위로 선택
    int remainingRoomIdx = Random.Range(0, remainingRooms.Count);
    var newRoom = remainingRooms.ElementAt(remainingRoomIdx);

    // 두 방을 연결
    if (TryConnect(connectedRoom, newRoom))
    {
        connectedRooms.Add(newRoom);
        remainingRooms.Remove(newRoom);
    }
}

 

이제 연결성이 보장되었기 때문에 에르되시-레니 모델 이론을 적용하여 노드쌍의 특정 확률로 연결성을 부여한다.

//추가 연결
float threshold = Mathf.Log(_rooms.Count) / _rooms.Count;
for (var i = 0; i < _rooms.Count; i++)
{
    for (var j = i + 1; j < _rooms.Count; j++)
    {
        //i <-> j 확률로 연결
        var connectProb = Random.value;
        if (connectProb <= threshold)
        {
            TryConnect(_rooms[i], _rooms[j]);
        }
    }
}

확률을 적절히 조정하면 그래프의 밀집도를 관리할 수 있다.

현재 설정된 임계점은 앞에서 설명했던 문지방 효과의 임계점이다.

이제 생성된 룸 연결 정보를 통해 실제 룸을 이동하는 과정을 구현할 것이다.

---