Как построить «дорожный ИИ»?

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

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

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

Трудно описать, но я думаю, вы понимаете, о чем я. Есть ли у вас какие-либо рекомендации для меня, где начать искать? Какие-нибудь бумаги, примеры проектов или подобные вещи, которые могли бы начать меня?

Я ценю вашу помощь!

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

• Вы строите симуляцию агента здесь. Поиск пути - это просто один вход в систему - у агента есть цель, а поиск пути - это просто способ достижения этой цели. На самом деле, думая об этом в реальном выражении, агент преследует две цели: главная цель водителя - «не разбиться», а вторая - «добраться туда, куда я хочу».

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

  обнаружение - признание того, что вы и встречная машина разбиваются, если вы не избегаете друг друга

  реакция - замедление и вступление в фазу переговоров.

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

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

• Предположим худшее. Даже в идеальной системе могут возникнуть странные ситуации, и ваши актеры должны действовать разумно. Это даже более вероятно, если игрок может вмешиваться (искусственно блокировать области и т. Д.). Часто, единственная разумная реакция - остановка в целом (тупик!) Вращение на месте или, очевидно, нахождение в нарушенном состоянии - это провал ИИ. Остановка в целом, по крайней мере, правдоподобна в реальных условиях.

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

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

• Поиск пути происходит из памяти, но ситуационная осведомленность основана на восприятии. Не пытайтесь сделать ваших агентов идеальными. Они знают путь от своего дома до офиса, поэтому они знают, какие очереди делать. Но они не знают, что улица в 2 милях отсюда заблокирована. Не пытайтесь заставить своих агентов прокладывать идеальный путь, потому что их нет - даже если он начинается идеально, другие факторы могут заблокировать их путь. Агенты должны планировать только несколько улиц впереди, куда они идут.

• Качество информации. Ваше поведение должно быть простым, но для достижения этого вам нужна хорошая функциональность запросов. Вы должны уметь задавать вопросы о вашем окружении, такие как «встречная машина занимает мою полосу?», «Сколько встречных машин?», «Есть ли машины позади меня», «могу ли я сделать разворот» ,

Увидев некоторые ужасные сбои в выпущенных играх, у меня есть пара предложений:

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

2) Какая-то логика, чтобы раскрутить пробку, если это происходит. Я наблюдал ситуации, когда обработка пробок применялась только к транспортным средствам, которые пытались столкнуться друг с другом, но полностью терпели неудачу при столкновении с шаблоном -> -> <- <-. Я вспоминаю одну карту, которая была склонна к этому - это была задушевная точка, предназначенная для того, чтобы сделать базу ИИ более трудной для атаки, но рано или поздно в этот момент приходили два сборщика ресурсов, когда группа нападавших уходила, и это было все. Части, находящиеся в контакте, вращались вокруг, пытаясь найти выход, но у них не было никаких законных действий. Он не отступил и не выяснил, что какое-то другое подразделение должно было двигаться первым, и поэтому ИИ не предпринимал никаких полезных действий, пока контрольно-пропускной пункт не был устранен. (Вы можете наблюдать, как юниты в контакте вращаются и больше ничего не делают.)

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

Обратите внимание, что простой поиск альтернативного пути часто является плохим ответом. Я наблюдал ситуацию с прямой блокировкой такого типа - блок А отмечает, что Б блокирует дорогу впереди, и поэтому он поворачивает, чтобы использовать другой маршрут. Это теперь блокирует дорогу для B, который поворачивается - теперь дорога разблокирована, так что оба снова поворачивают. Каждый ход они чередуются между движением вперед и движением назад.

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

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

Во-первых, для предотвращения узких мест, во-первых, у меня было бы две полосы движения, позволяющие транспортным средствам двигаться в противоположных направлениях. на той же «дороге».

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

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

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

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

Вы сказали, что просматривали несколько статей о поведении руля, хотя на всякий случай вы искали следующую?

http://www.red3d.com/cwr/steer/

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

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

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

A * (Звездочка) - это очень простой алгоритм поиска пути, который вы, вероятно, можете легко перевести в псевдо-код в Википедии на свой язык, и он будет работать: http://en.wikipedia.org/wiki/A*_search_algorithm

Когда я внедрил Enemy Nations, мой последний запасной вариант заключался в том, что, если автомобиль застрял более чем на 2 секунды, я бросил его вперед на своем пути. Поэтому, когда они застряли, юнит в основном перевозил. Никто никогда не жаловался, поэтому я полагаю, что несколько раз это случалось, никто не смотрел и не видел этого.