Алгоритм поиска пути с движущимися границами

Question

У меня есть небольшая проблема с теорией, поэтому я надеюсь, что вы, ребята, поможете мне.

Представьте себе 2D-игру ... Вы - какой-то квадрат, и вам нужно идти от начала до конца. Между началом и концом находятся некоторые движущиеся объекты. Они движутся вертикально и горизонтально с разной скоростью от игрока и друг от друга. Итак, мне нужен какой-то алгоритм для тестирования, есть шанс, что игрок закончит уровень, или есть какая-то ошибка в дизайне уровня. Если у вас есть более подробная информация, пожалуйста, google «The Worlds Hardest Game», попробуйте эту игру, и вы увидите, что мне нужно.

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

Приветствие :)

Answer 1

Я думаю, что это может быть сделано с основным путем нахождения алгоритмов - вы просто должны убедиться, что правильно рассчитать препятствия позиции для каждого государства.

Answer 2

Один из подходов к его решению как «правильный» Shortest Path problem - увеличить размерность проблемы.

Предположим, у вас есть сетка, поэтому ваш график фактически состоит из вершин: V={(x,y) | for each x,y on the grid} и краев E={(v1,v2) | can move from v1 to v2 in a single step }.
Вышеприведенный для «обычных» статических графов.

В вашей проблеме добавьте другое измерение - время. (поэтому вместо каждой вершины представлены только 2 измерения, теперь она представляет 3!). Вы получите график G=(V,E) следующим образом:

• V = {(x,y,t) | for each x,y and t}
• E={ ((x1,y1,t),(x2,y2,t+1) | if you can move from (x1,y1) to (x2,y2) in time t}
• Предполагая, что движущиеся объекты имеют некоторый шаблон, вы можете изменить его E={ ((x1,y1,t),(x2,y2,t+1%m) | ... } (где m является «круговой» повтор
.

Теперь у вас есть классическая кратчайшая проблема на графике. Если ваш исходный источник и цель (x_source, y_source) и (x_target, y_target), в измененной задаче вам нужно перейти от (x_source, y_source, 0) к (x_target, y_target, ~) (где ~ «не волнует»).

Эта проблема является доступной по A*, как вы сказали, с manhattan distances (только на x, y) в качестве допустимой эвристической функции.