понедельник, марта 01, 2010

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

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

(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-программера.

66 коммент.:

max.lapshin комментирует...

Фантастически интересные вопросы, потому что очень простые и нет ни единого ответа на них. Было бы интересно когда-нибудь попробовать этим всем позаниматься.

insooo комментирует...

Насчет f есть в сети постмортем от лид программера.
А так вопросы чудесные.

Andy One комментирует...

Спасибо, за вопросы, очень интересно. Но, нужно было слегка подредактировать вопросы, при знании английского очень просто найти первоисточник, по первому вопросу. Это ведь a**ndu?

Smirnov48 комментирует...

О горе мне! Я не знаю ни одного ответа на это!.. ушел учиться...

arg0 комментирует...

Да, у меня тоже с этим проблемы) Но интересно до жути)

ufonaut комментирует...

По результатам ответов на вопросы можно будет выпустить очередной том AI Programming Wisdom :)

Общий ответ на все вопросы - KISS!

Седативов геймдизайнерам, простой плоский FSM, скриптовые подпорки, красивые ролики на движке :)

Finder комментирует...

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

По-моему, люди, который умеют ответить на эти вопросы, редко ищут работу :)

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

Кроме того, ai без pathfinding'а - деньги на ветер.

Сами вопросы хорошие.

Finder комментирует...

А, в оригинале и про pathfinding есть, и про скрипты.
Тогда второй вопрос снимается.

gshadow2 комментирует...

И скока надо учиться что-бы отвечать на подобные вопросы?

Alena комментирует...

2Andy One:

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

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

Это ведь a**ndu?

Эммм, судя по всем нет. :-)

2ufonaut:

По результатам ответов на вопросы можно будет выпустить очередной том AI Programming Wisdom :)

угу :-)

Седативов геймдизайнерам, простой плоский FSM, скриптовые подпорки, красивые ролики на движке :)

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

Alena комментирует...

2Finder:
Алёна, я отвечать не буду

Похоже, ты тут единственный человек, который в приниципе может на всё это ответить :-).

По-моему, люди, который умеют ответить на эти вопросы, редко ищут работу :)

Судя по словам Пола, он много людей прособеседовал. Видимо, в Буржуляндии все сильно иначе чем у нас.

А, в оригинале и про pathfinding есть, и про скрипты.

Я не стала все сразу постить, потому что там много. Всё будет.

2gshadow:

И скока надо учиться что-бы отвечать на подобные вопросы?

Сложно сказать, от человека зависит. По-моему, пяти лет универа достаточно, имхо. Главное начать этим интересоваться довольно рано и читать правильную литературу.

jerom комментирует...

Боюсь, что тут нет правильного ответа. Все эти "как бы вы реализовали" - вопрос обсуждения.

Скажем, в 1d: пусть в начале у всех веса одинаковые. Можно просто после использования вес конкретной атаки понижать.

Дима комментирует...

> думайте, ошибайтесь.

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

1a) Не знаю, что такое иерархический КА, но предполагаю, что это КА, содержащий вложенные КА. Как бы design pattern КОМПОНОВЩИК.

2а) Их может быть недостаточно тогда, когда трудно выделить конкретные состояния. Или же их выделить можно, но количество будет "неуправляемо" большим. Случаи, когда необходимо генерировать состояния автоматически, могут говоряить о том, что КА - не лучшее решение.

1с) Дерево принятия решений - модель для принятия решения на основе входных данных. Вероятно сюда имеет отношение продукционная модель (набор правил ЕСЛИ А ТО Б)... Видимо такие деревья нельзя применять, когда логика не линейна и когда имеет место сеть решений (я не знаю, есть ли такой термин, но смысл понятен). Работать это будет очень эффективно. В рантайме это сделать должно быть реально (хотя эффективность упадет).

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

1e) ну тут не совсем понятно, могут ли боты общаться между собой и действовать сообща

1f) не знаю эту игру...(

1g) это составление задачи для достижения максимального результата. Может быть реализовано как прогон различные враиантов и последовательностей действий. Далее выбор цепочки с наибольшим количеством "очков".

1h) я бы рассчитал простоым перебором наиболее уронную последовательность заклинаний и применял бы ее по ходу игры. Перед каждым ходом ее, наверно, есть смысл пересчитывать.

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

photoscar комментирует...

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

photoscar комментирует...

по 1f:
распространения звука смоделировать как распространения газа/жидкости, побить лабиринт на кубы и по ним пустить волну с затуханием силы звука + признак звука (который тоже может изменяться при отражении), всё что требуется нотифицировать охранника о том что до него дошла волна

Alena комментирует...

2jerom:

Боюсь, что тут нет правильного ответа. Все эти "как бы вы реализовали" - вопрос обсуждения.

Безусловно так и есть. Это часто встречается в технических интервью.

Скажем, в 1d: пусть в начале у всех веса одинаковые. Можно просто после использования вес конкретной атаки понижать.

угу, это самый частый вариант. И самый хороший, имхо.

Alena комментирует...

2Дима:

1a) Не знаю, что такое иерархический КА, но предполагаю, что это КА, содержащий вложенные КА. Как бы design pattern КОМПОНОВЩИК.

Ну это да, догадаться тут несложно :-).

1f) не знаю эту игру...(

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

Avgustiner комментирует...

Думаю что могу решить все поставленные задачи хотя никогда не програмил 3д игры. С теорией - про планирование сложно гадать - надо почитать, остальное могу предположить. Как верно заметили товарищи - вариантов реализации много. ПыСЫ - в конторы для написания игр меня вряд ли возьмут :-) Нужно еще много чего выучить а не только алгоритмы придумать.

Avgustiner комментирует...

