Как использовать алгоритм поиска пути A * на двумерной плоскости без сетки?

Question

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

Answer 1

Создайте воображаемую сетку с любым разрешением, подходящим для вашей задачи: как можно более мелкозернистым для хорошей производительности, но достаточно мелкозернистым, чтобы найти (желательные) промежутки между препятствиями.Ваша сетка также может быть связана с квадродеревом с вашими объектами препятствий.

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

Кстати, вам не нужно фактическое расстояние (см. Ваше упоминание о теореме Пифагора): A * отлично работает с оценкой отрасстояние.Манхэттенское расстояние - популярный выбор: |dx| + |dy|.Если ваша сеточная игра допускает движение по диагонали (или сетка «поддельная»), просто max(|dx|, |dy|), вероятно, достаточно.

Answer 2

Звучит так, будто вы внедряете игру Wumpus, основанную на обсуждении Норвигом и Расселом А * в Искусственный интеллект: современный подход или что-то очень похожее.

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

Чтобы решить проблему туда и обратно, вам, возможно, потребуется сохранить пройденный путь, чтобы вы могли определить, были ли вы уже в каком-либо месте, и с помощью функции heurisitic изучить N последних ходов (например, 4).) и используйте это как тай-брейк (то есть, если я могу идти отсюда на север и восток, и мои последние 4 хода были на восток, запад, восток, запад, на этот раз на север)

Answer 3

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

Мы собираемся создать потенциальное поле из вашей игровой зоны, за которым может следовать объект.

1. Возьмите свое игровое поле и наклоните или деформируйте его так, чтобы начальная точка была на самой высокой точке, а цель - на самой низкой точке.

2. Ткните потенциальную яму в цель, чтобы подтвердить, что это пункт назначения.

3. Для каждого препятствия создайте потенциальный холм. Для неточечных препятствий, которые являются вашими, потенциальное поле может асимптотически увеличиваться на краях препятствия.

Теперь представьте ваш объект как мрамор. Если вы разместили его в начальной точке, он должен скатиться по игровому полю, обойти препятствия и упасть в цель.

Трудная часть, математика, которую я не помню, - это уравнения, которые представляют каждый из этих выступов и скважин. Если вы поймете это, сложите их вместе, чтобы получить окончательное поле, а затем сделайте некоторое векторное исчисление, чтобы найти градиент (как сказал towi), и это направление, в котором вы хотите двигаться на любом этапе. Надеюсь, этот метод достаточно быстр, чтобы вы могли пересчитать его на каждом шаге, так как ваши препятствия движутся.

Answer 4

Как представлены препятствия? Это полигоны? Затем вы можете использовать вершины многоугольника в качестве узлов. Если препятствия не представлены в виде полигонов, вы можете создать вокруг них некую выпуклую оболочку и использовать ее вершины для навигации. РЕДАКТИРОВАТЬ: Я только что понял, вы упомянули, что вы должны обходить относительно большое количество препятствий. Использование вершин препятствий может оказаться невозможным для многих препятствий.

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

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

Answer 5

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

Это в основном создает сетку для вас, вы можете изменить размер ячейки, выбрав маленькую эпсилон .Делая это вместо использования фиксированной сетки, вы сможете рассчитывать даже с небольшими градусами на каждом шаге - меньше, чем 45 ° от вашего 8-точечного примера.

Теоретически вы можете решить формулысимволически ( eps против 0 ), что может привести к оптимальному решению ... просто мысль.