의사 난수

의사 난수

프로그래밍에서 난수란 세 가지 카테고리로 나눌 수 있다.

 

• (거의) 진짜 난수 : 특별한 하드웨어로 만드는 난수들. 각종 물리 실험이나 장비등에 쓰임
• 암호학 난수(해시값 등) : 사실 난수는 아니지만 예측불가능하고 충분히 잘 분포됨.
• 보통의 의사난수 : Seed가 필요하며, 생성되는 난수들이 결정적(deterministic)임. 생성되는 난수들을 이용하여 역으로 Seed를 구할 수 있음

 

의사 난수 생성기는 Seed값에 따라 생성되는 난수들이 결정적이기 때문에, 이를 잘 활용하면 유용하다.

 

때로는 게임 전체에서 단 하나의 난수 생성기를 사용하기 보다는 분야별로 여러 개의 난수 생성기를 사용하는 것이 좋을 수 있다. 가령 절차적인 맵을 생성하는 게임에서 단 하나의 난수 생성기만 사용한다면 플레이어가 게임 도중 난수를 생성하는 이벤트를 발생시켰냐 아니냐에 따라 다음 맵의 구조가 달라질 수 있다.

 

이런 경우 하나의 마스터 난수 생성기를 두고 그 아래에 분야별로 하위 난수 생성기를 둘 수 있다.

 

class MasterRandom
{
    private Random _masterRng;
    private Random _mapRng;
    private Random _battleRng;
    
    public MasterRandom(int seed)
    {
        _masterRng = new Random(seed);
        _mapRng = new Random(_masterRng.NextInt());
        _battleRng = new Random(_masterRng.NextInt());
    }
}

 

 

대부분 언어에서 의사 난수 생성 클래스를 제공한다. 그러나 가끔 프로그래머들이 프로젝트에서 직접 구현해 쓰기도 하는데, 

1. 멀티 플랫폼에서 동일한 동작을 보증하거나
2. 미래에 있을 변경점으로 인하여 이전 시드들이 훼손되지 않도록 하기 위함이다.

 

 

홀턴 수열(Halton Sequence)

의사 난수 생성기에서 생성되는 난수들은 확률적으로 부자연스러운 값들이 연속적으로 등장할 수 있다. 가령 맵 생성 과정에서 보물상자들이 입구에 뭉쳐있다든가 하는 등의 경우가 존재할 수 있다. 이런 "뭉침"을 해결하기 위해서 홀턴 수열이란걸 쓰기도 한다.

 

홀턴 수열은 작은 값의 서로소(coprime)들을 이용한다. n차원 영역의 좌표값을 생성한다면 n개의 서로소를 이용하면 된다.

 

생성 과정은 다음과 같다. 이용할 서로소를 n으로 정했다면, n을 이용하여 0과 1사이의 값들을 생성한다.

 

가령 n=3으로 정했다고 해보자. 처음에는 다음의 수열을 생성한다.

$$1/3, 2/3 $$

 

그 다음에는 분모값으로 $3^2=9$를 사용한다. 이때 분자는 1부터 시작하지만 3씩 증가한다. 1보다 값이 커진다면 2부터 시작하여 3씩 증가시킨다. 그럼 다음과 같은 수열이 생성된다. 단 이전에 나왔던 값들은 제외시킨다 (분자가 3의 배수)

 

$$ 1/3, 2/3, 1/9, 4/9, 7/9, 2/9, 5/9, 8/9 $$

 

n=2인 경우라면 다음 수열이 생성될 것이다

 

$$1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8$$

 

이제 2차원 배열의 좌표를 각 수열에서 하나씩 순서대로 꺼내 쓰면 만들어낼 수 있다.

 

$$ (1/3, 1/2), (2/3, 1/4), (1/9, 3/4), ...$$

 

 

그러나 비교적 큰 값의 서로소를 쓸 때 수열의 초반부가 어색한 상황이 발생할 수 있는데 가령 97과 101을 쓴다면 생성되는 수열은 다음과 같다.

 

$$ (1/101, 1/97), (2/101, 2/97), (3/101, 3/97) ...$$

 

이는 두 좌표의 값이 서로 거의 같기 때문에 어색하게 보일 수 있다. 이러한 이유 때문에 사용되는 서로소의 값이 n이라면 처음의 n개의 값들은 넘기는 방식을 사용하기도 한다. 

 

게임에서 거의 쓸일은 없긴 하지만 n개 이상의 많은 값들을 스킵하기도 하며, 수열 중 k번째 값들(k는 n과 서로소)만을 사용하기도 한다.

 

당연히 홀튼 수열은 랜덤하게 생성된 값들이 아니라 그냥 균열히 분포된 값들일 뿐이다. 이런 수들을 준난수(quasi-random)이라고 표현하기도 한다.

 

홀튼 수열 사용하는 서로소에 따라 매번 똑같은 값들을 생성하기 때문에 여기에 변화를 주기 위해서 다른 서로소의 값들을 사용하거나 임의의 offset를 주는 등의 방식을 사용한다. 

 

 

 

Phyllotaxis angles

만약 각도에 대해서 균일한 분포를 주고 싶다면 황금 비율 값을 사용하기도 한다.

 

예를 들어 잎사귀가 생성되는 각도를 정하고자 한다면 $2\pi /1.618$의 간격을 두고 잎사귀를 생성해나갈 수 있다.

 

 

 

푸아송 디스크 샘플링(Poisson disk sampling)

절차적 맵 생성 과정에서 오브젝트를 배치할 때, 오브젝트끼리 서로 겹치면 안 되는 경우가 있다. (건물이나 바위 등) 이런 경우의 간단한 해법은 난수를 사용하는 과정에서 겹치지 않는 경우에만 이를 사용하는 것이다. 배치 과정에서 디스크(disk)라는 개념을 사용하는데 이는 그냥 위치(x,y)와 반지름(r)의 set (x,y,r)이다.

 

생성 과정은 다음과 같다.

 

1. 보통은 중간즈음에 하나를 배치하고, 여기서부터 거리가 (2r)에서 (2r+k)되게끔 주변에 디스크들을 생성한다.
2. 생성이 끝났다면 새로 생성된 디스크 하나를 선택하여 다시 이 과정을 반복한다. 
3. 위 과정을 더 이상 디스크를 생성할 수 없을 때까지 반복한다.

 

만약 디스크끼리 반지름이 달라야하는 경우라면 2r대신 r1+r2 씀 됨.