Доклад ориентирован на тех, кто вообще никогда не занимался ИИ в играх и хочет получить об этой области общее представление. Рассказ о задачах, которые стоят перед программистом ИИ в играх. О вечном споре с теоретиками по поводу нейронных сетей, об алгоритмах поиска пути, о некоторых не очень честных приемах и о вполне честных часто используемых подходах.
Искусственный интеллект в играх (Елена Сагалаева на ADD-2010)
Прелюбопытный доклад о том, какие алгоритмы используются в современных играх. Игра не должна быть справедливой, она должна быть интересной :) Поэтому точки зрения математики и геймдева на то, что такое "хороший" генератор случайных чисел, очень разные.
Искусственный интеллект в играх (Елена Сагалаева на ADD-2010)
АленаC++
У Елены есть свой блог в сети, я его иногда почитываю. В жизни она оказалась выше, стройнее и симпатичнее :) В самом начале доклада у нее что-то не заладилось с презентацией, один из организаторов конференции тут же поспешил ей на помощь.
В принципе, каждый из нас когда-нибудь в детстве писал игры, поэтому ничего особо нового она в своем докладе не открыла, но рассказывала интересно. Основная цель игры — проиграть пользователю, но проиграть надо красиво, иначе ему будет неинтересно. Откуда вывод: все эти нейронные сети, нечеткая логика, генетические алгоритмы хороши в науке и в теории, но мало применимы в реальной жизни. Цена их высока, пользы мало. Рассмотрели приемы красивого проигрыша.
«Генератор случайных чисел с состояниями» — это генератор не совсем случайных чисел, так как люди очень плохо интуитивно оценивают вероятность. Пример Сида Мейера о дизайне игры Цивилизация.
Проблема «одинокого гонщика» в гонках. В честной игре человек всегда будет ехать один, это неинтересно, должны быть догоняющие и догоняемые. Для решения применяется rubber banding.
Телепорт (но только когда пользователь отвернулся).
Далее рассматривались честны алгоритмы:
поиск пути
сглаживание пути
следование пути
В конце был показан steering behaviours — стайное поведение.
Искусственный интеллект в играх (Елена Сагалаева на ADD-2010)
Докладчик — известный блоггер alenacpp. Я даже немного читал блог.
В целом доклад ничего, но его название скорее «Некоторые алгоритмы в играх».
Был рассказ про эвристики и немного про алгоритмы на графах, но не было эмуляции человеческой деятельности (особенно творческой), которой характеризуется искусственный интеллект (естественно ИМХО, так как это нечеткие определения).
Было сказано, что игра должна доставлять fun игроку. В качестве примера были приведены следующие эвристики:
Если при стрельбе игрок попадает с вероятностью 50 %, то на третий раз должен железно попасть. Сказали, что это вероятность с состоянием.
В гонках соперничающие машины должны ехать неподалеку от игрока. Неважно, выигрывает он или проигрывает. Аналогия — машинки на резинке.
Дальше был рассказ про алгоритмы на графах. Точнее, какие используют: Дейкстра, A* и НA*?.
Первый я отлично знаю класса с 9-ого. Он ищет минимальные пути от заданной вершини до все остальных. Про A* — слышал. Это Дейкстра с консистентной эвристикой (удовлетворяет правилу треугольника). В худшем случае работает, как Дейкстра, но в лучшем сильно быстрее. Третий — модификация второго; ничего про него не слышал. Надо будет разобраться.
На вопрос про количество вершин — ответили, что было 100, а вообще не знают. Следующим вопросом выяснил, что число ребер порядка вершин (как правило в играх регулярное замощение карты). Вообще, для 100 вершин и такого же порядка ребер можно пускать Дейкстру10000 раз в секунду. И если граф не меняется, то можно Флойдом все вычислить пути для каждой пары. К сожалению не было рассказано, не были ли использованы инкрементальные алгоритмы a-la Беллман-Форд. Именно они используются в сетевом протоколе RIP, где ребра могу появляться и исчезать.
Также понятно, что если граф почти регулярный то пути можно считать без стандартных алгоритмов (грубо говоря формулой)— это вроде часть HA*?
Далее была рассказано как проходить путь. Проблема связана с появление препятствий, которые к тому же могут двигаться. Решение — прибавлять вектор отклонения от помехи.
Итого: спасибо докладчику, но как-то слабовато. Мало было самих алгоритмов, все было ооочень просто и на пальцах, несмотря на то, что я отвлекался на общение по-поводу своего доклада. И, опять-таки, мое предложение к докладчику сделать нормальную лекцию с обзором алгоритмов (например поиска пути на графах) и с доказательством корректности на пальцах.
Искусственный интеллект в играх (Елена Сагалаева на ADD-2010)
Елена Сагалаева. Организаторы конференции решили не писать, где работает Алена, справедливо решив, что блог известнее.
Для начала Алена честно предупредила, что чем больше узнаешь об играх изнутри, тем неинтереснее потом играть.
Так что заядлые игроки имели возможность уйти :)
Какие особенности у ИИ в играх? Вот:
Цель — развлечь, а не выиграть. Поэтому поддаваться надо, но незаметно.
Трудно отлаживать
ИИ — набор разрозненных алгоритмов
Вопреки распространенному мнения, ИИ в играх в большинстве случаев достаточно туп и не использует:
нейронные сети
нечеткую логику
генетические алгоритмы
Есть исключения, но на то они и исключения…
Затем рассказывалось о нечестных приемах, которые, на самом деле, правила:
Генератор случайных чисел генерирует не совсем случайные числа
Нельзя оставлять пользователя-гонщика одного. Если пользователь отстает, надо придержать всех и наоборот. Поддаваться надо, но незаметно.
Подкрутить что-то, пока пользователь отвернулся. Например, вбросить войcка из ниоткуда.
Еще докладчик рассказала об алгоритмах поиска пути, обхода препятствий с примерами из разных игрушек.
Искусственный интеллект в играх (Елена Сагалаева на ADD-2010)
Как и ожидалось, практически ни в каких играх сейчас нет хоть какого-то искуственного интеллекта. Его сложно писать, его сложно патчить и т. д. Так что все действия ботов программируются обычными алгоритмами.
Интересные фишечки про вероятность с состояниями, подкрутку поведения для более интересной игры и т. п.
Про алгоритмы было только в поисках пути, причем вся информация примерно как в Википедии.
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
