Портируем C++ SDL приложение на Android

В данной заметке я опишу свой опыт портирования прототипа 3D редактора Cube Art Project на Android.
Сначала посмотрим на результат, в эмуляторе запущен редактор с 3D курсором куба красного цвета:

Для успешной сборки нужно было сделать следующее:

  1. Установить последний Android SDK и NDK (версию ндк чем свежее тем лучше).
  2. Загрузить исходный код SDL2, взять оттуда шаблон для сборки андроид приложения.
  3. Добавить SDL Image, SDL Mixer к сборке.
  4. Добавить библиотеки моего игрового движка и тулкита, их зависимости (GLM, JSON for Modern C++)
  5. Адаптировать файлы сборок для Gradle.
  6. Адаптировать C++ код для совместимости с Android, изменения коснулись платформозависимых компонентов (OpenGL ES, инициализация графического контекста)
  7. Собрать и проверить проект на эмуляторе.

Шаблон проекта

Загружаем исходники SDL, SDL Image, SDL Mixer:
https://www.libsdl.org/download-2.0.php
В папке docs есть подробная инструкция по работе с шаблоном андроид проекта; скопируем директорию android-project в отдельную папку, сделаем симлинк или скопируем папку SDL в android-project/app/jni.
Подставляем правильный идентификатор для флага avd, запускаем эмулятор андроида из директории Sdk:


cd ~/Android/Sdk/emulator
./emulator -avd Pixel_2_API_24

Указываем пути в скрипте, собираем проект:


rm -rf app/build || true
export ANDROID_HOME=/home/demensdeum/Android/Sdk/
export ANDROID_NDK_HOME=/home/demensdeum/Android/android-ndk-r21-beta2/
./gradlew clean build
./gradlew installDebug

Должен собраться шаблон проекта SDL с кодом на Си из файла


android-sdl-test-app/cube-art-project-android/app/jni/src/YourSourceHere.c

Зависимости

Загружаем исходный код в архивах для SDL_image, SDL_mixer:
https://www.libsdl.org/projects/SDL_image/
https://www.libsdl.org/projects/SDL_mixer/

Загружаем зависимости вашего проекта, для примера мои shared библиотеки:
https://gitlab.com/demensdeum/FlameSteelCore/
https://gitlab.com/demensdeum/FlameSteelCommonTraits
https://gitlab.com/demensdeum/FlameSteelBattleHorn
https://gitlab.com/demensdeum/FlameSteelEngineGameToolkit/
https://gitlab.com/demensdeum/FlameSteelEngineGameToolkitFSGL
https://gitlab.com/demensdeum/FSGL
https://gitlab.com/demensdeum/cube-art-project

Все это выгружаем в app/jni, каждый “модуль” в отдельную папку, например app/jni/FSGL. Далее у вас есть вариант найти рабочие генераторы для файлов Application.mk и Android.mk, я не нашел, однако возможно есть простое решение на основе CMake. Переходим по ссылкам и начинаем знакомиться с форматом файлов сборки для Android NDK:
https://developer.android.com/ndk/guides/application_mk
https://developer.android.com/ndk/guides/android_mk

Также следует прочитать про разные APP_STL реализации в NDK:
https://developer.android.com/ndk/guides/cpp-support.html

После ознакомления создаем для каждого “модуля” файл Android.mk, далее пример файл сборки shared библиотеки Cube-Art-Project:


LOCAL_PATH := $(call my-dir)
include $(CLEAR_VARS)

APP_STL := c++_static
APP_CPPFLAGS := -fexceptions
LOCAL_MODULE := CubeArtProject
LOCAL_C_INCLUDES := $(LOCAL_PATH)/src $(LOCAL_PATH)/../include $(LOCAL_PATH)/../include/FlameSteelCommonTraits/src/FlameSteelCommonTraits
LOCAL_EXPORT_C_INCLUDES = $(LOCAL_PATH)/src/

