Описание алгоритма логики, и разбор рабочего примера в виде техно-демки-игры

WebGL2 версия этой демки https://danilw.itch.io/flat-maze-web остальные ссылки смотрите в статье.

Статья разбита на две части, сначала про логику, и вторая часть про применение в игре, первая часть:

• Ключевые особенности.
• Ссылки и краткое описание.
• Алгоритм работы логики.
• Ограничения логики. Баги/особенности, и баги Angle.
• Доступ к данным по индексу.

Дальше описание игровой-демки, вторая часть:

• Используемые возможности этой логики. И быстрый рендеринг миллиона частиц-пикселей.
• Реализация, немного комментариев к коду, описание работы коллизии в две стороны. И взаимодействие с игроком.
• Ссылки на используемую графику с opengameart, и шейдер теней. И ссылка статьи на cyberleninka.ru

Часть 1

1. Ключевые особенности

Идея — коллизия/физика сотен тысяч частиц между собой, в реальном времени, где у каждой частицы есть уникальный идентификатор ID.

Когда каждая частица индексирована, можно контролировать любые параметры любой частицы, например масса, свое здоровье(hp) или урон, ускорение, замедление, с какими объектами сталкиваться и реакции на событие в зависимости от типа/индекса частицы, также уникальные таймеры на каждую из частиц, и прочее по необходимости.

Вся логика на GLSL, полностью переносима на любой игровой-движок и любую ОС, где есть поддержка GLES3.

Максимальное количество частиц равно размеру framebuffer (fbo, все пиксели).

Комфортное количество частиц (когда частицам есть место для взаимодействия) это (Resolution.x*Resolution.y/2)/2 это каждый второй пиксель по x и каждая вторая строка по y, почему так указано в описании логики.

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

2. Ссылки и краткое описание

Я сделал три демки по этой логике:

1. На GLSL fragment-shader, на shadertoy https://www.shadertoy.com/view/tstSz7, смотрите код BufferC в нем вся логика. Этот код также позволяет отображать сотни тысяч частиц со своим UV, в произвольной позиции, на fragment-shader без использования instanced-particles.

2. Перенос логики на instanced-particles (используется Godot в качестве движка)

Ссылки Веб версия, exe(win), исходники проект particles_2D_self_collision.

Краткое описание: Это плохая демонстрация на instanced-particles, из за того что я делаю максимальное увеличение где видно всю карту, то обрабатываются всегда 640x360 частиц(230k), это много. Смотрите ниже в описании игры, там я сделал правильно, без лишних частиц. (в видео есть ошибка с индексом частиц, это исправлено в коде)

3. Игра, про нее ниже в описании игры. Ссылки Веб версия, exe(win), исходники

3. Алгоритм работы логики

Кратко:

Логика на подобии falling-sand, каждый пиксель сохраняет дробное значение позиции(сдвига внутри своего пикселя) и текущее ускорение.

Логика проверяет пиксели в радиусе 1, на то что их следующая позиция хочет перейти на этот пиксель (из за этого ограничение, см ограничения ниже), также пиксели в радиусе 2 для отталкивания (коллизия).

Уникальный индекс сохраняется переводом логики на int-float, и уменьшением размера под данные позиции pos и скорости движения vel.

Данные хранятся таким образом: (из за этого баг, см ограничения)

pixel.rgba
r=[0xfffff-posx, 0xf-data]
g=[0xfffff-posy, 0xf-data]
b=[0xffff-velx, 0xff-data]
a=[0xffff-vely, 0xff-data]

В коде, номера строк для BufC https://www.shadertoy.com/view/tstSz7, 115 transition-check, 139 collision-checks.

Это простые циклы по взятию соседних значений. И условие, если позиция взята равна позиции текущего пикселя — то перемещаем те данные в этот пиксель (из за этого ограничение), и меняется значение vel в зависимости от соседних пикселей если они есть.

Это вся логика частиц.

Лучше всего размещать частицы на расстоянии 1 пикселя друг от друга если они ближе 1 пикселя то будет идти отталкивание, как пример карта с лабиринтом в игре, частицы стоят по своим местам не двигаясь из за расстояния в 1 пиксель между ними.

Дальше идет рендеринг (отрисовка), в случае fragment-shader, берутся пиксели в радиусе 1 для отображения пересекающихся областей. В случае instanced-particles берется пиксель по адресу INSTANCE_ID переведенным из линейного вида в двухмерный массив.

4. Ограничения логики. Баги/особенности, и баги ANGLE