Скажем, в 1d: пусть в начале у всех веса одинаковые. Можно просто после использования вес конкретной атаки понижать.
IMHO неверно, ибо если для дальней доступна только одна - она все равно сработает при любом весе кроме нулевого.
Следует вводить кулдаун или вообще отключать последнюю, и включать ранее отключенную. Что делать если нет возможности подойти и нет дальней атаки - на усмотрение сценаристов.

Kirill комментирует...

95% что возьму на работу программиста, который ответит на половину этих вопросов.

Сам могу ответить на четверть\треть, но я не программист :)

Alena комментирует...

2Kirill:

95% что возьму на работу программиста, который ответит на половину этих вопросов.

Так вы бы координаты оставили. Профиль блоггеровский у вас недоступен, вас же не найдет никто. А тут много хороших людей бывает.

Или это была фигура речи?

Kirill комментирует...

Верно :)
пишите на job@gaijin.ru, напишите ответы в теле письма на вопросы :)

Меня зовут Кирилл Юдинцев, если что.

Alexey Baskakov комментирует...

Вопросы хорошие. В (1e) не хватает определенности по коллизиям? В некоторых играх персонажи проходят друх сквозь друга. А тем более через трупы. Ясно, что хотят худший вариант, т.е. экстра состояния у кнопок "занята".

my_dna комментирует...

Алена, добрый день. Сразу оговорюсь, не являюсь специалистом в коммерческом геймдеве. Однако, кое-что знаю (т.е., публикуюсь, учу и преподаю) в ИИ, машинном обучении и распознавании образов.

Так вот, с точки зрения основ современной теории ИИ, ворпосы весьма и весьма ограниченные. Например, отсуствует упоминание эволюционных методов (genetic algorithм, genetic programming), self-organizing maps, индуктивных методов, в т.ч. feature-based (ANN, SVM), graphical model (хотя здесь уже можно поспорить, насколько они к ИИ а не сугубо к статистическому МО относятся), Hidden Markov Models, semi-supervised learning, fuzzy systems, и многого-многого другого. Неужели коммерческий геймдев ТАК отстает от науки?

max.lapshin комментирует...

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

Такая же фигня творится со всеми остальными российскими вузами и образованием.

fuwaneko комментирует...

Ну я думаю, что коммерческому геймдеву и ну нужны подобные научные изыски. Просто результат не будет стоить вложенных денег. Как уже заметили выше — в большинстве случаев достаточно элементарного рандома + дерево решений. Ну и поиск путей конечно, куда без него :)

По поводу 1f мне кажется можно поступить так: боты обладают идеальным слухом и зрением, но увидев/услышав игрока, оценивают его текущий уровень скрытности, который включает в себя такие параметры: уровень шума, освещённость, что-нибудь-ещё. Далее делается оценка + добавляется рандом. Ну и на основе этой оценки бот уже принимает решение: заметил он игрока, или же тот аки настоящий тать ночной невидим и неслышен. Разумеется уровень текущей скрытности можно вычислять заранее и передавать всем ботам, которые добавят к нему свои параметры: положение в пространстве, усталость и прочее. Можно предусмотреть групповое поведение ботов, когда, скажем, два рядом стоящих бота имеют больший шанс заметить игрока.

my_dna комментирует...

2max.lapshin: Извините, но Вы написали феерическую чушь: "нет, это просто тем, кто занимается наукой настолько наплевать на применимость собственных наработок, что они не знают что где и как применяется."

Во всем мире большинство ИИ проектов возникают в следствии заинтересованности армии и индустрии. Вот вам навскидку парочку примеров использования нечеткой (fuzzy) логики: Токийская монорельсовая подземка и массовые сцены во Властелине Колец и Хрониках Нарнии (ребята из Massive Software не подвели). Ах, ну и конечно - куда же без него - Родни Брукс. Какие то ассоциации сие имя вызывает?

Так что, у меня складывается стойкое ощущение, что это все-таки геймдев от всех отстает.

П>С> наукой занимаюсь не в Росии

max.lapshin комментирует...

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

my_dna комментирует...

2max.lapshin
"однако вы не имеете никакого представления о нуждах геймдева и вам продолжают платить деньги."

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

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

Alena комментирует...

2my_dna:
Неужели коммерческий геймдев ТАК отстает от науки?

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


max.lapshin, пожалуйста, прекратите хулиганить. :-)

ufonaut комментирует...

Если посмотреть на современные мейнстримовые проекты, видно, что они становятся всё более нарративными, линейными - как фильм, или книга. В таких условиях важна не гибкость и свобода, а предсказуемость результата. Фактически, задача вида (1e) в идеале должна решаться вручную, скриптом - использование, например, планировщика, даст лишь уменьшение трудозатрат на хардкодинг. Неожиданные, непредусмотренные режиссёром решения такого AI могут расцениваться, как ошибки.

По моему скромному мнению, список задач для автора хорошего игрового ИИ (для 3д-шутера):

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

* Устойчивость к воздействиям извне AI-системы. Например, вмешательство дизайнерских скриптов, запуск "ролика на движке", уничтожение куска уровня по LOD-у . Важно, чтобы АИ умел как-то с этим жить.

Владимир комментирует...

Хм, интересно: а бросание банановой кожурой будет в программе?

(1a) "Дайте пример иерархического конечного автомата, который нельзя будет легко заменить конечным."
Есть 2 причины сомневаться в фразе. 1-я - лексическая. "Легко заменить" - а что такое тяжело и что такое лЁгко? 2-я более серьезна. Формально обосновать не смогу, поэтому сорри за вольные рассуждения. АФАИК, для ДКА и НКА можно построить эквивалентное им регулярное выражение. Если говорить об иерархическом КА, то это означает, что некоторые символы надо будет заменить на РВ, соответствующие подавтоматам. Но в результате вновь получим РВ(?). Если так, то хотя бы НКА мы получим всегда.

