Характеристики в Space Jaguar Action RPG

demensdeum Blog, Dev Diary

Первая статья про игру в разработке Space Jaguar Action RPG. В данной статье я опишу гемплейную особенность Ягуара – Характеристики.

Многие РПГ используют статичную систему характеристик персонажа, например характеристики из DnD (Сила, Телосложение, Ловкость, Интеллект, Мудрость, Обаяние), или Fallout – S.P.E.C.I.A.L (Сила, Восприятие, Выносливость, Харизма, Интеллект, Ловкость, Удача).

В Space Jaguar я планирую реализовать динамическую систему характеристик, например главный герой игры Джаг на старте имеет всего три характеристики – Владение блейдом (полусабля), теневые операции (заключение сделок в криминальном мире), плутовские способности (взлом замков, воровство). Во время игры персонажи будут наделяться и лишаться динамических характеристик в рамках игрового модуля, все проверки будут производится на основе уровня определенных характеристик необходимых для данной игровой ситуации. Например Джаг не сможет выиграть партию в шахматы, если не обладает характеристикой игры в шахматы, или не обладает достаточным уровнем для прохождения проверки.

Для упрощения логики проверок, каждой характеристике задается 6 значный код английскими буквами, имя, описание. Например для владения блейдом: 

var bladeFightingAbility = new Object(); 
bladeFightingAbility.name = "BLADFG"; 
bladeFightingAbility.description = "Blade fighting ability"; 
bladeFightingAbility.points = 3;

Перед стартом игрового модуля можно будет просмотреть список публичных проверок необходимых для прохождения, также создатель может скрыть часть проверок для создания интересных игровых ситуаций.

Ноу-хоу? Будет ли интересно? Лично я нахожу такую систему интересной, позволяющей одновременно обеспечить свободу творчества создателям игровых модулей, и возможность переноса персонажей из разных, но похожих по характеристикам, модулей для игроков.

0

Хеш таблица

demensdeum Техдок, Туториалы

Хеш таблица позволяет реализовать структуру данных ассоциативный массив (словарь), со средней производительностью O(1) для операций вставки, удаления, поиска.

Ниже пример простейшей реализации хэш мапы на nodeJS:

Как это работает? Следим за руками:

  • Внутри хеш мапы находится массив
  • Внутри элемента массива находится указатель на первую ноду связанного списка
  • Размечается память для массива указателей (например 65535 элементов)
  • Реализуют хеш функцию, на вход идет ключ словаря, а на выходе она может делать что угодно, но в итоге возвращает индекс элемента массива

Как работает запись:

  • На вход идет пара ключ – значение
  • Хэш функция возвращает индекс по ключу
  • Получаем ноду связанного списка из массива по индексу
  • Проверяем соответствует ли он ключу
  • Если соответствует, то заменяем значение
  • Если не соответствует, то переходим к следующей ноде, пока найдем либо, не найдем ноду с нужным ключом.
  • Если ноду так и не нашли, то создаем ее в конце связанного списка

Как работает поиск по ключу:

  • На вход идет пара ключ – значение
  • Хэш функция возвращает индекс по ключу
  • Получаем ноду связанного списка из массива по индексу
  • Проверяем соответствует ли он ключу
  • Если соответствует, то возвращаем значение
  • Если не соответствует, то переходим к следующей ноде, пока найдем либо, не найдем ноду с нужным ключом.

Зачем нужен связанный список внутри массива? Из-за возможных коллизий при вычислении хеш функции. В таком случае несколько разных пар ключ-значение будут находиться по одинаковому индексу в массиве, в таком случае осуществляется проход по связанному списку с поиском необходимого ключа.

Источники

https://ru.wikipedia.org/wiki/Хеш-таблица
https://www.youtube.com/watch?v=wg8hZxMRwcw

Исходный код

https://gitlab.com/demensdeum/datastructures

0

Работа с ресурсами в Android C++

demensdeum Техдок, Туториалы

Для работы с ресурсами в Android через ndk – C++ существует несколько вариантов:

  1. Использовать доступ к ресурсам из apk файла, с помощью AssetManager
  2. Загружать ресурсы из интернета и распаковав их в директорию приложения, использовать с помощью стандартных методов C++
  3. Комбинированный способ – получить доступ к архиву с ресурсами в apk через AssetManager, распаковать их в директорию приложения, далее использовать с помощью стандартных методов C++

Далее я опишу комбинированный способ доступа, использующийся в игровом движке Flame Steel Engine.
При использовании SDL можно упростить доступ к ресурсам из apk, библиотека оборачивает вызовы к AssetManager, предлагая схожие с stdio интерфейсы (fopen, fread, fclose и т.д.)


SDL_RWops *io = SDL_RWFromFile("files.fschest", "r");

После загрузки архива из apk в буфер, нужно сменить текущую рабочую директорию на директорию приложения, она доступна для приложения без получения дополнительных разрешений. Для этого воспользуемся оберткой на SDL:

 
chdir(SDL_AndroidGetInternalStoragePath());

Далее записываем архив из буфера в текущую рабочую директорию с помощью fopen, fwrite, fclose. После того как архив окажется в доступной для C++ директории, распакуем его. Архивы zip можно распаковывать с помощью комбинации двух библиотек – minizip и zlib, первая умеет работать со структурой архивов, вторая же распаковывает данные.
Для получения более полного контроля, простоты портирования, я реализовал собственный формат архивов с нулевым сжатием под названием FSChest (Flame Steel Chest). Данный формат поддерживает архивацию директории с файлами, и распаковку; Поддержка иерархии папок отсутствует, возможна работа только с файлами.
Подключаем header библиотеки FSChest, распаковываем архив:

 
#include "fschest.h" 
FSCHEST_extractChestToDirectory(archivePath, SDL_AndroidGetInternalStoragePath());

