@SilvianDev

Создаю пошаговую игру. Минимальная единица времени – тик. Персонаж может передвинуться на соседнюю клетку за 1 тик, но после этого он некоторое время должен бездействовать (время
бездействия зависит от направления движения (после передвижения по диагонали время бездействия больше)). Персонаж на данном изображении бездействует 9 тиков после движения на 1 клетку не по диагонали или 13 тиков после движения по диагонали. Таким образом на перемещение (вместе с бездействием) не по диагонали тратится 10 тиков, а по диагонали – 14. Персонаж управляется компьютером. Надо чтобы он пришел в определённую точку или подошёл вплотную к определённому объекту (в данном случае к синему кристаллу), минуя препятствия (в данном случае – деревянную стену рядом с персонажем) и после этого быть готовым к следующему действию (т. е. подождать, пока закончится вынужденная задержка после последнего перемещения) за максимально короткое время. При наличии одинаковых по времени прохождения маршрутов выбирается случайный из них.
Подскажите, пожалуйста, как это сделать, чтобы это не было слишком ресурсоёмко, т. к. таких персонажей будет много.



У меня есть одна идея: на каждой клетке отмечается минимальное время движения из неё до цели (или до клетки рядом с целевым объектом). Делается это так: на целевой клетке или клетках отмечается 0, на соседних с них не по диагонали – 10, по диагонали – 14, затем для клеток с наименьшими метками, не окружённых помеченными клетками, все соседние с ней не по диагонали клетки помечаются числами на 10 больше, затем непомеченные клетки, соседствующие с ними по диагонали, помечаются числами на 14 больше. В результате эти клетки становятся окружёнными помеченными клетками. Затем снова находятся клетки с наименьшими метками, не окруженные помеченными клетками, и процесс повторяется до тех пор, пока персонаж не будет окружен помеченными клетками (пример на 2-й картинке (до конца рисовать лень)). Затем персонаж перемещается на клетку с наименьшей меткой (по возможности не по диагонали). Затем, если персонаж становится не окружён помеченными клетками, клетки продолжают помечаться по вышеописанному алгоритму, пока персонаж снова не будет окружён ими. Это повторяется, пока персонаж не придёт в точку назначения.
Укажите, пожалуйста на ошибки, если они есть и по возможности подскажите менее ресурсоёмкий вариант (тогда ошибки можно не указывать).

0

@Mikhaylo

Изучайте динамическое программирование. Основная идея заключается в том, что в подобного рода задачах бот должен "жить текущим моментом". То есть каждое свое текущее оптимальное действие выбирает таким образом, исходя из того, что предыдущие действия тоже были оптимальные.
Вроде то самое, что Вы изобрели. Только у Вас вроде небольшой недочет: в соседних клетках рядом с целевой должны быть не нули, а числа 10, 14.

1

@Shamil1

Используйте A*

1

@Usaga

SilvianDev, давным давно, когда деревья были большими, а пиво не одавало помоями (не так сильно как сейчас), я писал одну стратегическую игрушку в жанре RTS и тоже озадачивался с алгоритмами поиска пути. Открытием для меня тогда оказался алгоритм волновой трассировки. Он хоть и не шибко производительный и память ему нравится кушать, но маршруты он находил безошибочно и самые короткие.

1

@SilvianDev

Mikhaylo, тут нет ошибки, т. к. целевые клетки - это не кристалл (туда пройти нельзя), а клетки рядом с ним

0

@Shamil1

Если клеток с препятствиями существенно меньше, чем свободных, и сами препятствия "ровные", то возможна дополнительная оптимизация:
Вычислить "узловые" точки - напротив выпуклых углов фигур-препятствий. (Если квадратик под человечком на рисунке не мешает ему пойти по диагонали направо-вниз, то на каждый угол препятствия будет две узловые точки.) Искать путь не по клеткам поля, а по узловым точкам.
Это имеет смысл, если узловых точек существенно меньше, чем клеток на поле.

Добавлено через 3 минуты
На рисунке будет 6 узловых точек. Маршрут человечка будет состоять из трёх отрезков (через две узловые точки). Вычисляться будет быстрее, чем маршрут по клеткам. Такой подход особенно выгоден, когда положение человечка задаётся с точностью до пикселя (то есть, каждый пиксель является клеткой).

0

@SilvianDev

Shamil1, а чтобы определить выпуклые углы препятствия надо действовать по принципу "Если рядом с блоком(не по диагонали) находится 0 блоков, 1 блок или 2 блока не с противоположных сторон, то это выпуклый угол"?

Добавлено через 3 минуты
Ещё, если стену можно сломать, то можно сделать так: узловые точки отмечаются на всех клетках рядом со стенами, время прохождения между ними будет = время на уничтожение стены + время на прохождение, или тогда лучше прокладывать по клеткам?

Добавлено через 25 минут
Shamil1, в случае с узловыми точками h(x) = расстояние по прямой?

0

@Shamil1

h(x) вычисляется точно также - как расстояние при отсутствии препятствий:
(dx - dy) + 1.4 * dy, где dx и dy - это разница между координатами точек, и dx > dy

вероятно, так
иначе, каждая точка рядом с препятствием становится узловой
но надо оценить, исходя из того, какие бывают конфигурации поля
Если считать по клеткам, то все клетки будут узлами графа, который Вы обходите. Если по узловым точкам, то все узловые точки + точки отправления и назначения. Узловых точек будет меньше, но нужно ещё вычислить рёбра (в Вашем случае это может быть очень сложно... сходу не могу сказать, насколько корректно будет просто проверять прямую видимость). Поэтому вариант с узловыми точкам стоит рассматривать только, если их существенно меньше.

Да. И все пустые клетки рядом с этим блоком будут узловыми точками.

Добавлено через 7 минут
Я тут подумал, что, возможно, в Вашем случае два "минуса" могут компенсировать друг друга. При подходе с узловыми точками не нужно вычислять рёбра, а просто удлинять путь в соответствии с количеством блоков, через которые проходит прямой путь между ними.

1