Szczegóły publikacji
Opis bibliograficzny
Optymalizacja algorytmu wave function collapse pod kątem czasu wykonania — Optimization of the wave function collapse algorithm for execution time / Filip Kowalski // W: Nauka – technika – technologia [Dokument elektroniczny] : seria wydawnicza AGH , T. 11 . — Wersja do Windows. — Dane tekstowe. — Kraków : Wydawnictwa AGH, 2025. — e-ISBN: 978-83-68219-80-7. — S. 43–59. — Wymagania systemowe: Adobe Reader. — Bibliogr. s. 58–59, Streszcz., Abstr.
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 165889 |
|---|---|
| Data dodania do BaDAP | 2026-03-06 |
| Tekst źródłowy | URL |
| DOI | 10.7494/978-83-68219-80-7_3 |
| Rok publikacji | 2025 |
| Typ publikacji | fragment książki |
| Otwarty dostęp |  |
| Creative Commons | |
| Wydawca | Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie |
Streszczenie
Algorytm wave function collapse (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.
Abstract
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.
