Как построить наименьшую траекторию перемещения по клеткам, имея возможность переставлять препятствия?

Question

[muzclubs]

Добрый день!

Необходимо разработать алгоритм для перемещения объекта из клетки А в клетку B таким образом, чтобы сумма перемещений препятствий для освобождения пути + сумма перемещений самого объекта была минимальной. Перемещение возможно в 8-ми направлениях(вперед/назад, влево/вправо, диагонали). Нужно учитывать, что препятствия потом должны встать обратно на свои места.

Подскажите пожалуйста идеи для реализации, что-то мне в голову ничего хорошего не приходит.

Answer 1

[Армянское Радио]

Строим дерево ходов, строим целевую функцию, берем один из популярных алгоритмов оптимизации на графах (либо колония муравьев, либо имитация отжига), смешиваем, но не взбалтываем.

Answer 2

[Евгений Шатунов]

Ответ относится к стандартным алгоритмам поиска пути.

Литература:
algolist.manual.ru/games/wavealg.php
algolist.manual.ru/games/smartmove.php
www.gamedev.ru/code/articles/?id=4246

Любой алгоритм удачно усложняется за счет использования потенциальных полей.
https://habrahabr.ru/post/262181/

Comments

[muzclubs]

Спасибо.

В статьях говорится либо о статичных препятствиях, либо передвигающихся по какой-то своей траектории, необходимой для усложнения передвижения юнита. В моем случае необходимо наоборот расставить препятствия таким образом, чтобы была 100% гарантированная траектория достижения юнитом точки B из точки А, при этом сумма перемещений юнита + сумма перемещений препятствий должна быть минимальна.

[Евгений Шатунов]

muzclubs , Мне это напоминает один жанр игрушек. Уж не бота ли ты решил для таких игрушек сделать? :)
Тебе надо немного подольше покурить предложенные материалы. Я чую там разгадку. Только ты дал очень мало информации по своей задаче.
Скажем, пусть препятствиями будут коробки. Игрок их только от себя толкать может? А что если на пути толчка вплотную еще одна коробка стоит? Или же игрок может просто взять коробку и переместить ее на любую другую свободную клетку вокруг себя? А ходить можно так же в 8 направлениях? А если хочется сходить по диагонали когда противоположная диагональ занята коробками, то что? Взаимодействие с коробкой является ходом или нет? И при взаимодействии игрок перемещается на место коробки или нет?
Я так весь день вопросы задавать могу. :) Думаю, если выделишь максимум возможных правил - решение с A* само подтянется.

[muzclubs]

Евгений Шатунов: В игрушки я давно не играю да и не могу припомнить такой игры, где понадобился бы подобных функционал. Разве что HWM, но там всё намного сложнее. :)
Буду подробно вникать в литературу, хотя с некоторыми алгоритмами знаком. Спасибо!
Игрок - абстракция. Нужно просто построить траекторию перемещения из клетки A в клетку B учитывая, что можно ещё перемещать препятствия(коробки). Перемещение препятствий аналогично передвижению игрока, т.е. пошагово(если соседняя клетка a[x][x] свободна, то перемещаемся на неё). Возможность перемещения препятствий не связана с игроком, т.е. можно передвигать "коробки" хоть на другом конце поля, лишь бы смысл от этого был. Передвигаются препятствия так же в 8-ми направлениях.

[Евгений Шатунов]

muzclubs , таких игр море - это жанр "push the box" или "sokoban". :) Только, да, в жанре предусмотрено непосредственное взаимодействие игрока с коробкой.
Можно подумать, наверное, так.
Можно построить взвешенный граф оптимального перемещения. В этом графе должны быть не только свободные клетки, но и все препятствия на пути оптимального перемещения. По этому графу станет видно, нужно ли вообще двигать препятствия. Пусть изначально переход на место препятствия будет вдвое дороже перехода на свободную клетку.
А далее начинается "оптимизация" графа. Армянское Радио правильную мыслю подсказывает.
Оптимизация заключается в том, чтобы попробовать отодвинуть самые "дешевые" препятствия, всякий раз пересчитывая стоимость всего пути.

Еще можно упростить себе жизнь, задав потенциальное поле удорожания маршрута на клетке каждого препятствия. В этом случае первым этапом будет создание потенциального поля. Оно создается от наиболее близких к свободным клеткам препятствий к центру их массы и буквально определяет удорожание пути при движении сквозь препятствия. А вторым шагом будет простой A*.

[muzclubs]

Евгений Шатунов: Большое спасибо!
С этим, относительно, понятно. А что делать, если на поле препятствия разного типа, которые имеют различные формы передвижения? Ну, например, как фигуры в шахматах. Каким образом в этом случае строить траекторию перемещения?

[muzclubs]

Евгений Шатунов: может быть в этом случае нужно смотреть уже в сторону нейронных сетей?

[Евгений Шатунов]

muzclubs , да не, не надо.
Сложность задачи от разнообразия препятствий не меняется. К тому, же, даже если все препятствия могут двигаться на любую из 8 клеток вокруг себя, то если два препятствия стоят вплотную рядом, у них уже появляется специфика перемещения. Они уже не могут перемещаться на клетки друг друга. И так далее.
Случай с шахматными фигурами никак не усложняет поиск, ведь цель передвижения препятствий - освободить оптимальный путь перемещения.

Может нам лучше перевести обсуждение непосредственно в область задачи? А то я так и чую что ты стараешься обойтись только наводящими вопросами. :)