2D алгоритм поиска пути - PullRequest
Новая
       46

2D алгоритм поиска пути

0 голосов
/ 10 февраля 2012

Я пытаюсь написать кусок кода, который находит кратчайший путь в 2D-карте, с некоторыми ограничениями:

  1. На карте нет препятствий.
  2. Карта «развернута», что означает, что ИИ может пересекать границу и появляться на противоположной стороне. (Очень похоже на игру со змеями на старых телефонах Nokia)
  3. Однако, если есть связанный путь между начальной точкой и пунктом назначения, время в пути для этого пути будет уменьшено, например, на 10%.
  4. Кратчайший путь должен быть выбран.

Обычный * алгоритм, кажется, не соответствует этим требованиям, так как он не позволяет телепортироваться от одной границы к другой и является Лучшим Первым. Итак, как мне решить эту проблему?

И так как я делаю это в C #, любой соответствующий пример в C # оценивается

1 Ответ

3 голосов
/ 10 февраля 2012

Алгоритм A * будет соответствовать вашим требованиям, вы просто должны подумать об этом немного по-другому.A * - это не просто алгоритм сетки, это алгоритм обхода графа .

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

Википедия содержит пример такого родаОбход графика вниз по странице со взвешенными краями.

Редактировать: Чтобы подробнее разобраться с проблемой обтекания.Скажем, у вас есть простая сетка точек, которые обернуты вокруг, как это 

+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 7 | 8 | 9 |
+---+---+---+

Обычно края здесь будут 

1-2, 2-3, 4-5, 5-6, 2-5, 3-6, 4-7, 5-8, 6-9, 7-8, 8-9

Чтобы сделать это обтекание, вы добавили бы края 

1-7, 2-8, 3-9, 1-3, 4-6, 7-9

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

Чтобы решить проблему некоторых деталей, вы сохраняете дополнительное значение на ребрахопределить сложность их прохождения.Скажем, что каждое ребро имеет значение 1, но ребро 4-5 труднее пройти.Затем вы должны присвоить этому краю значение 2 и использовать это значение при вычислении эвристического алгоритма для расстояния до точки цели.

...