Вопросы с собеседования: работа с пространством и скриптование

Это вторая часть вопросов. Все вопросы можно найти здесь.

Работа с пространством
(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)Возьмите для примера любую игру и опишите лучший путь построения системы скриптования, которая даст дизайнерам возможность на каком-то уровне контролировать ИИ в игре. Также опишите идеальные инструменты для отладки описанной вами системы.

Вопросы с собеседования: поведенческий ИИ

Это первая часть вопросов. Все вопросы можно найти здесь.

(1a)Какая разница между конечным автоматом(FSM) и иерархическим конечным автоматом(HFSM)? Дайте пример иерархического конечного автомата, который нельзя будет легко заменить конечным.

Конечные автоматы: http://en.wikipedia.org/wiki/Finite-state_machine
Иерархический конечный автомат, как многие догадались - это автомат, в качестве состояния у которого тоже автомат. http://www.eventhelix.com/RealtimeMantra/HierarchicalStateMachine.htm
Иерархический автомат всегда можно представить в виде неирархического. Но при определенном размере обычный конечный автомат получится такой здоровый, что с ним будет очень тяжело работать.
Также см. ответ тут

(1b)Какие есть недостатки у конечных автоматов? Когда разумно использовать конечные автоматы, а когда их недостаточно, чтобы реализовать нужное поведение в игре?
Не умеют работать с параллельными и асинхронными задачами.

Их нельзя использовать для поведений с целью, не умеют работать с параллельными и асинхронными задачами, плохо масштабируются.
Также см. тут, тут и иллюстрацию:

(1c)Что такое дерево принятия решений (decision tree)? Когда вы будете использовать такое дерево? Дайте оценки по производительности. Как сгенерировать дерево принятия решений автоматически из набора данных? Реально ли это сделать в рантайме, делалось ли это раньше в коммерческой игре? В каких ситуациях так следует делать и каким образом должны быть организованы данные, чтобы это было возможно?

http://en.wikipedia.org/wiki/Decision_tree
Минусы - каждый раз надо гнать заново сначала, не умеют хранить уже принятые решения, error propagation.
Автоматически генерятся с помощью алгоритмов типа C4.5 и ID3.
Игра Black&White использовала ID3. См. тут и тут[.ppt].

(1d)Вы реализуете схватку с боссом в 3D игре. У босса есть 15 вариантов атаки. Геймдизайнеры попросили вас сделать так, чтобы игрок в течение схватки видел как можно больше из этих 15 вариантов атак и чтобы он редко (а лучше никогда) видел одну и ту же атаку два раза подряд. Каким образом тут следует реализовать алгоритм атаки? Имейте в виду, что не все атаки досупны в каждый момент времени. Например, у босса есть атака, которая возможна только в ближнем бою, атака бомбами, которая возможна только если игрок далеко.

Рандом с весами (такой вариант был в комментариях). Флажками помечаем атаки, которые недоступны, по остальным гоним рандом. Нельзя убирать атаку, которая только что была, потому что если она всего одна, то нехорошо получится. Нужно уменьшать ее вес.
Также см. обсуждение и другие варианты ответов тут.

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

Узнаем у геймдизайнеров один ли лифт в игре. Скорее всего он один, поэтому скриптуем его.
Здесь можно реализовать групповое поведение, например на blackboard'ах. Основной проблемой тут будут проверки, много проверок. Что убежавший до кнопки добежал и кнопку нажал, убедиться, что лифт приехал и не пихать их всех в шахту, что все влезают в лифт и т.п.
Обсуждение и более подробно описанные варианты решения тут.

(1f)Вам дана задача разработать игру похожую на Thief: The Dark Project и вам нужно сделать стражников с неидеальными слухом и зрением и посадить их в тускло освещенные замки. Они могут искать игрока, если они думают, что к ним кто-то вторгся. Как вы смоделируете систему сенсоров для этих стражников, как вы будете собирать аудио, визуальные и другие стимулы системы? Как вы реализуете различные уровни тревоги стражников и почему?

Система сенсоров Thief'а описана здесь.

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

В целом про планирование: The Planning System.
Правильные ключевые слова: GOAP, STRIPS, HTN.
Также см. тут.

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

Делим все заклинания на "атакующие", "защитные" и еще какие-нибудь по вкусу. В зависимости от того, сколько маны и хитпоинтов у нас, сколько у противника используем заклинание из нужной группы, выбираем его рандомно.
Более подробное описание см. тут.
Этого должно хватить. Если геймдизайнерам это не понравится, можно использовать более умные методы.