А что касается тяжести - так люди разные бывают, некоторым и в носу ковыряться тяжело ;))))

Владимир комментирует...

(1b) У КА есть только одно преимущество: в моделировании они просты и надежны как валенок. Все прочее - недостатки. Начиная с того, что обязательно нужен добрый дядя - демон, который будет скармливать автомату символы. Автономно этот формализм функционировать не способен, в отличие, например, от Сетей Петри. Попытаюсь на память процитировать Котова, если что - не пинайте сильно. "Конечные автоматы способны генерировать чрезвычайно узкий класс языков. Сети Петри предоставляют гораздо более широкие возможности, но и они не обладают полнотой по Тьюрингу". В переводе на человеческий: с помощью конечного автомата можно моделировать небольшой круг задач. Но это не означает, что КА - маздай форева. На практике поступают так: формализм КА используют для workflow, а в узлах размещают код на каком-нить нормальном языке. См., напр., UML. Правда, в нем диаграмма деятельности - это не КА, но это не важно: принцип тот же.

Alena комментирует...

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

Народ заинтересовался, вот работа по ботам Quake3: The Quake III Arena Bot, [.pdf]

Timur комментирует...

(1a)Подозреваю, что разница такая: иерархический конечный автомат в простейшем случае представляет из себя 2 или более конечных автоматов, объединённых таким образом, что например один автомат (главный) имеет K состояний и в некоторых из них задействуются другие (подчиненные) автоматы. Иерархические КА нужны для упрощения логики. Грубо говоря, если КА задается на прямом произведении {S}x{I} (состояния х входные_паттерны), то введение иерархичности (при возможности) сильно упрощает итоговый автомат, так как он раскладывается на два или более, у которых мощность множества переходов значительно меньше.
Пример:
Иерархич.автомат состоящий из автоматов
FSM1 - 10 состояний, 10 возможных входных данных,
FSM2 - 5 состояний, 6 возможных входных данных.
FSM3 - 7 состояний, 3 возможных входных данных.
Итого, чтоб задать таблицу переходов понадобится 3 массива:
10*10=100 элементов
5*6 = 30 элементов
7*3 = 21 элемент
Всего 151 элемент. Инициализировать будет не сложно, т.к. каждый массив будет связан со своим автоматом.

Реализация его в виде неиерархического автомата приведет к автомату с
10+4+6 = 20 состояний
10+6+3 = 19 возможных входных данных
итого чтоб задать таблицу переходов понадобится массив порядка 20*19=380 ячеек. Чтоб его инициализировать и не ошибиться - это вообще будет сложно.

(1b)Основной недостаток: "полиномиальное разбухание". Т.е. по теории можно любое поведение запрограммировать с помощью КА. Но вот размер таблицы переходов может быть очень большим.
Второй недостаток: не всегда удобно автоматы согласовывать с многопоточностью. Т.е. если автомат применяется именно как средство параллельного исполнения кода, то лучше не смешивать с использованием потоков, иначе можно запутаться.

(1c)Дерево принятия решений - это способ структурированного хранения информации, позволяющий достаточно быстро обрабатывать массив входных данных и выдавать некоторое (как правило меньшего объёма) количество выходных. Примером хорошим будут таблица истинности для логической формулы и собственно логическая формула (например в КНФ или ДНФ). КНФ и ДНФ позволяют не считать значение формулы до конца. (И компиляторы часто генерируют код, который не считает до конца выражение, если его результат уже известен на каком-то шаге). Примером построения дерева по исходным данным является использование карт Карно для вывода формулы по таблице истинности.

Timur комментирует...

(1d)Завести массив, в котором хранить:
1) количество использований той или иной атаки, при этом атаки внутри массива должны быть упорядочены по возрастанию вероятности возможности их применить.
2) вероятность применения атаки в целом отношение кол-ва состояний, в которых можно применить атаку к общему кол-ву состояний.

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

(1e)Параметры алгоритма:
D-максимально возможное расстояние до лифта
V-скорость бота

Я бы сделал сначала логику каждого бота независимой. Т.е. просто чтоб у них состояния сменялись почти одинаково в зависимости от некоего времени. Например: после запуска процедуры убегания бот делает следующее:
1) бежит к лифту
2) проверяет, горит ли лампочка (вызыван ли лифт - это может быть указатель на поле в экземпляре структуры или класса, отвечающего за лифт).
3) если лампочка не горит - нажимает кнопку
4) если лифт на этаже и открыт, заходит в лифт, иначе ждёт приезда лифта и считает время ожидания (T).
5) зайдя в лифт узнаёт количество ботов в лифте, если оно равно 3, нажимает кнопку, иначе ждёт время D/V-T и тогда уже нажимает кнопку.

