Sokoban game: автоматически перемещать поля

Question

Я уже реализовал функцию, когда кипер автоматически перемещается с использованием алгоритма поиска по ширине. Теперь я хочу, чтобы он также автоматически перемещал поля (если хранитель может перемещать поле из источника в пункт назначения, не перемещая другие поля). Как это сделать? Я пробовал модифицировать BFS, но еще не успел.

ОБНОВЛЕНИЕ: Мне не нужно решать головоломку. Вместо этого я хочу разработать удобный пользовательский интерфейс, когда пользователь может перемещать коробки своей мышью. Для этого мне нужен некоторый алгоритм, который позволит вычислить последовательность перемещения. Но речь идет только о перемещении одного окна, и если для этого не нужно перемещать только другие блоки.

Answer 1

Используйте поиск по ширине, как раньше (или A *, если хотите), но ищите соответствующий набор состояний.

Когда вы ищете путь для хранителя, состояния соответствуют квадратам в сетке. Но когда вы ищете способ для хранителя перемещать блок, состояния соответствуют парам квадратов в сетке (один для хранителя, один для блока).

Вот самый маленький нетривиальный пример. Предположим, у нас есть уровень Sokoban с квадратами помечены следующим образом:

Сетка содержит хранитель и один блок.Пространство состояний состоит из пар квадратов, занятых хранителем и блоком. Есть 56 таких состояний, нарисованных как маленькие круги на диаграмме ниже.

Линия показывает возможные переходы внутри этого пространства состояний. Тонкие линии соответствуют перемещениям хранителя (и являются двунаправленными). Тяжелые линии соответствуют нажатию блока (следовательно, идут только в одном направлении). Это это состояние пробела, которое нужно искать.

Например, если блок начинается в 7 и хранителем на 8, то хранитель может нажать на блок 8, следуя красный путь в пространстве состояний:

Следует отметить, что вдоль этот путь, блок проходит через позиции 7-6-5-6-7-8. Вы не могли бы найти этот путь, просто рассматривая позиции для блока, так как блок дважды проходит через позиции 6 и 7.

Answer 2

От Wikipedia - Sokoban:

Sokoban можно изучать с помощью теории вычислительной сложности. Было доказано, что проблема решения головоломок Sokoban NP-hard. 3 Это также интересно для искусственного интеллекта исследователей, потому что решение Sokoban можно сравнить с проектированием робота , который перемещает коробки на складе. Дальнейшая работа показала, что решение проблем Sokoban также является PSPACE-полным. [4]

Sokoban затруднен не только из-за его фактора разветвления ( , сопоставимого с шахматами), но и его огромной глубины поиска дерева; для некоторых уровней требуется более 1000 «толкает». Квалифицированные человеческие игроки полагаются в основном на эвристику; они, как правило, могут быстро отказаться от бесполезных или избыточных линий игры, а также распознать узоры и подцели, , резко сократив количество поиска.

Некоторые Сокобан головоломки могут быть решены автоматически с помощью алгоритма поиска с одним агентом, таким как IDA *, повышается за счет нескольких методов, которые используют знания предметно-ориентированного. [5] Это метод , используемый Rolling Stone, решателем Sokoban, разработанным Университетом Альберты GAMES Group. Более сложные уровни Сокобана , однако, недоступны даже для лучших автоматических решателей.

Это то, что вы хотели знать?

Кстати, решение головоломок Sokoban в оптимально оптимальном варианте - NP-hard, что означает, что вас ждет $1,000,000 prize, если вы выясните, как это сделать.