Как стать автором
Обновить

Комментарии 13

Спасибо за статью, самому в юности нравилась задача написания солвера для Сокобана. Подскажите, приходилось ли решать обратную задачу: построение уровней для игры, с неким критерием оптимальности, например:
  • максимальное число шагов оптимального решения при минимальном размере поля
  • максимального различия (разнообразия) генерируемых уровней
  • максимальной длины решения при минимальном числе ящиков на поле
  • и т.д.

Понятно, что критерии слабо формализованы, но суть их сводится к генерации «интересных и разнообразных» уровней. Есть ли общепринятые подходы к задачам генерации уровней для подобных головоломок?
Нельзя ли пойти от обратного: нагенерировать уйму случайных уровней с нужным размером поля и числом ящиков и пройдя по ним солвером считать количество ходов для каждого, отсеивая уровни не удовлетворяющие запросу или не решаемые?
Наверное можно алгоритмом коллапса волновой функции строить «приемлемые» позиции, которые в дальнейшем проверять солвером. Ну это так, с целью отбросить на раннем этапе заведомо непроходимые карты. На маленьких размерностях хватит наверное обычного рандома.
Задача интересная, можно попробовать нагенерировать случайно много уровней, затем генетическими алгоритмами отобрать нужные, и т.д. в цикле. Через n поколений получим самые подходящие уровни.
Решётка # это стена, через неё нельзя пройти и продвинуть ящик.
Буква O это ящик.
Буква X это метка, куда нужно переместить ящик.
Собака @ означает игрока.
Точка. означает пустое место.
Буква G это ящик на метке.

Какая буква обозначает игрока на месте куда надо переместить ящик (X и @ для одной и той же клетки)?
@. Это видно на анимации.
1. Не нашёл решения 11-го уровня в конце статьи.
2. Хотелось бы иметь оценки скорости работы и объёма памяти для более сложных уровней.
3. Не вникал глубоко в код, поэтому вопрос — вершины в графе порождаются каждый раз динамически из родительской и сохраняются? Если сохраняются, то есть ли проверка, были ли мы в данной конфигурации? Сколько вершин в графе получается, когда решение найдено?
4. Что понимается под AI в данном алгоритме? Поиск пути A*?
5. «граф инцидентных клеток» — это какой-то неправильный термин. Лучше говорить о компонентах связности графа.
1. Добавил решение в спойлере.
2. Если брать BFS, то он будет за полиномиальное время со степенью, равной количеству меток. Поэтому чем больше меток, тем дольше выполнение.
3. Не совсем понял о чём вы. Да, проверка есть, мы храним множество посещённых вершин.
4. Под «AI» понимается BFS и A*, назвал статью «AI на минималках», т.к. это известные, чисто детерминированные алгоритмы без машинного обучения и прочих приблуд.
Тема на хабре поднималась применительно к одному из клонов сокобана — BoxWorld от китайского разработчика: «Бот для игры в Sokoban брутфорсом» — в 2011 году.
К сожалению, это приложение работало в XP, но не работает в Win 7 64 и Win 10 64
Но есть клон клона в Microsoft Store с одноименным названием.
И есть картинка самого большого уровня в статье:
Картинка
image

egryaznov, хороший вызов для Вашего бота? :-)
Upd. BoxWorld — 16 битное Windows приложение. В Windows XP запускалось через NTVDM.
На Windows 10 64 NTVDM нет и нет возможности установить (на Windows 10 32 можно включить соответствующий легаси компонент).
Но возможность запустить старичка на 64 битной системе все же есть — WineVDM
Саму игру взять можно здесь.
Игра запоминала текущий уровень и результаты в файл c:\windows\boxworld.ini.
Количество меток конечно сильно ухудшает время работы, каждая метка это +1 к степени в асимптотике. Спасти может только А* с отрезанием заранее тупиковых ветвей.
А* с отрезанием тупиковых ветвей облегчит ситуацию. Но все равно не спасает.
Проверено :(.
На английкой вики в статье про сокобан пишут что апгрейд алгоритма A* до IDA* очень помогает: en.wikipedia.org/wiki/Sokoban#cite_note-9
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.