Войти
ПрограммированиеСтатьиИгровая логика и ИИ

Статистическое предсказание.

Автор: Jakob Ramskov


Предисловие

Когда в 1996 году id software открыли миру Quake, в сетевом движке которого использовался ещё никогда ранее неиспользовавшийся метод предсказания (client prediction), я задался вопросом: "Каким образом они могут предсказать, где я нахожусь?". Позже я попытался разобраться с предсказанием (оно же Dead Reckoning), и как оказалось, оно не имело ничего общего с теорией хаоса или счастливым случаем. Сейчас имеется множество материалов по этому вопросу (например, на gamasutra.com), хотя я думаю, вы и сами это знаете.

Каково ваше следующее движение?

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

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

Что такое статистические данные?

Существует 2 способа сбора статистических данных. Вы можете создать набор правил (a set of rules),  по которым будут определяться, наиболее вероятные, по вашему мнению, действия в различных ситуациях. Ситуация - это набор различных параметров игрока, таких как положение, направление, скорость, действие в нужный момент времени. Либо, вы можете записать шаблоны (record patterns) действий в процессе реальной игры с человеком. Некоторые могут предположить, что это потребует вовлечения нейронных сетей. Такой вариант тоже возможен. Нейронные сети определенно позволяют увидеть большее количество шаблонов, чем может придумать человек, но зато наборы правил легче реализуемы и возможно требуют меньших вычислительных затрат.

Как это работает на практике?

Для каждого кадра, вы перебираете всех игроков и, основываясь на статистической модели, предсказываете их следующие положения. Вы предполагаете, что это предсказание - то, что они действительно делают, так что вы устанавливаете их новое положение, основанное на этом предсказании. ( Запомните: "Вы можете использовать другой алгоритм, как основу для предсказания."). Также, Вы можете предсказать своё собственное положение и сравнить его с реальными данными. Если эти 2 значения не совпадают, и если разница достаточно велика, то всем клиентам отсылается, так называемый корректирующий пакет (a correction packet) c вашим реальным положением. Основываясь на этих данных, клиенты подправляют на своих машинах ваше положение. Преимущество этого метода в том, что вы не должны сообщать о ваших действиях другим игрокам, пока они логичны (т.е. совпадают с предсказанием). При наличии "хорошо обученной" статистической модели можно достаточно сильно понизить количество передаваемых данных. Что и является окончательной целью этой техники. К слову сказать, её использование не ограничено только предсказанием живых игроков. Она будет полезна для создания правдоподобного AI, т.к. для его создания тоже используется предопределенный набор правил.

Почему этот метод до сих пор не реализован?

Возможно, что и реализован, но  это мало вероятно. Я надеюсь, вы представляете, сколько требуется процессорного времени, на предсказания для каждого клиента. Необходимо предсказывать движения всех игроков на каждом кадре каждому из клиентов. Запись статистических данных тоже может быть сложной задачей. Но я думаю, что в скором времени процессоры станут достаточно мощными, чтобы обрабатывать такие объемы данных.


Приветствуются любые комментарии.
(c) Jakob Ramskov/Ramosa Multimedia 1999.

13 марта 2003

Комментарии [2]