Алгоритм преследования движущейся цели в режиме реального времени с обходом препятствий

Здравствуйте. Недавно задался вопросом написания небольшой мини-игры на тему выживания. Игра заключается в следующем: есть небольшое поле с препятствиями, есть главный герой и случайным образом спавнящиеся боты. Цель игры: продержаться как можно больше времени на поле против ботов. Все бы ничего, да вот только обход препятствий ботами оказался немного проблематичен: я хотел использовать волновой алгоритм, но ежесекундный просчет пути до главного героя будет очень тяжелым. Какой алгоритм или метод использовать в данной ситуации?

0

Manolito, небольшое поле - это сколько на сколько?

0

Примерно 40x40 игровых метров (клеток)

Добавлено через 13 часов 14 минут
Up...

0

Manolito, и надо каждую секунду узнавать кратчайшее расстояние от всех противников до нас с учетом появления препятствий?

0

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

0

Manolito, ну так 40 на 40 - маленькое поле. должно быстро работать.
Ты скажи как ты хотел использовать волновой алгоритм?

0

SlavaSSU,
Для каждого противника на поле распространить волну (начальная точка - позиция противника, конечная - позиция героя, все препятствия внесены в массив) и составить массив с координатами точек самого короткого пути. Потом переместить этого соперника в точку, координаты которой находятся в первом элементе массива, очистить массив и перейти к следующему сопернику

0

Manolito, вот. теперь я скажу как лучше))) я не знаю что такое волновой алгоритм, но всегда когда слышал это словосочетание, думал, что это - поиск в ширину. если нет - то идея все равно такая же. вместо того, чтобы каждый раз запускать обход из каждоого противника до нас, можно 1 ЕДИНСТВЕННЫЙ раз запустить обход от НАС ДО ПРОТИВНИКОВ.

0

SlavaSSU, хочу возразить, если ошибаюсь - скажи. Пример: на поле 7 соперников (в разных точках всей карты), для каждого из них есть свой кротчайший путь до главного героя, получается надо будет выполнить алгоритм волны 7 раз (для вычисления пути для каждого соперника). Скриншот и ссылка:
Алгоритм Волны (Wikipedia)
(На картинке:
1ый прямоугольник: крест - главный герой, точки - соперники, цифрами отмечены прямоугольники с просчетами кратчайших путей для каждого из соперников

Миниатюры

 

0

Manolito, а теперь запусти волну 1 раз от героя. и кратчайшие ресстояния от каждого соперника до героя будут такими же

1

Еще можно пожертвовать памятью и заранее запомнить список всех возможных путей на карте.
Причем не обязательно хранить сам путь, можно хранить только направление (вверх/влево/вниз/вправо) куда ходить в текущей итерации. Затраты по памяти - квадрат от размера карты при худшей реализации.

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

Пуская волну от игрока для поиска путей для ботов можно использовать информацию по этой волне в следующей итерации, поскольку (похоже игра пошаговая) на следующем шаге игрок будет очень близко к предыдущей позиции.
Можно пометить клетки по которым должны пройти боты и запомнить их для следующей итерации. Пуская волну второй раз руководствоваться указаниями:
-волна распространяется дальше если
1) если соседняя клетка помечена и число в ней не больше чем в клетке волны.
2) если текущая клетка помечена и число в ней больше чем в клетке волны.
(но тут надо еще додумать, так как этого поведения недостаточно и бот может пойти не кратчайшим путем).

Еще есть такой нюанс - боты ведь могут мешать друг другу двигаться.

0

del

0