AI, который может перемещаться по случайно сгенерированному 2D городу

Question

Я пишу игру для iOS (с использованием UIView), в которой есть случайно сгенерированный 2D-город. Мне нужно атаковать А.И., который выберет разумный путь, чтобы найти игрока (без столкновения со зданиями). Может ли кто-нибудь указать мне правильное направление относительно того, какие алгоритмы я бы использовал для достижения этой цели?

Редактировать: я решил использовать A *. Я создам сетку на карте, протестирую каждую точку пересечения сетки, если эта точка находится внутри здания, я аннулирую эту точку. Атакующий А.И. Затем игрок переместится из своего текущего местоположения в действительную точку сетки, которая ближе к его цели (в пределах определенного радиуса его местоположения).

Answer 1

Вы ищете класс алгоритмов под названием алгоритмы поиска пути . Есть много подходов, которые вы можете использовать.

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

Если у вас есть много различных объектов, которые нужно перемещать к цели без вмешательства, вы можете изучить потенциальные поля, которые дают простую и гибкую структуру для того, чтобы несколько объектов приблизились к цели. Этот подход использовался Berkeley "Overmind" StarCraft AI и часто используется при планировании движения роботов. Интуитивно, этот подход работает, назначая «потенциальное» значение для каждого местоположения, затем заставляя объекты продолжать двигаться от высокого потенциала к низкому потенциалу, пока они не достигнут цели. Этот подход немного сложнее, но когда он работает, он приводит к гибкому, настраиваемому ИИ, который ведет себя разумно.

Надеюсь, это поможет!

Answer 2

Этот вопрос здесь: Пакман: ​​как глаза возвращаются к дыре монстра? - это хороший обзор подходов к AI-навигации по случайной 2D-сетке в поисках движущегося игрока. Общий консенсус (и подход, использованный Пакманом) заключается не в том, чтобы беспокоиться о запекании интеллектуальных алгоритмов поиска путей в ИИ, а в том, чтобы использовать саму карту для хранения информации о местонахождении игрока. Это увлекательное чтение, особенно второй и третий ответы (и их внешние ссылки) от ammoQ и Дэна Винтона.

Эта ссылка здесь Антиобъектная схема запаха Pacman описывает дешевый и эффективный подход.