Конкурс 96к (2015) (конкурс завершён) (79 стр)

Языки\Технологии:
Язык - Delphi 2007
Методики сжатия:
- DelphiUnitSizes c http://www.emix8.org/ для анализа того, на что уходит место в файле.
- т.к. kkrunchy лучше сжимает когда код и данные отделены друг от друга, то различные ресурсы старался выносить в константы. Правда на вынесение в константы предметов и оружия в итоге забил, так что в константы вынесены только текстуры (в виде макроязыка), шрифт и модель зомби.
- альтернативная версия System\SysInit отсюда.
Там вырезаны разные малоиспользуемые функции (из того с чем столкнулся - writeln в консоль и поддержка автоудаления динамических массивов структур, содержащих динамические массивы), но при этом самое важное, т.е. строки и динамические массивы на месте, в отличии от варианта с crinkler.
- dglOpenGL.pas в котором тоже есть опция компиляции снижающая размер исполняемого файла (не грузить все возможные функции, а только указанные вручную).
В итоге минимальное opengl приложение весит 10кб.
XNResourceEditorPortable которым вырезал ресурс PACKAGEINFO, который дельфи зачем-то добавляет в экзешник. Он примерно 512 байт, поэтому на размере экзешника это вообще может не сказаться, но после упаковки получается экономия на килобайт.
kkrunchy (точнее kkrunchy_023a4_asm07.exe из найденной FordPerfectом ссылки), обеспечивает финальное сжатие с 299008 до 61952 байт.

Конечно, до размера в 96к сильно не дотянул, и даже в размер 64к уложился без дополнительных усилий по экономии, так что все эти методы скорее на будущее, если будет конкурс 32к (но не 4к, там придется использовать crinkler и соответственно отказываться от стандартной библиотеки).

Контент -
1. для генерации текстур использовал свою переделку TFScript, для которой сделал "макроязык" (просто пронумеровал все доступные команды), так чтобы генерация текстур состояла не из последовательности вызова команд, а из набора чисел.

Для экспериментов сделал утилиту которая этот макроязык генерит из псевдокода

Итого в финальной версии 19 текстур, из которых 5 вообще без изменений взяты из примеров TFScript, остальные получены полуосмысленным ковырянием функций и подбором параметров. На будущее понимаю что имело бы смысл сделать более подробную утилиту показывающую содержимое промежуточных массивов, чтобы сделать эксперименты чуть более осмысленными. С другой стороны - не уверен что это бы помогло, как делается "бамп" или что-то осмысленное я все равно по-хорошему не разобрался, а красивые рандомные узоры можно и так генерить.

2. Шрифт. Нарисован вручную в собственной утилите:

Там и русский и английский и большие буквы и маленькие.
Ну, как вручную - там серым цветом рисовался Times New Roman 300-го размера, а я его обводил стараясь привязаться к сетке покрупнее и обвести минимальным числом линий. Потом автоматически размеры и смещение подогнал, ну и некоторые буквы подправил.
Результат получился так себе на маленьких размерах, но на больших выглядит более-менее.

3. Модель зомби. Скриптом на руби сконвертирована из модели отсюда: http://opengameart.org/content/zombie-0 в файл с константами.
Та модель анимированная, но до анимации я так и не дошел.

4. Карта города
Расположение домов генерируется с помощью BSP, так чтобы получались "улицы" с выравненными домами. Правда изнутри этого почти не видно. Но я отлаживал алгоритм в такой утилите и смотрел с разными масштабами.

Комнаты в домах - тоже что-то типа BSP, правда большинства задумок не успел сделать, и даже двери отображенные в утилите фиолетовым в игре сделал просто отсутствием стены.

Алгоритмы
Физика - самописная и кривая, я считал стены прямоугольниками а игрока точкой, а надо было прямоугольниками с полукругом на концах. Поначалу физику отлаживал в утилите с картинки выше, но потом забил и получилось то что получилось, на углах застревания нет, но зато иногда можно проходить сквозь стену. Я подозреваю что большинство смертей вызвано этим, потому что сам так и не смог пока пройти, всегда убивают со спины. При том что СПАУНА НЕТ, а зомбей я всегда проверяю и если что делаю контрольный в голову.

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

