[Ненормальное программирование, Разработка игр, Алгоритмы] Трассировка лучей в Notepad.exe со скоростью 30 кадров в секунду (перевод)

Автор Сообщение
news_bot ®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

Создавать темы news_bot ® написал(а)
24-Дек-2020 15:30

Несколько месяцев назад на Reddit былопубликован пост, где описывалась игра, в которой использовался клон Блокнота с открытым исходным кодом для обработки всего ввода и рендеринга. Читая об этом, я подумал, что было бы здорово увидеть что-то похожее, работающее со стандартным Блокнотом Windows. Тогда у меня было слишком много свободного времени.В итоге я создал игру Snake и небольшой трассировщик лучей, которые используют стандартный Блокнот для всех задач ввода и рендеринга, и попутно узнал о DLL Injection, API Hooking и Memory Scanning. Описание всего, что я узнал в процессе работы, может оказаться интересным чтением для вас.
Сначала я хочу рассказать о том, как работают сканеры памяти, и как я использовал их, чтобы превратить notepad.exe в цель рендеринга со скоростью 30+ кадров в секунду. Я также расскажу о построенном мною трассировщике лучей для визуализации в Блокноте.Отправка ключевых событий в блокнотНачну с того, что расскажу об отправке ключевых событий в запущенный экземпляр Блокнота. Это была скучная часть проекта, поэтому я буду краток.Если вы никогда не создавали приложение из элементов управления Win32 (например, я этого не делал), вы можете быть удивлены, узнав, что каждый элемент пользовательского интерфейса, от строки меню до кнопки, технически является собственным «окном», и отправка ключа ввода в программу включает отправку этого ввода в элемент пользовательского интерфейса, который вы хотите его получить. К счастью, Visual Studio поставляется с инструментом под названием Spy++, который может перечислить все окна, составляющие данное приложение.
Блокнот в Spy++Spy++ обнаружил, что дочернее окно Блокнота, которое я искал, было окном «Редактировать». Как только я это узнал, мне оставалось просто выяснить, как правильно сочетать вызовы функций Win32, чтобы получить HWND для этого элемента пользовательского интерфейса, а затем отправить туда входные данные. Получение HWND выглядело примерно так:Как только у меня появился HWND для правого элемента управления, рисование символа в элементе управления редактированием Блокнота было просто вопросом использования PostMessageдля отправки ему события WM_CHAR.Обратите внимание, если вы захотите использовать Spy++, то наверняка выберете его 64-разрядную версию. Однако она по необъяснимым причинам не является той версией, которую Visual Studio 2019 запускает по умолчанию. Вместо этого вам нужно будет искать в файлах программы Visual Studio «spyxx_amd64.exe».Когда всё заработало, мне потребовалось 10 секунд, чтобы понять, что даже если бы я смог найти способ использовать оконные сообщения для рисования полных игровых экранов в Блокноте, это получилось бы слишком медленно, и даже близко не будет похоже на цикл обновления 30 Гц. К тому же это выглядело очень скучно, поэтому я не стал тратить время на поиски способов ускорить процесс.CheatEngine для хороших парнейПри настройке поддельного ввода с клавиатуры мне вспомниласьCheatEngine. Эта программа позволяет пользователям находить и изменять память в процессах, запущенных на их машинах. Чаще всего её используют люди, чтобы получить больше ресурсов/жизней/времени в играх или делать другие вещи, которые огорчают разработчиков игр. Однако программа также может послужить и силам добра.Сканеры памяти наподобие CheatEngine находят все адреса памяти в целевом процессе, которые содержат определенное значение. Допустим, вы играете в игру и хотите поднять себе здоровье. Для этого вы можете выполнить процесс, который выглядит следующим образом:
  • С помощью сканера памяти найдите в памяти игры все адреса, по которым хранится значение вашего здоровья (скажем, 100)
  • Сделайте что-нибудь в игре, чтобы изменить свое здоровье до нового значения (например, 92)
  • Переберите все адреса, которые вы нашли ранее (которые хранят 100), чтобы найти те, которые теперь хранят 92
  • Повторяйте этот процесс, пока у вас не будет одного адреса памяти (который, скорее всего, является местом, где хранится ваше здоровье)
  • Измените значения адреса

CheatEngine и Блокнот "подружились" В принципе, я так и сделал, но вместо значения здоровья  искал память, в которой хранилась строка текста, отображаемая в настоящее время в Блокноте. После любимого мной метода проб и ошибок я научился использовать CheatEngine, чтобы находить (и менять) отображаемый текст. Я также узнал три важных факта о Блокноте:
  • В окне редактирования Блокнота экранный текст сохраняется в кодировке UTF-16, даже если в правой нижней части окна указано, что ваш файл имеет формат UTF-8.
  • Если бы я продолжал удалять и набирать одну и ту же строку, CheatEngine начал бы находить несколько копий этих данных в памяти (возможно, буфер отмены?)
  • Я не мог заменить отображаемый текст более длинной строкой. Это означает, что Блокнот не выделял текстовый буфер заранее
