Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 13
Спасибо за статью, самому в юности нравилась задача написания солвера для Сокобана. Подскажите, приходилось ли решать обратную задачу: построение уровней для игры, с неким критерием оптимальности, например:
Понятно, что критерии слабо формализованы, но суть их сводится к генерации «интересных и разнообразных» уровней. Есть ли общепринятые подходы к задачам генерации уровней для подобных головоломок?
- максимальное число шагов оптимального решения при минимальном размере поля
- максимального различия (разнообразия) генерируемых уровней
- максимальной длины решения при минимальном числе ящиков на поле
- и т.д.
Понятно, что критерии слабо формализованы, но суть их сводится к генерации «интересных и разнообразных» уровней. Есть ли общепринятые подходы к задачам генерации уровней для подобных головоломок?
Нельзя ли пойти от обратного: нагенерировать уйму случайных уровней с нужным размером поля и числом ящиков и пройдя по ним солвером считать количество ходов для каждого, отсеивая уровни не удовлетворяющие запросу или не решаемые?
Задача интересная, можно попробовать нагенерировать случайно много уровней, затем генетическими алгоритмами отобрать нужные, и т.д. в цикле. Через n поколений получим самые подходящие уровни.
Решётка # это стена, через неё нельзя пройти и продвинуть ящик.
Буква O это ящик.
Буква X это метка, куда нужно переместить ящик.
Собака @ означает игрока.
Точка. означает пустое место.
Буква G это ящик на метке.
Какая буква обозначает игрока на месте куда надо переместить ящик (X и @ для одной и той же клетки)?
1. Не нашёл решения 11-го уровня в конце статьи.
2. Хотелось бы иметь оценки скорости работы и объёма памяти для более сложных уровней.
3. Не вникал глубоко в код, поэтому вопрос — вершины в графе порождаются каждый раз динамически из родительской и сохраняются? Если сохраняются, то есть ли проверка, были ли мы в данной конфигурации? Сколько вершин в графе получается, когда решение найдено?
4. Что понимается под AI в данном алгоритме? Поиск пути A*?
5. «граф инцидентных клеток» — это какой-то неправильный термин. Лучше говорить о компонентах связности графа.
2. Хотелось бы иметь оценки скорости работы и объёма памяти для более сложных уровней.
3. Не вникал глубоко в код, поэтому вопрос — вершины в графе порождаются каждый раз динамически из родительской и сохраняются? Если сохраняются, то есть ли проверка, были ли мы в данной конфигурации? Сколько вершин в графе получается, когда решение найдено?
4. Что понимается под AI в данном алгоритме? Поиск пути A*?
5. «граф инцидентных клеток» — это какой-то неправильный термин. Лучше говорить о компонентах связности графа.
1. Добавил решение в спойлере.
2. Если брать BFS, то он будет за полиномиальное время со степенью, равной количеству меток. Поэтому чем больше меток, тем дольше выполнение.
3. Не совсем понял о чём вы. Да, проверка есть, мы храним множество посещённых вершин.
4. Под «AI» понимается BFS и A*, назвал статью «AI на минималках», т.к. это известные, чисто детерминированные алгоритмы без машинного обучения и прочих приблуд.
2. Если брать BFS, то он будет за полиномиальное время со степенью, равной количеству меток. Поэтому чем больше меток, тем дольше выполнение.
3. Не совсем понял о чём вы. Да, проверка есть, мы храним множество посещённых вершин.
4. Под «AI» понимается BFS и A*, назвал статью «AI на минималках», т.к. это известные, чисто детерминированные алгоритмы без машинного обучения и прочих приблуд.
Количество меток конечно сильно ухудшает время работы, каждая метка это +1 к степени в асимптотике. Спасти может только А* с отрезанием заранее тупиковых ветвей.
На английкой вики в статье про сокобан пишут что апгрейд алгоритма A* до IDA* очень помогает: en.wikipedia.org/wiki/Sokoban#cite_note-9
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
AI на минималках: пишем свой Сокобан и учим компьютер его решать