Доклад ориентирован на тех, кто вообще никогда не занимался ИИ в играх и хочет получить об этой области общее представление. Рассказ о задачах, которые стоят перед программистом ИИ в играх. О вечном споре с теоретиками по поводу нейронных сетей, об алгоритмах поиска пути, о некоторых не очень честных приемах и о вполне честных часто используемых подходах.
Искусственный интеллект в играх (Елена Сагалаева на 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*?
Далее была рассказано как проходить путь. Проблема связана с появление препятствий, которые к тому же могут двигаться. Решение — прибавлять вектор отклонения от помехи.
Итого: спасибо докладчику, но как-то слабовато. Мало было самих алгоритмов, все было ооочень просто и на пальцах, несмотря на то, что я отвлекался на общение по-поводу своего доклада. И, опять-таки, мое предложение к докладчику сделать нормальную лекцию с обзором алгоритмов (например поиска пути на графах) и с доказательством корректности на пальцах.
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
