В этом посте описан генератор уровней для моей игры-головоломки.
Линжат .
Пост можно читать без подготовки, но его будет легче переварить, если пройти несколько уровней.
Исходный код я опубликовано на github ; все обсуждаемое в статье есть в файле src/main.cc
.
Примерный план поста:
- Linjat — это логическая игра, в которой вам нужно покрыть линиями все числа и точки на сетке.
- Головоломки генерируются процедурно с использованием комбинации решателя, генератора и оптимизатора.
- Решатель пытается решать головоломки, как это делает человек, и присваивает каждой головоломке рейтинг интересности.
- Генератор головоломок устроен таким образом, что вы можете легко менять одну часть пазла (цифры) и при этом меняться все остальные части (точки), чтобы пазл оставался разрешимым.
- Оптимизатор головоломок многократно решает уровни и генерирует новые варианты из наиболее интересных, найденных на данный момент.
Правила
Чтобы понять, как работает генератор уровней, вам, к сожалению, необходимо разобраться в правилах игры.К счастью, они очень просты.
Головоломка представляет собой сетку, содержащую пустые квадраты, цифры и точки.
Пример: 
Цель игрока — провести вертикальную или горизонтальную линию через каждое из чисел при соблюдении трёх условий:
- Линия, проходящая через число, должна быть той же длины, что и число.
- Линии не могут пересекаться.
- Все точки должны быть покрыты линиями.
Ура! Дизайн игры готов, интерфейс реализован, и теперь осталось найти несколько сотен хороших головоломок.
А для таких игр обычно нет смысла пытаться создавать такие головоломки вручную.
Это компьютерная работа.
Требования
Что делает головоломку хорошей для этой игры? Я склонен думать, что головоломки можно разделить на две категории.Есть игры, в которых вы исследуете сложное пространство состояний от начала до конца (например, Сокобан или Час пик ), и в котором может быть неочевидно, какие состояния существуют в игре.
А есть игры, в которых все состояния известны с самого начала, и мы постепенно формируем пространство состояний, устраняя лишние (например, Судоку или Пикросс ).
Моя игра определенно попадает в последнюю категорию.
У игроков очень разные требования к разным типам головоломок.
Во втором случае они ожидают, что головоломку можно решить только путем дедукции и что им никогда не придется возвращаться назад/угадывать/методом проб и ошибок.
[0] [1] .
Недостаточно знать, можно ли решить головоломку, используя только логику.
Кроме того, нам нужен способ понять, насколько хороши головоломки, которые мы создаем.
В противном случае большинство уровней окажутся просто тривиальным шлаком.
В идеальной ситуации этот принцип можно также использовать для создания плавной кривой прогресса, чтобы уровни постепенно усложнялись по мере прохождения игроком игры.
Решатель
Первым шагом к удовлетворению этих требований является создание игрового решателя, оптимизированного для этой цели.Решатель методом перебора с обратным поиском позволит вам быстро и точно определить, разрешима ли головоломка; его также можно изменить, чтобы определить, является ли решение уникальным.
Но это не может дать представления о том, насколько сложна головоломка на самом деле, потому что люди решают ее по-разному.
Решатель должен имитировать поведение человека.
Как человек решает эту головоломку? Вот несколько очевидных ходов, которым учит внутриигровое руководство:
- Если до точки можно добраться только из одного числа, то для закрытия точки нужно провести линию от этого числа.
В данном примере до точки можно добраться только с тройки, но не с четверки:
И это приводит к такой ситуации:
- Если линия не умещается в одном направлении, то ее необходимо разместить в другом.
В примере, показанном выше, четверку больше нельзя расположить вертикально, поэтому мы знаем, что она будет горизонтальной:
- Если вы знаете, что линия длиной X должна находиться в определенном положении (вертикальном/горизонтальном) и пустого места недостаточно для размещения линии из X пустых квадратов с обеих сторон, то вам необходимо закрыть несколько квадратов посередине.
.
Если бы в приведенном выше примере четверка была тройкой, мы бы не знали, простирается ли она полностью вправо или влево.
Но мы бы знали, что линия должна охватывать два средних квадрата:
Игрок ищет способы немного растянуть одну линию, а затем снова изучает поле, потому что оно может дать ему информацию, позволяющую сделать еще один логический вывод. Создание решателя, который следует этим правилам, будет достаточно, чтобы определить сможет ли он человек решает головоломку, не возвращаясь назад. Однако это ничего не говорит нам о том, насколько сложен или интересен уровень.
Помимо разрешимости, нам нужно как-то количественно оценить сложность.
Очевидная первая идея функции подсчета очков заключается в том, что чем больше ходов требуется для решения головоломки, тем она сложнее.
Вероятно, это хороший показатель для других игр, но мой, вероятно, более важен для количества допустимых ходов, которые делает игрок.
Если игрок сможет сделать 10 логических выводов, то он, скорее всего, очень быстро найдет один из них.
Если правильный ход только один, то времени потребуется больше.
То есть в первом приближении нам нужно, чтобы дерево решений было глубоким и узким: существует длинная зависимость ходов от начала до конца, и в любой момент времени существует лишь небольшое количество способов продвижения вверх по цепочке.
[2] .
Как определить ширину и глубину дерева? Решение головоломки один раз и оценка сгенерированного дерева не дадут точного ответа.
Точный порядок сделанных ходов влияет на форму дерева.
Нам нужно рассмотреть все возможные решения и провести с ними что-то вроде оптимизации наилучшего и наихудшего случая.
Я знаком с техникой Графики перебора в играх-головоломках , но для этого проекта я хотел создать однопроходный решатель, а не какой-то перебор.
На этапе оптимизации я стремился к тому, чтобы время выполнения решателя измерялось в миллисекундах, а не в секундах.
Я решил не делать этого.
Вместо этого мой решатель на самом деле не делает один ход за раз, а решает головоломку послойно: взяв состояние, он находит все допустимые ходы, которые можно сделать.
Затем он применяет все эти ходы одновременно и снова начинает работу в новом состоянии.
Количество слоев и максимальное количество ходов, найденных на каждый слой, затем используются как приблизительные значения глубины и ширины дерева поиска в целом.
Вот так выглядит решение одной из сложных головоломок с помощью этой модели.
Пунктирные линии — это линии, растянутые на этом решающем слое, сплошные линии — те, которые не изменились.
Зеленые линии имеют правильную длину, красные еще не завершены.
Следующая проблема заключается в том, что все ходы, которые делает игрок, одинаковы.
То, что мы перечислили в начале этого раздела, — это просто здравый смысл.
Вот пример более сложного правила дедукции, для поиска которого потребуется немного больше размышлений.
Рассмотрим это поле: 
Точки C и D могут быть покрыты только пятеркой и средней четверкой (и ни одно число не может охватывать обе точки одновременно).
Это означает, что четверка посередине должна покрывать одну точку из двух и, следовательно, не может быть использована для покрытия А.
Следовательно, точка А должна быть покрыта четверкой в левом нижнем углу.
Очевидно, было бы глупо считать эту цепочку рассуждений эквивалентной простому выводу «к этой точке можно прийти только из этого числа».
Можно ли придать этим более сложным правилам больший вес в функции оценки? К сожалению, это невозможно в решателе на основе слоев, поскольку он не гарантирует нахождение решения с наименьшей стоимостью.
Это не только теоретическая проблема — на практике часто бывает, что часть поля можно решить либо одним сложным рассуждением, либо цепочкой гораздо более простых ходов.
По сути, решатель на основе слоев находит кратчайший путь, а не самый дешевый путь, и это не может быть отражено в функции оценки.
В итоге я пришел к такому решению: изменил решатель таким образом, чтобы каждый слой состоял только из одного типа рассуждений.
Алгоритм обходит правила рассуждения в приблизительном порядке сложности.
Если правило находит какие-то ходы, то они применяются, и эта итерация заканчивается, а следующая итерация начинает список с самого начала.
Затем решению присваивается оценка: каждому слою назначается стоимость на основе одного использованного правила.
Это еще не гарантирует, что решение будет наименее затратным, но при правильном подборе весов алгоритм как минимум не найдет затратное решение, если дешевое существует. Это также очень похоже на то, как люди решают головоломки.
Они сначала пытаются найти простые решения и начинают активно использовать свой мозг только в том случае, если простых ходов нет.
Генератор
В предыдущем разделе определялось, является ли конкретный уровень хорошим или плохим.Но этого недостаточно, нам еще нужно как-то сгенерировать уровни, чтобы решатель мог их оценить.
Очень маловероятно, что случайно сгенерированный мир будет разрешимым, не говоря уже о том, чтобы быть интересным.
Основная идея (она отнюдь не нова) заключается в поочередном использовании решателя и генератора.
Начнем с загадки, которая, вероятно, неразрешима: просто расставьте числа от двух до пяти в случайных квадратах: 
Решатель работает до тех пор, пока не перестанет развиваться: 
Затем генератор добавляет к головоломке дополнительную информацию в виде точки, после чего выполнение решателя продолжается.
В этом случае добавленной точки недостаточно для дальнейшего развития решателя.
Затем генератор продолжит добавлять новые точки, пока не удовлетворит решатель: 
И затем решатель продолжает свою обычную работу: 
Этот процесс продолжается либо до тех пор, пока головоломка не будет решена, либо до тех пор, пока не останется больше информации для добавления (например, когда каждый квадрат, до которого можно добраться из числа, уже содержит точку).
Этот метод работает только в том случае, если добавляемая новая информация не может опровергнуть ни один из ранее сделанных выводов.
Это было бы сложно сделать при добавлении чисел в сетку.
[3] .
Но добавление новых точек в поле имеет это свойство; по крайней мере, для правил рассуждения, которые я использую в этой программе.
Где алгоритм должен добавлять баллы? В конце концов я решил добавить их в пустое пространство, которое изначально может быть покрыто наибольшим количеством строк, чтобы каждая точка стремилась выдать как можно меньше информации.
Я не пытался намеренно разместить точку в том месте, где она была бы полезна для прогресса в решении головоломки в тот момент, когда решатель застревает. Это создает очень удобный эффект: большинство точек в начале головоломки кажутся совершенно бесполезными, из-за чего головоломка кажется сложнее, чем есть на самом деле.
Если есть много очевидных ходов, которые игрок может сделать, но ни один из них почему-то не работает так, как должен.
В результате оказалось, что генератор головоломок ведет себя немного как свинья.
Этот процесс не всегда дает решение, но он довольно быстрый (порядка 50-100 миллисекунд), поэтому его можно просто повторить несколько раз для создания уровня.
К сожалению, обычно он создает посредственные головоломки.
С самого начала слишком много очевидных ходов, поле заполняется очень быстро, а дерево решений довольно мелкое.
Оптимизатор
Описанный выше процесс давал посредственные головоломки.На последнем этапе я использую эти уровни в качестве основы для процесса оптимизации.
Это работает следующим образом.
Оптимизатор создает пул, содержащий до 10 вариантов головоломок.
Пул инициализируется новой сгенерированной случайной головоломкой.
На каждой итерации оптимизатор выбирает одну головоломку из пула и выполняет ее мутацию.
Мутация удаляет все точки, а затем слегка меняет числа (т. е.
уменьшает/увеличивает значение случайно выбранного числа или перемещает число в другую ячейку сетки).
К полю можно применить несколько мутаций одновременно.
Затем мы запускаем решатель в режиме генерации специального уровня, описанном в предыдущем разделе.
Он добавляет к головоломке достаточно очков, чтобы снова сделать ее разрешимой.
После этого снова запускаем решатель, на этот раз в обычном режиме.
Во время этого запуска решатель отслеживает а) глубину дерева решений, б) частоту необходимости использования правил разных типов, в) ширину дерева решений в разные моменты времени.
Загадка оценивается на основе критериев, описанных выше.
Функция подсчета очков предпочитает глубокие и узкие решения, а более высокие уровни сложности также придают больший вес головоломкам, требующим более сложных правил рассуждения.
Затем в пул добавляется новая головоломка.
Если в пуле больше 10 головоломок, худшая из них отбрасывается.
Этот процесс повторяется несколько раз (меня устроило около 10 000-50 000 итераций).
Версия головоломки с наивысшим баллом затем сохраняется в базе данных уровня головоломки.
Вот как выглядит прогресс лучшей головоломки за один прогон оптимизации: 
Я пробовал другие способы структурной оптимизации.
В одной версии использовался моделируемый отжиг, в других — генетические алгоритмы с различными операциями скрещивания.
Ни одно из решений не сработало так же хорошо, как наивный алгоритм с набором вариантов, поднимающимся наверх.
Уникальное единое решение
Когда головоломка имеет единственное, неповторимое решение, возникает интересная загадка.Можно ли позволить игроку предположить, что решение только одно, и сделать на основании этого выводы? Будет ли справедливо со стороны генератора головоломок предположить, что игрок так и сделает? В сообщении на HackerNews я сказал, что есть четыре способа подойти к этой ситуации:
- Заявите об уникальности решения с самого начала и заставьте генератор создавать уровни, требующие такого рода рассуждений.
Это плохое решение, поскольку оно усложняет понимание правил.
И обычно это детали, которые люди забывают.
- Не гарантируйте уникальность решения: потенциально есть много решений и примите их все.
На самом деле это не решает проблему, а отодвигает ее в сторону.
- Просто предположим, что это очень редкое событие, не имеющее практического значения.
(Это именно то решение, которое использовалось в исходной реализации.
)
- Измените генератор головоломок, чтобы он не генерировал задачки, в которых помогло бы знание уникальности решения.
(Возможно, правильное решение, но требует дополнительной работы.
)
Оказалось, что я учел только один способ, при котором уникальность решения привела к утечке информации, и это на самом деле довольно редко.
Но есть и другие; один из них по существу присутствовал на каждом уровне, который я создавал, и часто делал решение тривиальным.
Поэтому в мае 2019 года я изменил режимы Hard и Expert, чтобы использовать третий вариант.
Самый неприятный случай — это двойка с пунктиром на таком поле: 
Почему хитрый игрок сделал такой вывод? Двойка может закрыть любую из четырех соседних клеток.
Ни у одного из них нет точек, поэтому их не обязательно закрывать линией.
И квадрат ниже не пересекается ни с какими другими цифрами.
Если существует единственное решение, то должно быть так, что остальные числа покрывают три других квадрата, а два — квадрат под ним.
Решение — добавить еще несколько пунктов при распознавании таких случаев: 
Другой распространенный случай — двойка с пунктирной линией в этом поле: 
Квадраты слева и сверху ничем не отличаются от двух.
Ни в одном из них нет смысла, и ни с одного другого номера до него невозможно дозвониться.
Любое решение, в котором два покрывают верхний квадрат, будет иметь соответствующее решение, в котором они покрывают левый квадрат, и наоборот. Если бы существовало одно-единственное решение, то этого не могло бы случиться, и оба должны были бы покрывать нижний квадрат. Я решил этот тип случая, используя метод «если болит, не трогай».
Решатель применил это правило на ранних этапах списка приоритетов и присвоил таким ходам большой отрицательный вес.
Головоломки с этой функцией обычно отбрасываются оптимизатором, а те немногие оставшиеся отбрасываются на этапе окончательного выбора уровня опубликованной игры.
Это не полный список; в ходе плейтеста с целенаправленным поиском ошибок я нашел множество других правил уникальных решений.
Но большинство из них казались редкими и их было трудно найти, поэтому игру они не сильно облегчали.
Если кто-то решит головоломку, используя такие рассуждения, я не буду его за это винить.
Заключение
Изначально игра разрабатывалась как эксперимент по созданию процедурных головоломок.Дизайн игры и генератор шли рука об руку, поэтому сами методы сложно применить непосредственно к другим играм.
Вопрос, на который у меня нет ответа: стоит ли вкладывать столько усилий в процедурную генерацию? Отзывы игроков о дизайне уровней были очень неоднозначными.
В положительных комментариях обычно говорилось, что в головоломках всегда было ощущение, что в них есть какой-то хитрый трюк.
Большинство отрицательных отзывов говорили мне, что в игре отсутствует градиент сложности.
У меня есть еще пара головоломок в зачаточном состоянии, и генератор мне настолько понравился, что я, вероятно, буду использовать для них аналогичный процедурный подход. Изменю только одно: с самого начала буду проводить активное плейтестирование для поиска ошибок.
Примечания
[0] По крайней мере, я так думал.Но когда я наблюдал за игроками вживую, почти половина из них просто предполагала, а затем повторяла их.
В любом случае.
[1] Читателям моей статьи также следует прочитать статью Решение Сапера и улучшение его качества Магнус Хоффа.
[2] Чтобы уточнить, глубина/узкость дерева — это показатель, который я считаю актуальным для моей игры, а не для всех других головоломок.
Например, есть хороший аргумент что головоломка «Час пик» интересна, если она имеет несколько путей к решению почти одинаковой, но не совсем одинаковой длины.
Но это потому, что «Час пик» — это игра, в которой нужно найти кратчайшее решение, а не любое решение.
[3] За исключением добавления единиц.
В первой версии головоломки не было точек, и генератор планировал добавлять их по мере необходимости.
Но это казалось слишком ограничительным.
Теги: #Разработка игр #Алгоритмы #Игровой дизайн #Логические игры #пазлы #процедурная генерация #игра-головоломка
-
Программное Обеспечение «Смысл Жизни»
19 Oct, 24 -
Mit: Сенсорный Экран На Любой Поверхности
19 Oct, 24 -
Вечеринка По Случаю Запуска Windows 7
19 Oct, 24
