C++23과 HashLife 알고리즘으로 구현한 컨웨이의 생명 게임, 무한 시뮬레이션의 세계로!
by DD
2개월 전
조회수 8
HashLife 알고리즘을 활용하여 컨웨이의 생명 게임을 거의 무한대로 시뮬레이션하는 GOLDE 프로젝트 소개
C++23의 기능을 통해 코드 안전성, 가독성, 성능을 향상시켰으며, 특히 `std::jthread`와 `std::stop_token`을 활용하여 스레드 안전성을 확보
LifeNodeArena를 활용한 메모리 관리, `ankerl::unordered_dense`를 사용한 해시 테이블 구현 등, 현대 C++의 특징을 적극 활용
토로이드(Torus) 토폴로지 지원을 위한 추상화 설계, 임의의 스텝 사이즈(Step Size)를 지원하기 위한 Rokicki의 아이디어 차용
HashLife 알고리즘의 핵심: 쿼드트리(Quadtree) 기반의 메모이제이션(Memoization)
GOLDE는 HashLife 알고리즘을 사용하여 컨웨이의 생명 게임을 효율적으로 시뮬레이션한다. 핵심은 게임의 유니버스를 메모이제이션된 쿼드트리(Quadtree)로 표현하는 것이다. 각 노드는 미래 세대의 상태를 캐싱하며, 동일한 하위 패턴은 중복 계산되지 않도록 설계되었다. 특히, $2^n \times 2^n$ 크기의 노드는 $2^{n-2}$ 세대까지 계산할 수 있다. 이러한 접근 방식은 무한대 시뮬레이션(Infinite Simulation)을 가능하게 하는 핵심 원리이다.
C++23의 활용: 안전하고 효율적인 메모리 관리
저자는 C++23의 기능을 활용하여 코드의 안전성과 성능을 향상시켰다. 특히, `LifeNodeArena`를 사용하여 bump-pointer allocator를 구현, 메모리 할당의 효율성을 높였다. 또한, `std::construct_at`을 사용하여 placement new를 대체하고, `std::unique_ptr`와 커스텀 딜리터를 결합하여 메모리 관리를 단순화했다. 이러한 기법들은 를 방지하고, 코드의 가독성을 높이는 데 기여한다.
