Я ищу лучшее решение для поиска пути в моей игре. Карта в конечном счете основана на сетке, но объекты позиционируются с использованием плавающих элементов и могут перемещаться в любом направлении в любую точку на карте. «Земля» в моей игре имеет одинаковую стоимость передвижения, но, конечно, могут быть препятствия, которые блокируют путь. Большинство препятствий будут статичными, и хотя в игре будут присутствовать и другие одушевленные существа, я могу остаться без внимания - это изометрическая стратегическая игра в стиле тематической больницы , так что никаких боев.
Большинство статей о поиске пути, которые я видел, охватывают трехмерное или основанное на сетке двухмерное движение. Любые предложения для чего-то, что может охватить мой вариант использования? Большое спасибо.
источник
Ответы:
Это называется «проблемой поиска пути под любым углом». У вас есть два варианта:
Создайте навигационную сетку для своей карты и выполните поиск по ней, используя A *
Поиск по сетке с использованием алгоритма, предназначенного специально для поиска пути под любым углом. Традиционно, способ сделать это - A * + сглаживание пути (линейная интерполяция и т. Д.) , Но в наши дни более популярной альтернативой является Theta * , который проще в реализации, работает быстрее и дает лучшие результаты, чем сглаживание пути.
Все вышеперечисленные методы дают почти оптимальные результаты. Если по какой-то причине вам нужны оптимальные результаты, эта статья была выпущена несколько недель назад. У меня еще не было возможности прочитать его, поэтому я не знаю, насколько он эффективен или насколько сложно его реализовать.
источник