(1f)мне кажется, что тут надо просто пытаться симулировать реальных стражников: т.е. вводить
а) пороговые функции для подозрения и точного обнаружения стимула для каждого из стражников (или общие, если стражники одинаковые).
б) функции генерации стимулов, т.е. игрок (в зависимости от его уровня, одежды, "прокачки" обладает определённым уровнем заметности, шумности и т.д, которые ослабевают с расстоянием. Т.е. в итоге заметит стражник или нет, будет определяться как
sigma(
AttenuateSound(p_serviceman->coord, p_serviceman->orientation, p_player->noise, p_player->coord)+
AttenuateVisibility(p_serviceman->coord, p_serviceman->orientation, p_player->colour, p_player->coord, ambient)+
AttenuateSmell(p_serviceman->coord, p_serviceman->orientation, p_player->odour, p_player->coord, p_wind)
)

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

(1g)Наверняка имеется в виду планирование отличное от планирования потоков. Поэтому с этим вопросом честно сдаюсь. Хотя, если имеется в виду решение задачи оптимизации (например, нахождение оптимального плана симплекс-методом), то думаю, что в реал-тайм игре планирование устроить будет сложно, потому что там нет дискретности, т.е. фактически нахождение оптимального плана сведётся к чему-то типа дифференциальной игры, но это уже будет совсем не нахождение оптимального плана.
Думаю, что в играх, где есть понятие "автобой" (например, HMM) как раз именно оно и используется.


(1h)Надо соорудить некую целевую функцию для оценки текущего состояния противника (учитывающую его здоровье, способность наносить повреждение волшебнику, подвижность и т.п.) Затем взять время самого медленного кулдауна (т.е. заклинания, обладающего самым большим периодом рефрактерности). Умножить это время примерно на 2 или 3. Попытаться разумным перебором найти оптимальный план, при котором целевая функция покажет максимальный ущерб для игрока. Под разумным перебором подразумевается перебор, проверяющий сначала наиболее вероятные варианты-кандидаты. Можно, например, воспользоваться одним из приблизительных решений задачи о рюкзаке. Применительно к данной ситуации нужно заклинания ранжировать по соотношению урона к затрачиваемым ресурсам (времени, маны) при этом (т.к. тратится 2 типа ресурса время и мана) надо ввести некоторые весовые коэффициенты эквивалентности, т.е. все заклинания будут ранжированы в одном списке.
Соответственно начинать перебор надо с наиболее эффективных заклинаний.

Timur комментирует...

В последнем время кулдауна умноженное на 2 или 3 нужно для получения периода, на который составляется план. Т.е. подразумевается, что каждый такой промежуток времени действия будут повторяться (при возможности (наличии маны))

Oreolek комментирует...

Конечные автоматы относительно просто проектировать и проверять, у них нет гибкости - это и недостаток, и преимущество. Как только игрок просекает хотя бы часть логики на конечном автомате, игра фактически заканчивается.
1d: проще всего сделать пару наборчиков действий и выпихивать их по одному по мере надобности. Действительно, те же весы прекрасно решат задачу и не потребуют больших вычислений.
1e: щас буду показывать свою неопытность :-)
Для одного бота всё просто - линейная последовательность. Если ботов два и оба одновременно достигают лифта, то они могут нажать кнопку оба, но по очереди (кто первым, определить случайно).
Подъехал лифт, два бота стоят перед ним. В лифте есть место для одного - он заходит. Второй проверяет, есть ли место ещё и для него - если есть, тоже заходит.
Усложним задачу в этот момент: пусть третий бот бежит к лифту. Здесь надо оговориться, что поведение ботов может зависеть от геймдизайна (дилемма преступника :-)) - допустим, они действуют исключительно для своего блага и ждать кого-то ещё им не надо, тогда опять оба по очереди нажимают на кнопку и лифт уезжает. Если боты заинтересованы в том,чтобы спасти своих, а третий бот именно бежит к ним, то они могут его подождать прежде чем нажимать на кнопку. Если третий бот довольно долго перестаёт бежать к лифту (например, по причине своей смерти или он занят в перестрелке), то его два дружка могут устать и поехать без него. Можно сделать вообще, чтобы если они не увидят, что он умер - они будут ждать его до конца (ну или в течение nдцати минут), но это будет похоже на застревание. В любом случае, лимит ожидания в минуту-две будет нелишним, чтобы предотвратить застревание.
1f)Здесь удобно следить за расстоянием игрока до стражников. Чем оно ближе, тем меньше шанс игрока действовать бесшумно для них. Шанс никогда не упадёт до нуля - это же неидеальный слух, но тем не менее, любой шаг может стать провалом. Если стражник что-то услышал, он туда поворачивается и (возможно) подходит. Так как раций у стражников нету, то они между собой не контактируют, значит, эта схема должна работать. Если рассматривать зрение, нужно вспомнить сколько у нас измерений. В 2d мы берём какую-то площадь перед лицом стражника и действуем в ней также,как и со слухом: чем ближе и чем светлее, тем хуже шанс быть невидимым. Стражники, конечно, будут ходить и поворачиваться, но тем не менее. Да, и эта умная площадка должна быть довольно маленькой: не больше роста двух стражников в длину и ширину, это же плохое освещение. Хотя здесь её можно менять, можно следить за светом.

Oreolek комментирует...

Если 3d, то такого простого подхода будет недостаточно: можно подойти сверху и снизу вплотную, и всё ещё быть невидимым. Проверять же трёхмерное поле на наличие в нём игрока довольно затратно.Может быть, здесь стоит сделать "слепые зоны", куда стражник посмотрит только если он что-нибудь услышит. А видеть в них он будет в окрестностях той же 2d-площадки.
1g)В реалтайме планировать действия можно, но очень ограниченно. Его нельзя использовать повсеместно: планировать можно, например, экономическое развитие в соответствии с текущей ситуацией на поле, но боевые действия требуют немедленной реакции, любая неизвестность - и ИИ снова в раздумьях. Возможно, ИИ всеведущ и у него нет неизвестностей? Но тогда его действия будут оптимальными, а это может погубить игру, ведь не каждый игрок готов продумывать свои действия дальше, чем это может сделать компьютер.
Я представляю себе полное планирование только в TBS, но там надо хорошо определиться с целями и их приоритетами. И вообще, надо ли это? В тех же "Героях 3" была местами довольно жёсткая линия поведения (например, ИИ всегда рвался на слабого врага, если мог - выставив перед замком 10 пакетов пушечного мяса,можно было его замедлить и выиграть день; затем по приоритетам шли то ли монстры, то ли шахты). Время от времени всё равно придётся действовать нерационально - захватывать сейчас ненужные рудники, открывать новые сейчас ненужные земли, иначе ИИ просто проиграет, когда получит новую проблему и не успеет её решить.
1h)Если применять планирование или заранее рассчитать стратегию, то ИИ будет идеален в бою, но в каждом бою неизбежно будет повторяться. Здесь достаточно чего-то простого. Скажем, так.
Лёгкий уровень: случайно кидает заклинания, потом кидает те, которые может.
Средний уровень: кидает самые сильные заклы из доступных, не обращая внимания на ману.
Тяжёлый уровень: кидает всегда самые оптимальные (или одни из самых оптимальных,чтобы не очень повторяться) заклы по отношению сила\мана.