define walk
$(wildcard $(1)) $(foreach e, $(wildcard $(1)/*), $(call walk, $(e)))
endef

ALLFILES = $(call walk, $(LOCAL_PATH)/src)
FILE_LIST := $(filter %.cpp, $(ALLFILES))
$(info CubeArtProject source code files list)
$(info $(FILE_LIST))
LOCAL_SRC_FILES := $(FILE_LIST:$(LOCAL_PATH)/%=%)

LOCAL_SHARED_LIBRARIES += FlameSteelCore
LOCAL_SHARED_LIBRARIES += FlameSteelBattleHorn
LOCAL_SHARED_LIBRARIES += FlameSteelCommonTraits
LOCAL_SHARED_LIBRARIES += FlameSteelEngineGameToolkit
LOCAL_SHARED_LIBRARIES += FlameSteelEngineGameToolkitFSGL
LOCAL_SHARED_LIBRARIES += FSGL
LOCAL_SHARED_LIBRARIES += SDL2
LOCAL_SHARED_LIBRARIES += SDL2_image

LOCAL_LDFLAGS := -static-libstdc++
include $(BUILD_SHARED_LIBRARY)

Любой опытный CMake пользователь поймет этот конфиг с первых строк, форматы очень похожи, в Android.mk отсутствует GLOB_RECURSIVE, поэтому приходится рекурсивно искать исходные файлы с помощью функции walk.

Меняем Application.mk, Android.mk со-но для сборки C++ а не Си кода:


APP_ABI := armeabi-v7a arm64-v8a x86 x86_64
APP_PLATFORM=android-16
APP_STL := c++_static
APP_CPPFLAGS := -fexceptions

Переименовываем YourSourceHere.c -> YourSourceHere.cpp, grep’аем по вхождениям, меняем путь в сборке, например:


app/jni/src/Android.mk:LOCAL_SRC_FILES := YourSourceHere.cpp

Далее попробуйте собрать проект, если вы увидете ошибки от компилятора об отсутствии хидеров, то проверьте корректность путей в Android.mk; если ошибки будут от линковщика вида “undefined reference”, то проверьте корректность указания файлов исходного кода в сборках, оттрейсить списки можно через указание $(info $(FILE_LIST)) в Android.mk файле. Не забудьте о двойном механизме линковки, с помощью модулей в ключе LOCAL_SHARED_LIBRARIES и корректной линковке через LD, например для FSGL:


LOCAL_LDLIBS := -lEGL -lGLESv2

Адаптация и запуск

Пришлось поменять некоторые вещи, например убрать GLEW из сборок для iOS и Android, переименовать часть вызовов OpenGL, добавив постфикс EOS (glGenVertexArrays -> glGenVertexArraysOES), включать макрос отсутствующих модерновых функций дебага, вишенка на торте это неявный инклуд GLES2 хидеров с указанием макроса GL_GLEXT_PROTOTYPES 1:


#define GL_GLEXT_PROTOTYPES 1
#include "SDL_opengles2.h"

Также наблюдал черный экран на первых запусках с ошибкой вида “E/libEGL: validate_display:255 error 3008 (EGL_BAD_DISPLAY)”, поменял инициализацию окна SDL, профайла OpenGL и все заработало:


SDL_DisplayMode mode;
SDL_GetDisplayMode(0,0,&mode);
int width = mode.w;
int height = mode.h;

window = SDL_CreateWindow(
            title,
            0,
            0,
            width,
            height,
            SDL_WINDOW_OPENGL | SDL_WINDOW_FULLSCREEN | SDL_WINDOW_RESIZABLE
        );

SDL_GL_SetAttribute( SDL_GL_CONTEXT_PROFILE_MASK, SDL_GL_CONTEXT_PROFILE_ES );

На эмуляторе приложение по умолчанию устанавливается с иконкой SDL и именем “Game”.

Мне осталось исследовать возможность автоматической генерации файлов сборки на основе CMake, либо же мигрировать сборки для всех платформ на Gradle; однако CMake остается выбором дефакто для текущей разработки на C++.

Исходный код

https://gitlab.com/demensdeum/android-sdl-test-app
https://gitlab.com/demensdeum/android-sdl-test-app/tree/master/cube-art-project-android

Источники

https://developer.android.com/ndk/guides/cpp-support.html
https://developer.android.com/ndk/guides/application_mk
https://developer.android.com/ndk/guides/android_mk
https://lazyfoo.net/tutorials/SDL/52_hello_mobile/android_windows/index.php
https://medium.com/androiddevelopers/getting-started-with-c-and-android-native-activities-2213b402ffff

0

Перевернутый мир

Для разработки нового проекта Cube Art Project взял на вооружение методологию разработки Test Driven Development. В данном подходе сначала реализуется тест для определенного функционала приложения, а затем уже реализуется конкретный функционал. Большим плюсом в данном подходе я считаю реализацию финальных интерфейсов, максимально непосвященных в детали реализации, до начала разработки функционала. При таком подходе тест диктует дальнейшую реализацию, добавляются все преимущества контрактного программирования, когда интерфейсы являются контрактами для конкретной реализации.
Cube Art Project – 3D редактор в котором пользователь строит фигуры из кубов, не так давно этот жанр был очень популярен. Так как это графическое приложение, то я решил добавить тесты с валидацией скриншотов.
Для валидирования скриншотов нужно получить их из OpenGL контекста, делается это с помощью функции glReadPixels. Описание аргументов функции простейшие – начальная позиция, ширина, высота, формат (RGB/RGBA/проч.), указатель на выходной буфер, любому работавшему с SDL или имеющему опыт с буферами данных в Си будет просто подставить нужные аргументы. Однако считаю необходимым описать интересную особенность выходного буфера glReadPixels, пиксели в нем хранятся снизу вверх, а в SDL_Surface все базовые операции происходят сверху вниз.
То есть загрузив референсный скриншот из png файла, я не смог сравнить два буфера в лоб, так как один из них был перевернутым.
Чтобы перевернуть выходной буфер из OpenGL вам нужно заполнить его отнимая высоту скриншота для координаты Y. Однако стоить учесть что есть шансы выйти за пределы буфера, если не отнять единицу во время заполнения, что приведет к memory corruption.
Так как я повсеместно стараюсь использовать ООП парадигму “программирования интерфейсами”, вместо прямого Си-подобного доступа к памяти по указателю, то при попытке записать данные за пределами буфера объект мне об этом сообщил благодаря валидации границ в методе.
Итоговый код метода получения скриншота в стиле сверху-вниз:


    auto width = params->width;
    auto height = params->height;

    auto colorComponentsCount = 3;
    GLubyte *bytes = (GLubyte *)malloc(colorComponentsCount * width * height);
    glReadPixels(0, 0, width, height, GL_RGB, GL_UNSIGNED_BYTE, bytes);

    auto screenshot = make_shared(width, height);

    for (auto y = 0; y < height; y++) {
        for (auto x = 0; x < width; x++) {
            auto byteX = x * colorComponentsCount;
            auto byteIndex = byteX + (y * (width * colorComponentsCount));
            auto redColorByte = bytes[byteIndex];
            auto greenColorByte = bytes[byteIndex + 1];
            auto blueColorByte = bytes[byteIndex + 2];
            auto color = make_shared(redColorByte, greenColorByte, blueColorByte, 255);
            screenshot->setColorAtXY(color, x, height - y - 1);
        }
    }

    free(bytes);

Источники

https://community.khronos.org/t/glreadpixels-fliped-image/26561
https://stackoverflow.com/questions/8346115/why-are-bmps-stored-upside-down

Исходный код

https://gitlab.com/demensdeum/cube-art-project-bootstrap

0

Longest Common Substring

В данной заметке я опишу алгоритм решения задачи наибольшей общей подстроки. Допустим мы пытаемся расшифровать зашифрованные бинарные данные, для начала попробуем найти общие паттерны с помощью поиска наибольшей подстроки.
Входная строка для примера:
adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdf
Мы ищем повторяющуюся дважды строку:
DATAHEADER??

Префиксы

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


        val lhs = "asdfWUKI"
        val rhs = "asdfIKUW"

Результирующая строка – asdf
Пример на Kotlin:


fun longestPrefix(lhs: String, rhs: String): String {
        val maximalLength = min(lhs.length-1, rhs.length -1)
        for (i in 0..maximalLength) {
            val xChar = lhs.take(i)
            val yChar = rhs.take(i)
                if (xChar != yChar) {
                    return lhs.substring(0, i-1)
                }
        }
        return lhs.substring(0,maximalLength)
}

Brute Force

Когда не получается по хорошему, стоит прибегнуть к грубой силе. Используя метод longestPrefix пройдем по строке двумя циклами, первый берет строку от i до конца, второй от i + 1 до конца, передает их в поиск наибольшего префикса. Временная сложность данного алгоритма примерно равна O(n^2) ~ O(n*^3).
Пример на Kotlin:


fun searchLongestRepeatedSubstring(searchString: String): String {
        var longestRepeatedSubstring = ""
        for (x in 0..searchString.length-1) {
            val lhs = searchString.substring(x)
            for (y in x+1..searchString.length-1) {
                val rhs = searchString.substring(y)
                val longestPrefix = longestPrefix(lhs, rhs)
                if (longestRepeatedSubstring.length < longestPrefix.length) {
                    longestRepeatedSubstring = longestPrefix
                }
            }
        }
        return longestRepeatedSubstring
}

Суффиксный массив

Для более элегантного решения нам потребуется инструмент - структура данных под названием “Суффиксный массив”. Данная структура данных представляет из себя массив из подстрок заполняемых в цикле, где каждая подстрока начинается со следующего символа строки до конца.
Например для строки:


adasDATAHEADER??

Суффиксный массив выглядит так:


adasDATAHEADER??
dasDATAHEADER??
asDATAHEADER??
sDATAHEADER??
DATAHEADER??
ATAHEADER??
TAHEADER??
AHEADER??
HEADER??
EADER??
ADER??
DER??
ER??
R??
??
?

Решаем сортировкой

Отсортируем суффиксный массив, затем пройдем по всем элементам циклом где в левой руке (lhs) текущий элемент, в правой (rhs) следующий и вычислим самый длинный префикс с помощью метода longestPrefix.
Пример на Kotlin:


fun searchLongestRepeatedSubstring(searchString: String): String {
    val suffixTree = suffixArray(searchString)
    val sortedSuffixTree = suffixTree.sorted()

    var longestRepeatedSubstring = ""
    for (i in 0..sortedSuffixTree.count() - 2) {
        val lhs = sortedSuffixTree[i]
        val rhs = sortedSuffixTree[i+1]
        val longestPrefix = longestPrefix(lhs, rhs)
        if (longestRepeatedSubstring.length < longestPrefix.length) {
            longestRepeatedSubstring = longestPrefix
        }
    }
    return longestRepeatedSubstring
}

Временная сложность алгоритма O(N log N), что гораздо лучше решения в лоб.

Источники

https://en.wikipedia.org/wiki/Longest_common_substring_problem

Исходный код

https://gitlab.com/demensdeum/algorithms

0

Insertion Sort, Merge Sort

Insertion Sort

Сортировка вставками – каждый элемент сравнивается с предыдущими по списку и элемент вставляется на место большего. Так как элементы сортируются с первого по последний, то каждый следующий элемент сравнивается с уже отсортированным списком, что *возможно* уменьшит общее время работы. Временная сложность алгоритма O(n^2), то есть идентична баббл сорту.

Merge Sort

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


["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["Alice", "John"], ["#1", "Mike"], ["20", "Артем"], ["60", "60"], ["DoubleTrouble"]]
[["#1", "Alice", "John", "Mike"], ["20", "60", "60", "Артем"], ["DoubleTrouble"]]
[["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"], ["DoubleTrouble"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

Вывод алгоритма для многопоточного выполнения:


["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["20", "Артем"], ["Alice", "John"], ["60", "60"], ["#1", "Mike"], ["DoubleTrouble"]]
[["#1", "60", "60", "Mike"], ["20", "Alice", "John", "Артем"], ["DoubleTrouble"]]
[["DoubleTrouble"], ["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

Временная сложность алгоритма O(n*log(n)), что немного лучше чем O(n^2)

Источники

https://en.wikipedia.org/wiki/Insertion_sort
https://en.wikipedia.org/wiki/Merge_sort

Исходный код

https://gitlab.com/demensdeum/algorithms

0

Сортировка пузырьком на Erlang

Сортировка пузырьком это достаточно скучно, но становится интереснее если попробовать реализовать его на функциональном языке для телекома – Erlang.

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

На практике его использовать не стоит из-за большой временной сложности алгоритма – O(n^2); я реализовал его на языке Erlang, в императивном стиле, но если вам интересно то можете поискать лучшие варианты:


-module(bubbleSort).
-export([main/1]).

startBubbleSort([CurrentHead|Tail]) ->
    compareHeads(CurrentHead, Tail, [], [CurrentHead|Tail]).

compareHeads(CurrentHead, [NextHead|Tail], [], OriginalList) ->   
    if
        CurrentHead < NextHead ->
            compareHeads(NextHead, Tail, [CurrentHead], OriginalList);
        true ->
            compareHeads(CurrentHead, Tail, [NextHead], OriginalList)
    end;
    
compareHeads(CurrentHead, [NextHead|Tail], OriginalOutputList, OriginalList) ->
    if
        CurrentHead < NextHead ->
            OutputList = OriginalOutputList ++ [CurrentHead],
            compareHeads(NextHead, Tail, OutputList, OriginalList);
        true ->
            OutputList = OriginalOutputList ++ [NextHead],
            compareHeads(CurrentHead, Tail, OutputList, OriginalList)
    end;
  
compareHeads(CurrentHead, [], OriginalOutputList, OriginalList) ->
    OutputList = OriginalOutputList ++ [CurrentHead],
    if
        OriginalList == OutputList ->
            io:format("OutputList: ~w~n", [OutputList]);
        true ->
            startBubbleSort(OutputList)
    end.
  
main(_) ->
    UnsortedList = [69,7,4,44,2,9,10,6,26,1],
    startBubbleSort(UnsortedList).

Установка и запуск

В Ubuntu Эрланг установить очень просто, достаточно в терминале набрать команду sudo apt install erlang. В данном языке каждый файл должен представлять из себя модуль (module), со списком функций которые можно использовать извне – export. К интересным особенностям языка относится отсутствие переменных, только константы, отсутствие стандартного синтаксиса для ООП (что не мешает использовать ООП техники), и конечно же параллельные вычисления без блокировок на основе модели акторов.

Запустить модуль можно либо через интерактивную консоль erl, запуская одну команду за другой, либо проще через escript bubbleSort.erl; Для разных случаев файл будет выглядеть по разному, например для escript необходимо сделать функцию main, из которой он будет стартовать.

Источники

https://www.erlang.org/
https://habr.com/ru/post/197364/

Исходный код

https://gitlab.com/demensdeum/algorithms/blob/master/bubbleSort/bubbleSort.erl

0

Алгоритм лексикографического сравнения

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

Пример для языка Си можно посмотреть здесь:
https://github.com/gcc-mirror/gcc/blob/master/libiberty/memcmp.c

Следует учитывать что сравнивать символы нужно в единой статичной кодировке, например в Swift я использовал посимвольное сравнение на UTF-32. Вариант сортировки массива с использованием memcmp сработает точно для однобайтовых символов, в остальных случаях (кодировки переменной длины) возможно порядок будет некорректен. Не исключаю возможности реализации на основе кодировок переменной длины, но скорее всего будет на порядок сложнее.

Временная сложность алгоритма в лучшем случае O(1), среднем и худшем O(n)

Источники

https://ru.wikipedia.org/wiki/Лексикографический_порядок

Исходники

https://gitlab.com/demensdeum/algorithms/blob/master/lexiCompare/lexiCompare.swift

0

Разработка игры для ZX Spectrum на C

Эта непутевая заметка посвящена разработке игры для старого компьютера ZX Spectrum на C. Давайте взглянем на красавца:

Он начал производится в 1982 году, и выпускался до 1992 года. Технические характеристики машины: 8-битный процессор Z80, 16-128кб памяти и прочие экстеншены, например звуковой чип AY-3-8910.

В рамках конкурса Yandex Retro Games Battle 2019 для данной машины я написал игру под названием Interceptor 2020. Так как учить ассемблер для Z80 времени не было, я решил разработать ее на языке Си. В качестве тулчейна я выбрал готовый набор – z88dk, который содержит компиляторы Си, и много вспомогательных библиотек для ускорения реализации приложений для Спектрума. Он также поддерживает множество других Z80 машин, например MSX, калькуляторов Texas Instruments.

Далее я опишу свой поверхностный полет над архитектурой компьютера, тулчейном z88dk, покажу как удалось реализовать ООП подход, использовать паттерны проектирования.

Особенности установки

Установку z88dk следует проводить по мануалу из репозитория, однако для пользователей Ubuntu я хотел бы отметить особенность – если у вас уже установлены компиляторы для Z80 из deb пакетов, то следует их удалить, так как z88dk по умолчанию будет обращаться к ним из папки bin, из-за несовместимости версий тулчейн-компилятор вы скорее всего ничего не сможете собрать.

Hello World

Написать Hello World очень просто:


#include 

void main()
{
    printf("Hello World");
}

Собрать в tap файл еще проще:


zcc +zx -lndos -create-app -o helloworld helloworld.c

Для запуска используйте любой эмулятор ZX Spectrum с поддержкой tap файлов, например онлайн:
http://jsspeccy.zxdemo.org/

Рисуем на картинку на весь экран

tl;dr Картинки рисуются тайлами, тайлами размера 8×8 пикселей, сами тайлы встраиваются в шрифт спектрума, затем строкой из индексов печатается картинка.

Библиотека вывода спрайтов и тайлов sp1 выводит тайлы с помощью UDG. Картинка переводится в набор отдельных UDG (тайлы), затем собирается на экране с помощью индексов. Следует помнить что UDG используется для вывода текста, и если ваша картинка содержит очень большой набор тайлов (например больше 128 тайлов), то придется выходить за границы набора и стирать дефолтный спектрумовский шрифт. Чтобы обойти это ограничение, я использовал базу от 128 – 255 с помощью упрощения изображений, оставляя оригинальный шрифт на месте. Об упрощении картинок ниже.

Для отрисовки полноэкранных картинок нужно вооружиться тремя утилитами:
Gimp
img2spec
png2c-z88dk

Есть путь настоящих ZX мужчин, настоящих ретро-воинов это открыть графический редактор, используя палитру спектрума, зная особенности вывода картинки, подготовить ее вручную и выгрузить с помощью png2c-z88dk или png2scr.

Путь попроще – взять 32 битное изображение, переключить в Gimp количество цветов до 3-4-х, слегка подредактировать, затем импортировать в img2spec для того чтобы не работать с цветовыми ограничениями вручную, экспортировать png и перевести в Си массив с помощью png2c-z88dk.

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

В результате вы получите h файл, который содержит количество уникальных тайлов, если их больше ~128, то упрощайте в Gimp картинку (увеличьте повторяемость) и проводите процедуру экспорта по новой.

После экспорта вы в прямом смысле загружаете “шрифт” из тайлов и печатаете “текст” из индексов тайлов на экране. Далее пример из “класса” рендера:


// грузим шрифт в память
    unsigned char *pt = fullscreenImage->tiles;

    for (i = 0; i < fullscreenImage->tilesLength; i++, pt += 8) {
            sp1_TileEntry(fullscreenImage->tilesBase + i, pt);
    }

    // ставим курсор в 0,0
    sp1_SetPrintPos(&ps0, 0, 0);

    // печатаем строку
    sp1_PrintString(&ps0, fullscreenImage->ptiles);

Рисуем спрайты на экране

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

Рисуем в Gimp монохромную png картинку 16×16, далее с помощью png2sp1sprite переводим ее в ассемблерный файл asm, в Си коде объявляем массивы из ассемблерного файла, добавляем файл на этапе сборки.

После этапа объявления ресурса спрайта, его надо добавить на экран в нужную позицию, далее пример кода “класса” игрового объекта:


    struct sp1_ss *bubble_sprite = sp1_CreateSpr(SP1_DRAW_MASK2LB, SP1_TYPE_2BYTE, 3, 0, 0);
    sp1_AddColSpr(bubble_sprite, SP1_DRAW_MASK2,    SP1_TYPE_2BYTE, col2-col1, 0);
    sp1_AddColSpr(bubble_sprite, SP1_DRAW_MASK2RB,  SP1_TYPE_2BYTE, 0, 0);
    sp1_IterateSprChar(bubble_sprite, initialiseColour);

По названиям функций можно примерно понять смысл – аллоцируем память для спрайта, добавляем две колонки 8×8, добавляем цвет для спрайта.

В каждом кадре проставляется позиция спрайта:


sp1_MoveSprPix(gameObject->gameObjectSprite, Renderer_fullScreenRect, gameObject->sprite_col, gameObject->x, gameObject->y);

Эмулируем ООП

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

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

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

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

За основу хранения данных экземпляра класса удобнее взять структуры Си. Конечно можно использовать байтовый буфер, создать свою собственную структуру для классов, методов, но зачем переизобретать колесо? Ведь мы и так переизобретаем синтаксис.

Данные класса

Пример полей данных “класса” GameObject:


struct GameObjectStruct {
    struct sp1_ss *gameObjectSprite;
    unsigned char *sprite_col;
    unsigned char x;
    unsigned char y;
    unsigned char referenceCount;
    unsigned char beforeHideX;
    unsigned char beforeHideY;
};
typedef struct GameObjectStruct GameObject;

Сохраняем наш класс как “GameObject.h” делаем #include “GameObject.h” в нужном месте и пользуемся.

Методы класса

Возьмем на вооружение опыт разработчиков языка Objective-C, сигнатура метода класса будут представлять из себя функции в глобальном скопе, первым аргументом всегда будет передаваться структура данных, далее идут аргументы метода. Далее пример “метода” “класса” GameObject:


void GameObject_hide(GameObject *gameObject) {
    gameObject->beforeHideX = gameObject->x;
    gameObject->beforeHideY = gameObject->y;
    gameObject->y = 200;
}

Вызов метода выглядит так:


GameObject_hide(gameObject);

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

Работа с памятью

Ручное управление памятью вида с помощью malloc и free обернутых в макросы new и delete для соответствия с C++:


#define new(X) (X*)malloc(sizeof(X))
#define delete(X) free(X)

Для объектов которые используются несколькими классами сразу, реализовано полу-ручное управление памятью на основе подсчета ссылок, по образу и подобию старого механизма Objective-C Runtime ARC:


void GameObject_retain(GameObject *gameObject) {
    gameObject->referenceCount++;
}

void GameObject_release(GameObject *gameObject) {
    gameObject->referenceCount--;

    if (gameObject->referenceCount < 1) { sp1_MoveSprAbs(gameObject->gameObjectSprite, &Renderer_fullScreenRect, NULL, 0, 34, 0, 0);
        sp1_DeleteSpr(gameObject->gameObjectSprite);
        delete(gameObject);
    }
}

Таким образом каждый класс должен объявлять использование общего объекта с помощью retain, освобождать владение через release. В современном варианте ARC используется автоматическое проставление вызовов retain/release.

Звучим!

На Спектруме есть пищалка способная воспроизводить 1-битовую музыку, композиторы того времени умели воспроизводить на ней до 4-х звуковых каналов одновременно.

Spectrum 128k содержит отдельный звуковой чип AY-3-8910, на котором можно воспроизводить трекерную музыку.

Для использования пищалки в z88dk предлагается библиотека

Что предстоит узнать

Мне было интересно ознакомиться со Спектрумом, реализовать игру средствами z88dk, узнать много интересных вещей. Многое мне еще предстоит изучить, например ассемблер Z80, так как он позволяет использовать всю мощь Спектрума, работу с банками памяти, работу со звуковым чипом AY-3-8910. Надеюсь поучаствовать в конкурсе на следующий год!

Ссылки

https://rgb.yandex
https://vk.com/sinc_lair
https://www.z88dk.org/forum/

Исходный код

https://gitlab.com/demensdeum/zx-projects/tree/master/interceptor2020

0

Двоичный поиск

Допустим нам необходимо узнать относится ли адрес электронной почты “demensdeum@gmail.com”  к списку разрешенных email адресов для получения писем.

Переберем весь список от первого до последнего элемента, проверяя равен ли элемент указанному адресу – реализуем алгоритм линейного поиска. Но это же будет долго, или не будет?

Для ответа на этот вопрос используют “Временную сложность алгоритмов”, “О” нотацию. Время работы линейного поиска в худшем случае равно n-му количеству элементов массива, напишем это в “О” нотации – O(n). Далее нужно пояснить что для любого известного алгоритма есть три показателя производительности – время выполнения в лучшем, худшем и среднем случае. Например адрес почты “demensdeum@gmail.com” находится в первом индексе массива, тогда он будет найден за первый шаг алгоритма, из этого следует что время выполнения в лучшем случае – O(1); а если в конце списка, то это худший случай – O(n)

Но как же детали реализации ПО, производительность железа, они ведь должны влиять на big O? А теперь выдохните и представьте что расчет временной сложности рассчитывается для некой абстрактной идеальной машины, в которой есть только этот алгоритм и больше ничего.

Алгоритм

Ок, получается что линейный поиск достаточно медленный, попробуем использовать Бинарный поиск. Для начала следует пояснить что с бинарными данными мы работать не будем, такое название данному методу дано из-за особенностей его работы. Изначально мы сортируем массив в лексикографическом порядке, затем алгоритм берет диапазон всего массива, получает средний элемент диапазона, сравнивает его лексикографически, и в зависимости от результата сравнения решает какой диапазон брать для поиска дальше – верхнюю половину текущего или нижнюю. То есть на каждом шаге поиска принимается решение из двух возможных – бинарная логика. Этот шаг повторяется до тех пор, пока либо слово найдется, либо не найдется (произойдет пересечение нижнего и верхних индексов диапазона).

Производительность данного алгоритма – лучший случай когда сразу найден элемент в середине массива O(1), худший случай перебора O(log n)

Подводные камни

При реализации бинарного поиска я встретился мало того с интересной проблемой отсутствия стандартизации лексикографического сравнения в библиотеках языков программирования, но даже обнаружил отсутствие единого стандарта реализации localeCompare внутри JavaScript. Стандарт ECMAScript допускает разную реализацию данной функции, из-за этого при сортировке с помощью localeCompare, на разных движках JavaScript может наблюдаться абсолютно разный результат.

Поэтому для корректной работы алгоритма нужно обязательно сортировать и использовать в работе только один и тот же алгоритм лексикографического сравнения, иначе работать ничего не будет. Со-но если например попытаться сортировать массив в Scala, а искать с помощью nodejs, не реализуя собственную сортировку/сортировку одной реализации, то кроме разочарования в человечестве вас ничего не ждет.

Источники

Что такое лексикографическое сравнение и что оно собой представляет?
Почему для вычисления сложности алгоритмов используется log N вместо lb N?
Двоичный поиск
Знай сложности алгоритмов
https://stackoverflow.com/questions/52941016/sorting-in-localecompare-in-javascript

Исходный код

https://gitlab.com/demensdeum/algorithms

0