AI-навигация по 2-й карте - избегая препятствий

Question

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

В настоящее время я работаю над проектом, в соответствии с которым мне дали карту, и я кодирую «Криттера», который должен иметь возможность перемещаться по карте; у твари есть и другие функции, но они не имеют отношения к текущему вопросу. Вся программа и решение написаны на C #.

Я могу контролировать скорость твари и получать его текущее местоположение на карте, возвращая его текущее положение X и Y, я также могу установить его направление, когда оно сталкивается с местностью, которая его блокирует.

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

Я не программист игр, и это для программного обеспечения, поэтому я не имею понятия о методах ИИ.

Вот ссылка на изображение того, как выглядят карты и твари:

Карта и изображение Криттера

Я ни в коем случае не ищу никого, кто бы дал мне полное решение, просто толчок в общем направлении при навигации по карте.

Answer 1

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

Некоторые из наиболее популярных типов алгоритмов ...

• A * Поиск (Классика)
• Графики видимости
• Диаграммы Вороного (аналогично вышеуказанному)
• Потенциальные поля

Потенциальные поля - причудливый способ сказать, что каждое препятствие или стена имеет «отталкивающую силу», в то время как каждая цель имеет «силу притяжения». Сила силы основана на расстоянии от объекта и «серьезности» объекта. (Яма лавы намного тяжелее для прохождения, чем неровная дорога). После построения силовых полей наивный алгоритм сводится к тому, чтобы следовать по пути наименьшего сопротивления. Лучшие версии могут обнаруживать локальные минимумы и максимумы и выходить из этих скважин.

    Critter
    -----\    /-------\
          \  /         \ 
           \/           \
   Local Minima Trap     \
                          \
                           \
                             Goal

Answer 2

A * Поиск

Посмотрите на алгоритм поиска путей A *. По сути, это стандартный подход к таким вещам.

Амит Патель пишет о pathfinding для игр имеет довольно хорошее введение в A *, а также популярные варианты алгоритма.

Вы найдете реализацию C # здесь и здесь

Динамический A *

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

Хотя это работоспособное решение, перезапуск алгоритма планирования с нуля каждый раз, когда вы обнаруживаете новое препятствие , приводит к значительному количеству избыточных вычислений. Например, когда вы преодолеете препятствие, может оказаться, что наиболее эффективный путь к цели следует тому, который вы планировали пройти до того, как обнаружили препятствие. Просто повторно запустив A *, вам нужно пересчитать этот раздел предыдущего пути.

Вы можете избежать этого, используя Dynamic A * (D *) . Так как он отслеживает ранее вычисленные пути, когда агент находит новое препятствие, система должна только вычислять новые маршруты в области вокруг препятствия. После этого он может просто повторно использовать существующие пути.

Answer 3

Кажется, я опоздал на вечеринку. Если у вашего твари есть GPS и полная карта под рукой, то, безусловно, нужно сделать A *, и если карта достаточно мала, простая BFS также подойдет, если вы не хотите кодировать A * (A * имеет несколько угловых случаев, которые вы хотите обработать правильно).

Однако другой вопрос заключается в том, что если ваш твари знает только направление цели и может наблюдать только локально что вокруг нее? Что если ваш зверь не знает полную карту?

В этом случае вы хотели бы реализовать «алгоритм ошибок» для навигации. Ссылка: http://www.cs.cmu.edu/~./motionplanning/lecture/Chap2-Bug-Alg_howie.pdf

Это симпатичный алгоритм, который работает для всех неизвестных карт, я уверен, что вы бы взорвали его кодировку.

Answer 4

Я бы использовал целенаправленный подход. Ваш вопрос гласит, что цель состоит в том, чтобы изучить карту и избежать препятствий, поэтому мы и ставим перед собой цель. Но как мы исследуем всю карту? Мы исследуем то, что не исследовано.

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

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

Вот и все для описания высокого уровня. Надеюсь, это поможет!