Процедурная генерация уровней, которые точно решаемы
В своей головоломке я хотел бесконечные уровни без ручной расстановки. Насыпать случайных плиток на поле — дело пяти минут. Беда в том, что случайный уровень с большой вероятностью нерешаем, а нет ничего хуже, чем головоломка без решения: игрок не понимает, тупит он или игра сломана.
Соблазн, который не работает
Первая мысль — генерировать случайно, а потом проверять решателем: решаемо — оставляем, нет — генерируем заново. Для простых уровней сойдёт, но с ростом сложности доля решаемых случайных раскладок падает почти до нуля, и генератор начинает крутиться сотнями попыток. Плюс нужен полноценный решатель, а это отдельная большая работа.
Генерация от решения
Приём, который всё изменил: строить уровень с конца. Не насыпать случайность и проверять, а начать с заведомо решённого состояния и перемешать его обратимыми ходами.
- Беру собранное, «победное» поле — оно решаемо по определению.
- Делаю N случайных разрешённых правилами ходов в обратную сторону.
- Получившаяся раскладка гарантированно решаема: чтобы её пройти, достаточно повторить те же ходы в прямом порядке.
Сложность уровня — это просто число обратных ходов N. Хочешь легче — меньше перемешиваешь. Проверять решаемость больше не нужно: она встроена в способ генерации.
Так собирают перемешивание кубика Рубика: никто не проверяет случайный кубик на собираемость — его просто крутят из собранного, и он всегда собираем.
Чтобы не было скучно
У приёма есть тонкость: чисто случайные обратные ходы дают пресные уровни. Я добавил лёгкое смещение — генератор охотнее выбирает ходы, которые двигают плитки в разные углы, а не топчутся в одном месте. Ещё отсекаю раскладки, где решение получилось слишком коротким (два хода — не головоломка), и переигрываю.
Один и тот же уровень по желанию
Раз генерация детерминированная, весь уровень задаётся одним числом — зерном (seed) генератора случайных чисел. Это удобно: «уровень дня» — это просто зерно от сегодняшней даты, у всех игроков одинаковое. И баг-репорт «на уровне 4820 что-то не так» воспроизводится мгновенно — достаточно того же зерна.
Мораль простая: не проверяй сложную случайность на корректность, а строй её так, чтобы она была корректной по построению. Для головоломок это разница между генератором, который иногда работает, и генератором, который не может выдать плохой уровень.