안녕하세요?
- 정말 오랜만의 포스팅이군요.
- 그 자체제작 엔진 개발에서 손을 뗀 건 아닙니다. 계속 개발은 하고 있었지만 현생에 치여 블로그 포스팅을 할 짬이 나지 않았다는 슬픈 사정이 있었죠.
- 물론 제가 게을러서 시간이 생겨도 침대에 누워 쇼츠만 봤다는 사실은 변치 않지요. 하하하.
SSEngineDefault
- 하하. 각설하고 본론으로 들어가 볼까요?
- 게임엔진 뿐 아니라 꽤 규모있는 프로젝트를 밑바닥부터 제작하는 프로젝트를 진행하는 경우 해당 프로젝트의 지지기반이 될 수 있는 플랫폼 코드가 필요한 경우가 많습니다.
- 저는 이러한 플랫폼 코드를 별도의 라이브러리로 분리하여 개발 관리하고 있습니다.
- 그리고 위와 같은 기반 코드를 제작하며 여러 상용엔진들, 강의들로부터 영감을 받았습니다.
- 그 중에서도 제 엔진 플랫폼에 중심을 이루는
SHasher라는 클래스는 언리얼 엔진의FName기능과 상당히 유사하지요.
언리얼 엔진의 FName??
- 언리얼 엔진의
FName은 쉽게 생각하면 특정 스트링을 특정 ID와 대응시키는 기능이라 생각하면 편합니다. - 왜 굳이 스트링을 ID와 대응시켜야 하냐 라고 묻는다면…
- 개발을 하다보면 인스턴스별로, 인스턴스의 타입별로 ID를 부여하는 것이 편리한 경우가 아주 많습니다. 이러한 경우 인스턴스에 임의의 정수로 ID를 부여해 줄 수도 있겠지만 문자열과 1:1 대응이 되는 ID를 부여해 준다면 디버깅 시 해당 객체의 이해못할 정수가 아닌 스트링으로 인지하면 아주 편리합니다.
- 연산이 간단해집니다. 게임 도중 맵에 배치된 특정 이름을 가진 캐릭터를 찾고싶다고 예를 들어봅시다. 맵에 캐릭터가 1000명이 있고 찾고자 하는 캐릭터의 이름이 10글자라고 한다면 스트링비교를 통한 캐릭터 찾기는 O(1000 * 10)의 연산시간이 소요됩니다. 그러나 이를 ID와 대응시키면 ID의 비교는 단순 정수값이 같은지 확인하는 단순한 연산이기에 O(1000)시간밖에 들지 않습니다. 빠른 연산은 비교 뿐 아니라 복사와 같은 다른 연산들에도 똑같이 장점이 됩니다.
- 이 외에도 다양한 장점이 있을 수 있지만 사실 위 장점들 만으로 충분합니다. 간단한 연산, 디버깅 편의성 이라는 장점만으로 기존에 스트링, ID만으로 처리하기 꺼려졌던 많은 일들을 기꺼이 할 수 있게 해줍니다.
- 물론, ID와 대응되지 않는 스트링이 가지는 연산의 범용성과 단순 정수형 ID의 단순함을 완전히 대체할 순 없습니다. 스트링을 ID화 하는 연산의 오버헤드도 신경 써야 하죠. 원래 코딩에 마법은 없습니다. 그렇지만 내가 고를 수 있는 선택지가 하나 더 생긴다는 것 만으로 개발의 효용성은 크게 올라갑니다.
그래서? FName이 어떻게 작동하는데?
-
사실 스트링과 ID를 대응시키는 방법은 언리얼 엔진만의 전유물이 아닙니다. 그저 언리얼 엔진이 유명해서 FName이라는 기능이 유명할 뿐이죠.
-
그렇기에 언리얼 엔진의 구체적인 구현체를 분석하기 보다는 스트링을 ID로 변환하는 일반적인 방법론에 대해 설명해 드리겠습니다.
-
해당 방법은 바로 스트링 해시맵의 인덱스를 이용하는 것입니다.
- 예를 들어 “Apple”, “Banana”, “Cat” 이라는 문자열을 저장한다고 해봅시다.
- “Apple”, “Banana”, “Cat” 이라는 문자열을 스트링 해시 알고리즘(CityHash, FNV-1a 등…)을 통해 해시값을 구해줍니다. 해시값은 다음과 같이 나왔다고 가정해봅시다.
- Apple → 10923
- Banana → 86942
- Cat → 436784
- 이제 해시테이블을 하나 만들어줍시다. 해시테이블의 사이즈는 8입니다.
- 스트링의 해시값을 8으로 나눈 나머지를 구합니다.
- Apple → 10923 →
10924 % 8== 4 - Banana → 86942 →
86942 % 8== 6 - Cat → 436783 →
436784 % 8== 0
- Apple → 10923 →
- 해당 값을 인덱스로 문자열을 저장해줍니다.
- 이렇게 하면 해시배열의 인덱스를 스트링과 1:1 대응시킬 수 있습니다. 해시배열의 인덱스를 ID로 활용할 수 있다는 뜻입니다.
- 만약 새로운 “Dog” 라는 문자열의 해시값이
8888이고 8으로 나눈 해시 인덱스가 0이라서 “Cat”이라는 문자열과 충돌이 난다면 Cat 다음에 저장해주면 됩니다(Open Addressing). 그럼 ID값이1이 되겠죠
자체제작한 SHasher의 작동방식
- 제가 만든 SHasher의 경우에도 위와 유사한 작동방식을 가지고 있습니다. 그런데 저는 해시멥에서 OpenAddressing이 아닌 Chaining 방식을 사용하고 있어요.
- OpenAddressing의 경우 해시맵이 꽉 차면 그 용량을 늘려주기 위해 전체 테이블을 리해싱 해야 하는 오버헤드가 있고 알고리즘 특성상 충돌구간이 길어지는 경우도 있어서 그렇습니다.
- 체이닝 방식을 적용하고, 상위비트에 해쉬값을 저장하고 링크드 리스트에서 몇 번째에 위치해 있는지를 하위비트에 적용하면 uint64비트 사이즈 하나로 ID를 구성해 줄 수 있게 됩니다.
union { struct { uint32 _HashedValue; // 해쉬 상위 32비트 uint32 _CurNodeCnt; // 해쉬 하위 32비트 }; uint64 _hashX; // 해쉬 64비트 전체값 };
코드
- 코드는 아래에 첨부해 두겠습니다. 전체 코드에 대한 스트링 풀과 ID를 담고있는 코드들입니다.
- 스트링 풀 인터페이스:
- 스트링 풀 구현체:
- ID클래스.h
- ID클래스.cpp
게임엔진코드싸개(진)