Что нового я узнал о компьютере, когда решил написать Chrome Dino на C

Немного о проекте

Для знакомства с языком с я решил написать небольшое приложение chrome dino, которое является неудачным клоном всем знакомого динозаврика из хрома. Из-за отсутствия классов в си я решил изобрести свой велосипед: поля и методы класса поместил в структуру, конструктором стала функция, которая возвращает эту структуру. Внутренние поля и методы скрыты, указав перед ними static. (Про это есть несколько статей)

.

typedef struct Barrier {
    int width, height;
    int *picture;
    int x0, y0;
} Barrier;

Barrier* new_Barrier() {
  Barrier* barrier = NULL;
  barrier = malloc(sizeof(Barrier));

  return barrier;
}

Для удобства работы с графикой изображения хранятся в виде матрицы со
значениями [0, 1, 2, 3], это решение подтолкнуло на написание этой
статьи.
0 — прозрачный,
1 — синий,
2 — черный,
3 — серый.

Компьютер не знает что такое массивы, а двумерные — тем более

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

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

Для перебора ряда данных (одномерный массив) берется адрес первого элемента, а затем в цикле (с шагом = размер типа данных) осуществляется переход на следующий адрес.

int n = 10;
int step = sizeof(Barrier);
Barrier* barrier = malloc(step * n);

for (int i = 0; i < n; i += step) {
  *(barrier + i) = data;
}

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

где A — двумерный массив,
    &nbsp i — индекс строки,
    &nbsp j — индекс столбца,
    &nbsp w — длинна вложенного массива A (ширина массива)

Еще сложнее найти элемент трехмерного массива, для его поиска необходимо воспользоваться формулой:

где B — трехмерная матрица,
    &nbsp k — индекс ряда двумерных матриц,
    &nbsp h — длина вложенного массива B(высота матрицы).

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

где C — n-мерный массив,
    &nbsp n — вложенность,
    &nbsp  — индекс i-го массива,
    &nbsp  — длинна массива i.

Если за ось ординат принять количество операция компьютера, а за ось абсцисс — вложенность, то можно увидеть, как растет количество операций для вычисления элемента массива с увеличением вложенности. (Сумма и умножение приняты за одну операцию).

Помнить о памяти

В высокоуровневых языках имеются сборщики мусора и выделение памяти работает под капотом языка. В низкоуровневых языках приходится это делать самостоятельно: перед тем как записать данные в память, нужно зарезервировать некоторую ее область. Для набора данных необходимо самостоятельно высчитывать количество памяти для резервации.

Рассмотрим случай одномерного массива c элементами типа Barrier. Если количество элементов известно заранее, то для такого массива память выделяется один раз. В случае динамического массива, приходится каждый раз пересчитывать размер выделяемой для него памяти (если длина массива изменяется). Тогда для реализации стандартного метода push (добавление элемента в конец массива) необходимо выделить область памяти (равный сумме размера старого массива и величины типа элемента) и записать туда новый массив, а старый удалить. То же и с удалением элемента из массива.

int n = 10;
int step = sizeof(Barrier);
Barrier* barrier = malloc(step * n);

for (int i = 0; i < n; i += step) {
    *(barrier + i) = data;
}

n = 11;
free(barrier);
barrier = malloc(step * n);

for (int i = 0; i < n; i += step) {
    *(barrier + i) = data;
}

Можно сделать вывод: изменение размера массива довольно затруднительная операция, особенно если идет большой цикл добавления элементов в массив. Некоторые высокоуровневые языки выделяют чуть больше области памяти под массивы (например, ArrayList в java), видимо для повышения производительности.

Не примитивный примитив

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

Посмотреть проект можно туть.