Как рассчитать путь вокруг движущегося объекта - PullRequest
Новая
       4

Как рассчитать путь вокруг движущегося объекта

1 голос
/ 16 января 2011

Я написал небольшой игровой движок с картой на основе тайлов и алгоритмом A * для поиска пути.Но у меня есть проблема, когда 2 объекта сталкиваются и блокируют путевую точку.Они идут с противоположных направлений, поэтому они больше не могут двигаться и никогда не достигнут своей следующей путевой точки.Я думал о некоторых возможных решениях, таких как

  • подвижные объекты не могут сталкиваться с другими подвижными объектами
  • пересчитать путь, помечая заблокированные плитки
  • , просто вычислите путь к следующейсвободная путевая точка, помечающая каждую плитку с подвижными объектами как заблокированную

Я действительно не хочу использовать первую возможность, которая немного потрепана для движка, не похожего на экшн.Последние две возможности могут стать очень медленными, если на карте много подвижных объектов.Как ты думаешь, что мне делать?Кстати, первая возможность реализована в «Stronghold», две другие можно найти в любой более новой стратегической игре.

1 Ответ

1 голос
/ 18 января 2011

Конечно, нет однозначного правильного ответа, но я могу поделиться тем, что я сделал, с похожей проблемой:

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

Если это не работает для вашей игры, обычно лучше всего добавлять блоки.Если вас беспокоит стоимость поиска пути, вы можете подождать, пока не произойдет столкновение, временно добавить «блоки» и выполнить повторный путь.Другой подход заключается в том, чтобы просто периодически вставлять блоки и повторять путь.Это может дать естественные пути и избежать «столкновения друг с другом перед движением», что может выглядеть странно.

Стоимость во многом зависит от вашего алгоритма A *.Если алгоритм не кэширует результаты, тогда блоки не имеют дополнительных затрат, и вы можете запускать A * так часто, как это имеет смысл.Например: запустите A * один раз за кадр и сохраните очередь задач A *.

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

...