Поиск пути к движущейся цели

Question

Работая над недавним проектом, я задавался вопросом, как найти хороший / идеальный путь к цели, которая движется с постоянной скоростью.Я пробовал использовать стандартный поиск A * pathfinding, но он потерпел неудачу, поскольку эвристика будет неправильной по мере движения объекта, и я просто не могу найти способ заставить это работать для меня.Может быть, у вас, ребята, есть другой алгоритм, который должен работать просто отлично, или какая-то настройка вычислений с A *, которая будет работать ...

Спасибо за ваш вклад:)

Answer 1

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

Однако, если вам действительно нужно что-то более мощное, проверьте Обобщенный Адаптивный A *, алгоритм, специально разработанный для обработки движущихся целей.И если вы действительно хотите быть на переднем крае, есть несколько адаптаций GAA *, которые в некоторых случаях выполняются быстрее - см. этот пост (в разделе "перемещение точек цели") для более подробной информации.

Answer 2

Использование A * с движущейся целью - это нормально, но вы должны снова пересчитать весь путь.Я не думаю, что A * нравится просто менять назначение / цель.

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

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

Однако A * может быть не лучшим поиском пути для вашего приложения, но мне нужно увидеть вашу карту и дополнительную информацию ..