Oreolek комментирует...

Почему коммент можно писать только до 4000 знаков? :-) и ещё он мой OpenID oreolek.net.ru не принимает :-(

Alena комментирует...

2Timur:
Я бы сделал сначала логику каждого бота независимой.
....
Например: после запуска процедуры убегания бот делает следующее:
1) бежит к лифту
2) проверяет, горит ли лампочка (вызыван ли лифт - это может быть указатель на поле в экземпляре структуры или класса, отвечающего за лифт).
3) если лампочка не горит - нажимает кнопку


Некрасиво будет выглядеть. У нас три бота. Сначала они все ломанутся к лифту. Потом все ломанутся к кнопке. Хотя достаточно, чтобы к кнопке пошел один, а остальные бы его подождали.

Alena комментирует...

2Oreolek:

Если ботов два и оба одновременно достигают лифта, то они могут нажать кнопку оба, но по очереди (кто первым, определить случайно).

Определили, он пошел и его убили, кнопку нажать не успел. Остальные стоят и его ждут.

Почему коммент можно писать только до 4000 знаков? :-)

Не знаю, вы первый кто пожаловался. :-)

и ещё он мой OpenID oreolek.net.ru не принимает :-(

У Блоггера есть проблемы с пониманием некоторых OpenID. Чинить не обещают :-).

Mikhail Edoshin комментирует...

Да, интересные задачи :), спасибо.

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

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

(1d) Сами события вроде бы не совсем ИИ, а больше физика, а нам, как я понимаю, нужно рассмотреть как они приходят к стражнику и что с ними случается.

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

нормально -> обычный сигнал -> нормально
нормально -> необычный сигнал -> сомнение

сомнение -> необычный сигнал -> сомнение
сомнение -> обычный сигнал * N -> нормально

(любое) -> явно чужеродный сигнал -> тревога
тревога -> (любой сигнал) -> тревога

Тревога — состояние устойчивое, не меняется очень долго (в обычной жизни дни и месяцы).

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

задача ::== действие 1 | действие 2, задача 2 | (задача 3)+, действие 4

Например

определить источник шума ::= молчать и прислушиваться
| сделать вид, что ничего не замечаешь, молчать и прислушиваться
| достать оружие?, пойти к источнику шума

и т. п.

Выбирать вариант будем случайно или в зависимости от характеристик стражника (хитрый-простой, опытный-новичок, и т. д).

В состоянии тревоги стражники объединяются в команду, у которой свои задачи и свои паттерны решений (зависящий от руководителя).

(1e) Раз боты могут друг друга ждать, нужно собирать их в команду, которая будет КА, переходящим из состояния в состояние: 1) нажать кнопку (выбранным по какому-то критерию членом команды, например, ближайшим), одновременно двигаясь по направлению к лифту 2) дождаться пока вся команда будет в лифте, 3) нажать кнопку в лифте. Убитый бот выбывает из команды.

Ilya комментирует...

Я совершенно незнаком с ИИ и разработкой игр, но вопросы настолько интересны, что хочется попробовать пофантазировать :)

(1а) Говорим, разумеется, только о тех задачах, в которых КА применимы. Конечные автоматы прекрасны и эффективны, когда генерируются автоматически из более простой нотации, типа регулярных выражений (которые можно осмысленно отлаживать в изначальном виде). Если же мы работаем с конечным автоматом напрямую, то его отладка может превратится в ад. Каждое новое состояние добавляет строку и столбец к матрице. К тому же все состояния линейны, предполагают переход из одного в другое (в противном случае нужно тщательно следить за матрицей). Что если задача по сути иерархична, то есть есть подмножества состояний, в которых возможны переходы только внутри друг-друга или в другое подмножество? Тогда иерархичность естественна, и это делает отладку и дизайн адекватными.
Очень важна такая абстракция как хуки на переход из состояния в состояние. Я встречал библиотеки FSM, в которых нельзя было повесить хук типа "перед выходом из стейта", "после выхода из стейта". Для иерархичных автоматов такие хуки очень важны.
Наконец, иерархичный КА может динамически подгружать вложенные КА. По поводу игр я представляю себе персонажа-трансформера. Каждая из его сущностей может являться КА, а переключения между сущностями будет описывать КА более высокого порядка. Если новые сущности можно приобретать в процессе игры (например, съел таблетку и научился превращаться в шкаф), то без иерархии КА тут не обойтись.
(1b) Подозреваю, что КА будут неадекватны если: а) состояние задается сложным образом (например, большое кол-во параметров с плавающей точкой или состояние это неопределенной количество неопределенных тэгов в заданый момент времени) б) переходы между состояниями задаются не матрицей переходов, а какими-то формулами (может быть даже со стохастическими параметрами)
Например, Безумный Шляпник будет ненатурален, если его выразить через обычный КА.

Ilya комментирует...

