Optymalizacja algorytmu wave function collapse pod kątem czasu wykonania

Abstract

Algorytm <i>wave function collapse</i> (WFC) ma zalety, dzięki którym stanowi narzędzie przydatne w generowaniu proceduralnym, jednak często jest wymagający obliczeniowo, co ogranicza możliwości jego praktycznego stosowania. W niniejszej pracy przeanalizowano czas wykonania algorytmu WFC i zaproponowano metody jego optymalizacji. Z przeprowadzonych testów wynika, że wąskim gardłem jest krok obserwacji, w szczególności obliczanie minimalnej entropii. Aby skrócić czas wykonania algorytmu, wykorzystano dwie techniki optymalizacyjne: zapamiętywanie wartości entropii poszczególnych komórek oraz buforowanie listy indeksów komórek o aktualnie najniższej entropii. Testy przeprowadzone na siatkach o różnych rozmiarach wykazały, że zaproponowane usprawnienia pozwoliły na ponad 100-krotne przyspieszenie algorytmu, co znacząco poprawia jego użyteczność w zastosowaniach wymagających większej wydajności.

The wave function collapse (WFC) algorithm, despite its advantages in procedural generation, is often computationally expensive, limiting its practical applications. The following paper analyzes the execution time of WFC and proposes methods for its optimization. It identifies the observation step, specifically the calculation of minimum entropy, as a key bottleneck. Two successive optimization techniques are introduced: memoization of individual cell entropy values and caching of the list of cell indices with the currently lowest entropy. Tests conducted on grids of varying sizes demonstrate that the proposed improvements achieve speedups exceeding 100x, significantly enhancing the algorithm’s utility in performance-demanding applications.