Бонусная задачка от senigami:
Вот такая задачка: представьте себе Красную площадь в довольно людное время суток. И много людей которые пытаются перейти площадь с одной стороны на другую( Из одной рандомной точки одной стороны в другую рандомную точку другой) Как сделать так, чтобы люди не сталкивались при движении (т.е. обходили друг друга)?

Что-то не густо с ответами на мою задачу. Как и обещал хозяйке поста - мои варианты решения задачи. Их несколько, ну как и у любой интересно задачи. Первая реализация, которую я сразу придумал занимаясь когда-то этой задачей называется Steering behaviour. Реализация в моем случае была достаточно простая: к НПЦ, идущим по просчитанному заранее пути прикладываются силы. Первая возникает только тогда, когда НПЦ отклоняется от просчитанной траектории и старается "вернуть" НПЦ на траекторию. Вторая возникает когда поблизости возникает другой НПЦ. НПЦ отталкиваются друг от друга как одинаковые заряды. Этот способ конечно не нов и использовался уже в играх (я на КРИ пару раз слышал такие идеи от АИ программистов). Что-то подобное реализовано, как я понимаю, тут http://opensteer.sourceforge.net/
Второй подход - реализовать все с помощью коллижена. НПЦ ходят в виде больших вертикальных цилиндров. Когда на некотором апдейте они заколлизятся то их их скорости просто вычитается проекция вектора скорости на линию центров (нужно конечно немножко читить чтобы при этом скорость не оказалась равна 0). Визуально выглядит этот вариант не очень красиво :(
Третий подход, о котором я сам недавно узнал - на основании данных о размерах и желаемых скоростях объектов составлять и решать некоторую оптимизационную задачу. В результате решения задачи получим скорость, применяя которую на данном апдейте мы гарантированно не заколлизимся. Статья с подробным описанием для интересующихся тут http://gamma.cs.unc.edu/CA/

Я добавила нумерацию, чтобы на вопросы было проще ссылаться из комментариев. Комментируйте, не стесняйтесь. Если стесняетесь, комментируйте анонимно :-).

Updated: вопросы вызвали неожиданную реакцию и народ предался самоуничижению, что отнюдь не было моей целью. Думайте, ошибайтесь. Эти вопросы, они для того, чтобы научиться, чтобы посмотреть на реальные примеры задач из работы ai-программера.

Вопросы из собеседования по ИИ в играх

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

Там не только чисто теоретические вопросы, но и много задач, которые реально возникали у него в работе.

Я думаю, многим будет интересно на них посмотреть и попробовать самим поотвечать. Поэтому в течение недели я буду их переводить и постить пачками каждый день с понедельника по пятницу. А в выходные будут танцы! допишу к ним ответы.
Оглавление:
Поведенческий ИИ
Работа с пространством и скриптование
Стиринги
Поиск пути и навигация
Общие вопросы

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

Updated:
Вопросы задавал Пол Тозур(Paul Tozour): Interviewing AI Developers
Часть ответов можно найти на форумах aigamedev.com и тут: Response to AI Developer Interview Questions - Part 1.

C++0x: Делегирующие конструкторы (Delegating Constructors)

Еще одна приятная фича C++0x, которой лично мне очень не хватало - делегирующие конструкторы. Дальше я кратко изложу вот этот документ: Delegating Constructors (revision 3)[pdf].

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

class X {
  void CommonInit();
  Y y_;
  Z z_;
public:
  X();
  X( int );
  X( W );
};

X::X() : y_(42), z_(3.14) { CommonInit(); }
X::X( int i ) : y_(i), z_(3.14) { CommonInit(); }
X::X( W e ) : y_(53), z_( e ) { CommonInit(); }

Недостатки этого метода:
1. Несмотря на то, что тела у этих конструкторов совпадают, слить их в один не получится.
2. Невозможно делегировать инициализацию переменных.

Начинающие программисты часто не знают, что вызвать один конструтор из другого нельзя и пишут что-то вроде такого:

class X {
  int i_;
public:
  X();
  X( int );
};
X::X() { DoSomethingObservableToThisObject(); }
X::X( int i ) : i_(i) { X(); } 

Этот код компилируется, но делает совсем не то, что хотел программист.

Чего будет в С++0x: один конструктор, он называется "делегирующий конструктор", сможет вызывать другой, "целевой конструктор".

Пример кода:

class X {
  int i_;
public:
  X( int i ) : i_(i) { }
  X() : X(42) { } // i_ == 42
};

Сильно лучше, чем было, но я нашла один существенный минус. Если делегирующие конструкторы образуют цикл, то результатом будет undefined behavior. Диагностику новый Стандарт не требует.

Также см. Стандарт C++0x, 12.6.2.