(1с) Дерево принятия решений, насколько я понимаю, в каждой вершние вычисляет некоторую функцию на основе параметров и принимает решение по какой ветке переходить. Все рано или поздно кончается листом-решением. Например функция максимизирует потери соперника, а ветки это выбор оружия для атаки, потом перемещение и т.п. Оценка может быть очень разной - зависит от однородности дерева и функци. Сгенерировать автоматически: просто построить дерево, вершиной которого будет объект, содержащий параметры решающей функции. Там может быть также параметр, задающий какой функцией пользоваться. Там получатся красивые ООП вещи :) В рантайме - да, в игре - хз )
Подозреваю, что его очень удобно использовать, чтобы считать стратегии выигрыша - на ум сразу приходят шахматы и битва отряд на отрад в хироез оф майт энд мэджик - можно сгенерировать дерево на основе того какие персонажи в команде и какие у них способы биться и параметры и считать какой ход наиболее выигрышный, чтобы нанести максимальный урон и минимизировать свой _на_много_ходов_вперед_.
По поводу организации данных, не очень понятен вопрос, что приходит в голову (может вопрос не об этом), так это абстракция типа "узел дерева", которая умеет работать с фабриками (чтобы строиться на основе внешних данных), перегружать метод решающей функции и т.п. Тогда алгоритм обхода дерева и принятия решения можно отделить от самого дерева (как в STL)
1d) Алгоритму босса нужно дополнительная структура, которая хранит память о предыдущих атаках. Ее можно реализовать независимо от самого боевого алгоритма. Например есть алгоритм, который выдает саму эффективную на данный момент атаку, потом решение проходит сквозь фильтр, который хранит память о предыдущих атаках и, если атака уже случалась, просит боевой алгоритм перерешить и вернуть следующее по эффективности решение. Для оптимизации возможно, чтобы боевой алгоритм сразу возвращал атаки отсортированные по эффективности, а фильтр-память отбирал ту, которая еще не встречалась. Когда все исчерпаны, фильтр сбрасывает память и все с начала. Тут конечно может получится фигня, так как босс станет небоеспособным, и понадобится что-то более сложное, чтоб сохранить баланс между интересностью и крутизной босса :)
1е) Можно сделать отдельный объект, типа "коллективный разум", привязанный к комнате. Например, когда боты попадают в комнату, они автоматически регистрируются в текущем коллективном разуме, тот в свою очередь обрабатывает событие "в меня добавлен бот". У ботов есть собственное AI, но есть и общий коллективный. Например, в квант времени бот должен принять решение, что делать дальше. Он принимает его на основе своего AI, а также обращается к коллективному за рекомендацией. Тот говорит - сдвинься, пожалуйста, поближе к кнопке :) Бот может суммировать свои и коллективные решения, может отвергать коллективное, если дела идут плохо :) Коллективный AI соотвественно хранит КА состояния типа "кнопка уже нажата" или "загоняю ботов в лифт" :) Тогда боты могут одновременно и отстреливаться и отходить к лифту. Более того, коллективных разумов может быть много, то есть боты могут находить друг-друга по радиосвязи и дейстсвовать сообща. Тогда у каждого бота будет список коллективных AI, в которых он зареган (связанных с локацией или динамически созданных в присутсвии других ботов) и т.п. У них могут быть приоритеты... я увлекся :)
А конфликты типа смерти одного из ботов обрабатывает коллективный ИИ на основе событий.

Ilya комментирует...

1f) Это очень интересно. Можно создать физическую модель отражающихся от стен волн, при этом для слуха это будет одно, для зрения другое (для обоняния третье). У стражников может быть набор органов чувств (унаследованных от одного абстрактного класса). У стражника есть заданный порог чувствительности и тервоги. Если сигнал, пришедший по одному из объектов-органов чувств первысил заданный порог - стражник активизируется. Модель с волнами может быть очень сложна и неоправданна, можно сдлеать что-нибудь по проще. Например в 2d пространство вокруг героя можно представить в виде мелкой сетки, ячейки в которой содержат число - коэффициент его видимости. Самые близкие к игроку ячейки содержат большее число, самы дальние - меньшие. При движении игрока числа в сетке персчитваются. если одна из ячеек вблизи стражника стала содержать число выше его порогового уровня - стражник активизируется и начинает идти по градиенту - в направлении увеличения этих чисел. Таких механизмов может быть несклько, с одним интерфейсом для разных органов чувств.
Особенно интересно, если стражники ничего не знают о стенах, препятсвиях и т.п., то есть они так же плохо видят карту, как и героя. Или они могут хорошо слышать, но плохо видеть, тогда волны рулят - можно отвлечь стражника, кинув кмаень или пользуясь эхом. Или стражник может идти по запаху, это вообще бомба, там будут не волны, а постепенно рассеивающийся след, причем сквозняки могут его рассеивать или напротив доносить в дальние части карты.
1g) Я так понимаю, что речь идет о выполнении какой-то крупной цели. Можно представить себе граф, узлами которого являются промежуточные цели, а ребрами - средства достижения целей. Рассмотрим например битву команды ботов с командой живых игроков в capture the flag. Команде ботов надо а) прорваться к флагу б) захватить флаг в) вернуться с флагом и поставить его на место на своей базе. Т.е. есть три промежуточных цели, причем в графе есть цикл: если флаг потерян, то надо снова переходить к а). тут нужны во-первых какие-то метрики, которые оценивают окружающий мир и говорят алгоритму планирования достигнута ли промежуточная цель и какая. Эти метрики могут пересчитываться регулярно, а могут по каким-то триггерам (например алгоритм планирования подписан на событие "украли флаг"). Переходами между узлами графа ведают различные ИИ типа "коллективый разум", кот. я описал в 1е). Это может быть все-что угодно, вплоть до тренированной НС. Главное, что по достижению или провалу цели, объект ИИ скорее всего меняется на другой. Например коллектиый разум, выполняющий пункт а) скорее всего сведется к нахождению пути к вражескому флагу и аккамулированию достаточной ударной силы на вражеской базе перед тем как переходить непосредственно к захватау, а вот ИИ на этапе в) будет другой - ему будет важно прикрывать бота несущего флаг, не заботясь о количестве выживших.
У плана, вероятно, будут задаваемые параметры - например один и тот же план может выполняться на разных картах и т.п.
1h) Тут сложно :) Наверное, нужно было бы построить дерево возможных вариантов, но, боюсь, оно получился СЛИШКОМ большим и непросчитываемым в реальном времени. Хорошо хоть, что манна не регенирируется и дерево это будет конечным. Возможно его можно заранее обсчитать на кластере, выделить в нем похожие поддеревья и как-то ужать.
Другой подход - попытаться описать это функцией от времени и применить методы мат. оптимизации. Типа симплекс-метода, чтобы на каждой следующей итерации решение были ближе к оптимальному.
Вобщем, ключевой вопрос к выбору метода: может ли быть такое, что на следующем шаге выбор кажется оптимальным, но в долгосрочной перспективе он проигрышный? Если да, то я бы прежде чем браться, почитал бы про реализацию шахматных программ.