Шейдеры - мое первое знакомство с освещением. Т.к. единственный источник света совпадает с игроком, то теней нет, несколькими параметрами настраивается интенсивность "луча" и рассеянного света в зависимости от заряда батареек игрока. В ранних версиях луч был более интенсивным, но потом я понял что это издевательство и усилил рассеянный свет. Правда наверное слегка переборщил. Если доводить до ума - надо было бы чтобы с полным уровнем батареек был хороший и фонарик и фоновый свет, при среднем - оставался только луч света, при низком и нулевом - луч постепенно угасал и и оставалось равномерное "ночное видение".
Для анализа выстрелов используется чтение из текстуры, при выстреле рисую в буфер глубину до цели и номер зомби\головы зомби в точке. Первое используется чтобы узнать где рисовать партиклы от выстрела, второе для смерти\оглушения зомби. Подозреваю что такой метод устарел и сейчас делают физикой с учетом баллистики пули, но на фоне всего остального неважно.
Из неприкрученных возможностей opengl с которыми планировал разобраться остались MRT, UBO, MSAA.

Язык FreeBasic
GUI для разработки своя. Отслеживает кол-во команд asm по группам, и изменения в размере выходного файла. Далее сжимает через Upack.
kkrunchy не использовал т.к. Upack распаковывает быстрее и "менее популярный" для антивирусов.
Иконку добавлял отдельно, редактором ресурсов.

Звук.
Всего 11 звуков. Генерируются, там, всякими формулами.

Музыка

В игре всего 5 партитур. Писал сам.

В игре 44 уровня. Рисовал сам.
FPS решил сделать фиксированным, т.к. игра хардкорная и все события на уровнях должны точно повторять эти события у другого игрока. Кадр в кадр.
Спрайты сгенерированны и нарисованы примитивными командами line, pset, paint, circle. Всего 34 спрайта.
Карта рисуется в 4 слоя: Обзор ботов, "тень" от стен/игровые объекты, радиусы от орудий, стены/ящики/двери/боты
Для ботов делал трассировку лучей по карте в секторе видимости, чтобы показать обзор бота. Рисуется самописным, закрашенным полигоном.
Джойстик
Все данные хранятся строковыми переменными.

