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

21

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

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

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

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

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

Lunikon
источник
Совместное распространение может помочь вам с чем-то. Это простой способ решить проблему поиска путей для нескольких агентов одновременно + агенты, избегающие себя. Пожалуйста, поделитесь где-нибудь своим опытом, спасибо. ;)
user712092

Ответы:

12

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

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

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

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

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

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

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

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

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

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

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

MrCranky
источник
Спасибо за ваш сложный ответ. Ваш совет должен быть действительно полезным, когда я добираюсь до обычного дорожного движения. Но я, вероятно, упустил отметить два важных аспекта в моем первоначальном посте: 1. Игрок сам не участвует в трафике. Это больше похоже на бизнес-сима, и он строит сеть. 2. Однонаправленные пути встречаются особенно в аэропортах, но в аэропортах агенты не "на себя", а имеют башню, сообщающую им, куда идти. Башня должна идентифицировать сложные ситуации, но также обладает полным знанием. Поэтому я полагаю, что это на один уровень выше описанных вами ситуаций / поведения.
Луникон,
5

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

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

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

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

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

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

Лорен Печтель
источник
2
Хороший ответ - мне нравится идея трансляции «застрявших» сообщений, чтобы каждый, кто может выйти, сделал это.
MrCranky
4

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

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

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

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

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

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

Рэй Дей
источник
Да, следует использовать две полосы (потому что есть просто две полосы), но это не решает никаких проблем, связанных с
уступкой
4

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

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

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

Tyrfing
источник
0

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

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

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

justin.m.chase
источник
4
Как я уже упоминал в своем первом посте, я уже реализовал алгоритм A *, и у меня также есть соответствующие структуры данных. Кроме того, простое снижение скорости любого из агентов звучит для меня слишком «легко».
Луникон
Это не проблема поиска пути, это проблема симуляции агента. Поиск пути - это только самый низкий уровень интеллекта, который актеры должны применять.
MrCranky
Слишком легко? ха - ха. Ну, это то, что я делаю, когда я за рулем! Если я могу предсказать столкновение с моим текущим путем, я изменю свою скорость.
justin.m.chase
А светофор? А что делать, если ваш путь заблокирован другим транспортным средством? Что делать, когда ваш путь говорит идти вперед, но ваша скорость равна нулю, чтобы избежать столкновения. Столкновение с другой машиной, чей путь говорит идти вперед (через вас), и их скорость также равна нулю?
MrCranky
В сценарии с одной полосой движения, если вы используете скорость других автомобилей для расчета их будущих пунктов назначения, когда первая машина обнаруживает столкновение и останавливается, другой машине также не нужно будет останавливаться, поскольку скорость первой машины теперь равна 0. Это предполагает, что вы Вы сможете заглянуть достаточно далеко вперед, чтобы увидеть столкновения с машинами на длинных однополосных дорогах. Мой друг предлагает вам добавить узел STOP в свой алгоритм A *. При этом с точки зрения любого отдельного автомобиля вы бы просто посчитали другие автомобили препятствием. Остановка может разблокировать ваш путь, если сделать это достаточно долго.
justin.m.chase
0

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

Дэвид Тилен
источник