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

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

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

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

Ваше здоровье :)


algorithm path-finding pathfinder
person Ilija Petkovic    schedule 12.02.2014    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Один из подходов к решению этой «обычной» задачи о кратчайшем пути заключается в увеличении размерности задачи.

Допустим, у вас есть сетка, поэтому ваш граф на самом деле состоит из вершин: 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,~) (где ~ означает «don' мне все равно").

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

person amit    schedule 12.02.2014

arrow_upward
0
arrow_downward

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

person korhner    schedule 12.02.2014
comment
Это не так тривиально, как вы выразились. Алгоритмы поиска пути традиционно работают со статическими графами, где ребра не меняются. - person amit; 13.02.2014