Язык:  C++.
Компилятор - mingw32-g++.exe (tdm-1) 4.7.1.
IDE - Code::Blocks 13.12.
Сжатие: kkrunchy_023a4_asm07.
С самого начала выбрал kkrunchy, а не UPX, на случай, если места не хватит. Считаю, что удачно. UPX на моём файле вообще дохнет. Кстати, кто-то может, пожалуйста, попробовать у себя - вдруг у меня ему тупо памяти не хватило. С crinkler не стал разбираться.
kkrunchy не любит TLS (thread local storage), который MinGW использует по умолчанию. Решил отключением startup code и кастомной точкой входа. Задокументированно здесь:
http://www.gamedev.ru/projects/forum/?id=198179&page=27#m402
http://www.gamedev.ru/projects/forum/?id=198179&page=37#m546 → http://www.gamedev.ru/projects/forum/?id=198179&page=37#m547
В результате этого отвалились наследование, RTTI, exceptions.
Также отвалилась инициализация объектов со статическим временем жизни (причём иногда без предупреждения - компилируется, линкуется нормально, но в памяти нули, т. к. конструкторы не вызвались). Всё с нетривиальными конструкторами - живёт на куче или локально.
Стандартная библиотека C используется; линковка динамическая (к msvcrt.dll, которая system library, а не C runtime - http://blogs.msdn.com/b/oldnewthing/archive/2014/04/11/10516280.aspx ).
Т. к. в ней не все версии функций (есть sqrt, но не sqrtf), то вся математика в коде обёрнута в касты (сделать хелпер-функции руки не дошли):
http://www.gamedev.ru/projects/forum/?id=198179&page=53#m790

Опции:
Компиляция:
-std=c++11 -Wextra -Wall -Wconversion -fno-exceptions -fno-rtti -Os
Линковка:
-nostdlib -Wl,-e_entry -s  -lcrtdll -lkernel32 -luser32 -lgdi32 -lopengl32 -lglu32 -lgcc -lwinmm -mwindows

Векторная/матричная алгебра - на шаблонах. Чуть code bloat, но сильно меньше, чем я боялся. Плюс код похожий, kkrunchy его жмёт хорошо. Вектор параметризован типом. В коде используются 2 вида: vec{2/3/4}<float> vec{2/3/4}<int32_t>.

Технологии: отталкивался от OpenGL 1.1 (без расширений) для графики, waveOut для звука, WinAPI для вызовов ОС.
Т. к. OpenGL 1.1, то на мультитекстуру не закладывался. Detail texture рисуется 2-м проходом, с

glDepthFunc(GL_LEQUAL);
glPolygonOffset(-1.0f,-1.0f);

и мультипликативным блендингом. Detail textures - низкоконтрастные, цвет обычно в диапазоне [0.75 .. 1.0].
Освещение - вершинное, динамическое. Для стен софтварно считаются цвета в вершинах от 16 ближайших (что-то умнее, типа "наиболее сильных" не стал делать) источников. Для объектов - встроенное OpenGL освещение, для каждого видимого объекта сначала находятся 8 ближайших источников (столько в OpenGL).
Небо - скролящаяся текстура, в зависимости от движения игрока.
Прозрачка - сортируется и рисуется за 1 вызов, т. к. лежит вся в одном атласе (tex_all_things_transparent). Это, в частности, означает, что для всего используется 1 тип блендинга - обычный, не аддитивный. Вроде на огне тоже сносно смотрится, вопреки conventional wisdom. Цвет фаерболов в текстуре уводится в ярко-оранжевый по мере увеличения прозрачности.
Звук - свой примитивный движок (sound.hpp, sound.cpp, sound_win32.cpp) поверх waveOut. Позиционирование, всякое такое. Чуть глючный. Архитектурно вдохновлялся OpenAL, но намного проще.

Большая часть кода - переностимая, платформонезависимая. Win32-specific - в 2-х файлах (os_win32.cpp и sound_win32.cpp). Асм-вставок, SIMD - нет.

Вообще, код очень low-tech, много хардкода.
Видимость определяется порталами. Бажит, подпёрто костылями. Вроде работает, но в комнате с Артефактом (большое открытое помещение) - тормозит.
Монстры апдейтятся каждый кадр все, во всём лабиринте. Их что-то около 2000 (3000 если считать грибы).
Collision detection - bounding box'ами, всё. Кроме взрывов, которые отдельно. Фаерболы квадратные, а взрывы от них круглые.
Всё состояние мира хранится в переменной world.state. Quick save = fwrite. Указателей там нет, только индексы.
GUI - страшный, хардкод.

No malloc per frame. Да, вобщем, и незачем.
Соответственно, сложных динамических структур тоже не густо.
Текст пишется в предвыделенные буферы. Буферы ресайзится не умеют, по переполнению дропают ввод.
Все сущности (монстры, двери, etc.) - одного типа (Entity), полиморфизма нет. Поля Entity реюзаются, чтобы хранить разное. Фаербол в hp хранит дамаг, в mp - радиус. Дверь (и сундук) - в hp степень открытости.
У Player'а есть ещё немного отдельных свойств.

Генерация:
Музыка: MIDI заэмбежен в файл (в чуть сжатом виде). Из него на стартапе генерируется PCM.
Шрифт: Взят \(\LaTeX\)'овский \mathfrak и нарисован в однобитную текстуру. Текстура заэмбежена в файл, из неё на стартапе получается jittered-версия, которая даёт полупрозрачность.
Текстуры: кодом, основываясь на примитивах:

прототипировалось в отдельной тулзе, тоже кодом с примерно теми же примитивами (но она быстрее компилируется и запускается).
Текстуры итемов - затенением аналитически заданного heightfield.
Звуки: Прототипировались в
https://jsfiddle.net/arfp072t/
потом практически дословно переносились в код.
Шагов - 8 штук.
Спасибо foxes за его версию звука монетки.
Лабиринт: сетка (x&y&1)==1 к которой в цикле добавляются случайные стены до указанного количества циклов. Если добавление делает уровень неодновсязным - стену убираем.
Спуск/подъём - случайно, не очень близко к предыдущим/следующим. Верхние/нижние - фиксированы.
Монстры - в случайных пустых клетках в количестве соответствующем глубине.
Итемы - спавнятся в сундуках/монстрах/магазинах. Пропорции определяются из весовых коэффициентов, зависящих от глубины. Параметры итема - рандомные, в зависимости от параметра quality, который тоже зависит от глубины (по-разному, в магазинах качественные вещи появляются раньше.)
Меши: большинство - деформацией сферы, аналитически. Слизняки - marching tetrahedra, 32 кадра. Бабочки - marching tetrahedra, 1 кадр (крылья отдельно).

Исходники можно глянуть здесь: https://github.com/Panzerschrek/Micro-F
Язык: С++
Компилятор и IDE: Microsoft Visual Studio C++ 2008
Сжатие: Тестировался на UPX, специальным скриптом вёл лог размера. Ближе к концу конкурса обаружил, что .kkrunchy даёт примерно на 5 кб лучший результат. Но за предел не вышел не на одном упаковщике.

Игровой уровень:
ландшафт генерируется обычным шумом. В ландшафте проризается река, строящаяся по контрольным точкам. Всё что ниже некого уровня - считается водой. Деревья расставляются по алгоритму poisson disc sampling с плотностью, уменьшающейся при отдалении от реки.
Модели:
В игре есть набор заранее заготовленных моделей, сделанных вручную и сохранённых в очень компактном формате. Так хранятся модели самолётов, подбираемых предметов. Деревья генерируются процедурно - сначала ствол-цилиндр, а потом к нему добавляются модели кроны. Крона - замоделена вручную как икосаэдр с немного растопыренными треугольниками.
Текстуры:
Есть стандартный набор функций - шум, клеточная текстура, шестиугольная сетка, градиенты и т. д. Ничего особенного вроде нету. Модели текстурировались раскраской вручную в Blender, с последующим восстановлением похожей на нарисованную текстуру в игре.
Графика:
Игру я решил делать с упором на графон, использовал OpenGL 3.3 по полной.  Для отражений весь мир рисовался в текстуру, уменьшенную в 2 раза. Я даже запилил какие-то волны, но они вышли не очень. Освещение очень простое - один источник света и константное фоновое освещение. На самолётах использовализь блики, с глянцевостью, задаваемой в альфе текстуры. Для теней мир рисовался в теневую карту, использовалась техника GPSM (http://www.gamedev.ru/code/articles/GPSM). Для рисования тысяч деревьев использовал инстансинг. Самозатенение на самолётах делалось стенсильными тенями, теневые объёмы считались для каждого треугольника отдельно в геометрическом шейдере. Конечно это не очень оптимально, но на низкополигональных моделях оно не тормозило. На подбираемых предметах использовался специальный шейдер, дающий интересное переливание цветов.
Небо - особая гордость. Для расчёта цвета используется perez sky model. Облака генерируются во фргментном шейдере, трассировкой луча в скалярное поле, определяющем плотность облаков. Облака освещаются солнцем, затеняются, свет рассеивается. Для ночного режима генерируется луна по низкодетализированной заготовленной однобитной текстуре. Звёзды распределяются случайно и равномерно по небесной сфере.
Система частиц:
Все эффекты в игре сделаны через частицы. Частицы имеют скорость, ускорение, время жизни. Каждый тип имеет свои особые параметры эволюции во времени. Частицы имеют собственную светимость, прозрачность, диффузный свет. Рассчитываются частицы на CPU, перед отрисовкой они сортируются от ближних к дальним. Рисуются они за один проход с хитрым смещиванием, выполняемым частично в шейдере.
Игровой процесс:
Для самолётов используется приближенная к реальность, хоть и немного упрощённая. Параметры у всех самолётов одинаковые, на создание разных самолётов не хватило времени. Чтобы хоть как-то можно было управлять самолётом, в игру встроена система стабилизации, которая работает на погашение угловой скорости в осях, по которым нету сигнала управления от пользователя. Искусственный Интеллект управляет теми-же самыми самолётами, никаких преимуществ у него нет. ИИ умет поворачивать, преследовать игрока, выходить на нужную высоту. Научить поворачивать было сложнее всего. Оружие у игрока и у ботов - пулемёты с разными характеристиками для каждого типа самолёта, но боты не имеют ракет.
GUI:
Простой самописный интерфес. Состоит из затекстурированных вкадратов и текстов. Шрифт в игре один  - заранее припасённая текстура со шрифтом fixedsys. Текстуры контрольной панели все честно генерируются, а вот иконки на навигационном шаре припасены заранее.
Звук:
Для звуков игры использовался DirectSound. Это позволило честный трёхмерный звук и даже эффект Доплера. Генеруются звуки из синусоид, шума, квадратного сигнала. Музыка довольно проста - мелодия в формате midi зашита в игру и выводится через mciSendCommand.

Монстры, генерация:
slime: 32 на стартапе просчитанных кадра . Каждый - marching tetrahedra, 33 шарика, формулы влоб те же, что и в http://chrishecker.com/My_liner_notes_for_spore#cite_ref-3 . Текстурные координаты - тупо из пространственных - нормируем вектор, дальше проекция (не меркатор, но похоже). Центры шариков - фигуры Лиссажу зависящие от номера кадра, с поворотом.
acidfly: Marching tetrahedra, 5 шариков, центры по параболе. Текстурные координаты - так же, как и для слизняка. Текстура от гриба. Крылья - 2 полупрозрачных прямоугольника.
floating eye: Деформированная сфера. Сфера - рекурсивное разбиение октаэдра в 4⁴ раз. Текстурные координаты - из изначальных пространственных координат (до деформации) точек на сфере.
mantispider: Набор примитивов (шип, блин, шарик), из которых он собирается чисто в рендере. Тупой хардкод. Лапы двигаются по синусоидам, амплитуда зависит от скорости паука, подбиралось так, чтобы визуально было поменьше проскальзывания. Текстуры реюзались дерева и камня.
balefire: чисто частицами. Двигаются по фигурам Лиссажу.

AI у монстров тупой. Floating eye вообще не агрессивен, и игрока игнорирует. Раз в 2 (вроде) секунды выбирает новое направление и получает импульс в нём. Матрица ориентации плавно меняется, приближая "вперёд" к текущей скорости.
Остальные - ползают рандомно, похожим образом, пока не заметят игрока (тупо по расстоянию, могут сквозь стены). Дальше - прут прямо на игрока (точнее, раз в сколько-то фреймов получают импульс в направлении игрока). И атакуют по cooldown. У дистанционных может заканчиваться мана, которая медленно регенерирует, но её дофига.

Генерация лабиринта:
Лабиринт - 32x64x32 блоков, всего 65536.
Верхний уровень - небо.
Блок занимает 8 бит: solidness (2 bits: 00=empty, 01=stairs_bottom, 10=stairs_top, 11=solid), direction (2 bits: 0..3 = {+x,-z,-x,+z}, важно только для stairs), material (4 bits: sandstone, cobblestone, sky, marble, etc.).
2 этапа.
1. Генерация камня (gen_dungeon.cpp).
1.1. Генерация переходов между уровнями. Рандом, не слишком близко от предыдущего, не слишком близко от входа, Артефакта.
1.2. Для уровня генерируется сетка: (x&z&1)==1:

#.#.#.#.#.
..........
#.#.#.#.#.
..........

1.3. Дальше для уровня ставятся внешние стены, вырезаются дырки возле переходов наверх/вниз.
1.4. Дальше - рандомное добавление стен не портящих односвязность (проверяется BFS).
1.5. И так - для всех уровней.
1.6. Верхний и нижний - special case. В верхнием дырка на верх и нет подъёма. В нижнем - нет спуска и платформа для Артефакта. Также вырезано пространствно под комнату для Артефакта (на предыдущем этапе оно заполнено сплошняком). Единственная комната высоты больше 1.
1.7. "Раскраска" блоков видами камня. Вид камня - в зависимости от высоты, с рандомной добавкой (random dithering).
2. Добавление сущностей (game.cpp:spawn_initial_entities).
2.1. Массив 65536 клеток - "занятость". Больше одной сущности в клетку не добавляются. Пространство у входа/Артефакта помечено как занятое.
2.2. Уникальные объекты: входная дверь, лестница, артефакт.
2.3. Грибы. Рандомом в подходящих местах (сверху есть на чём ему расти).
2.4. Монстры. Рандомом в зависимости от уровня. Пытается спавнить n штук, если клетка занята или стена спавн не удался. Удаётся около половины. Значения n:
slime: \(n=\lfloor \frac{y}{2} \rfloor + 5\)
floating eye: \(n=10-(\frac{y}{2}-25)^2\)
acidfly: \(n=20-\frac{(\frac{y}{2}-17)^2}{5}\)
mantispider: \(n=17-\frac{(\frac{y}{2}-12)^2}{5}\)
balefire: \(n=17-\frac{(\frac{y}{2}-5)^2}{5}\)
где y - высота, отсчитывая снизу: \(\mathrm{dungeon level}=\lfloor \frac{64-y}{2} \rfloor\)
2.5. Двери, магазины, сундуки. Рандомом, в подходящих местах до определённого максимума на уровень или определённого числа попыток на уровень. Для дверей подходят клетки с 2 соседями с противоположных сторон. Для сундуков/магазинов - тупики (3 соседа).
2.6. Генерация итемов в сундуках/магазинах/монстрах. Трупы наследуют лут монстра.