После распаковки интерфейсам C/C++ будут доступны файлы из архива. Таким образом мне не пришлось переписывать всю работу с файлами в движке, а лишь добавить распаковку файлов на этапе запуска.

Источники

https://developer.android.com/ndk/reference/group/asset

Исходный Код

https://gitlab.com/demensdeum/space-jaguar-action-rpg
https://gitlab.com/demensdeum/fschest

0

Стек машина и RPN

demensdeum Техдок, Туториалы

Допустим нам необходимо реализовать простой интерпретатор байткода, какой подход к реализации этой задачи выбрать?

Структура данных Стек предоставляет возможность реализовать простейшую байткод-машину. Особенности и реализации стек машин описаны во множестве статей западного и отечественного интернета, упомяну только что виртуальная машина Java является примером стековой машины.

Принцип работы машины прост, на вход подается программа содержащая данные и коды операций (опкоды), с помощью манипуляций со стеком выполняется реализация необходимых операций. Рассмотрим пример программы байткода моей стековой машины:

 
пMVkcatS olleHП

На выходе мы получим строку “Hello StackVM”. Стэк машина прочитывает программу слева-направо, загружая посимвольно данные в стек, при появлении опкода в символе – выполняет реализацию команды с использованием стека.

Пример реализации стековой машины на nodejs:

Обратная польская запись (RPN)

Также стековые машины легко использовать для реализации калькуляторов, для этого используют Обратную польскую запись (постфиксную запись).
Пример обычной инфиксной записи:
2*2+3*4

Конвертируется в RPN:
22*34*+

Для подсчета постфиксной записи используем стек машину:
2 – на вершину стека (стек: 2)
2 – на вершину стека (стек: 2,2)
* – получаем вершину стека два раза, перемножаем результат, отправляем на вершину стека (стек: 4)
3 – на вершину стека (стек: 4, 3)
4 – на вершину стека (стек: 4, 3, 4)
* – получаем вершину стека два раза, перемножаем результат, отправляем на вершину стека (стек: 4, 12)
+ – получаем вершину стека два раза, складываем результат, отправляем на вершину стека (стек: 16)

Как можно заметить – результат операций 16 остается в стеке, его можно вывести реализовав опкоды печати стека, например:
п22*34*+П

П – опкод начала печати стека, п – опкод окончания печати стека и отправки итоговой строки на рендеринг.
Для конвертации арифметических операций из инфиксной в постфикснуют используют алгоритм Эдсгера Дейкстры под названием “Сортировочная станция”. Пример реализации можно посмотреть выше, либо в репозитории проекта стек машины на nodejs ниже.

Источники

https://tech.badoo.com/ru/article/579/interpretatory-bajt-kodov-svoimi-rukami/
https://ru.wikipedia.org/wiki/Обратная_польская_запись

Исходный код

https://gitlab.com/demensdeum/stackvm/

0

Скелетная анимация (Часть 2 – иерархия нод, интерполяция)

demensdeum Blog, Техдок, Туториалы

Продолжаю описывать алгоритм скелетной анимации, по мере его реализации в игровом движке Flame Steel Engine.

Так как алгоритм является наисложнейшим из всех что я реализовывал, в заметках о процессе разработки могут появляться ошибки. В прошлой статье о данном алгоритме я допустил ошибку, массив костей передается в шейдер для каждого мэша по отдельности, а не для всей модели.

Иерархия нод

Для корректной работы алгоритма необходимо чтобы модель содержала в себе связь костей друг с другом (граф). Представим себе ситуацию при которой проигрываются одновременно две анимации – прыжок и поднятие правой руки. Анимация прыжка должна поднимать модель по оси Y, при этом анимация поднятия руки должна учитывать это и подниматься вместе с моделью в прыжке, иначе рука останется сама по себе на месте.

Опишем связь нод для данного случая – тело содержит руку. При отработке алгоритма будет произведено чтение графа костей, все анимации будут учтены с корректными связями. В памяти модели граф хранится отдельно от всех анимаций, только для отражения связанности костей модели.

Интерполяция на CPU

В прошлой статья я описал принцип рендеринга скелетной анимации – “матрицы трансформации передаются из CPU в шейдер при каждом кадре рендеринга.”

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

Для интерполяции позиции и увеличения используют вектора, для поворота используются кватернионы, т.к. они очень легко интерполируются (SLERP) в отличии от углов Эйлера, также их очень просто представить в виде матрицы трансформации.

Как упростить реализацию

Чтобы упростить отладку работы вертексного шейдера, я добавил симуляцию работы вертексного шейдера на CPU с помощью макроса FSGLOGLNEWAGERENDERER_CPU_BASED_VERTEX_MODS_ENABLED. У производителя видеокарт NVIDIA есть утилита для отладки шейдерного кода Nsight, возможно она тоже может упростить разработку сложных алгоритмов вертексного/пиксельных шейдеров, однако проверить работоспособность мне так и не довелось, хватило симуляции на CPU.

В следующей статье я планирую описать микширование нескольких анимаций, заполнить оставшиеся пробелы.

Источники

https://www.youtube.com/watch?v=f3Cr8Yx3GGA

0