[Из песочницы] Как я делал игру под AVR

Уже давно было желание написать статью по какой-нибудь поделке. Но изо дня в день, читая очередную статью про очередной «умный дом» или «умную метеостанцию на Ar…» все меньше хотелось написать точно то же самое, но с другого ракурса, а тем у меня было не много. И вот однажды…

1f66f0a99be4476387c6d4f3d755f071.png

Внимание! Под катом кривой код, пара изображений и много воды.
Все началось с того, что как-то раз заметил свою вторую половинку за игрой про некогда популярный интернет-мем «Nyan Cat», мне он настолько понравился, что я неудержимо захотел сделать с ним игру! Беглый поиск на наличие подобных статей на GT и H дал нулевой результат. В принципе не удивительно, мало кто сегодня будет заморачиваться и делать подобное (знаю, что есть GameBuino, но на GT и H нет ни одного упоминания). Что ж, раз пусто, значит, заполним эту пустоту!

Суть


Сделать нечто в ретро стиле, что-нибудь простое… И конечно же! На ум сразу приходит классика жанра — Space Invaders. Что может быть проще, чем сделать свой клон?

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

Железо


Микроконтроллер Atmel AVR ATmega328P на частоте 16 МГц (плата Arduino Nano). Экран ILI9341 SPI TFT 2.4» 320×240 и резистивный сенсорный экран на драйвере XPT2046 (китайский клон ADS7846). Заказан экран с Али (предназначался под осциллограф на STM32), о чем сперва пожалел, так как нормально работающих библиотек под драйвер сенсорного экрана почти нет. Впоследствии с этого был профит в виде сносно работающей библиотеки, хоть и собранной из кусков.

Софт


К сожалению, в силу своей титанической ленивости, на первых порах использовалась Arduino IDE. Потом из-за разросшегося проекта там стало тесно, и я перешел на Sublime Text 2 с последующим прикручиванием Arduino IDE (библиотеки, компилятор — слишком тяжело отказаться). Под конец, ради спортивного интереса и оптимизации собрал все в Atmel Studio (Кто-то скажет, что сразу надо было писать там! Как уже писал: просто лень). В итоге так и оставил все под Arduino IDE, исходя из соображений, что далеко не у каждого есть желание ставить и разбираться с Atmel Studio.

Изображения


Поскольку ресурсы контроллера весьма скромны, то впоследствии от некоторых идей пришлось отказаться (например, фон стал одноцветный, хотя в планах была текстура). Более того пришлось перечитать кучу статей по NES, именно из них я почерпнул некоторые трюки по оптимизации.

Первая проблема началась с изображений, а именно из-за их размера. Места просто не хватало. Экран принимает цвета 16 бит на пиксель, т.е. мы рисуем картинки в RGB565. Читать изображения через SPI с SD карты без DMA очень затратно и долго.
Например, картинка ниже занимает при размере 51×20 — 1360 байт, но для нормальной анимации таких нужно 6!

Один из 6 кадров
0d88b665681b4a1b982b3b14bfd29f7d.png


Приступим к искривлению сжатию пространства изображения. Первое решение, которое было найдено мгновенно — использовать повторяющиеся элементы.

Например, радугу можно сделать из двух картинок, что на четыре меньше! Далее тело. Это одно и то же тело на всех 6 кадрах! Вместо 6 используем одно! Идентично с головой. Остальное не содержит повторений (или можно пренебречь).

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

Слабонервным не смотреть!
ab346035d3914d5d91f97720d31638a8.png


После того как остался набор отдельных изображений, они все равно много занимают (5504 байт вместо 8160).

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

так:
void drawRainbow()
{
  // rainbow size:  24x21 (WxH) 

  uint8_t countRainbow;     // count of colors
  uint8_t rbElementY = 0;   // pos of small block in Y 
  uint8_t rbElementX = 0;   // position of each block in X
  uint8_t rbElementNum = 2; // first up, after down blocks

  uint16_t color;

  rainbowState = !rainbowState; // invert rainbow

  // Full rainbow consist of 4 blocks: 2 blocks up, 2 blocks down
  while(rbElementNum--) {
    // 6 colors + 2 color of background; just overdraw colors
    for(countRainbow=0; countRainbow <= 7; countRainbow++) {

      color = PGRW_U16(pCatsRainbow, countRainbow);
      
      // 6 - width; 3 - heigth 
      tftFillRect(rbElementX, rbElementY + nyan.base.posY + (rainbowState ? 1 : 0), 6, 3, color);

      tftFillRect(rbElementX+6, rbElementY + nyan.base.posY + (rainbowState ? 0 : 1), 6, 3, color);
      
      rbElementY += 3;
    }
    rbElementY = 0;   // reset position
    rbElementX += 12; // now second - up or down bloks
  }
}



