Лирика
Речь пойдет об игре Need for Speed: Most Wanted. Эта игра очень популярна и крайне любима многими геймерами-энтузиастами, и многими считается чуть ли не лучшей в серии. Даже если вы не азартный игрок, то наверняка слышали об этой игре в частности или о серии в целом. Но обо всем по порядку.
Я – спидранер. Прохожу игры на скорость. Довелось мне быть одним из первопроходцев в деле скоростного прохождения гоночных игр, поэтому я заодно являюсь одним из «глобальных модераторов» спидран-коммьюнити серии NFS. Участь со мной разделил чех под ником Ewil.
Почему участь? Потому что в один прекрасный момент к нам в дискорд-сервер пришел человек и заявил, что все наши рекорды трасс неправильны, и что мы – нубы. Скрепя сердце, подавляя багет от, как казалось, необоснованного обвинения и борясь с языковым барьером (английским этот человек владеет на очень плохом уровне), мы начали разбираться, что же не так с нашими рекордами. Из обрывков речи мы поняли, что в игре есть некий «timebug», который делает IGT неправильным. Ewil пересмотрел некоторые записи и руками пересчитал время. Оказалось, нам не врали. На записях IGT резко отличалось от RTA. Это были не пара миллисекунд, которые тоже могу решить исход рекорда, а местами разница доходила даже до нескольких секунд(!).
Мы начали искать причину и последствия этого явления. Еще задолго до этого я в личных интересах пытался «вытащить» из игры IGT. Моя попытка не увенчалась успехом, и я как-то забил на эту идею. Информации в интернете мы найти не смогли, за исключением какой-то английской странички с очень коротким описанием, без какой-либо доказательной базы. Поиск по ютубу также не принес результатов, но были найдены записи, которые гласили «No TimeBug».
Чуть позже я познакомился со SpeedyHeart, и она мне подсказала, что в игре время считается как float. Тут все начало проясняться, и мы медленно переходим от унылого вступления к лютому экшону!
Как это работает
Вооружившись Cheat Engine, OllyDbg, DxWND и NFS: MostWanted версии 1.3, я полез рыться в памяти. Выкопал я примерно вот что (картинка кликабельна):
Нас интересуют последние три адреса. Они хранят в себе IGT для разных ситуаций. Почему они float – одному Блэк Боксу известно… Но так не делают! Float, у него же точность, как у дробовика, а может и того хуже.
Собственно, немного о самих таймерах. Таймеры хранят время в секундах, т. е. целая часть – количество полных секунд. Два из этих таймеров, а именно Global IGT и Race IGT, периодически обнуляются. Для Global IGT это происходит в момент выхода в главное меню, а Race IGT обнуляется при рестарте гонки. Подсчет IGT производится через Global IGT, и в какой-то момент времени ему уже не хватает точности. Из-за этого время считается неправильно.
На этой стадии меня заинтересовали несколько вопросов:
- Раз уж есть разница во времени, то отличается ли геймплей с багом и без? Логично предположить, что если IGT ускоряется, то и в целом игра должна становиться «быстрее»
- Какие рамки у этого бага? Как он будет себя вести при разных значениях таймера, и как на это будет реагировать игра.
Ответ на вопрос номер 1 был найден крайне быстро. Я просто взял и изменил показания Global IGT на 300000.0 и получил то, что получил. Время ускорилось почти в два раза(!), однако на физике и поведении игры это никак не отразилось. Прикола ради я тыркал и другие таймеры, но они, почему-то, ни на что не влияют. Собственно, если бы с ускорением времени ускорялся и геймплэй, то в нашем мире спидранерства это считается вполне законным. Все таки мы любим баги. Но такой расклад никого не устроил.
Я пошел немного глубже и нашел ответ на вопрос 2. Как только Global IGT достигает отметки в 524288 время в игре полностью останавливается. Это немного смущает игру, и она начинает
Float — ад перфекциониста.
Хоть и не в прямом смысле, но все же. Для наглядной демонстрации я написал небольшую программу, которая поможет мне оценить всю печальность происходящего.
Перед непосредственно кодом, распишу немного про цели. Известно, что игра «блокирует» цикл обновления физики на 120 раз в секунду (опять же, спасибо SpeedyHeart за информацию). Однако vsync обрубает обновление физики еще сильнее, до 60 раз в секунду. Соответственно, мы просто возьмем float-переменную и будем циклически туда добавлять 1/60 секунды. Потом мы посчитаем, за сколько шагов мы добились результата, и за сколько шагов мы должны были добиться этого результата. Также будем делать все циклически для разных случайных величин и считать среднюю погрешность в рассчетах. Любые отклонения в 2 и менее шагов (33мс) мы будем считать незначительными, потому что игра показывает время до сотых секунды.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <conio.h>
#define REPEATS 1000 // Количество проверок
#define ESCAPE 27 // Код клавиши ESCAPE
#define TEST_TIME 2 // Время, проведенное на трассе
#define START_TIME 0 // Изначальное значение внутриигрового таймиера
void main( )
{
time_t t;
srand( time( &t ) );
while ( true )
{
float diffs[ REPEATS ];
int frame_diffs[ REPEATS ]; // Сторэйдж разниц
for ( int i = 0; i < REPEATS; i++ )
{
int limit = rand( ) % TEST_TIME + 1;// Генерируем случайное кол-во времени,
// +1 не даст нам сгенерировать 0
limit *= 60; // Минуты в секунды
limit += (START_TIME * 60); // Выравниваем конечное время
float t = 0.0f + (START_TIME*60); // Выравниваем начальное время
float step = 1.0f / 60.0f; // И лочим все на 60 фпс
int steps = 0;
while ( t < limit )
{
steps++;
t += step;
}
// Считаем ожидания и выводим их на экран
double expectation = (double)(limit - START_TIME*60)/ ( 1.0 / 60.0 );
printf("%f\n", t );
printf("Difference = %f; steps = %d\n", t - limit, steps );
printf( "Expected steps = %f; frames dropped = %d\n",
expectation, (int)expectation - (int)steps );
diffs[i] = fabs( t - limit );
frame_diffs[ i ] = (int)expectation - (int)steps;
}
// Считаем среднее и статистику
float sum = 0;
int frame_sum = 0;
for ( int j = 0; j < REPEATS; j++ )
{
sum += diffs[ j ];
frame_sum += frame_diffs[ j ];
}
printf( "Avg. time difference = %f, avg. frame difference = %d\n",
sum / REPEATS, frame_sum / REPEATS );
// В случае "any key" продолжаем, в случае "ESCAPE" выходим
printf( "Press any key to continue, press esc to quit\n" );
if ( getch() == ESCAPE )
break;
}
}
Меняя значения START_TIME и TEST_TIME мы можем получить необходимую нам статистику. В целом, пока START_TIME не превышает 15 минут, то обычный 2-х минутный заезд окажется «свободным» от бага. Разница остается не критичной в рамках игры, 1-2 кадра:
16 Минут же оказались «критической точкой», когда время беспощадно плывет:
Интересен так же тот момент, что в зависимости от START_TIME будет меняться «сторона» ошибки. Например, после полутора часового непрерывного геймплея время начнет течь медленнее, чем должно:
Поигравшись со значениями еще немного я оценил, что в получившейся программе «время» течет примерно так же, как в игре. Это было подтверждено практически – любые рекорды, записанные «из главного меню» в течение первых 15 минут геймплея были чистыми. При START_TIME близкому к 300000 секунд количество шагов было почти в два раза меньше, чем ожидалось. При START_TIME, большем магической константы 524288 программа переставала работать. Все это подтверждало, что процесс подсчета времени был скопирован верно.
Устраняем нежелательное поведение
Теперь, когда известна проблема и ее поведение, можно ее устранить. Нужно лишь перезаписывать Global IGT всякий раз, когда игрок начинает заезд заново. Это можно узнать довольно просто – в этот момент обнуляется Race IGT. Но тут есть проблема.
Есть два издания игры: NFS: Most Wanted и NFS: Most Wanted Black Edition. Второе издание включает в себя две дополнительные машины и две трассы, да 69-ое испытание. Но, технически, это две совершенно разные игры! Их запускаемые файлы отличаются. Помимо этого, есть патч 1.3… Который отличается для каждого издания. В итоге у нас есть 4 разных версии игры, которые надо поддерживать. Этот факт делает «правильный» путь чрезмерно сложным и неоправданным. По-хорошему, нужно слегка подправить запускаемый файл и обнулять счетчик там, но… Править 4 разных экзешника, которые еще и запакованы, да защищены от отладки… Лучше просто напишем простую программку, которая будет в реалтайме отслеживать состояние таймеров и обнулять их при необходимости. Писать будем на C#.
Вот такую архитектурку я набросал. GameProcess – это вспомогательный класс, который упрощает доступ к чтению-записи памяти процесса. GameHolder – сердце программы. Он будет инициализировать GameProcess, а при «подцепе» процесса будет определять версию игры и создавать необходимый экземпляр наследника Game. Поскольку логика «фикса» не отличается от версии к версии, то ее лучше вынести в один класс.
Как же нам определить версию? Просто – по размеру основного модуля. Я специально реализовал проперти ImageSize. А чтобы не захламлять код магическими константами, запилим enum:
enum ProcessSizes
{
MW13 = 0x00678e4e
}
Остальные версии добавим по мере их попадания ко мне в руки.
isUnknown отвечает за тот факт, удалось ли нам определить версию или нет. Из всего класса нам интересен только метод Refresh, вот он:
public void Refresh()
{
if(!process.IsOpen)
{
// In cases when the process is not open, but the game exists
// The process had either crashed, either was exited on purpose
if(game != null)
Console.WriteLine("Process lost (quit?)");
game = null;
return;
}
if(isUnknown) // If we couldn't determine game version, do nothing
{
return;
}
// If process is opened, but the game doesn't exist, we need to create it
if(process.IsOpen && game == null)
{
Console.WriteLine("Opened process, size = 0x{0:X}", process.ImageSize);
switch((ProcessSizes)process.ImageSize) // Guessing version
{
case ProcessSizes.MW13:
game = new MW.MW13(process);
break;
default:
Console.WriteLine("Unknown game type");
isUnknown = false;
break;
}
}
// At last, update game
game.Update();
}
Логика фикса вышла совсем простенькой:
public abstract class Game
{
private float lastTime;
private GameProcess game;
/// <summary>
/// Synch-timer's address
/// </summary>
protected int raceIgtAddress;
/// <summary>
/// Timer-to-sync address
/// </summary>
protected int globalIgtAddress;
private void ResetTime()
{
byte[] data = { 0, 0, 0, 0 };
game.WriteMemory(globalIgtAddress, data);
}
public void Update()
{
float tmp = game.ReadFloat(raceIgtAddress);
if (tmp < lastTime)
{
ResetTime();
Console.WriteLine("Timer reset");
}
lastTime = tmp;
}
public Game(GameProcess proc)
{
game = proc;
lastTime = -2; // Why not anyway
}
}
Дело осталось за малым: реализовать версию, выставив в конструкторе необходиме значения соответствующим protected-переменным. В мэйне же просто кидаем цикл обновления в отдельный трэд и забываем про него. Ах да, из-за особенностей карточек Nvidia и особенностей реализации установщика игр NFS мы будет принимать на вход имя процесса, чтобы была возможность кастомизации.
class Program
{
static void Run(object proc)
{
GameHolder holder = new GameHolder((string)proc);
while (true)
{
Thread.Sleep(100);
holder.Refresh();
}
}
static void Main(string[] args)
{
Thread t = new Thread(new ParameterizedThreadStart(Run));
t.Start(args[0]);
Console.WriteLine("Press any key at any time to close");
Console.ReadKey();
t.Abort();
}
}
На этом фикс заканчивается. Компилируем, запускаем и забываем о таймбаге, yay! ^_^ Картинка кликабельна.
На самом деле, никуда этот баг не денется. Если один заезд физически не уложится в рамки 15 минут, то тут уже ничего не поделаешь. Но таких заездов в игре аж один, и тот от полиции.
Полные исходники на гитхабе.
Summary
Вот так один маленький баг нехило подпортил нам жизнь. А ведь его можно было избежать, если бы Black Box использовали в свое время double, но нет. Кстати, это яркий пример того, как «написанное однажды» выливается в кучу неулавливаемых/перекатывающихся багов. Timebug присутствовал в каждой игре от Black Box ever since. В Carbon, ProStreet и даже Undercover. В последнем они поменяли логику подсчета IGT, но эти три таймера там все так же присутствуют, и ошибки округления приводят к странным последствиям. SpeedyHeart обещала сделать видео-обзор всей найденой в процессе информации, так что ждем-с.
Чему меня научила эта ситуация? Не знаю. Я и так понимал, что использовать float для серьезных вычислений – идея сомнительная. Но теперь я лучше представляю, как именно все это будет работать на практике. Однако забавно получилось, что такая серьезная компания могла допустить такую серьезную ошибку, да еще и несколько лет подряд не замечать ее.
Мне кажется, что для данной задачи (подсчет IGT) нужно использовать такой путь: ставить timestamp в начале заезда, а потом вычитать из текущего времени. Причем арифметических операций стоит избегать, даже над целыми числами. 1/60 секунды это 16,(6) миллисекунд, поэтому в случае целого числа мы будем наивно откидывать 0,(6) при каждом сложении, что приведет к неточностям в подсчете.
В некоем обозримом будущем я постараюсь написать фикс и на другие версии. На этом у меня все, спасибо за внимание.
UPD: Поправил ссылку на гитхаб всвязи с переездом на новое имя.
Комментарии (38)
VEG
19.07.2017 15:47+4Не могу не похвастать тут моим большим патчем для Need For Speed III: Hot Pursuit :) Там даже из машинного кода было ясно, как много не очень качественного кода было написано, который просто должен был сломаться со временем. Целый ряд переполнений значений int32: при определении свободного пространства на диске, количества RAM, количества памяти в GPU, частоты процессора. У игры получались отрицательные числа и она считала, что машина слабее Pentium 166, из-за чего в некоторых случаях запускала ветки кода для самых слабых компьютеров. Также тут было большое количество ошибок вроде переполнения буфера из-за полного отсутствия проверок выхода за пределы массивов и тому подобных глупых ошибок. Например, массив, который хранил в себе список поддерживаемых драйвером видеокарты форматов текстур, был рассчитан на не более чем 14 форматов, и как только драйвера стали поддерживать больше — переполнение буфера и падение. А люди винили в этом новые драйвера (ведь игра стала падать при обновлении драйвера), хотя виноват был именно код в игре. Ну и в этом духе. В сумме уже накопилось наверное сотни две исправлений.
GrimMaple
19.07.2017 16:29В любой части NFS очень много некачественного кода. Например, ProStreet отказывается нормально работать, если частота процессора не делится на 2 нацело. А совсем правильно он будет работать только на частоте 3.20 ГГц (привет порт с Х360). Хотя трудно в этом винить разработчиков — их заставляли за год клепать ААА игру с поддержкой как минимум 3-х разных платформ (PC, PS2, PS3, X360), я вообще удивлен, что они делали игры стабильные хотя бы на железе уровня выхода игры. Большая часть проблем с ними возникает на более шустрых железках. А мелкие баги не так уж и печальны :)
ilyaplot
19.07.2017 15:54Простите, что немного не по теме. Хотелось бы узнать, при прохождении таких игр, как NFSU, NFSU2 и вышеупомянутой игры, используются ли стены для поворотов на скорости? Насколько я понимаю, игровая механика каким-то образом учитывает столкновения, которые влияют не только на скорость машинки, но и на скорость ботов? Просто у меня сложилось впечатление, что любой контакт со стеной снижает время прохождения трассы ботами.
GrimMaple
19.07.2017 16:18+2Во все игры NFS встроен механизм, который называется Catch-up. Он нацелен на «выравнивание» сложности, чтобы хорошие игроки не скучали, а плохие не сильно страдали от выбранной сложности. Как этот механизм работает доподлинно не известно, но он просто «накручивает» характеристики машинам ИИ и те едут быстрее. Механизм явно меняется от игры к игре. Например в Carbon иногда можно наблюдать, как ИИ в прямом смысле пролетает камеры на скорости 500+ км/ч, что иногда вводит в ступор. Но кетчуп — не односторонний механизм, он так же может накручивать и игроку, но это реже заметно.
Стены используются в основном в NFSU2, в других частях это не дает такого сильного выигрыша. В основном, когда сбросить скорость касанием стены быстрее, чем тормозить, и угол выхода из поворота получается лучше.
Про вашу догадку с сокращением времени и касанием стен: опять же, доподлинно не известно, влияют ли конкретно столкновения, но такая тенденци была замечина. Вот это видео неплохо демонстрирует механику кетчупа в целом и касания стен в частности.ilyaplot
19.07.2017 16:39Спасибо за разъяснение, я в основном, то в NFSU2 и играл, проходя несколько раз. Самый последний раз был настолько быстрым, что я даже расстроился, что игра такая короткая. Во время последнего прохождения как раз и было четко заметно влияние столкновений на характеристики ИИ, который, кстати, весьма глуп на поворотах.
gearplex
23.07.2017 14:40Самый суровый catch-up, на момей памяти, был в NFSU. Если стараться удерживать первое место, игра превращалась в ад — боты за спиной проходили участки дороги любой сложности, даже не снижая скорости, гражданские машины «выныривали» в самых неудобных местах. А вот держаться вторым, и рвануть перед финишем было проще всего — тогда и боты начинали ошибаться и врезаться.
questor
19.07.2017 21:46+1Ничего не хочу писать умного, просто поделюсь эмоциями:
Хабр — торт! Прочитал статью на одном дыхании.
HounD
19.07.2017 22:34+1float summation известная проблема для которой существуют известные решения. Сам по себе float ни плох ни хорош, а такой какой есть ))
AlB80
20.07.2017 04:19Причем арифметических операций стоит избегать, даже над целыми числами.
int64 и наносекунды отлично подходят друг к другу. Во многих реализациях c++11 классы std::steady_clock и std::system_clock реализованы именно так.GrimMaple
20.07.2017 04:26Идея хороша, если не несколько «но»: в Windows размер тика составляет 1/10000 миллисекунды, а получить «цельное» количество обновлений в секунду очень сложно. В конечном итоге все равно каждый кадр будет занимать 16,(6) миллисекунд, ибо обрубится vsync-ом. Для 120/144Hz мониторов число будет другое, но оно все равно получится не целым, и даже не дробным. Переводя в тики процессора, мы получим 166666,(6) тиков, и при сложении мы будем всякий кадр забывать про ~0,67 тика. Это примерно 40 тиков в секунду. Со временем ошибка накопится и выльется в парочку миллисекунд, что не особо критично, но неприятно.
Можно попытаться выносить обновление физики в отдельный поток и его насильно блокировать на 100фпс, но это уже значительно сложнее реализовать.
ThirteenAG
20.07.2017 10:36В итоге у нас есть 4 разных версии игры, которые надо поддерживать. Этот факт делает «правильный» путь чрезмерно сложным и неоправданным. По-хорошему, нужно слегка подправить запускаемый файл и обнулять счетчик там, но… Править 4 разных экзешника, которые еще и запакованы, да защищены от отладки… Лучше просто напишем простую программку, которая будет в реалтайме отслеживать состояние таймеров и обнулять их при необходимости.
На самом деле нет. Лучше сделать плагин, который загружается вместе с игрой без необходимости запускать какие-либо программы. А для поддержки разных экзешников у нас есть паттерны :)
Пример здесь и здесь.GrimMaple
20.07.2017 11:04Привет, ThirteenAG!
Я, увы, сделал решение по мере своих сил и возможностей. Решении с Extra Options очень популярно в нашем коммьюнити, и изначально хотел делать через него, но… Extra Options вызывают ряд дополнительных проблем, с которыми мы столкнулись, и из-за которых сейчас стоит вопрос о запрете использования их в целом. Поэтому я преследовал цель оставить исходный код игры в самом минимально измененном варианте :)
mayorovp
Проблема была не во float, а в накоплении ошибок округления. При правильном решении (получать системную отметку времени и вычитать начальное значение) точности float вполне хватило бы.
GrimMaple
Думаю, это была «одна из ошибок». В условиях того кода, что есть, банальное использование double полностью исключило бы баг. Я не думаю, что кто-то в здравом уме будет настолько сильно увлечен беспрерывным переигрыванием одного уровня, чтобы дабл «поехал». Хотя я согласен с вашим решением, что и написал в конце статейки :)
mayorovp
Подход "всюду используем только double" жрет много памяти и работает медленнее. А для того чтобы догадаться использовать double для таймера — надо знать про эту ошибку. Но тогда ничего не мешало бы и нормальное решение сделать.
Jef239
Почему медленней на современных х86? FPU — 80 бит, то есть long double, ширина шины памяти — 64 бита и выше. С чего float будет медленней? Скорее уж наоборот. Ну разве что если кэша не хватит…
Аналогично short int и char работают чуть медленней, чем intна современных машинах.
rogoz
1 регистр SSE — 2 double или 4 float.
VEG
Это касается только тех мест, где векторизованные вычисления вообще возможны. В описанном же примере нет никаких массивов чисел и однообразных операций над ними.
mayorovp
В любой 3D-игре таких мест должно быть полно. Чтобы знать что конкретно в этом месте double бы не помешал — нужно думать. А программист не думал.
VEG
В данном случае лучше было использовать целочисленную переменную для внутриигровых тиков. В более старом NFS3, например, внутриигровое время представлено целым числом тиков, где 128 тиков = 1 секунда.
Jef239
Очень сомневаюсь, насчет «любой», Фиксированная точка (int c масштабированием) быстрее плавающей, поэтому AFAIK старые движки жили на ней.
Кроме того, движок и сама игра — чуть разные вещи и программируются зачастую разными людьми. А в самой игре (без движка) как-то не видно, где векторизация возможна.
MacIn
Смотря какой процессор.
Jef239
Гм… ну приведите пример процессора, где умножение и деление с плавающей точкой быстрее, чем целое умножение и деление.
Temtaime
Сейчас многие современные компиляторы отказываются от 80-bit fpu, потому что оно неудобно и тянет старые инструкции.
Всё считают с помощью SSE.
lorc
Не факт что это правильное решение. Время в игре может не совпадать с реальным временем по разным причинам: игру поставили на паузу, игра показывает повтор ситуации, игра тормозит и не успевает обсчитывает свою механику в реальном времени, время в игре намеренно ускоряется или замедляется и т.д.
mayorovp
Все эти ситуации решаемые если вспомнить математику.
VEG
Заводим целочисленную переменную int32, каждый игровой «тик» добавляем в неё единичку, а затем сразу же в оригинальную переменную пишем значение нашей целочисленной переменной, умноженное на размер тика (то, на сколько в оригинальном коде увеличивается эта переменная каждый раз). Таким образом, накопления ошибки не будет. Это, думаю, можно сделать прямо внутри исполняемого файла, пропатчив соответствующий машинный код. Но нужно, конечно же, детальнее вникнуть в код, чтобы выяснить, подойдёт ли такой вариант :)
lorc
Пишем или добавляем?
Вообще, у игры должны быть свои часы, согласно которым происходят все события. Эти часы должны быть целочисельными. Один цикл просчета состояния игры — один игровых тик часов. Потом эти тики пересчитываются в секунды согласно игровых правил.
VEG
Пишем. Псевдокод (предположим, игра тикает 120 раз в секунду):
i32_ticks++;f_step = 1.0 / 120.0
f32_time = i32_ticks * f_step;
В оригинале же, судя по описанию, что-то типа:
f_step = 1.0 / 120.0f32_time = f32_time + f_step;
lorc
А, теперь понял. Мы говорили о том же самом, просто разными словами.
pestilent
Если я правильно понимаю, дело не только в накоплении ошибок, но и именно в недостатке точности float.
GrimMaple
Если быть совсем честным, то проблема в решении целиком. Оно какое-то неудачное, как мне кажется. Но как уж сделали :)
mayorovp
Если бы ошибки не накапливались — точности float вполне хватило бы.
pestilent
Я просто хочу сказать, что хотя переменная step и может храниться с достаточной точностью, но когда мы подсчитываем прошедшее время t, step всё равно фактически округляется до того знака, сколько сейчас помещается в частичной сумме. Конечно, вряд ли кто-то будет несколько суток нон-стоп ездить, чтобы всё совсем сломалось, но заметные эффекты, как свидетельствует статья, появляются уже через 15 минут.