Материалы с GDC2010

Game Developer Conference проходит ежегодно в марте. GDC этого года уже прошла и в Интернете начали появляться материалы оттуда.


На русском
orvind рассказывает о GDC2010: раз, два и три.
_winnie перессказывает orvind'а
Updated 28.04.2010: gdc san francisco 2010

На английском
Пит Исенси, Микрософт, Effective Management: Getting the Best from Your Team [.ppt]


GDC 2010: Reading the Player’s Mind Through His Thumbs: Inferring Player Intent Through Controller Input

GDC 2010 Networked Physics Slides + Demo (Glenn Fiedler, Sony Santa Monica) - много интересных бенчмарков пропускной способности интернетов. Подробно с примерами рассказывает о синхронизации игроков в мультиплеерных играх.

The AI of BioShock 2, Kent Hudson, 2K. Все материалы в каком-то кривом формате.

Пол-Кристиан Энгстад, Naughty Dog. Слайды про PS3 SPU. Часть1 и часть2. Они по ним раньше вновь прибывших учили, а теперь решили поделиться знаниями с миром.

Сид Мейер (он Цивилизацию придумал) рассказывает о психологии игроков.

Рассказывает, что есть некоторые игроки, которые перед каждым боем сохраняются. И, если бой прогрывают, то загружают сейв и переигрывают битву заново. (это обо мне, ага :-) ). Так вот, они стали запоминать с сейвом некий ключ. И исход битвы будет таким же, сколько ни перегружайся. "Ха-ха-ха" - добавляет в конце Сид.

Небольшая презентация от Havok'а. У них теперь есть Havok AI.


Еще много ссылок тут: GDC 2010 proceedings

Приставочные игры через видеопоток

Знаю о двух проектах, которые собираются давать играть через видеопоток.

Spawn Labs - нужен специальный девайс, который уже продается. И можно удаленно играть на собственной приставке. Отзывов покупателей не нашла.

onlive.com - тоже нужен специальный девайс. Это сервис, то есть своя приставка не нужна. Работать собираются по подписке. Открываются летом.

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

Народ настроен скептически. Тем более, что технической информации о проектах мало, в основном красивые ролики и презентации.

Хорошо там, где нас нет

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

Веб-программисты иногда думают о том, чтобы попрограммировать "по-настоящему". Не на PHP, а на C++. Лучше на С. Чтобы близко к железу. Это и есть настоящее программирование и там живут суровые системные программисты. И платят там больше.

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

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

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

Так что где бы вы ни работали, что бы вы ни программили, помните, что где-то в далеком офисе сидит человек, который страшно завидует именно вам. :-)

Lock-free контейнеры

Пост Андрея Гулина(Яндекс, Поиск) с реализацией TLockFreeQueue и обсуждение на rsdn. По ссылкам - много полезной информации по lock-free контейнерам и готовый код.

Спасибо orvind'у за ссылку.

Питер Норвиг отвечает на вопросы reddit-коммьюнити

Питер Норвиг ответил на вопросы, которые ему задавали пользователи reddit'а. Работает ли Гугл над strong AI, почему Лисп не используется широко в Гугле, кьюбиклы или отдельные офисы. В целом забавно, но никаких откровений. И да, рубашка у него зачетная :-).



Нашла по ссылке отсюда.

Вопросы с собеседования: общие вопросы

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

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

(5b) Как должна ИИ-система выбирать анимации для проигрывания? Другими словами, какими должны быть интерфейсы для кода и для данных, каким образом данные должны быть абстрагированы, чтобы ИИ-система могла как можно проще доступаться до анимаций? Опишите достоинства и недостатки различных путей описания анимаций и доступа к ним.

(5c) Расскажите о самой крутой ИИ-системе, которую вы видели в игре. Что именно вас впечатлило? Как вы думаете, как именно она была реализована. Каковы возможны проблемы по производительности у такой системы?

(5d) Как можно использовать машинное обучение(ML) в играх. Какие проблемы ML помогло вам решить? Каковы достоинства и недостатки различных подходов? Каковы характеристики по производительности различных ML-подходов? Какие ML-подходы могут быть использованы в реалном времени, а какие лучше считать заранее? Дайте различные примеры использования ML, неважно, успешные или нет.