То размер радуги уменьшится c 2016 байт до 16 байт + примерно 200 байт на код. При этом, немного потеряв в производительности.

Промежуточный итог №1.

Высвободилось примерно 1800 байт (целый кот занимает 3704). Можно сделать меньше? Конечно! Вместо огромных массивов с цветами использовать два массива: один таблица цветов с типом uint16_t, второй изображение, но вместо цветов индексы нужного цвета в таблице цветов. Для этого уже вполне подойдет uint8_t (для 255 цветов вполне хватит, привет GIF).

Промежуточный итог №2.

Освободилось еще 1944 байт (целый кот теперь занимает 1760). Можно сделать меньше? Можно! Внимательно смотрим на массивы и видим колоссальные однотипные последовательности! Бежим читать про RLE сжатие (забавное совпадение, через некоторое время, когда уже сделал кодер и декодер, на H появилось несколько статей на тему RLE, как мне не хватало их несколько раньше).

Если с декодером проблем не возникло, я четко знал, что у меня будет на входе и что я буду со всем этим делать, то вот с кодером как раз наоборот…

На вход декодера идет:

— координаты на экране где выводим изображение;
— высота и ширина в пикселях;
— таблица с индексами цветов;
— таблица цветов;
— размер сжатого изображения.

Декодер
void drawBMP_RLE_PGR(int16_t x, int16_t y, uint8_t w, uint8_t h,
  const uint8_t *colorInd, const uint16_t *colorTable, uint16_t sizePic) 
{
  // This is used when need maximum pic compression,
  // and you can waste some CPU resources for it;
  // It use very simple RLE compression;
  // Also draw background color;

  uint16_t count = 0;
  uint16_t repeatColor;
  uint8_t tmpInd, repeatTimes;  // for big pics need uin16_t

  tftSetAddrWindow(x, y, x+w-1, y+h-1);

  while(count < sizePic ) {  // compressed pic size!
    // get color index or repeat times
    tmpInd = pgm_read_byte(colorInd + count );
    
    if(~tmpInd & 0x80) { // is it color index?
      repeatTimes = 1;
    } else {   // nope, just repeat color
      repeatTimes = tmpInd - 0x80;
      // get previous color index to repeat
      tmpInd = pgm_read_byte(colorInd + (count - 1));
    }

    // get color from colorTable by tmpInd color index
    repeatColor = PGRW_U16(colorTable, tmpInd);

    do {
      --repeatTimes;
      tftPushColor(repeatColor);
    } while (repeatTimes);

    ++count;
  }
}



Кодер написал как смог на Qt (собирал статику Qt 4.8.6 под OS X). Суть кодера: сжать идентичные последовательности в файлах изображений и поместить результат в заголовочные файлы.

Вышел он очень привередливый к входным изображениям. Нужно убирать альфа канал и экспортировать как raw data RGB565, хорошо хоть в Gimp это делается легко. Использование: помещаем в папку с программой *.data файлы изображений, запускаем, и на выходе заголовочные файлы.

Промежуточный итог №3.

Места стало больше всего на 229 байт (все вместе занимает 1531). Отчего так мало? Не стоит забывать, что из-за некоторых проблем с отрисовкой (неправильное наложение цветов) сжато по RLE было только тело. Так же, я не рассматривал изображения Invaders и подарка, которые так же были сжаты по RLE и уменьшили свой размер с 3456 байт до 722 байт.

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

Многозадачность


Вторая проблема пришла с ростом количества задач. В начале, задач было мало и все выполнялись последовательно, вполне быстро — 20–28 кадров в секунду. Со временем, рост количества задач привел к падению до 7–10 кадров в секунду! Сначала думал о банальной нехватке ресурсов ЦПУ, уже планировал перейти на более серьезный МК. Но меня осенило! Я ведь делаю действия, которые, по сути, не требуют постоянного выполнения в каждом цикле! Нужно размазать задачи во времени, сделать подобие многозадачности!

