За лаштунками
Як генеруються рівні
Поля Sokoban-Lettres не малюють вручну одне за одним. Генератор створює їх зі слова й зерна, проводить через низку перевірок і дає розв’язати розв’язувачу перед публікацією. Ця сторінка описує процес таким, яким його реалізовано насправді.
Слово й зерно
Кожен рівень походить із двох вхідних даних: слова, яке треба скласти, і зерна — числа, що живить генератор псевдовипадкових чисел. Та сама пара завжди дає те саме поле. Завдяки цьому рівень можна відтворити ідентично, а всі гравці гарантовано отримують однакове поле в межах одного Щоденного виклику.
Почати з розв’язку
Генератор спершу розміщує цілі: одну суцільну горизонтальну лінію без стін завдовжки зі слово. Якщо місця для такої лінії немає, спробу відкидають. Ящики спочатку ставлять на цілі, а потім відводять від них серією поштовхів, зіграних у зворотному напрямку. Цей метод гарантує, що хоча б один розв’язок існує: досить відтворити перемішування навпаки.
Перемішування, що не зрушило жодного ящика, відкидається, так само як і те, що залишає ящик у куті. Потім літери перерозподіляються між ящиками, щоб початкова позиція не підказувала порядку слова.
Розділи, що стають вимогливішими
Параметри генератора змінюються від першого до десятого розділу Пригоди. Між цими крайнощами кожен параметр зростає рівномірно:
- щільність стін зростає з 20% до 30% поля;
- цільова кількість поштовхів зростає з 2,5 до 6 довжин слова;
- середня відстань між ящиком і його ціллю має зрости щонайменше з 2 до 5 клітинок;
- допустима частка ящиків, уже близьких до цілі, зменшується з 50% до 20%;
- допустима частка вирівняних ящиків зменшується з 60% до 30%.
Фільтри якості
Згенероване поле не обов’язково цікаве. Тому кожен кандидат проходить низку фільтрів у такому порядку: мінімальна кількість поштовхів у розв’язку, достатня середня відстань між ящиками й цілями, достатній проміжок між ящиками, достатнє розосередження по полю, а потім обмеження на ящики, вже близькі до цілі, і на вирівняні ящики. Поле, що не пройшло хоча б один фільтр, відкидається.
Кілька кандидатів, один обраний
Для кожного рівня генератор створює кілька полів-кандидатів — від 4 у першому розділі до 16 у десятому — і дає собі до 16 спроб на кожне. Серед тих, що пройшли всі перевірки, залишають поле з найкращою оцінкою.
Перевірка розв’язувачем
Нарешті обраного кандидата передають розв’язувачу IDA*, який шукає розв’язок, економний за поштовхами. Поле, визнане нерозв’язним, відкидається. Бюджет пошуку зростає з розділами — від 100 000 до 500 000 розглянутих позицій. Якщо бюджет вичерпано без висновку, поле залишають — воно розв’язне за побудовою, — а його пар оцінюють, а не обчислюють. Пар пояснено на сторінці рахунок і пар.
Чому саме такий підхід
Генерація замість ручного малювання дає змогу щодня пропонувати нове поле трьома мовами й з різними словами, гарантуючи, що кожне з них розв’язне. Фільтри якості захищають від тривіальних полів, які генератор створює природним чином. Витоки Sokoban розповідають, як жанр перейшов від намальованих рівнів до обчислених.