(5e) У вас есть игра, в которой 1000 ботов ищут путь через сложный уровень игры, у каждого из них разные цели и система поведения. Сделаем допущение для данного вопроса, что это вражеские солдаты и офицеры, патрулирующие и защищающие базу в шутере от первого лица. Каким образом вы будете оптимизировать производительность ИИ для ваших ботов?

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

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

(4a) Расскажите об алгоритме A*. Сравните его с другими алгоритмами, почему его обычно используют в играх с расчетами в реальном времени? В каких случаях у A* низкая производительность?

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

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

Можно разделить на клеточки: квадратные, шестиугольные. Плохо подходят для трехмерных миров. Занимают много памяти. Требуют дополнительной интерполяции пути юнитов, иначе юниты, которые ходят по клеточкам, будут выглядеть глупо. Но зато есть random access look-up.
Waypoints. Найденный путь не всегда оптимальный. Хорошо работает в трехмерных играх.
Navigation mesh. Нужно хранить большое количество полигонов, если мир сложный. Хорошо работают как на открытых пространствах, так и в закрытых. Можно генерировать автоматически. Но сложно.
Использование сильно зависит от задачи.
Все это подробно и с картинками изложено здесь: Pathfinding: Search Space Representations

(4c) Назовите все способы, какие знаете, для оптимизации поиска пути без потери качества найденного пути. Перечислите все дополнительные расходы (например, увеличившийся расход памяти) для каждой из этих оптимизаций.

Речь будет идти про А*, поскольку он самый популярный.
Оптимизировать можно двумя путями: пространство поиска и сам алгоритм. Сначала про пространство поиска:
Можно разделить пространство поиска на клеточки покрупнее, алгорим будет работать быстрее.
Есть HPA* (hierarchical pathfinding A*) - Иерархию двух пространств поиска. Грубо говорят - клеточки покрупнее, которые делятся на клеточки поменьше. Сначала ищем по крупным клеточкам, потом, когда путь найден, уточняем по мелким. Больше двух никто не делает - получается сложно, выигрыш маленький, не нужно это.
Оптимизация самого алгоритма:
Играем с эвристикой.
Если идет несколько поисков одновременно, можно запоминать промежуточные данные одного поиска и использовать их в другом.
Можно аллоцировать необходимую для алгоритма память заранее.

Также см. Game Parogramming Gems, глава A* Speed Optimizations

(4d) Ваша система поиска пути была написана с расчетом на солдата, и она хорошо работает для солдат. Посередине разработки дизайнеры решают добавить 3 новых типа юнитов: инопланетянина ростом 15 футов, который не пролезает через большУю часть дверей в игре, очень широкую машину на воздушной подушке, которая не пролезает в узкие коридоры и через маленькие двери, и солдата на мотоцикле, который довольно медленно поворачивает( например, 15 градусов в секунду на любой скорости). Какие изменения вы внесете в свой AI, чтобы они все заработали нормально?

(4e) У вас есть система поиска пути, которая отлично работает, но она не умеет работать с динамическими объектами (ящиками, бочками, машинами, другими юнитами). Игрок играет супергероем, который может использовать суперспособность "бросить автомат с газировкой на пути юнита". ИИ-юнит не может подвинуть или уничтожить этот автомат. Когда юнит видит, что автомат заблокировал его путь, какими способами он может найти способ обойти его, при этом придерживаясь своего начального направления движения и дойдя до цели? Что будет, если автомат сбросили на точку назначения? Что если автомат заблокировал дверь, через которую юнит должен пройти согласно своему предрассчитанному пути?

Ставим автомату вектор отталкивания, соответственно модифицируем вектор движения нашего юнита.
Если закрыло точку назначения - встаем до нее, чего делать.
Если заблокировало дверь - пересчитываем путь, когда в эту дверь упремся.
Подробнее здесь: Avoiding Dynamic Obstacles and Hazards

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

