[Из песочницы] Запуск 619 тысяч тетрисов на GLSL, их рендеринг и простой бот09.03.2019 13:34

У меня была «идея» сделать максимальное число одновременно запущенных «Тетрисов» для одного шейдера (одной текстуры фреймбуфера).

Далее небольшое описание как работает полученный код.


Что это:

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



Хранение данных

Таблица «тетриса» размера [10, 22] (10 ширина, 22 высота).
Каждая ячейка может быть либо пустой либо не пустой.
Итого 22 * 10 = 220 бит требуется для хранения всей таблицы.
Один «пиксель» это четыре 24-битных float, 96 бит в пикселе.

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

image

2 * 96 + 24 + 4
Два пикселя, один float третьего пикселя, 4 бита второго float третьего пикселя
Осталось два неиспользованных float в третьем пикселе pixel3.zw, они хранят состояние логики, точнее


  • z хранит три восьми-битные числа [a,b,c]
    — a позиция текущего блока, как ID позиции в массиве (массив размера 220 бит, максимальная позиция равна 220 что меньше 0xff)
    — b время до автоматического падения вниз (таймер) каждый фрейм -1 к этому числу, как стало 0 то падает на блок вниз
    — c ID текущего блока
  • w также [a,b,c], но также знак (положительное или отрицательное) всего float является флагом конца игры в текущей таблице (чтоб не тратить ресурсы если поле завалено)
    — a действие, нет действия (0), влево (1), вправо (2) и так далее полный код в Common, действия имеют два состояния, влево_проверить и если возможно подвинуть влево то действие устанавливается влево_подвинуть.
    — [b,c] 0xffff(16 бит) очки текущей таблицы, количество линий которые сгорели

Осталось 20 бит неиспользованных во втором float третьего пикселя.

debug фрейм показывающий что логика сохранения работает верно
слева идут белое поле размером три пикселя, установлено специально чтобы показать что разрывы обработаны верно (при разрешении не кратном трем полоса будет идти под углом)
условие на строке 75 Buffer A

image


Зачем нужны ID действий:


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


Медленное место


  • Каждый третий пиксель (пиксель логики) распаковывает всю карту (читая все три пикселя).
  • Остальные два пикселя распаковывают только «сами себя» (один пиксель) для выполнения сохраненного действия.
  • При действии линия сгорела загружается еще один пиксель, так как таблица падает вниз и нижние куски таблицы должны знать что сверху.


Производительность алгоритма хранения данных

Для теста установите #define debug в Common и AI 0 там-же.
Я получил такой результат — 10ФПС при рендеринге и обработке всех 619200 полей,
на 120 тысяч полей (25фпс)

image


Логика бота

Логика Очень плоха, бот сгорает в течении минуты, и получает до 60 очков.

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

Моя логика бота работает так
Вся логика находится в функции AI_pos_gen в Buffer A, ее там десяток строк.

Псевдокод:
высота проверки для установки блока равна максимальной для поля в текущей колонке (проверка по одной строке по высоте)

цикл(4 поворота текущего блока){
  цикл(по ширине таблице(10)){
    ЕСЛИ(блок можно поставить в текущее положение){
      если (текущая высота блока и позиция, меньше прошлой)
        то запоминаем best ID(блока) и best POS
    }
  }
}

функция (блок можно поставить в текущее положение)
проверяет циклом (по размеру блока) чтоб все элементы поля были 0 там где элементы блока 1

Получается три цикла которые банально — ставят блок так чтобы высота была минимальна.

Функция AI_pos_gen вызывается при появлении нового блока, и возвращает позицию для падения сверху, принимая ID блока и делая его вращение, функция работает в третьем пикселе (логике) то есть имеет полную загруженную карту (массив map).
Легко можно попробовать написать свой бот, если если желание.

Самое медленное место
Добавив всего один цикл для проверки дыр у меня драйвер видеокарты падал при количестве ботов больше 10тыщ… тот бот что я написал это максимально «минималистичный» вариант бота который я смог сделать, и он очень плох к сожалению.


Интерфейс/рендеринг UI

Весь рендеринг в Image, логика UI в Buffer B.

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

Логика загрузки карты — не распаковывается всю карта каждый пиксель, распаковывается только «нужный бит» (буквально), код функции: 

int maptmp(int id, int midg) {
    int nBits = 8;
    ivec4 pixeldata = loadat(id, midg);
    int itt = (id / 24) / 4; //data pixel id 0-2
    int jtt = (id - itt * 24 * 4) / 24; //component in data pizel id 0-3
    int ott = (id - itt * 24 * 4 - jtt * 24) / 8; //component in unpacked value 0-2
    int ttt = (id - itt * 24 * 4 - jtt * 24 - ott * 8); //bit after int2bit 0-7
    ivec3 val = decodeval16(pixeldata[jtt]);
    int n = val[ott];
    for (int i = 0; i < nBits; ++i, n /= 2) {
        if (i == ttt) {
            if ((n % 2) == 0)return 0;
            else return 1;
            //switch + return does not work on windows(Angle)
            /*switch (n % 2) {
               case 0:return 0;break;
               case 1:return 1;break;
            }*/
        }
    }
    return 0;
}

Чтоб избежать пикселизации при прокрутке, начиная с 43000 идет потеря дробной части float, и никак не выйдет добавить 619 тысяч к UV для прокрутки (будут пиксели вместо таблиц).
Вся прокрутка делится на один большой тайл и крутится по кругу прибавляя максимум 32 к UV. (строка 207 в Image).

Тоже самое сделано для определения ID поля. (строка 215 в Image)


UI

Числа:
Желтое — количество полей тетриса.
Слева большое — номер текущего поля.
Справа меньшее — очки текущего поля.


Исходник и запуск

Bufer A логика, Bufer B это управление UI, Image отрисовка
Исходник по ссылке https://www.shadertoy.com/view/3dlSzs (время компиляции через Angle 16 сек)
Там отключен бот (можно включить), и все поля играбельные с клавиатуры.

Управление стрелками влево/право/вверх/вниз.

UI красный прямоугольник сброс, перемещайте (тащите мышь нажав ЛКМ) и клик мышкой по полям для прокрутки или выбора поля для показа.

Запуск из веб-браузера:


  • запустите хром командой chrome.exe --use-angle=gl
  • перейти по ссылке на shadertoy
  • в редакторе на сайте выбрать Common и удалить #define no_AI
  • (также в Common) установить #define AI 199 равным 0, тоесть #define AI 0
  • нажать кнопочку компиляции (под окном редактора на шадертое) и нажать фулскрин

Второй вариант, запустить шейдер в любом «лаунчере шейдеров», вот ссылка на архив (скачать) в котором *.exe файл с этим шейдером.

OpenGL время компиляции около 10 сек.

© Habrahabr.ru