Процедурна генерація рівнів · Поширення обмежень · Вибір за ентропією
Спостерігайте алгоритм WFC, що генерує узгоджені тайлові мапи в реальному часі. Тайли поширюють обмеження суміжності по сітці, а ентропія керує порядком колапсу.
WFC підтримує суперпозицію можливих тайлів у кожній клітині. Клітина з найнижчою ентропією Шеннона колапсує першою. Поширення обмежень усуває несумісних сусідів, зменшуючи ентропію по сітці.
Оберіть набір тайлів та розмір сітки. Натисніть Старт для спостереження колапсу. Клітини колапсують по одній, обмеження поширюються назовні. Колір показує залишкову ентропію.
WFC створений Максимом Гуміним у 2016 році, натхненний нотацією квантової механіки. Алгоритм використовується в комерційних іграх (Townscaper, Bad North) та архітектурному дизайні.
Ця демонстрація запускає алгоритм колапсу хвильової функції (Wave Function Collapse) — метод задоволення обмежень для процедурної генерації карт. Кожна клітинка сітки починає в суперпозиції всіх дозволених плиток. На кожному кроці симуляція колапсує клітинку з найнижчою ентропією — тут це просто кількість плиток-кандидатів, що залишилися, — а потім поширює цей вибір назовні, відсіюючи сусідів, чиї крайові сокети більше не збігаються. Запозичений квантовий словник є метафоричним, але отримані карти виходять узгодженими й напрочуд органічними.
WFC-розв'язувач на основі плиток на квадратній сітці. Кожна плитка має чотири крайові сокети (північ, схід, південь, захід); дві плитки можуть стояти поруч лише тоді, коли їхні звернені одна до одної сокети мають однаковий id. Колапс випадково обирає клітинку з найменшою кількістю кандидатів серед рівних, фіксує одну плитку, а крок поширення на основі стеку фільтрує кожного зачепленого сусіда. Клітинки, які неможливо задовольнити, рахуються як суперечності.
Натисніть «Нова карта», щоб скинути, «Крок», щоб колапсувати одну клітинку, або «Авто» для безперервного запуску. Вкладки «Повільно/Середньо/Швидко» задають затримку на крок (200, 30 або 0 мс). Повзунок розміру сітки охоплює від 10 до 50 клітинок на бік, і ви можете перемикатися між наборами плиток «Земля» та «Підземелля». Панель «Статистика» відстежує колапсовані клітинки, ті, що залишилися, та будь-які суперечності.
Колапс хвильової функції опублікував Максим Гумін у 2016 році, назвавши його на честь квантово-механічної ідеї про те, що виміряний стан осідає в один результат. Тепер ця техніка з'являється в комерційних іграх, таких як Townscaper і Bad North, а також в архітектурних інструментах та інструментах синтезу текстур.
Це техніка процедурної генерації, яка заповнює сітку плитками так, щоб кожна сусідня пара дотримувалася набору правил суміжності. Кожна клітинка починає з усіма можливими плитками, і алгоритм багаторазово фіксує одну клітинку та поширює наслідки, доки вся сітка не стане узгодженою. Назва є аналогією до квантового вимірювання, а не реальною фізикою.
Розв'язувач шукає неколапсовану клітинку з найменшою кількістю плиток-кандидатів, що залишилися, обираючи серед рівних випадково. Він присвоює цій клітинці одну випадкову плитку з її кандидатів, а потім виконує прохід поширення: кожен сусід залишає лише ті плитки, чий звернений крайовий сокет збігається, і будь-яка зміна поширюється далі назовні через стек.
«Нова карта» очищає та перезапускає, «Крок» виконує один колапс, а «Авто» зациклюється з обраною швидкістю (200, 30 або 0 мс на крок). Повзунок сітки задає довжину сторони від 10 до 50 клітинок. «Земля» будує воду, пляж, траву, ліс і гірський рельєф; «Підземелля» будує порожнечу, стіни, коридори, кімнати, смолоскипи та лаву, кожне зі своєю сумісністю сокетів.
Ентропія — це міра того, наскільки клітинка ще не визначена. У цій симуляції вона наближено оцінюється кількістю плиток, якими клітинка ще може стати; класичний алгоритм використовує ентропію Шеннона, зважену за частотами плиток. Колапс клітинок із низькою ентропією спочатку зберігає узгодженість найбільш обмежених областей і зменшує ймовірність глухих кутів.
Суперечність виникає, коли поширення залишає клітинку без жодної придатної плитки, тобто жодна плитка не може задовольнити всіх її сусідів. Оскільки ця демонстрація використовує простий упорядкований колапс без зворотного відстеження, вона розв'язує такі клітинки, примусово встановлюючи запасну плитку та рахуючи цю подію, замість перезапуску. Багатші реалізації виконують зворотне відстеження або перезапуск, щоб гарантувати повністю коректну карту.