일화

진행 중인 프로젝트에서 옆자리 팀원이 랜덤 시드 관리 작업을 하고 있었다. 그런데 전투맵 생성 시드로 예전과 똑같이 12345를 줬는데 맵이 전혀 다른 모양으로 생성됐다. 버그인가 싶어 어떻게 구현했냐고 물어봤더니 이제 시드를 그대로 쓰지 않고 FNV-1a로 한 번 파생시킨다고 했다. 12345라는 숫자는 같아도 Derive(12345, "CombatMap")을 거치면서 실제 맵에 들어가는 시드값이 달라진 것이다. 일단 흥미로워서 블로그 주제로 잡았다.

FNV-1a 해시, 문자열을 숫자 하나로 고정하기

게임을 만들다 보면 문자열 키를 자주 쓰게 된다. 리소스 이름, 이벤트 이름, 애니메이션 스테이트 같은 것들. 그런데 이 문자열을 매 프레임 비교하고 조회하는 건 은근히 비싸다. 이럴 때 문자열을 미리 숫자 하나로 고정해두면 훨씬 빠르게 다룰 수 있는데 그 변환에 자주 쓰이는 게 FNV-1a 해시다.

FNV-1a가 뭔데?

FNV-1a(Fowler-Noll-Vo)는 문자열이나 바이트 데이터를 고정 크기 숫자로 바꿔주는 비암호화 해시 함수다. 구조가 단순해서 빠르고 구현이 몇 줄이면 끝난다.

동작은 이렇다.

hash = offset_basis
각 바이트마다:
    hash = hash XOR 바이트
    hash = hash × FNV_prime

XOR을 먼저 하고 곱셈을 나중에 한다는 게 원본 FNV-1과의 차이다. 이 순서 덕분에 입력이 조금만 바뀌어도 결과가 크게 흩어지는 avalanche 효과가 더 좋다.

32비트 기준 상수는 다음과 같다.

• offset_basis = 2166136261
• FNV_prime = 16777619

왜 게임에서 쓰는가

핵심은 문자열 비교를 정수 비교로 바꾸는 것이다.

// 매번 문자열 비교 — 느림
if (resourceName == "wood") { ... }

// 해시로 고정해두고 정수 비교 — 빠름
static readonly uint Wood = Fnv1a("wood");
if (resourceHash == Wood) { ... }

문자열 비교는 길이만큼 문자를 하나씩 확인하지만, 해시값끼리는 uint 하나를 비교하면 끝난다. Dictionary 키로 쓸 때도 문자열 해싱 비용을 매번 치를 필요가 없어진다.

readonly로 초기화 시점에 한 번 계산해두면, 이후로는 그 값이 프로그램 내내 고정된 채로 쓰인다. 이게 "고정 해시"라고 부르는 이유다.

주의할 점

• 해시 충돌: 서로 다른 문자열이 같은 해시값을 가질 수 있다. 키 개수가 많거나 안전이 중요하면 32비트 대신 64비트 버전을 쓰거나, 충돌 검증을 한 번 해두는 게 좋다.
• 암호화 용도 금지: FNV-1a는 빠른 대신 예측 가능하다. 보안이 필요한 곳(비밀번호 등)에는 절대 쓰면 안 된다.
• 플랫폼 일관성: 해시값을 저장하거나 네트워크로 주고받는다면, 모든 환경에서 같은 비트 폭과 상수를 써야 값이 일치한다.

정리

FNV-1a는 자료구조가 아니라 해시 테이블 같은 자료구조를 떠받치는 알고리즘이다. 문자열 키가 많은 게임에서 이걸 한 번 계산해 정수로 고정해두면, 비교와 조회 비용을 눈에 띄게 줄일 수 있다. 구현도 짧으니 프로젝트에 유틸 하나 넣어두면 두고두고 쓴다.

실전: 결정론적 시드 파생에 써먹기

FNV-1a는 문자열 비교 최적화 말고도 쓸 데가 있다. 우리 프로젝트에서는 하나의 마스터 시드로부터 시스템별 시드를 파생하는 데 썼다. (팀원이 작성해준 코드 가져왔습니다 ㅎ..)

전투 맵, 영토 생성처럼 랜덤이 들어가는 시스템이 여러 개일 때, 각자 Random을 따로 굴리면 호출 순서에 따라 결과가 흔들린다. 그래서 마스터 시드 하나만 저장해두고, 시스템마다 고유한 태그 문자열을 붙여 FNV-1a로 섞어 각각의 시드를 뽑아냈다.

public static int Derive(int masterSeed, string systemTag)
{
    if (string.IsNullOrWhiteSpace(systemTag))
        throw new ArgumentException("시스템 태그가 비어 있습니다.", nameof(systemTag));

    unchecked
    {
        uint hash = 2166136261u;

        // masterSeed를 4바이트로 분해해 먼저 섞는다 (엔디안 고정)
        MixByte(ref hash, (byte)masterSeed);
        MixByte(ref hash, (byte)(masterSeed >> 8));
        MixByte(ref hash, (byte)(masterSeed >> 16));
        MixByte(ref hash, (byte)(masterSeed >> 24));

        // 그 다음 태그 문자열을 섞는다
        foreach (byte value in Encoding.UTF8.GetBytes(systemTag))
            MixByte(ref hash, value);

        int result = (int)(hash & 0x7FFFFFFF);   // 항상 양수 int
        return result == 0 ? 1 : result;         // 0은 특수값이라 피함
    }
}

private static void MixByte(ref uint hash, byte value)
{
    hash ^= value;
    hash *= 16777619u;
}

순수 FNV-1a에 몇 가지 실용 장치를 얹었다.

• masterSeed를 바이트로 분해해서 섞기: int를 리틀엔디안 순서로 직접 넣어, BitConverter 같은 플랫폼 의존성 없이 어디서든 같은 결과가 나오게 했다.
• unchecked: FNV는 곱셈이 계속 오버플로되며 wrap-around 되는 걸 전제로 한다. 의도를 명시했다.
• & 0x7FFFFFFF: uint 해시에서 부호 비트를 잘라 항상 양수 int로 만든다. Unity Inspector나 System.Random(int)에 그대로 넣기 위함이다.
• 0을 1로 치환: 0을 "override 안 함" 같은 특수값으로 쓰기 위해 시드 공간에서 0을 피했다.

이렇게 하면 Derive(seed, "CombatMap")과 Derive(seed, "Territory")가 서로 독립적이면서도, 같은 마스터 시드에 대해 언제 어디서 호출하든 항상 같은 값을 돌려준다. 리플레이나 시드 공유 기능을 붙일 때 이 결정론성이 결정적으로 중요하다.