1. Размер пикселя, BALL_SIZE в коде, для расчета должен быть в пределах, большеsqrt(2)/2 и меньше 1. Чем ближе к 1 тем меньше места для хождения внутри пикселя(самому пикселю), чем меньше тем больше места. Такой размер нужен чтоб пиксели не проваливались друг в друга, меньше 1 можно ставить когда у вас маленькие объекты, создается иллюзия объектов меньше 1 пикселя(расчетного).
2. Скорость не может быть больше 1 пикселя иначе пиксели будут пропадать. Но иметь скорость больше 1 за кадр-можно, если сделать несколько framebuffer(fbo/viewport) и обрабатывать сразу несколько шагов логики за кадр-скорость увеличиться в количество раз равное количеству дополнительных fbo. У меня так сделано в демке с фруктами, и по ссылке на shadertoy (bufC скопирован в bufD).
3. Ограничение по давлению (как гравитация, или другие force-normal-map). Если несколько соседних пикселей принимают позицию этого(см картинку выше) то сохраняется только один, первый пиксель остальные пропадают. Это легко заметить в демке на shadertoy установите мышь в Force, измените значение MOUSE_F в Common на 10, и направьте частицы в угол экрана они будут пропадать друг в друге. Или тоже самое со значением гравитации maxG в Common.
4. Баг в Angle. Для работы этой логики в GPU(instanced)-particles лучше (дешевле, быстрее) всего рассчитывать позицию, и все прочие параметры частицы для отображения, в instance-shader. Но Angle не разрешает использовать больше одной fbo-texture для шейдера, поэтому расчет части логики надо перенести в Vertex-shader куда передавать номер индекса из instance-шейдера. У меня так сделано в обоих демках с GPU-частицами.
5. Серьезный баг в обоих демках(кроме игры) значение позиции будет теряться если оно не кратно 1/0xfffff тест бага тут https://www.shadertoy.com/view/WdtSWS
   Если точнее, это не баг, так и должно быть, для простоты в рамках этого алгоритма я назвал это баг.

Фикс бага:
Не конвертируйте значение позиции в int-float, из за этого пропадет 0xff, 8 бит доступных для данных, но останется 0xffff значение для данных, чего может хватить для много чего.
В демке игры я так и сделал, я использую только 0xffff для данных, где хранятся тип частицы, таймер анимации, здоровье, и еще остается свободное место.

5. Доступ к данным по индексу

instanced-particle имеет свой INSTANCE_ID, по нему берется пиксель из текстуры фреймбуфера с логикой частиц (bufC, пример на шадертое), если там частица то распаковываем (см хранение данных) ID этой частицы, по этому ID читаем текстуру с данными для частиц (bufB, пример на шадертое).

В примере на shadertoy в bufB храниться всего лишь цвет для каждой частицы, но очевидно что там могут быть любые данные, как написал ранее масса, ускорение, замедление, также любые логические действия (например можно перемещать любую частицу в любое положение(телепортировать) если сделать соответствующее логическое действие в коде), также управлять движением любой частицей или группой с клавиатуры тоже можно…

Имею в виду, что делать можно что угодно с каждой из частиц как будто это обычные частицы в массиве на процессоре, доступ двухсторонний из GPU-частицы можно менять свое состояние, но также из CPU можно менять состояние частицы по индексу(используя логические действия и текстуру-буфер данных).

Часть 2

1. Используемые возможности этой логики. И быстрый рендеринг миллиона частиц-пикселей

Размер framebuffer(fbo/viewport) для частиц 1280x720, частины расположены через 1, это 230 тысяч активных частиц (активных элементов в лабиринте).
На экране всегда не более 12 тысяч GPU-instanced particles.

Логика использует:

• Логика игрока находится отдельно от логики частиц, и только читает данные из буфера частиц.
• Игрок замедляется при столкновении с объектами.
• Объекты типа монстр наносят урон игроку.
• Игрок имеет 2 атаки, одна отталкивает все вокруг, вторая создает частицы типа fireball (картинка такая)
• Тип fireball имеет свою массу, и работает двустороннее отслеживание столкновений с другими частицами
• другие частицы типа приведение и зомби (один тип приведения неуязвим) уничтожаются при столкновении с fireball
• fireball гаснет после одного столкновения
• уровни физики — деревья и квадраты отталкиваются игроком, другие частицы не взаимодействуют, на fireball не действуют никакие ускорения
• таймеры анимации уникальны на каждую из частиц

По сравнению с демкой с фруктами, где есть overhead, в этой игре количество GPU-instanced particles всего 12 тысяч.

Это выглядит так:

Их количество зависит от текущего увеличения (zoom) карты, и увеличение ограничено на определенной величине, поэтому считаются только те что видны сейчас на экране.
Экран сдвигается с игроком, логика расчета сдвигов немного комплексная, и очень ситуативная, сомневаюсь что ей найдется применение в другом проекте.

2. Реализация, немного комментариев к коду.

Весь код игры находиться на GPU.

Логика расчета сдвига частиц в экране с увеличением, в функции vertex в файле /shaders/scene2/particle_logic2.shader это файл шейдера к частицам(vertex и fragment), не instanced-шейдер, instanced шейдер не делает ничего, только передает свой индекс из за бага описанного выше.

частицы по типам и вся логика взаимодействия частиц в файле, это файл шейдера фреймбуфера частиц shaders/scene2/particles_fbo_logic.shader