KharnKeeper комментирует...

Програмированием ИИ и вообще чего то связаного с игроиндустрией не занимался, так что не судте строго. )))

Задачи 1d) Что бы делал я :

а) Для всех атак ввел бы некий коэф., чем он больше тем более вероятно использование этой атаки.

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

в) После выполненой атаки : ее коэф становится минимальным, чуть больше чем никогда; коэфициенты всех остальных увеличиваются.

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

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

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

Щса подумаю над другими ...

KharnKeeper комментирует...

Задачка 1e :

Вообще учитывая что убежать нужно всем, я бы к кнопе отправил несколько ближайших. Точнее не так...
Одного ближайшего к кнопе (назовем его жертва =) ) выполнять вызов лифта.
Остальных - по маршруту наиболее приближающему к лифту но наименее отдаляющий от кнопки.
При этом если наш алгоритм пасфаинда достаточно хорошо( читай быстро) работает в этой комнате и сделать это не сложно(читай дофига человекочасов на решение и тесты) то динамически пересчитывать маршрут так чтобы чем ближе "жертва" к кнопке тем больше остальные боты старались приблизиться к лифту и меньше неудаляться от кнопки.
При смерти "жертвы" из живых ботов выбирается следующая жертва которая бежит напрямую к кнопке. Подбежав к кнопке жартва ее включает.
Как только кнопка включена все бегут в лифт.
Как только все живые боты в лифте случайный из них (лифтер) нажимает кнопку, если умер неуспев нажать (всякое бывает) следующий пытается таки нажать злополучную кнопку )))
Боты счаливы или мертвы )))

По реализации :
Каждый бот при жизни начинает бежать по "среднему" маршруту и проверяет эвенты "бот =Я= жертва"/"кнопка раз нажата"/"бот =Я= лифтер".
По первому бежит к кнопке, по второму к лифту, по третему жмет кнопку в лифте.
Каждый бот включает эветн "бот =Я= в лифте" плюс жерва и лифтер "кнопка раз нажата"/"кнопка 2 нажата"(когда нажимают соответствующие кнопки), плюс "бот =Я= сдох" если нет отдельного манагера следящего за смертями.

Манагер ботофф выбирает "жертву" включает соответствующй евент и ждет эвентов : "бот =Х= умер"/"кнопка раз нажата"/"бот =Х= в лифте" /"кнопка 2 нажата".
При получении сигнала о смерти бота манагер проверяет не выполнял ли он ответственное задание если да то выбирает другого бота и включает воответствующий эвент. По эвенту "бот Х в лифте" проверяет есть ли еще живые недобежавшие, если нет то выбирает лифтера включает соответствующий эвент.

Вроде все.

ЗЫ : Остальные позже, а то спокойно не посидеть.

Алексей комментирует...

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

Алексей комментирует...

(1b) FSM-ы идеальны, ими можно сделать все-что-угодно :) На самом деле не надо забывать, что FSM-ы - это просто один из алгоритмов планирования и использование определяется удобством и знакомством программиста с другими алгоритмами. Ведь если обобщать, то STRIPS-планеры - это те-же FSM-ы с неявно заданной матрицей переходов :)

Алексей комментирует...

(1d) Использовать алгоритм планирования исполнения потоков с динамической приоритеризацией. Тимур нормально описал пример :)

Алексей комментирует...

(1e) Налицо необходимость в планировании группового поведения. По-моему, почти идеальная задача для GOAP. Действия "нажать кнопку", "охранять", "бежать в лифт". Один бежит, другие охраняют/ждут, потом все бегут в лифт. Убили - план пересчитывается.
Можно проще - каждый кадр проверяется переменная "лифт вызван". Если нет, то бежит ли кто-нибуть. Если да, то все в лифт.

Алексей комментирует...

(1f)Подходит ли вариант "почитаю как сделано в Thief-e и сделаю также"? Как видно из комментариев, есть много решений, но только некоторые из них работают. Не хотелось бы тратить время на нечто тяжелое и в последствии так и не заработавшее :) Помнится один неглупый человек предлагал рендерить в текстурку мир с точки зрения бота...
Мой вариант зрения:
- конус зрения с описанными сферами объектов
- трассировка лучей к объектам
- умножение полученных результатов на освещенность объекта
- долгая и нудная отладка
Слуха:
- менеджер собирает все проигранные звуки, сортирует вместе с ботами по какой-нибуть координате, попарно ищет что-то похожее на расстояние и сообщает боту что он слышал
- отладка и решение проблемы со слышимостью сквозь стены
Уровни тревоги:
- каждая секунда видимости добавляет значение, невидимости - отнимает, заданы пороги - волнуюсь, нервничаю, боюсь :)
- звуки - сложнее, ведь звук выстрела намного страшнее, чем хруст или шум ветра, нужна завязка на тип звука и громкость

Алексей комментирует...