Создание сканера памятиНесмотря на невозможность изменить длину текстового буфера, найденный функционал выглядел многообещающе, и я решил написать собственный небольшой сканер памяти для проекта.Я не смог найти много информации о создании сканеров памяти, но вблоге Криса Веллонса говорится о сканере памяти, который он написал для своего читерского инструмента. Используя эти сведения и немного опыта работы с CheatEngine, я смог кое-что сваять, и в результате основной алгоритм для сканера памяти выглядит примерно так:
FOR EACH block of memory allocated by our target process
    IF that block is committed and read/write enabled
        Scan the contents of that block for our byte pattern
        IF WE FIND IT
            return that address
Моя версия сканера памяти составила всего ~ 40 строк кода.Итерация по памяти процессаПервое, что нужно сделать сканеру памяти, — это перебрать выделенную для процесса память.Поскольку диапазон виртуальной памяти для каждого 64-битного процесса в Windows одинаков (от 0x00000000000 до 0x7FFFFFFFFFFF), я начал с создания указателя на адрес 0 и использовал VirtualQueryEx для получения информации об этом виртуальном адресе для моей программы.VirtualQueryEx группирует смежные страницы с идентичными атрибутами памяти в структуры MEMORYBASICINFORMATION, поэтому вполне вероятно, что структура, возвращаемая VirtualQueryEx для данного адреса, содержит информацию о более чем одной странице. Возвращенная MEMORYBASICINFORMATION хранит этот совместно используемый набор атрибутов памяти вместе с адресом начала диапазона страниц и размером всего диапазона.Как только у меня появилась первая структура MEMORYBASICINFORMATION, итерация по памяти сводилась только к добавлению элементов BaseAddress и RegionSize текущей структуры вместе и передаче нового адреса в VirtualQueryEx для получения следующего набора страниц
char* FindBytePatternInProcessMemory(HANDLE process, const char* pattern, size_t patternLen)
{
  char* basePtr = (char*)0x0;
  MEMORY_BASIC_INFORMATION memInfo;
  while (VirtualQueryEx(process, (void*)basePtr, &memInfo, sizeof(MEMORY_BASIC_INFORMATION)))
  {
    const DWORD mem_commit = 0x1000;
    const DWORD page_readwrite = 0x04;
    if (memInfo.State == mem_commit && memInfo.Protect == page_readwrite)
    {
      // search this memory for our pattern
    }
    basePtr = (char*)memInfo.BaseAddress + memInfo.RegionSize;
  }
}
Приведённый выше код также определяет, зафиксирован ли набор страниц и разрешено ли чтение/запись путём проверки элементов структуры .State и .Protect. Вы можете найти все возможные значения для этих переменных в документации для MEMORYBASICINFORMATION, но значения, которые требовалисьмоему сканеру, имели состояние 0x1000 (MEMCOMMIT) и уровень защиты 0x04 (PAGEREADWRITE).Поиск байтового шаблона в памяти процесса Невозможно напрямую прочитать данные в адресном пространстве другого процесса (по крайней мере, я не догадался, как это сделать). Вместо этого мне сначала нужно было скопировать содержимое диапазона страниц в адресное пространство сканера памяти. Я сделал это с помощью ReadProcessMemory.После того, как память была скопирована в локально видимый буфер, поиск в ней байтового шаблона стал достаточно простым. Чтобы упростить задачу, я проигнорировал возможность того, что в моей первой реализации сканера могло быть несколько копий целевого байтового шаблона в памяти. Позже я придумал метод решения этой проблемы, который избавил меня от необходимости решать её в логике моего сканера.
char* FindPattern(char* src, size_t srcLen, const char* pattern, size_t patternLen)
{
  char* cur = src;
  size_t curPos = 0;
  while (curPos < srcLen){
    if (memcmp(cur, pattern, patternLen) == 0){
      return cur;
    }
    curPos++;
    cur = &src[curPos];
  }
  return nullptr;
}
Если FindPattern() вернул указатель совпадения, его адрес нужно было преобразовать в адрес того же бита памяти в адресном пространстве целевого процесса. Для этого я вычел начальный адрес локального буфера из адреса, который был возвращен FindPattern, чтобы получить смещение, а затем добавил его к базовому адресу блока памяти в целевом процессе. Вы можете увидеть это ниже.
char* FindBytePatternInProcessMemory(HANDLE process, const char* pattern, size_t patternLen)
{
  MEMORY_BASIC_INFORMATION memInfo;
  char* basePtr = (char*)0x0;
  while (VirtualQueryEx(process, (void*)basePtr, &memInfo, sizeof(MEMORY_BASIC_INFORMATION))){
    const DWORD mem_commit = 0x1000;
    const DWORD page_readwrite = 0x04;
    if (memInfo.State == mem_commit && memInfo.Protect == page_readwrite){
      char* remoteMemRegionPtr = (char*)memInfo.BaseAddress;
      char* localCopyContents = (char*)malloc(memInfo.RegionSize);
      SIZE_T bytesRead = 0;
      if (ReadProcessMemory(process, memInfo.BaseAddress, localCopyContents, memInfo.RegionSize, &bytesRead)){
        char* match = FindPattern(localCopyContents, memInfo.RegionSize, pattern, patternLen);
        if (match){
          uint64_t diff = (uint64_t)match - (uint64_t)(localCopyContents);
          char* processPtr = remoteMemRegionPtr + diff;
          return processPtr;
        }
      }
      free(localCopyContents);
    }
    basePtr = (char*)memInfo.BaseAddress + memInfo.RegionSize;
  }
}
Если вы хотите увидеть пример того, как это работает, посмотрите проект «MemoryScanner» врепозитории на github. Попробуйте в Блокноте! (ни на чём другом не пробовал, так что ymmv, ваши результаты могут быть другими).Использование байтовых шаблонов UTF-16Как вы помните, Блокнот хранит свой экранный текстовый буфер как данные UTF-16, поэтому байтовый шаблон, который передается в FindBytePatternInMemory (), также должен быть UTF-16. Для простых строк это просто включает добавление нулевого байта после каждого символа. Проект MemoryScanner в github делает это за вас:
//convert input string to UTF16 (hackily)
const size_t patternLen = strlen(argv[2]);
char* pattern = new char[patternLen*2];
for (int i = 0; i < patternLen; ++i){
  pattern[i*2] = argv[2][i];
  pattern[i*2 + 1] = 0x0;
}
Обновление и перерисовка элемента управления редактированием БлокнотаСледующим шагом после того, как я получил адрес отображаемого текстового буфера в Блокноте, было использование WriteProcessMemoryдля его изменения. Написать код для этого было просто, но я быстро понял, что просто записи в текстовый буфер было недостаточно, чтобы Блокнот перерисовал элемент управления Edit.К счастью, Win32 api предоставляет функциюInvalidateRect, с помощью которой можно заставить элемент управления перерисовываться.В целом, изменение отображаемого текста в Блокноте выглядело примерно так:
void UpdateText(HINSTANCE process, HWND editWindow, char* notepadTextBuffer, char* replacementTextBuffer, int len)
{
  size_t written = 0;
  WriteProcessMemory(process, notepadTextBuffer, replacementTextBuffer, len, &written);
  RECT r;
  GetClientRect(editWindow, &r);
  InvalidateRect(editWindow, &r, false);
}
От сканера памяти к рендереруРазрыв между сканером рабочей памяти и полноценным рендерером блокнота на удивление невелик. Было только три проблемы, которые нужно было решить, чтобы перейти от того, что я успел добиться, к трассировщику лучей,  который и был мне нужен.Вот эти проблемы:
  • Мне нужно было контролировать размер окна Блокнота
  • Мне всё ещё не удалось увеличить размер текстового буфера на экране
  • Мой сканер памяти не обрабатывал повторяющиеся последовательности байтов
