Привет!
В данном посте речь пойдет о моем участии в конкурсе Ludum Dare 34, который был около трех недель назад.
В результате получился пазл под названием Growing Sakura, геймплей которой можно видеть на гифке (не пугайтесь, она весит всего 300Кб):
Кратко о правилах игры: изначально у нас есть гексагональное поле и несколько корневых бутонов (или один, как на гифке выше). Из него можно пустить 3 ветки (двумя способами — кликая левой или правой кнопкой мыши). Из каждого бутона на ветке левым кликом мыши можно сделать Y-разветвление, а правым — просто продолжить ветку дальше (I-разветвление). Если в каком либо направлении ветка расти не может (соответствующая клетка занята или в нужном направлении нет клетки) — то ветка не растет. В соответствии с последним условием нужно правильно выбирать порядкок «разворачивания» веток. В итоге получится дерево (или несколько деревьев) такое, что между двумя смежными ветками нет острых углов. Цель игры — покрыть все клетки игрового поля.
Не заглядывая под кат попробуйте подумать секунд 10 и прикинуть, насколько сложной может быть эта игра.
Что за Ludum Dare?
Этот конкурс проводится раз в 4 месяца и в этот раз это было уже 34-ое по счету мероприятие. Суть конкурса (в номинации Compo): требуется за 48 часов создать компьютерную игру на заданную тему. Тема становится известна в первые минуты соревнования. Игра должно быть создана соло и с нуля (все с нуля: код, графика, звуки и тд), впрочем разрешается использовать сторонние программы и наработки кода, но о них нужно объявить заранее (скажем, написать в своем бложике на сайте Ludum Dare «я буду использовать Paint, Unity, C++ и Delphi, вот по ссылке шаблон стартового проекта»). Есть еще упрощенная расслабляющая номинация Jam, где можно делать игру командой аж 72 часа, использовать старые наработки и даже (о ужас!) не требуется в конце вместе с игрой публиковать исходники. Впрочем, лично мне номинация Jam не интересна, я в нее иногда перехожу только если в 48 часов уложиться не успеваю.
Тема конкурса определяется голосованием и в этот раз наибольшее число голосов набрали сразу две темы: «Growing» и «Two Button Controls». Можно было использовать либо одну из этих тем, либо обе сразу. Интерпретация темы остается на усмотрение участника: так, первую темы можно было интерпретировать как «Рост», «Выращивание» или «Взросление», а вторую — «Управление двумя кнопками» или «Власть двух пуговиц». Как можно видеть из описания игры выше, я в некотором смысле соединил обе темы воедино.
День первый
Когда я проснулся, конкурс уже шел пару часов. Тема очевидных решений не предлагала. Неспешно завтракая и заливаясь кофе, я обдумывал что-же такое подогнать интересное под данную тему. Конечно же, хотелось соединить обе темы воедино. Всплыли несколько концептов:
- Головоломка, которая эмулирует оконный менеджер: на экране куча окошечек (с двумя кнопками каждое!), их надо все закрыть, но все осложняется тем, что обе доступные кнопки иногда совершают очень хитрые действия (скажем, закрыть окошко правее данного). В качестве шутки была идея сделать окна с заголовком «Agreement», заполненные текстом вроде «Bla-bla-bla-bla» с двумя кнопками «Agree» и «Disagree», которые просто это окно закрывают.
- Стратегия-рогалик: развитие подземной базы. База состоит из квадратных тайлов, с каждым из которых можно сделать одно из двух действий, таким образом расширяя (growing!) базу.
- Какой-нибудь странный механизм, состоящий из кучи агрегатов, на каждом агрегате есть две кнопки «Вклюкл» и «Выклюкл».
- Опять стратегия, на этот раз минималистичный клон Settlers II. Тайлы гаксагональные, с ними опять же можно сделать одно из двух действий (больше дорог или построить домик). Задумка была в том, что для постройки более крутых зданий нужно было подвести к тайлу несколько дорог. Но эксперименты на бумажке показали, что дороги как-то быстро заканчивались, что останавливало рост поселения.
Все эти концепты были то скучные, то слишком сложные в реализации (а у меня до этого конкурса был месяц авралов по работе и учебе, поэтому напрягаться ой как не хотелось). Еще была идея сделать клон Super Hexagon (там управление двумя кнопками!), но на эту идею я забил, ибо там не было «Growing». К середине дня появилась следующая концепция, которая получилась путем упрощения идеи про поселенцев:
- Есть гексагональное поле, в некоторых клетках — камни, в некоторых — бобы. И мы из бобов должны вырастить корни каких-то растений. Корни выращиваются по правилам, которые были описаны в самом начале данного поста. Для каждого боба известно сколько клеток должна покрыть корневая система, чтобы бобовое дерево росло большим и здоровым. Ну и задача игрока — вырастить корешки так, чтобы все бобы выросли.
Правила игры возникли из следующей математической задачки:
Стало быть, я просто предположил, что следуя таким правилам можно сделать какую-нибудь достаточно сложную головоломку.
По-быстрому набросал прототип игровой механики:
И увидел, что это хорошо!
Под конец первого дня идея выращивания корней была преобразована в идею выращивания ветвей сакуры (но в коде игры все объекты до сих пор называются в соответствии с корнями!). Для упрощения игры все числа были выкинуты и цель свелась к простейшей по формулировке: просто покрыть все игровое поле. Прототип игры дорос до следующего:
Была задумка сделать так, чтобы ветви дерева становились толще в соответствии с расстоянием до самого дальнего листа (и это видно на гифке). Однако для длинных ветвей растяжение становилось настолько большим, что портился их внешний вид. Довольно много времени я потратил на то, чтобы все получилось красиво. В итоге забил — еще много вещей надо было сделать. Отныне все ветви оставались одинаковой толщины.
На этом я решил закончить первый день и ушел спать.
День второй
Как обычно, на сне после первого дня я решил не экономить, а вместо этого не спать вторую ночь. С утра сидел придумывал уровни. Даже набросал в Ворде гексагональную сетку и распечатал, орудуя далее карандашом и ластиком. Стало понятно, что без автоматического решателя дальше будет трудновато.
Сказано — сделано. Набросал простенький решатель головоломки на C++. Он рекурсивно перебирает все возможные действия игрока и смотрит решена головоломка или нет. На каждой итерации перебора текущее состояние игры сохраняется в std::set. Если позже найдется такое-же состояние игры — то перебор откатывается. Таким образом, решатель не рассматривает по сто раз одни и те же варианты развития событий.
Оказалось, что упомянутая выше на двух гифках головоломка (назовем ее головоломка A) имеет аж 47 различных решений. На полный перебор потребовалось 93 секунды, при этом было рассмотрено 10810046 состояний игры. Этот солвер очень сильно помог в дальнейшем.
Пример работы решателя уже для другого уровня:
Этот уровень был решен за 7 секунд, в std::set было сохранено 711211 состояний и было найдено ровно одно решение. Странная строчка в самом низу — описание уровня, которое вставляется уже в саму игру.
Чуть позже солвер был оптимизировал эвристикой «одинокой клетки». А именно: если на каком-то шаге одна из свободных клеток оказывалась окружена занятыми клетками («стенами» или клетками, в которые уже проросли ветви сакуры), причем пустить ветвь в данную клетку из соседних невозможно — то становилось ясно, что здесь решений нет и перебор откатывался. После добавления этой эвристики головоломка A стала обрабатываться за 5 секунд при количестве рассмотренных состояний всего 723225.
До конца второго дня я руками рисовал интересные игровые сетки и решал их моей программкой. Тем временем, я добавил в игру меню (ну а что еще делать, когда солвер перебирает решения?), перерисовал иконки. Игра стала выглядеть следующим образом:
Как можно видеть из гифки, я поставил себе довольно амбициозную задачу: разработать целых 40 головоломок. К моменту создания гифки были готовы только 17 уровней из 40. До конца конкурса оставалась еще ночь, а именно около 10 часов.
Часть уровней генерировались следующим образом: рисовалась какая-нибудь симметричная фигура, в случайную ее клетку тыкался корневой бутон. После этого запускался решатель. Если полученных решений получалось слишком много или вообще ни одного — уровень немного модифицировался (немного меняем форму или пересаживаем корневой росток куда-нибудь в другое место) и опять запускался решатель, и так до тех пор, пока подходящий уровень не был построен.
Для других уровней фигура была намеренно несимметричной, обычно там несколько ветвей сакуры сходились в общий «ком», после чего нужно было их аккуратно сплести друг с другом. Эти уровни создавались тоже с помощью решателя.
Далее я стал добавлять уровни, которые имели несколько корневых бутонов. Игра сразу же стала гораздо разнообразней! Пример уровня с несколькими бутонами:
Да, иногда для прохождения уровня не удается покрыть всего один бутон…
Ночью я добавил в игру экран с правилами игры, создал несколько звуков с помощью замечательной программки Bosca Ceoil ну и наконец добил все 40 уровней (сорок, Карл!), как и планировалось. Последние уровни настолько сложны, что не поддаются полностью моему решателю: он находит несколько решений перед нем, как заканчивается память, и он крашится. Поэтому я не знаю точно сколько именно там решений, хотя с уверенностью можно сказать — все головоломки в игре имеют решение.
Игра была закончена в последний час и уже слабеющими руками выхожена на сайте конкурса.
После завершения конкурса организаторы выделяют 3 недели на голосование. Участники Ludum Dare скачивают игры других участников и оценивают их. Я тоже этим занимался около недели, а параллельно все думал насколько игра Growing Sakura может быть сложна. В результате, все вылилось в следующее:
Growing Sakura NP-трудна
Здесь я постараюсь изложить свое доказательство (надеюсь я в нем нигде не напортачил!).
В данной статье можно найти доказательство того, что задача проверки существования гамильтонова цикла в планарном кубическом 3-связном графе NP-полна (давайте для краткости назовем ее задача X). Сразу расшифрую все непонятные слова:
Граф — это несколько точек (они называются вершинами), некоторые пары которых соединены линиями (они называются ребрами). Граф называется планарным если его можно расположить на плоскости так, чтобы ребра не пересекались. Граф называется кубическим, если из каждой его вершины исходит ровно 3 ребра. Граф называется 3-связным, если для того, чтобы раздраконить его хотя бы на 2 части, надо удалить не менее 3 ребер. Гамильтонов цикл в графе — это последовательность попарно различных вершин v1, v2,…, vn таких, что vi и vi+1 связаны ребром для любого 1<=i<n, а также ребром связаны вершины vn и v1, где n — это число вершин в графе. Например, на следующей картинке изображен гамильтонов цикл в планарном кубическом 3-связном графе:
С определением NP-трудности и NP-полноты все не так просто. Но я попробую вкратце разъяснить дело под спойлером.
Она: ответь мне, только честно, да или нет, хорошо?
Он: спрашивай
Она: почему мужчины смеются над блондинками?
Он: да
(баш о decision problem)
Класс NP — это множество таких задач разрешимости, для которых ответ «да» можно проверить за полиномиальное время при наличии некоторых дополнительных сведений (так называемого сертификата). Причем, для любых входных параметров, если ответ «да», сертификат должен обязательно существовать (а не так, чтобы для некоторых входных данных при ответе «да» он есть, а для некоторых его нет). Например, для задачи разрешимости «Вот есть граф G на n вершин, верно ли, что в нем есть гамильтонов цикл?» сертификатом является (например!) сам гамильтонов цикл — последовательность из n чисел, указывающих в каком порядке этот гамильтонов граф обходить. Значит она лежит в классе NP.
Очень похож на класс NP так называемый класс co-NP — множество таких задач разрешимости, для которых ответ «нет» можно проверить за полиномиальное время при наличии дополнительных сведений (так называемого контрпримера). Например, для задачи разрешимости «Вот число X, верно ли, что оно простое?» контрпримером является делитель числа X, отличный от 1 и X. Значит эта задача лежит в классе co-NP. Опять же, на каждое «нет» обязательно нужен контрпример.
Еще есть класс P — множество всех задач разрешимости, которые можно решить за полиномиальное время. Заметим, что формально в P лежат именно что задачи разрешимости, т.е. вопрос «Сколько будет A+B?» туда не входит! (Он входит немного в другой класс FP). Но задачи подобного рода всегда можно переформулировать в серию задач разрешимости, добавив еще один параметр k: «Верно ли, что k-й бит выражения A+B равен 1?». Сделав серию таких запросов мы, фактически, полиномиально сводим по Куку вопрос «Сколько будет A+B?» к задаче разрешимости. Но об этом чуть ниже.
Любая задача из класса P лежит в классе NP, поскольку ответ «да» можно проверить за полиномиальное время с помощью вообще любого сертификата (например, подойдет сертификат "мамой клянусь!"). Алгоритм проверки следующий: выкинуть сертификат и просто найти ответ на изначальный вопрос с нуля за полиномиальное время. По аналогичной же причине любая задача из класса P также лежит в классе co-NP.
Еще раз о тонкостях принадлежности к классам. Вопрос «Верно ли, что число X простое?» принадлежит co-NP, а вопрос «Верно ли, что число X составное?» принадлежит NP. Согласно алгоритму трех индусов, на оба из этих вопросов можно найти ответ за полиномиальное время. Значит оба эти вопроса, ко всему прочему, принадлежат классу P! Однако эти оба вопроса имеют мало общего со следующим очень похожим вопросом «Чему равен наименьший делитель X, больший 1?» (который ни в NP, ни в co-NP не входит, и отвечать за полиномиальное время на него никто не умеет (и для шифрования RSA это хорошо!)). Т.е. смотрите, вопрос «Верно ли, что число X составное?» лежит в NP, поскольку для ответа «да» существует сертификат — делитель X между 1 и X, который позволяет за полиномиальное время проверить, что ответ действительно «да». Но, благодаря алгоритму трех индусов, подходящим сертификатом также является и "мамой клянусь!", т.е. алгоритм, решающий задачу, не должен предоставлять тот сертификат, который показывает принадлежность задачи к классу NP!
Кстати, существуют задачи разрешимости, которые не принадлежат ни к P, ни к NP, ни к co-NP. Например, классическая проблема останова: «Дан код программы, верно ли, что он выполнится за конечное время?». Но это уже совсем другая история…
Теперь о полиномиальной сводимости. Есть несколько схем сводимости задач друг к другу.
По Карпу, задача U считается полиномиально сводимой к задаче V, если для любых входных данных u для задачи U мы можем их за полиномиальное время преобразовать во входные данные v для задачи V, скормить их V, и получить ответ (который «да» или «нет», помните?), который будет ответом и на изначальную задачу U.
По Куку, задача U считается полиномиально сводимой к задаче V, если существует полиномиальный по времени алгоритм, который решает задачу U, при этом используя задачу V в качестве оракула, т.е. алгоритм может строить сколько угодно (но полиномиальное количество!) наборов входных данных для задачи V и узнавать ответ за одну итерацию.
Оба эти сведения показывают, что в некотором смысле задача U не сложнее задачи V. Т.е. если мы умеем решать V в некотором смысле быстро — то и U мы тоже умеет решать в некотором смысле быстро. А если мы не умеем решать U в некотором смысле быстро, то и V мы быстро в некотором смысле решать не умеем. Таким образом, упомянутый выше вопрос «Сколько будет A+B?» не сложнее вопроса «Верно ли, что k-й бит выражения A+B равен 1?», а поскольку второй из них лежит в P, на первый вопрос ответить легко (за полиномиальное время!), хотя он и не лежит в P.
По сути, сведение по Карпу — частный случай сведения по Куку, т.е. в случае сведения по Карпу оракул вызывается единственный раз в самом конце и его ответ без всяких изменений считается ответом на исходную задачу. Ну и еще, в случае сведения по Куку, задачи U и V не обязательно должны быть задачами разрешимости.
Задача из класса NP называется NP-полной, если любая задача из класса NP (т.е. вообще любая!) полиномиально к ней сводится. Задача выполнимости булевых формул (SAT) — первая задача, для которой была доказана NP-полнота явным сведением любой задачи из класса NP к SAT. Т.е. SAT является некой универсальной задачей, которая, будучи оракулом, позволяет быстро решать любую задачу из класса NP. Позже было обнаружено, что огромное количество других задач из класса NP также NP-полны! Обычно, это легко доказывается полиномиальным сведением какой-нибудь другой NP-полной задачи (как правило, SAT, возможно, через цепочку других задач) к данной.
Задача называется NP-трудной, если к ней сводится какая-нибудь NP-полная задача. Если эта NP-трудная задача еще и сама принадлежит классу NP, то она, очевидно, является NP-полной задачей. Пример NP-трудной задачи, не принадлежащей к классу NP — задача упаковки в контейнеры «В какое наименьшее число контейнеров можно упаковать все эти предметы?», поскольку к ней сводится NP-полная задача о дележе «Можно ли разделить все эти предметы на две равные по суммарному весу кучки?».
Самый большой вопрос во всей этой демагогии такой: а решается ли какая-нибудь NP-полная задача за полиномиальное время? Если да — то тогда P=NP и любую задачу из класса NP можно будет решать за полиномиальное время и это очень хорошо для многих прикладных комбинаторных задач и очень плохо для некоторых алгоритмов шифрования.
Для формальности сформулируем задачу X и игру Growing Sakura как задачи разрешимости.
Задача X: «Дан кубический планарный 3-связный граф G, верно ли, что в нем существует гамильтонов цикл?».
Игра Growing Sakura: «Дан уровень из игры Growing Sakura, верно ли, что он имеет решение?».
Ну так вот, мы будем сводить NP-полную задачу X к игре Growing Sakura. Т.е. по входным данным задачи X мы построим такой уровень для Growing Sakura, что его решение будет давать ответ и для изначальной задачи X. Этим мы покажем, что задача X не сложнее, чем игра Growing Sakura.
Для этого нам потребуются следующие конструкции:
AND-gadget
Тут все просто — ветвь сакуры, пришедшая с любой из трех сторон может расти дальше в обоих направлениях одновременно.
OR-gadget
Для данного элемента ветвь сакуры должна выбрать ровно одно направление из двух (на самом деле — не более одного, но это действие бессмысленно). Второе направление придется покрывать позже и уже с другой стороны.
ONE-WAY-gadget
Эта конструкция — своеобразный диод. Она пропускает ветвь сакуры только в одном направлении.
Т.е. в таком направлении пропускает:
А в таком нет:
Мне не удалось придумать такую-же конструкцию без дополнительных корневых точек, может получится у вас?
LOCK-gadget
Самый сложный элемент, его конструирование заняло довольно много времени.
Суть этого элемента в следующем. Он имеет решения только в следующих конфигурациях:
а)
б)
При этом в следующей конфигурации решений нет:
Более того, нельзя даже покрыть ни один из крестиков, не получив при этом ситуацию «одинокой клетки».
А теперь соединим все вместе!
Из OR-гаджетов уже можно собрать первое приближение к планарному кубическому 3-связному графу. Но, правила игры требуют, чтобы были покрыты в том числе и ребра, не входящие в гамильтонов цикл. И чтобы это обеспечить, нужна более громоздкая конструкция. Вот она:
Эта конструкция соответствует одной вершине в нашем кубическом графе.
Давайте теперь рассмотрим как она работает. Без ограничения общности, пусть ветка сакуры пришла слева снизу (сразу по двум путям). Тогда покрытой окажется следующая часть схемы:
Теперь, в зависимости от того, какой из двух вариантов мы выберем, получим следующие развития событий:
Заметим, что в обоих случаях мы отправили две ветви сакуры в одном из направлений и ровно одну из них в другом направлении. Т.е. в одну сторону мы покрасили ребро в графе, а в другую — нет. Теперь, когда наш путь гамильтонов путь дойдет до той вершины в графе, куда мы сейчас не покрасили ребро, оттуда придет еще одна ветка (отмечена ниже зеленым цветом), которая разблокирует LOCK-гаджет и покроет все, что надо покрыть:
Случаи, когда мы пришли в вершину, для которой одна или две соседние вершины уже были посещены нашим путем, предлагается разобрать читателю самостоятельно.
Ну и теперь просто для всего планарного кубического 3-связного графа построим громадный уровень, проверим есть ли у него решение. Если есть — то для исходного графа цикл восстановить несложно — достаточно посмотреть как растет ветка сакуры в OR-гаджетах (хотя, формально, явно его восстанавливать не требуется). Построить такой уровень всегда можно — все гаджеты можно вращать и соединять цепочкой ячеек достаточной длины. Поскольку изначально граф планарный — решать задачу перекрещивания путей не нужно.
Казалось бы все, доказали? Нет, не доказали. У построенного уровня решения вообще не будет — у нас не инициирован процесс «цепной реакции» — гамильтонову пути неоткуда начинаться. Решается это очень просто. Берем любое ребро (а точнее, соответствующий ему LOCK-гаджет) и делаем так:
Красный кружочек — это откуда мы начинаем растить нашу ветку. И нам обязательно надо покрыть обрывающийся конец, чтобы гамильтонов цикл замкнулся!
Теперь-то доказали? Да нет же! Вдруг в графе есть гамильтонов цикл, который не проходит по ребру, с которого мы начали его искать! Что же делать? Нужно попробовать поискать цикл начиная с другого ребра. Очевидно, что для любых двух ребер, выходящих из одной вершины, хотя бы по одной из них будет проходить искомый гамильтонов путь, если он существует. Поэтому для решения задачи X нужно будет не более двух уровней игры Growing Sakura.
«Позвольте!» — скажете вы, — «чуть выше было написано, что мы будем решать только один уровень игры Growing Sakura, эквивалентный графу в задаче X!» Верно, я вас нагло обманул! Впрочем, доказательство от этого не портится — просто я воспользовался сведением по Куку, а не сведением по Карпу.
Теперь NP-трудность игры Growing Sakura доказана! Ура, товарищи!
Growing Sakura NP-полна
Как известно, задача NP-полна, если она NP-трудна и лежит в классе NP. Первый пункт мы доказали чуть выше.
Принадлежность же данной задачи к NP довольно очевидна. Напомним, что задача принадлежит к классу NP, если решение данной задачи — один из ответов «да» или «нет», причем для ответа «да» существует сертификат, который позволяет проверить, что ответ действительно «да» за полиномиальное время. Ну и действительно, для игры Growing Sakura сертификат можно записать в виде строки длины O(n), сохраняя в каком порядке и какой кнопкой мы нажимали на соответствующие клетки, где n — количество клеток на поле. Ну и за O(n) можно проверить что сертификат «валидный» — просто разворачивая ветки в соответствии с сертификатом и правилами игры.
Ура, Growing Sakura NP-полна! Если вдруг кто напишет решалку для данной игры, работающую за полиномиальное время — можете забрать свой миллион.
Заключение
То, что Growing Sakura NP-полна, не означает, что все уровни в данной игре будут непомерно сложны. Это означает всего лишь, что такие уровни возможно создать. А остальное уже зависит от дизайна уровней. Известно, что многие классические игры от Nintendo NP-трудны, и это не мешает наслаждаться ими. NP-трудна даже такая казуалка как Candy Crush, не говоря уже о тетрисе, сапере и прочих судоку.
Голосование на Ludum Dare закончится уже завтра, в update я опубликую какое место мне удалось заполучить. Надеюсь войти в сотню лучших игр.
Автор: ripatti