(4h) Вы делаете шутер по мотивам Второй Мировой со сражениями на улицах Берлина. Дизайнер хочет, чтобы в определенные моменты игры нацисты, котролируемые компьютером, обходили игрока с флангов, т.е. чтобы небольшие отряды нацистов подходили с разных сторон, с боковых улиц и дворов. Допустим, жульничать нельзя (т.е. нельзя просто телепортировать юнитов туда, где они должны оказаться) и мы предполагаем, что дизайнеры не могут сделать это с помощью скрипта. Опишите как минимум 2 пути реализовать такую систему.

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

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

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

Это вопросы по steering behaviors, в просторечье "стиринги". Я видела перевод "стайное поведение", но он мне не очень нравится.

(3a)Как работают системы, эмулирующие стаю? Каковы компоненты такой системы и как они объединены? Когда поведение стаи не работает или дает нежелательный результат? Есть ли в стандартной стайной модели Крэйга Рейнольдса (Craig Reynolds) проблемы с производительностью? Если да, то как с ними справиться?

Модель Крейга Рейнольдса тут.

(3b)Что такое аттракторы и репульсоры? (в оригинале "attractors and repulsors", хороший перевод не придумала) Какое отношение они имеют к стиринг-системе. Когда они полезны, каковы их ограничения? Когда они могут быть использованы для огибания препятствий, а когда их недостаточно?

Можно задать притяжение (это attractors) или отталкивание (repulsor) между объектами. Их можно использовать в дополнении к существующему поиску пути, в дополнении к стирингам. Притяжение и отталкивание не обязательно должны быть линейными. Можно нарисовать всякие интересные кривые. Можно кривые менять во времени. Например, зайцы убегают от волка. Но если у волка мало здоровья, то они убегают вяленько.
Страдают от проблемы локального минимума.
Не нашла ничего в открытом доступе, поэтому отсылаю вас к Game Programming Gems 4, Глава 4.6, Attractors and repulsors.

(3c)Вы начинаете работать над игрой, и один из ваших коллег предлагает полностью отказаться от поиска пути и использовать потенциальные поля для поиска пути и навигации. Он предлагает покрыть весь мир двумерной сеткой, в каждой ячейке которой записано расстояние для ближайшего препятствия. Хорошая ли это идея? Почему "да" или почему "нет"? Когда с этим решением возможны проблемы? Вне зависимости от ответа на этот вопрос, где еще может быть использована такая система?

Идея не хорошая, потому что у потенциальных полей много проблем, они любят застревать в локальных минимумах. Можно их использовать на тайловых малодетализированных уровнях. Подробнее: Motion Planning Using Potential Fields и Using Potential Fields in a Real-time Strategy Game Scenario (Tutorial)

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

Краткий ответ. Если надо просто выстроиться в месте назначения - заранее определяем кто где будет стоять и направляем юнитов туда, это просто. Если надо сохранять порядок при передвижении - разделяем юниты по скорости. Обсуждение это вопроса есть тут.
Подробнее смотрите статьи: Movement Issues Facing Game Developers и Implementing Coordinated Movement.

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

(3f)Дополнение к предыдущему вопросу. Толпа должна разбегаться, когда начинается драка. Как вы реализуете такое разбегание? Как вы сделаете так, чтобы толпа не возвращалась тут же обратно? Как вы сделаете так, чтобы толпа с течением времени "забывала" об этом инциденте и возвращалась обратно?

Repulsor, который с течением времени затухает.

(3g)У вас в игре есть машина на воздушной подушке и дизайнеры хотят, чтобы она двигалась линейно по определенным точкам. Она должна доходить до точки, останавливаться, стрелять в игрока несколько секунд, а затем случайно двигаться к следующей или к предыдущей точке из последовательности. Путь до новой точки должен занимать 4-5 секунд. Как вы реализуете движение такой машины, чтобы оно выглядело как можно более убедительно? Нужно ли здесь использовать физику, если да, то почему?

Я бы сгладила путь сплайнами, ну и всё. Без физики. Если бы это было не воздушная подушка, а грузовик на колесах, пришлось бы делать реалистичный разворот, учитывать радиус разворота.
Подробнее об этом рассказывается в AI game programming wisdom, глава Realistic Turning between Waypoints.

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

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

Работа с пространством
(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.