// 1-2 ghost
// 3-zombi
// 4-18 blocks 
// +20 is on fire
// 40 is bullet(right) 41 left 42 top 43 down

хранение данных pixel[pos.x, pos.y, [0xffff-vel.x, 0xff-data1],[0xffff-vel.y, 0xff-data2]]
data1 — это тип, data2 это HP или таймер.

Таймер идет по фреймам в каждой частице, макс значение таймера 255, мне не нужно так много я использую лишь 1-16 максимум(0xf), и остается еще 0xf не использовано где можно например реальное значение HP хранить, у меня не используется. (тоесть да я использую 0xff для таймера, но по факту у меня всего меньше 16 кадров анимации, и хватилобы 0xf но мне не нужны были дополнительные данные)
Реально 0xff используется только на таймере горящих деревьев, они превращаются в зомби после 255 фреймов. Логика таймера частично в type_hp_logic в шейдере фреймбуфера частиц(ссылка выше).

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

Файл shaders/scene2/particles_fbo_logic.shader строка 438:

if (((real_index == 40) || (real_index == 41) || (real_index == 42) || (real_index == 43)) && (type_hp.y > 22)) {
  int h_id = get_id(fragCoord + vec2(float(x), float(y)));
  ivec2 htype_hp = unpack_type_hp(h_id);
  int hreal_index = htype_hp.x;
  if ((hreal_index != 40) && (hreal_index != 41) && (hreal_index != 42) && (hreal_index != 43)) type_hp.y = 22;
} else {
  if (!need_upd) {
    int h_id = get_id(fragCoord + vec2(float(x), float(y)));
    ivec2 htype_hp = unpack_type_hp(h_id);
    int hreal_index = htype_hp.x;
    if (((hreal_index == 40) || (hreal_index == 41) || (hreal_index == 42) || (hreal_index == 43)) && (htype_hp.y > 22)) {
      need_upd = true;
    }
  }
}

real_index это тип, выше перечислены типы, 40-43 это fireball.
дальше type_hp.y > 22 это значение таймера, если оно больше 22 то fireball не сталкивался ни с чем.
h_id = get_id(... берем значение типа и HP (таймера) частицы с которой столкнулись
hreal_index != 40... игнорируются свойже тип (другие fireball)
type_hp.y = 22 ставится таймер на 22, это индикатор что этот fireball столкнулся с одним объектом.
else { if (!need_upd)переменная need_upd проверяет чтоб не было повторных столкновений, так как функция находиться в цикле, сталкиваемся с одним fireball.
h_id = get_id(... если столкновение еще не было то берем объект тип и таймер.
hreal_index == 40...htype_hp.y > 22 что объект столкновения fireball и он не гаснет.
need_upd = true флаг что надо обновить тип так как столкнулись с fireball.

дальше строка 481
if((need_upd)&&(real_index<24)){ real_index<24 по типу меньше 24 находятся не горящие деревья зомби и приведения, и дальше в этом условии обновляем тип в зависимости от текущего типа.

Таким образом можно сделать практически любое взаимодействие объектов.

Взаимодействие с игроком:

Файл shaders/scene2/logic.shader строка 143 функция player_collision

Эта логика читает пиксели вокруг игрока в радиусе 4x4 пикселя, берет позицию каждого из пикселей и сравнивает с позицией игрока, если найден элемент то дальше проверка на тип, если это монстр то отнимаем HP у игрока.

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

Частицы отталкиваются от игрока и эффект отталкивания при атаке:

Используется framebuffer(viewport) в который пишется normal текущих действий, и частицы (particles_fbo_logic.shader) берут эту (с normal) текстуру по своей позиции и применяют значение к своей скорости и позиции. Весь код этой логики прост буквально пара строк, файл force_collision.shader

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

Можно либо сделать нормальную зону(форму) для спавна частиц со сдвигом появляющихся относительно игрока(это не сделано).
Либо можно сделать fireball отдельным объектом как игрока и рисовать normal в буфер для отталкивания частиц от fireball, тоесть по аналогии с игроком…
Кому надо думаю сами разберутся.

3. Ссылки на используемую графику с opengameart, и шейдер теней

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

Шейдер теней работает очень просто, на основе этого шейдера https://www.shadertoy.com/view/XsK3RR (у меня модифицированный код)
Шейдер строит 1D Radial Lightmap

и рисование теней в коде рисования пола shaders/scene2/mainImage.shader

Ссылки на используемую графику, вся графика в игре с сайта https://opengameart.org
fireball https://opengameart.org/content/animated-traps-and-obstacles
персонаж https://opengameart.org/content/legend-of-faune
деревья и блоки https://opengameart.org/content/lolly-set-01
(и еще пара картинок с opengameart)

Графика в меню получена 2D_GI шейдером, утилитой для создания таких меню:

Кто дочитал до конца — молодец :)
Если есть вопросы, спрашивайте, могу дополнить описание по запросам.