(1g)Планирование - средство достигнуть цели, возможно, отдаленной. Преимущество - намного большая вероятность достижения цели и обычно с меньшими затратами. Emergent агент при цели "убить игрока" будет просто в него стрелять, планирующий - побежит, возьмет оружии помощнее, съест аптечку (чтобы не досталась), потом постреляет. В типичном шутере разница заметна редко :) Игра - FEAR и вообще любая, которая использует поиск по графам состояний/действий, в т.ч. использующие FSM.

Алексей комментирует...

(1h)Ой, наверное классический альфа-бета с какой-нибуть эвристикой оценки позиции.

Alena комментирует...

2Алексей:

(1f)Подходит ли вариант "почитаю как сделано в Thief-e и сделаю также"?

Подходит любой вариант :-)

Sergey комментирует...

Жаль, не указан уровень детализации ответа. По этому буду придумывать ответы на очень высоком уровне. Опыта геймдева нет.

(1d) Следует класифицировать возможные атаки в зависимости от состяния босса. Например, в зависимости от расстояния между боссмо и игроком, получится 3и классификации: ближний бой, бой на средней дистанции, бой на дальней дистанции. Босс находясь в одном из положений по кругу меняет варианты атаки и стремится изменить расстояние.

(1е) Алгоритм:
- Елси лифт не вызван, то вызвать.
- Ждать призеда лифта
- Если лифт приехал, войти в лифт.
- Если кнопка этажа не нажата, то нажать.
- Ждать закрытия дверей.

По идее взаимных блокировок не будет.

(1f) Каждый раздражитель имеет радиус действия. У каждого стражника также есть радиус действия восприятия. Чем дальше от цетра, тем способность слышать воиспроизводить уменьшается.
При возникновении раздражителя проверяется есть ли пересечения с кругом восприятия.
Если есть пересечение, то в зависимтости от растояния дается оценка восприятия, например, от 1 до 100 и плюсуется к уровню тревоги. 100 - противник обнаружен.
Количество пересечений считается (количество встреч).
При каждом последующем пересечении уровень тревоги растет в геометрической прогрессии.
По таймеру забывания количеств встреч падает, в результате уровень тревоги уменьшается.
При встрече стражников, они обмениваются своими уровнями выбираются того показатели, у которго они больше.

(1h)
В цикле:
Есть сильные повреждения, кастовать телепорт.
Есть повреждения, кастовать защиту.
Если противник может атаковать, запретить противнику атаковать.
Если притвника нельзя убить двумя атаками и он не остановлен, Остановить противника.
Нанести урон противнику.

Finder комментирует...

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

Убирать нельзя, а вот уменьшать вероятность в 3 раза - можно (и даже нужно).

Alena комментирует...

2Finder:

Убирать нельзя, а вот уменьшать вероятность в 3 раза - можно (и даже нужно).

Ну да, собственно веса для этого.

senigami комментирует...

Привет всем. Надеюсь уважаемая Alena позволит немножко пооффтопить в комментах. Задачки хорошие. Видно что писал человек который в геймдеве работает. Я сам работаю в геймдеве уже 5 лет. И хотел бы предложить задачку очень простую на первый взгляд, я ее сам пытался решить когда только начинал программить ИИ для игр. Вот такая задачка: представьте себе Красную площадь в довольно людное время суток. И много людей которые пытаются перейти площадь с одной стороны на другую( Из одной рандомной точки одной стороны в другую рандомную точку другой) Как сделать так, чтобы люди не сталкивались при движении (т.е. обходили друг друга)?

Alena комментирует...

2senigami:

Надеюсь уважаемая Alena позволит немножко пооффтопить в комментах.

Позволит :-)
Но за вами ответ :-)

senigami комментирует...

2Alena:
Да, конечно напишу ответ. Есть только мысль чуть-чуть подождать чтобы сами подумали :)

senigami комментирует...

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

Alena комментирует...

2senigami

Что-то не густо с ответами на мою задачу.

Да с ответами в принципе негусто, надо признать...

Dorjo комментирует...

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

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

Seagull комментирует...

Спасибо! Очень нравится Ваш блог, особенно ценными ссылочками на хорошие источники, и вообще приятным, грамотным изложением.
А можно чуточку по поводу f... Прочел статью про то как это сделано в самой игре, нашёл многое что использовал, или думал использовать сам. Просто в данный момент реализую зрение-слух, но много проще, для 2d и флеша. Учебно-коммерческую(ага,ага, дожить до этого надо) попытку выйти в (флеш)геймдев, сочетаемую с углублённым изучением теории, той же институтской дискретной математики, темами которой являются и поиск пути, и КА...
Сам делал так:
один конус, рейкаст, с периодическим оглядыванием, в зависимости от задачи\состояния. В случае "замечания" игрока, конус сужается, удлиняется и следует за игроком. Кроме того некоторые препятствия становятся односторонне-прозрачными при приближении смотрящего к ним. Это сделано для того, чтоб можно было как-бы выглянуть из-за укрытия, в то же время будучи невидимым с расстояния и из-за препятствия. Ну человек спрятавшийся за кустом ведь может найти себе удобную щёлочку, для подглядывания=) Проблему слуха сквозь стены я не рассматриваю, ибо оно мне не надо. Геймдев позволяет, посему работает только фактор расстояния=) Кстати с рейкастом можно естественным образом получать фактор невнимательности. Просто впереди лучи гуще, по краям - реже + чем дальше цель от смотрящего, тем больший просвет остаётся между "лучами зрения", куда может попасть объект, и стать незамеченным. При "беглом взгляде", конус смещается на дискретные, достаточно большие углы => образуются "бреши" в поле обзора. Кстати в моей игре, поле зрения врага видно игроку, но только тогда, когда игрок видит самого врага. Игрок тоже видит конусом.