Это вторая часть вопросов. Все вопросы можно найти здесь.
Работа с пространством
(2a)На примере системы ИИ из игры Thief из прошлой серии вопросов (1f) расскажите, каким образом вы реализуете поведение стражников "поиск игрока" и пустите их разведывать территорию так, чтобы это выглядело праводоподобно? Как вы убедитесь, что это поведение не слишком сложное для игрока, что игрока нельзя найти, если он играет хорошо?
Можно составить карту влияния (influence map) по результатам работы сенсоров. Также можно ввести уровень пароноидальности ботов. А дальше все это надо долго и нудно настраивать в зависимости от того, чего хотят геймдизайнеры. Не встречала никаких статей по тулзам Thief'а, предполагаю, что они это все программили в обнимку с геймдизайнерами.
Подробнее обсуждается тут.
(2b)Ваша задача реализовать компьютерного игрока в стратегии реального времени (RTS). Допустим, туман войны не нужен. Как ваш компьютерный игрок будет определять какие части карты контролируются вражескими игроками, а какие можно исследовать? Как вы определите геостратегические регионы карты? Как вы найдете границу между частями карты под вашим контролем и частями под контролем врагов? Как вы определите готовящуюся атаку врага, изменение в уровне агрессии врага?
Опять influence map. Каждое здание "излучает" влияние. Сила влияния зависит от здания. Те места, где влияния нет, никому не принадлежат и их можно исследовать. Вражеские атаки тоже можно определить через влияния. Тут его будут "излучать" юниты врага.
Геостратегические регионы (английский термин лучше и короче - choke points ) - мосты, ущелья и т.п. Можно напрячь дизайнеров уровней их помечать на карте. Если дизайнеры уровней сопротивляются или если эти точки можно создавать динамически, то можно пытаться карту анализировать как-то так: если между двумя смежными регионами A и B можно пройти только через R, то R - choke point.
Подробное обсуждение тут.
(2c)В вашей RTS игре компьютер время от времени посылает разведчиков разведывать территорию. Дизайнеры хотят, чтобы каждый разведчик двигался полуслучайно и обходил различные части карты, предпочитая те, которые были открыты недавно. Допустим, что игра использует сетку и что есть туман войны. Также допустим, что разведчики стоят дешево и их не жалко, их можно пускать на вражеские базы и в другие опасные места. Как вы реализуете систему, которая будет решать куда идти разведчику? Какие структуры данных вам понадобятся? Как вы поймете, что разведчики достаточно хорошо исследуют карту? Дайте оценку по производительности вашего решения. Есть ли риск того, что разведчик будет пытаться добраться до недоступного места и застрянет?
Скриптование
Ответы на большинство вопросов по скриптованию можно найти тут: Дзэн-3, скрипт
(2d)Как связаны скриптование и ИИ? Когда следует контролировать ИИ с помощью скриптов? Когда дизайнеры используют ИИ для контроля над ИИ-агентами, на каком уровне скрипт должен взаимодействовать с ИИ?
(2e)Расскажите о нескольких системах скриптования, которые вы использовали в работе, или которые видели в других играх. Расскажите о достоинствах и недостатках тех или иных подходов к скриптованию.
(2f)Каковы достоинства и недостатки скриптования в целом? Когда скриптование использовать не надо?
(2g)Возьмите для примера любую игру и опишите лучший путь построения системы скриптования, которая даст дизайнерам возможность на каком-то уровне контролировать ИИ в игре. Также опишите идеальные инструменты для отладки описанной вами системы.
Atom feed
6 коммент.:
2a) Прежде всего: каждый стражник имеет область поиска. Он ходит и бродит по ней туда-сюда, если всё нормально. Он может ходить куда захочет, это можно реализовать, скажем, набором целей. На одной улице стоит один узелок, на второй улице - второй. Стражник идёт по улице, вдруг по мере приближения к узлу он передумывает и начинает идти ко второй цели. Он достигает второй цели, поворачивает на первую и т.д.
Как только у него появляется малейшее подозрение, он начинает поиск игрока. Итак, он подозревает,что игрок находится где-то в определённом районе. Это может быть "вокруг меня", "где-то там" и "неизвестно где". Если это "неизвестно где", то он бродит и дальше, только следит за тем,чтобы не оставлять надолго какую-нибудь улицу без присмотра...может ускорить шаг.
В других случаях - это геймдизайн, здесь нет идеального решения. Поставим себя на место стражника - какие у него есть стратегии? Прямолинейная, хитрая и случайная.
У него есть подозрительный район. Прямолинейная стратегия: пойти прямо туда и прошарить полностью. Хитрая: обойти его со всех сторон, пытаясь поймать игрока на выходе, но не входя в подозрительную область. Конечно, при этом стоит стараться ещё и присматриваться. Случайная стратегия: идти туда и бродить там, пока не наткнёшься на игрока. Думаю, что если эти стратегии хорошо разнообразить и чередовать, поведение будет адекватным. Для того,чтобы выиграть, игроку придётся очень быстро реагировать на движения стражника (особенно в случайной схеме), это может стать трудностью...возможно,такая схема слишком сложна.Две остальные легко просечь и подготовиться. Уровень сложности всё решит.
2b)Враг готовится к атаке тогда,когда он за малое время значительно увеличивает численность армии.Раздел территорий можно сделать достаточно тупо - по областям. Город захвачен - область захвачена...это частая практика, как минимум в SPORE я такое помню. Тупо и делает акцент на столицах, но имеет право на существование.
2c)Вспоминается Warcraft II...
Разведчики хорошо исследуют карту, когда они приносят много информации. Много - это в процентах от доступной для изучения. Разведчиков буду слать либо случайно, либо в места наибольшей вражеской активности, из структур данных понадобятся только массивы. :-)
2f)Поправьте меня, но лучший пример - Max Payne 1. Каждый враг жёстко заскриптован, ИИ управляет только стрельбой и движением. Опытный игрок играет так: шаг - выстрел - поворот - шаг - прыжок... всё прописано наперёд :-) тем не менее, это довольно интересно. Это - к недостаткам скриптов. Достоинства - в первую очередь, упрощение вычислений. Действительно, если тебе бросают под ноги гранату, единственное логичное действие - спасаться. Но жёсткое скриптование сильно подрывает replayability, причём чем больше скриптов - тем ниже стимул переигрывать. К тому же, скрипты имеют свойство фатальнее ломаться. В Half-Life 2 нельзя убивать дружественных персонажей. Прекрасно. Я беру кактус, подбрасываю и стреляю в него. Кактус отскакивает от стены и попадает в голову NPC, тот умирает от физического повреждения (так как имел всего 4 HP). Если ломается AI - худшее,что может случиться, это застрянет бот. Если ломается скрипт - может случиться всё,что угодно. Я никогда не встречался со скриптами как разработчик :-) поэтому большего сказать не смогу.
Увы, очень мало знаю о программировании игр, но люблю сложные вопросы.
Попробую поотвечать.
2а. Постараюсь изобразить модель реального постового, как её понимаю:
- маршруты и интервалы обхода, точки встреч. Если кто-то не пришёл на точку встречи, поднять тревогу;
- когда обнаруживаем вторжение, прочёсываем начиная от точки вторжения так, чтобы покрыть обходом всю территорию, и стражники видели друг друга (а может быть, и прикрывали спину).
- Полное покрытие участка - это задача коммивояжёра.
Обход двумя стражниками - это разбить один участок на два, так, чтобы одну половину перекрывал сосед слева, а вторую - сосед справа, и обойти сначала одну, потом другую, совместно с соседом.
- Обходить можно, скажем, по расширяющейся спирали. Это вполне реалистично.
- Если слышим шум, или теряем одного из стражников и он не приходин на место встречи, начинаем новыый поиск от предполагаемого места.
- Никакое поведение не будет слишком сложным для игрока.
2b. Сначала нужно разбить карты на участки связности, т.е. собственно выделить те самые регионы. Это:
- ресурсы;
- узкие проходы находим, найдя все возможные пути из каждой точки в каждую, Дийкстрой. Заранее, для каждой точки карты. Чем больше через неё проходит таких путей, тем более узкое (и важное!) это место.
Проход состоит из двух сильно нагруженных групп точек (правого и левого края), и проходимых точек между ними.
Потом отдельно добавляем весов путям между ресурсными участками, чтобы увеличить вес проходам к ним.
(Если не пелены, ни тумана войны нет, то мы всех видим, так?)
Контроль над территорией описываем функцией. Допустим, это интеграл от количество дэмэджа, которое вражеские юниты могут нанести по этой точке в течение, скажем, 30 секунд, помноженной на весовую функцию, скажем, убывающую от 1 до 0 линейную.
Для каждого вражеского юнита считаем время выхода на дистанцию огня и дэмэдж после этого времени и до 30 секунд.
Вражескими игроками контролируются все точки, для которых такая функция контроля более чем, скажем, в 1.5 больше нашей.
Точки, где функция контроля ниже порогового значения - ничейные.
Готовящаяся атака:
- по концентрации подвижных войск, и их выдвижению к нашей территории (а для экспанда - к ресурсным регионам). Т.е. если его функция контроля возрастает в малом количестве точек, особенно - если близко к одной из наших баз;
- по использованию ресурсов: строятся не здания, а войска.
- об уровне агрессии: если функция контроля врага в сумме значительно меньше нашей, нужно обработать специльные случаи - он либо готовит трюк, либо уже проигрывает.
2c. ("обходил" в каком смысле?)
Как решаем, куда идти:
- регулярно наведываемся на вражеские базы - посчитать войска;
- регулярно обходим возможные экспы;
- регулярно прочёсываем близлежащие к нам территории, особенно г.с.р. - не затаился ли там враг. Т.е. придаём им тем больший вес, чем ближе каждый г.с.р. к нашим базам.
Каждую из трёх целей выбираем случайно, взвешенно. Исследование каждой цели разведчиком временно понижает её вес в общем списке целей.
Из структур данных понадобятся:
- разбиение карты на участки с г.с.р. (грубо говоря, раскраска сетки карты),
- список баз,
- список участков для эксп,
- список близлежащих к нам г.с.р. Грубо говоря, списки целей разведки.
У каждой цели есть вес, "потребность в информации" - насколько нам нужно разведать именно её. У недавно разведанных целей вес временно понижается.
Карту разведывают достаточн хорошо, когда сумма произведений "потребности в информации" по каждой цели на её стратегический вес по всей карте меньше порогового значения.
Вычислительная производительность, после того, как цели определены, мне видится линейной.
- Разведчик, открывая участок, меняет вес цели для разведки, и только;
- Списки целей и их веса будут меняться по мере появления зданий/баз и истощения ресурсов. Список близлежащих г.с.р. может обновляться с квадратичной сложностью, но можно и линейно, если у нас построен граф связности участков;
Сложность по памяти: нужен двумерный массив для разбиения карты на участки, каждой ячейке поставить в соответствие участок. Остальное не стит упоминания.
Застрянет ли разведчик:
Кажется, я неправильно истолковал вопрос.
Если он ещё и в поиске ПУТЕЙ для всех разведчиков, то, опять же, строим пути разведчиков так, чтобы они обходили цели с максимальными весами как можно раньше.
Скажем, на каждом шаге решаем задачу мульти-коммивояжёра, но не точно, а жадным алгоритмом - это будет гудинаф.
Если все пути на карте построены, и разведчики постоянно в движении (потому что веса целей меняются), то как разведчик может застрять?
Этот алгоритм сносно юнит-тестируется.
2d. Скриптуют детерминироанные задачи, которые от игровых условий зависят простым и чётким способом: нажали педаль - открылась дверь и ИИ монстра проснулся, или получил новое целеуказание.
ИИ подстраивают скриптами, чтобы установить ему цели и уровни агрессии.
Не знаю, что такое ИИ-агенты. Увы мне.
Кажется, это всё, что я могу сказать по этому вопросу.
2e. В Battle for Wesnoth скрипты встроены в карту/сценарий. Это собственный, более-менее полный язык, который вешается на триггера, и который может обращаться к API объектов игры.
В последней версии есть API, чтобы ставить цели AI (точки на карте) и менять его уровень агрессии. Да, ещё порядок покупки войск.
Сам AI использует эвристический поиск в глубину.
Никакого скриптования собственно AI там нет. Более того, я могу только догадываться, как скриптуют AI.
В Wargus всё, кроме графического-ресурсного-юнитного движка, написано на Lua. AI тоже в движке и управлять им можно только через целеуказание.
2f пропускаю.
2g. В Wesnoth-е я затрудняюсь что-нибудь улучшить. Может быть, API, который позволит приписывать целям веса, и делать целями не только точки, но и юниты.
Идеальным инструментом был бы, пожалуй, отладчик с картой, на которой можно было бы прокрутить бои с определёнными расстановками юнитов.
Дополнительно на карте рисовать heatmap целей ИИ.
Не помешает инструмент, который покажет механизм формирования heatmap, если таковой не совсем тривиален.
Возможность прокручивать бой туда-сюда была бы совсем не лишней.
Равно как и возможность ограничить тест куском карты и подмножеством юнитов.
2: это дизайнеру вопросы, а не программисту. Совсем.
А программисту должно уже со-вер-шенно другое ТЗ прийти.
2golergka:
2: это дизайнеру вопросы, а не программисту. Совсем.
А программисту должно уже со-вер-шенно другое ТЗ прийти.
Вопросы сформулированы туманно, возможно, это сделано намеренно. Я бы сказала, что над ними должны работать и программисты, и дизайнеры совместно.
ОК :)
Про разведчика - с моей, дизайнерской, колокольни.
На самом деле, нужно гораздо меньше: чтобы игрок видел разведчиков. А игрок находится в первую очередь на своей базе и там, куда он посылает свих юнитов. При этом я предполагаю, что разведчики хотя бы минимально могут "кусаться" - потому что посылать безоружных скаутов на врага это уже не весело.
Никакой "информации", которую знает AI об игроке, эмулировать не надо, потому что это уже чересчур.
Опять используем упоминавшиеся ранее зоны "влияния" (но не только зданий, а зданий и юнтов). Выбираем случайный регион, исходя из влияния противника на нём: чем больше, тем более вероятно будет выбран этот регион в качестве цели разведчика.
У каждого развед-отряда (не одного юнита, а у юнитов, объединённых общей целью) поведение управляется стейт-машиной.
Базовый стейт: движение к цели.
От него может быть переход:
* когда цель достигнута - к достижению новой цели (после короткого выбора)
* когда встречен враг (в том числе на цели) - к стейту боя
* когда общий AI считает, что этот развед-отряд ему больше не нужен - к уничтожению. В смысле, не юнита, а абстракции развед-отряда; после этого можно на отряд повесить абстракцию, соответствующей другой функции, и дальше чтобы работал интеллект уже этой абстракции. Например, когда игрок собрал супер-армию и для обороны нужно мобилизировать стариков и детей.
Стейт боя - ну, тут всё понятно.
Два перехода:
* Победили противника - обратно к достижению цели
* Противник одолевает - к убеганию.
Убегание. Выбираем цель, исходя из дружественного влияния зданий и юнитов и движемся к ней.
Два перехода:
* Цель достигнута - выбираем другую
* Силы друзей вокруг и врага равны - переходим к нормальному бою
Отправить комментарий