Навигация AI вокруг 2-й карты - предотвращение препятствий

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

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

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

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

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

A* Поиск

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

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

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

Dynamic A*

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

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

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

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

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

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

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