Первый вопрос сам по себе не представлял большой проблемы. Добавить вызов MoveWindow было нетрудно, но я упомянул этот процесс, потому что он стал важной частью моего подхода к следующей проблеме в списке.В итоге я жестко запрограммировал размер окна Блокнота, а затем подсчитал, сколько символов (моноширинного шрифта) потребуется, чтобы точно заполнить окно такого размера. Затем после вызова MoveWindow я предварительно выделил экранный текстовый буфер, отправив такое количество сообщений WM_CHAR в Блокнот. Это было похоже на читерство, но это хороший вид читерства.Чтобы убедиться, что у меня всегда был уникальный шаблон байтов для поиска, я просто рандомизировал, какие символы я отправляю в сообщениях WM_CHAR.Вот пример того, как может выглядеть подобный код. Фактический код в репозитории github отформатирован немного иначе, но работает точно так же.
void PreallocateTextBuffer(DWORD processId)
{
  HWND editWindow = GetWindowForProcessAndClassName(processId, "Edit");
  // it takes 131 * 30 chars to fill a 1365x768 window with Consolas (size 11) chars
  MoveWindow(instance.topWindow, 100, 100, 1365, 768, true);
  size_t charCount = 131 * 30;
  size_t utf16BufferSize = charCount * 2;
  char* frameBuffer = (char*)malloc(utf16BufferSize);
  for (int i = 0; i < charCount; i++){
    char v = 0x41 + (rand() % 26);
    PostMessage(editWindow, WM_CHAR, v, 0);
    frameBuffer[i * 2] = v;
    frameBuffer[i * 2 + 1] = 0x00;
  }
  Sleep(5000); //wait for input messages to finish processing...it's slow.
  //Now use the frameBuffer as the unique byte pattern to search for
}
По факту это означало, что сразу после запуска я должен был увидеть, как окно моего Блокнота медленно заполняется случайными символами, прежде чем я смогу получить указатель текстового буфера и очистить экран.
Всё вышеперечисленное зависит от использования известного начертания и размера шрифта для правильной работы. Я собирался добавить код, чтобы заставить блокнот использовать нужные мне шрифты (Consolas, 11pt), но по какой-то причине отправка сообщений WM_SETFONT продолжала портить отображение шрифтов, и мне не хотелось выяснять, что пошло не так там. Consolas 11pt был шрифтом Блокнота по умолчанию в моей системе, и этого мне было достаточно.Трассировка лучей в блокнотеОбъяснение того, как создать трассировщик лучей, выходит далеко за рамки того, о чем я хочу рассказать сейчас. Если вы в целом не знакомы с трассировкой лучей, перейдите наScratchAPixel и навсегда научитесь этому. Я хочу закончить эту историю быстрым обсуждением тонкостей подключения трассировщика лучей ко всему тому, о чём я только что говорил.Вероятно, имеет смысл начать с буферов кадров. Чтобы свести к минимуму количество вызовов WriteProcessMemory (как для разумности, так и для производительности), я выделил локальный буфер трассировщика лучей того же размера, что и текстовый буфер Блокнота (количество символов * 2 (из-за UTF16)). Все вычисления рендеринга будут записываться в этот локальный буфер до конца фрейма, когда я использую один вызов WriteProcessMemory для одновременной замены всего содержимого буфера Блокнота. Это привело к действительно простому набору функций для рисования:
void drawChar(int x, int y, char c); //local buffer
void clearScreen(); // local buffer
void swapBuffersAndRedraw(); // pushes changes and refreshes screen.
Что касается трассировки лучей, то, учитывая низкое разрешение моей цели рендеринга (131 x 30), мне пришлось всё упростить, поскольку «пикселей» просто не хватало для качественного отображения мелких деталей. Я закончил трассировку только одного первичного луча и теневого луча для каждого пикселя, в котором выполняется рендеринг, и я даже думал о том, чтобы отбросить тени, пока не нашел насайте Пола Бурка красивую плавающую шкалу оттенков серого в цветовую шкалу ascii. Наличие такой низкой сложности сцены и небольшой поверхности рендеринга означало, что мне вообще не придётся распараллеливать рендеринг.Я также столкнулся с проблемой отображения. Нужно было добиться, чтобы всё выглядело правильно, даже когда персонажи были выше их ширины. В конце концов, я «исправил» это, уменьшив вдвое значение ширины, которое я использовал при расчётах соотношения сторон.
float aspect = (0.5f * SCREEN_CHARS_WIDE) / float(SCREEN_CHARS_TALL);
Единственная проблема, для которой я не нашел рабочего решения, заключается в том, что обновление содержимого элемента управления редактированием Блокнота вызывает очень заметное мерцание. Я пробовал кучу разных вещей, чтобы избавиться от этого, включая попытку удвоить буфер элемента управления редактирования, выделив вдвое большее количество символов и используя сообщения WM_VSCROLL, чтобы «поменять местами» буфер, регулируя положение полосы прокрутки. К сожалению, ничего из того, что я пробовал, не сработало, и мерцание осталось.Часть 2: Доступен ввод Boogaloo!Следующей (и последней) частью моих поисков по созданию игры в реальном времени в Блокноте было выяснить, как обрабатывать ввод данных пользователем. Если вы хотите большего, следующий постможно найти здесь!
===========
Источник:
habr.com
===========

===========
Автор оригинала: Kyle Halladay
===========
Похожие новости: Теги для поиска: #_nenormalnoe_programmirovanie (Ненормальное программирование), #_razrabotka_igr (Разработка игр), #_algoritmy (Алгоритмы), #_bloknot (блокнот), #_trassirovka_luchej (трассировка лучей), #_programmirovanie (программирование), #_gore_ot_uma (горе от ума), #_windows, #_nenormalnoe_programmirovanie (
Ненормальное программирование
)
, #_razrabotka_igr (
Разработка игр
)
, #_algoritmy (
Алгоритмы
)
Профиль  ЛС 
Показать сообщения:     

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 22-Ноя 15:39
Часовой пояс: UTC + 5