글에서 backtracking을 단순히 500단계로 제한했다고 하지만, 실제로 제약 프로그래밍은 매우 흥미롭고 복잡한 분야임
Knuth의 Algorithm X와 dancing links를 사용하면, 글에서 언급된 "Layer 2" 영역을 86%보다 높은 성공률로 해결할 수 있을 것 같음
또한 다양한 휴리스틱을 적용하면 단순한 brute force보다 훨씬 빠르게 탐색 가능함. Sudoku 솔버를 만들어본 사람이라면 brute force가 얼마나 느려지는지 잘 알 것임
이런 종류의 제약 기반 조합 최적화 문제에는 이미 전용 솔버나 고수준 모델링 언어가 많이 존재함
예를 들어 MiniZinc은 여러 솔버 백엔드를 지원하는 고수준 모델링 언어를 제공함
직접 알고리즘을 짜기보다 이런 산업용 솔버를 활용해 문제를 모델링하고, 솔버가 무작위 혹은 전체 탐색으로 해답을 찾게 하는 편이 효율적임
그러면 솔버 작성에 시간을 쓰기보다, 문제 정의를 조정해 더 흥미로운 맵을 만드는 데 집중할 수 있음
내 노트북(11세대 Core i5, Iris Xe, Chrome 최신 버전)에서는 데모가 5 FPS로 실행됨. GPU가 병목인 듯함
글에서는 모바일에서 60 FPS로 돌아간다고 했기에 좀 더 효율적일 줄 알았음
맵은 아름답지만, WFC의 타일 단위 제약 때문에 비자연스러운 결과가 생김. 비국소적 영향(non-local influence)을 반영하기 어렵기 때문임
타일을 하나씩 탐험하는 게임에는 괜찮지만, 전체 맵 생성에는 적합하지 않음
Red Blob Games의 노이즈 기반 접근법이 더 나은 결과를 보여줌. 강은 습도 추적으로, 도로나 다리는 별도 패스로 처리하면 더 빠르고 견고함
그래도 WFC는 흥미로운 프로그래밍 문제라 구현 자체는 즐거웠을 것임. 전반적으로 훌륭한 글과 인상적인 데모였음
혹시 Windows나 Linux에서 실행 중인지, 아니면 CPU 렌더링을 쓰고 있는지 궁금함
내 모바일에서는 잘 작동함. FPS는 어떻게 측정했는지 궁금함. 사이트에 표시가 없던데, 혹시 Chrome Dev Tools로 본 것인지?
Oskar Stålberg가 Wave Function Collapse(WFC) 를 여러 게임에서 사용했음. 대표적으로 Townscaper가 있음
관련 발표 영상은 SGC21 - Beyond Townscapers에서 볼 수 있음
Jasper Flick의 Unity 튜토리얼 Hex Terrain이 떠오름
이 프로젝트는 미리 만든 타일을 제약 조건으로 맞추는 반면, Jasper의 튜토리얼은 타일 경계를 동적으로 생성함
두 접근 모두 흥미롭고 읽는 재미가 있음
정말 멋진 프로젝트였음
참고로 작성자가 본다면, 타일의 superposition 상태(가능한 옵션 집합)를 bitfield로 표현하는 방법을 고려했는지 궁금함
예전에 WFC를 구현할 때 bitfield로 바꾸자 속도 향상이 엄청났음. 백트래킹보다 전체 청크를 다시 계산하는 게 더 빨라졌음
나도 비슷한 경험이 있음. 내 WFC 봇은 Carcassonne 맵을 생성하는데, bitset 라이브러리를 사용하면서 성능이 크게 개선됨
일정 주기마다 상태를 스택에 저장하고, 막히면 마지막 상태로 되돌아가는 식으로 동작함
변수 이름이 tenper인 걸 보면 과거의 나를 약간 원망하게 됨
제약을 만족하는 배열을 찾는 게 가장 어려운 부분 같음
혹시 SAT solver를 사용하는 대안이 있을까 생각해봄. 다만 그럴 경우 항상 ‘쉬운’ 해만 찾고 무작위성이 떨어질 수 있음
일부 SAT 솔버는 초기 변수값을 무작위로 설정할 수 있지만, 그게 곧 무작위 해답을 의미하진 않음. 혹시 비슷한 시도를 해본 사람이 있는지 궁금함
SAT 솔버는 계산 복잡도도 높고, 형식 방법(formal methods) 을 배우지 않은 사람에게는 이해가 어렵다는 문제가 있음
반면 WFC는 단순한 brute force 방식이라 구현이 쉽고, 막다른 길만 많지 않다면 계산 비용이 낮음
게임에서는 완벽한 해보다 ‘충분히 괜찮은’ 결과면 되기에 WFC가 더 실용적일 수 있음
영감을 주는 프로젝트였음. 참고 자료도 훌륭하고 소스 코드도 공개되어 있음
여기에 Here Dragons Abound의 비주얼 스타일을 결합하면 멋질 것 같음
비정사각형(non-square) 그리드에서의 WFC 탐구가 흥미로움
제약 전파의 복잡도가 기존 예제보다 훨씬 높을 것 같음
이런 복잡한 위상에서는 Constraint Logic Programming 같은 다른 제약 솔버가 표현력과 성능 면에서 유리할 수도 있겠다는 생각이 듦
Hacker News 의견들
글에서 backtracking을 단순히 500단계로 제한했다고 하지만, 실제로 제약 프로그래밍은 매우 흥미롭고 복잡한 분야임
Knuth의 Algorithm X와 dancing links를 사용하면, 글에서 언급된 "Layer 2" 영역을 86%보다 높은 성공률로 해결할 수 있을 것 같음
또한 다양한 휴리스틱을 적용하면 단순한 brute force보다 훨씬 빠르게 탐색 가능함. Sudoku 솔버를 만들어본 사람이라면 brute force가 얼마나 느려지는지 잘 알 것임
예를 들어 MiniZinc은 여러 솔버 백엔드를 지원하는 고수준 모델링 언어를 제공함
직접 알고리즘을 짜기보다 이런 산업용 솔버를 활용해 문제를 모델링하고, 솔버가 무작위 혹은 전체 탐색으로 해답을 찾게 하는 편이 효율적임
그러면 솔버 작성에 시간을 쓰기보다, 문제 정의를 조정해 더 흥미로운 맵을 만드는 데 집중할 수 있음
내 노트북(11세대 Core i5, Iris Xe, Chrome 최신 버전)에서는 데모가 5 FPS로 실행됨. GPU가 병목인 듯함
글에서는 모바일에서 60 FPS로 돌아간다고 했기에 좀 더 효율적일 줄 알았음
맵은 아름답지만, WFC의 타일 단위 제약 때문에 비자연스러운 결과가 생김. 비국소적 영향(non-local influence)을 반영하기 어렵기 때문임
타일을 하나씩 탐험하는 게임에는 괜찮지만, 전체 맵 생성에는 적합하지 않음
Red Blob Games의 노이즈 기반 접근법이 더 나은 결과를 보여줌. 강은 습도 추적으로, 도로나 다리는 별도 패스로 처리하면 더 빠르고 견고함
그래도 WFC는 흥미로운 프로그래밍 문제라 구현 자체는 즐거웠을 것임. 전반적으로 훌륭한 글과 인상적인 데모였음
Oskar Stålberg가 Wave Function Collapse(WFC) 를 여러 게임에서 사용했음. 대표적으로 Townscaper가 있음
관련 발표 영상은 SGC21 - Beyond Townscapers에서 볼 수 있음
Jasper Flick의 Unity 튜토리얼 Hex Terrain이 떠오름
이 프로젝트는 미리 만든 타일을 제약 조건으로 맞추는 반면, Jasper의 튜토리얼은 타일 경계를 동적으로 생성함
두 접근 모두 흥미롭고 읽는 재미가 있음
정말 멋진 프로젝트였음
참고로 작성자가 본다면, 타일의 superposition 상태(가능한 옵션 집합)를 bitfield로 표현하는 방법을 고려했는지 궁금함
예전에 WFC를 구현할 때 bitfield로 바꾸자 속도 향상이 엄청났음. 백트래킹보다 전체 청크를 다시 계산하는 게 더 빨라졌음
일정 주기마다 상태를 스택에 저장하고, 막히면 마지막 상태로 되돌아가는 식으로 동작함
변수 이름이
tenper인 걸 보면 과거의 나를 약간 원망하게 됨제약을 만족하는 배열을 찾는 게 가장 어려운 부분 같음
혹시 SAT solver를 사용하는 대안이 있을까 생각해봄. 다만 그럴 경우 항상 ‘쉬운’ 해만 찾고 무작위성이 떨어질 수 있음
일부 SAT 솔버는 초기 변수값을 무작위로 설정할 수 있지만, 그게 곧 무작위 해답을 의미하진 않음. 혹시 비슷한 시도를 해본 사람이 있는지 궁금함
반면 WFC는 단순한 brute force 방식이라 구현이 쉽고, 막다른 길만 많지 않다면 계산 비용이 낮음
게임에서는 완벽한 해보다 ‘충분히 괜찮은’ 결과면 되기에 WFC가 더 실용적일 수 있음
영감을 주는 프로젝트였음. 참고 자료도 훌륭하고 소스 코드도 공개되어 있음
여기에 Here Dragons Abound의 비주얼 스타일을 결합하면 멋질 것 같음
OP가 이미 알고 있을 수도 있지만, Red Blob Games의 Hexagon 수학 페이지에는 훌륭한 예제와 코드가 많음
비정사각형(non-square) 그리드에서의 WFC 탐구가 흥미로움
제약 전파의 복잡도가 기존 예제보다 훨씬 높을 것 같음
이런 복잡한 위상에서는 Constraint Logic Programming 같은 다른 제약 솔버가 표현력과 성능 면에서 유리할 수도 있겠다는 생각이 듦
Dorfromantik이 떠오름. Steam 링크