Первое что пришло на ум: FreeRTOS… К сожалению, при 16 (17 если вывод debug info) задачах это оказалось не по силам этой AVR.

Поиск решения приводил в основном к статьям DIHALT. Изучив их, сделал свой велосипед менеджер задач. Что есть:

— добавление задачи (как же без этого);
— удаление всех или одной задачи;
— замены одной задачи на другую;
— количество задач до 254 (по факту, сколько хватит памяти);
— 9 байт на задачу (можно и меньше).
— используется timer 0 в качестве системного таймера;
— таймаут вызова задачи (ради этого все и делалось);
— флаг необходимости исполнения задачи;
— глупая защита от не выделения памяти синим экраном;
— указатели, много указателей;
— ???;
— PROFIT!!!

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

— создаем структуру (в ней указатель на массив и количество текущих задач);
— указываем что это наш основной массив задач;
— добавляем все задачи, какие нужно;
— вызываем функцию runTasks () и больше оттуда не возвращаемся.

Благодаря этому основной цикл стал выглядеть так:
void runTasks()
{
  uint32_t currentMillis;
  volatile uint8_t count;

  for(;;) {
    for(count=0; count < pCurrentArrTasks->tasksCount; count++) {
      // Have func and need execute?
      if(pCurrentArrTasks->pArr[count].pTaskFunc && pCurrentArrTasks->pArr[count].execute) {
        currentMillis = TIMER_FUNC;
        
        // check timeout
        if((currentMillis - pCurrentArrTasks->pArr[count].previousMillis) >
                                       pCurrentArrTasks->pArr[count].timeToRunTask) {
          pCurrentArrTasks->pArr[count].previousMillis = currentMillis;
          pCurrentArrTasks->pArr[count].pTaskFunc();
        } 
      }
    }
  }
}



В основном цикле перебирается весь массив задач. Задачи выполняются только по таймауту и если флаг на выполнение в истине.
На счет эффективности решения ничего говорить не буду, просто напишу, что стало значительно лучше! Даже эта кривая реализация разгрузила ЦПУ и падение частоты кадров пропало от слова совсем.

Полет в космос


В оригинале кот летит в космосе мимо звезд (судя по синему фону летит на околосветовой), не беда прикрутим звезды и будем их двигать!

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

Создаем следующим образом:
  while((maxStars > 0) && (starStruct == NULL)) {
    // if we cant make so much stars
    if((starStruct = (tStarType*) malloc(sizeof(tStarType) * maxStars)) == NULL)
      --maxStars; // we try to make for one less
  }



Но звезд на экране может поместиться много, неужели придется писать координаты для каждой? Нет, присвоим псевдослучайные значения. Возьмем значение температуры с 8 канала ADMUX (нам все равно на точность, чем не точнее, тем лучше) и загрузим в srand (при этом, если температура всегда одинакова, то и rand будет идентичен).

Замеряем температуру:
uint16_t getTemp(void)
{
  // The internal temperature has to be used
  // with the internal reference of 1.1V.

  // Set the internal reference and mux.
  ADMUX = ((1<


Если хотя бы одна звезда была создана, то применяем параметры для каждой:

псевдослучайно:
if(maxStars) {
    for(uint8_t count =0; count < maxStars; count++) {
      starStruct[count].state = randNum() % STAR_STEP;
      starStruct[count].posX = randNum() % TFT_W + 22;
      starStruct[count].posY = randNum() % TFT_H + 22;
    }
  }



Invaders


Они есть. Их пять (столько отлично помещается в ряд) и они как терминатор (все время возвращаются обратно).

Оптимизация


После переноса в Atmel Studio (выдернув что нужно из Arduino), где можно было с легкостью получить asm листинг и примерно понять, что я натворил, начал переписывать используемые библиотеки и некоторые кодовые конструкции (некоторые заметят, что я понаделал неведомой фигни непонятно зачем, и будут правы).

Что это дало? Высвободило около 6 Кбайт ПЗУ, уменьшило объем используемой ОЗУ и увеличило скорость передачи данных по SPI (пожертвовав некоторыми возможностями).

Итог


Хоть игра примитивна, но вполне неплохо работает и может занять на некоторое время. Более того, осталось свободно 10 Кбайт ПЗУ и около 1 Кбайт ОЗУ.

Что в планах:

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

Архив с игрой.

Архив с кодером.

Собственно как выглядит игра:

© Geektimes