Случайная выборка с учетом веса

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

Я написал особую реализацию алгоритма такой выборки – она работает не с обычными массивами, а с перечислениями (enum). В шаблон функции передаются два перечисления – самих элементов и их весов. Этот пример иллюстрирует также богатые возможности метапрограммирования, CTFE и интроспекции в D.

import std.stdio;
import std.traits;
import std.random;
import std.algorithm;

T weightedRandomEnum(T, W)()
    if (isNumeric!W &&
        is(T == enum) && is(W == enum) && 
        EnumMembers!T.length == EnumMembers!W.length)
{
    enum members = [EnumMembers!T];
    enum weights = [EnumMembers!W];
    enum weightsSum = reduce!("a + b")([EnumMembers!W]);
    
    auto randomNumber = uniform(0, weightsSum);
    
    foreach(i, weight; weights)
    {
        if (randomNumber < weight)
            return members[i];
        else
            randomNumber -= weight;
    }
    
    assert(0, "Should never get here");
}

enum Color
{
    Red, Yellow, Green, Blue
}

enum Weights
{
    Red = 100, 
    Yellow = 20, 
    Green = 20, 
    Blue = 5
}

void main()
{
    foreach(i; 0..10)
        writeln(weightedRandomEnum!(Color, Weights));
}

Обновление dlib

Состоялось серьезное обновление набора библиотек dlib. В числе нововведений:

  • Появилась начальная поддержка быстрого преобразования Фурье (FFT) в dlib.image. Возможна фильтрация и свертка изображений (со стороной 2^n) в частотной области;
  • Обновлен пакет dlib.math, добавлена реализация комплексных и дуальных чисел, а также внесены исправления и дополнения в dlib.math.matrix3x3 и dlib.math.matrix4x4;
  • Обновлен пакет dlib.geometry, добавлен класс ориентированных боксов (OBB), трехмерных треугольников и полигональных мешей. Реализована проверка на пересечение между сферой и треугольником, а также сферой и OBB. Добавлен модуль dlib.geometry.bezier с реализацией кривых Безье.

Иллюстрация FFT-свертки: быстрое синтетическое боке (оптическое размытие):

Изменения доступны в ревизии r21 и выше. В ближайшем будущем ожидается первый релиз проекта.

http://code.google.com/p/dlib/

Дао программиста

Некоторые из принципов, которых я придерживаюсь в своей работе, можно выразить в виде вот таких афоризмов:

1. Лучшая программа — это та, которая не была написана.

2. Простота — мать надежности.

3. Сложное должно быть простым.

4. Обычный программист думает: «Как сделать так, чтобы оно работало?»
   Хакер думает: «Как сделать так, чтобы оно не сломалось?»
  
5. Оптимизация — это зло.

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

8. Хороший код не нуждается в комментариях.

9. Красивое решение — правильное решение.

10. Улучшить порой сложнее, чем переписать заново.

Пример физики на движке Chipmunk

Пример рисования мышью многоугольников, которые сразу же начинают «жить» в физическом мире. В качестве физического движка используется ChipmunkD — прямой порт Chipmunk на D. Демка может быть использована в качестве основы для physics-based 2D-игры. Единственное ограничение — поддерживаются только выпуклые многоугольники, неконвексная геометрия просто отсеивается и не тесселируется до простых форм.

В архиве — исходники и сборки для Win32 и Linux x86:
polyshaper-all-platforms.zip (1.16 МБ)

Внимание! Пример писался достаточно давно — исходный код, скорее всего, не скомпилируется современными версиями DMD без дополнительных «танцев с бубном».

Обновление dlib

Была значительно обновлена коллекция библиотек dlib: добавлены новые модули в пакет geometry (реализация AABB и сфер, а также пересечений между ними), исправлен баг с нахождением обратной матрицы 4×4, добавлен модуль dlib.math.matrix3x3, а также несколько полезных функций для векторов, матриц и кватернионов. Изменения доступны в ревизии r12 и выше.

http://code.google.com/p/dlib/

Физический движок

Не писал уже целый месяц, приношу за это извинения читателям этого блога =) Месяц ушел на создание каркаса физического движка для Atrium. Для решения контактов используется метод Sequential Impulses, поддерживается трение. На данный момент реализованы два типа геометрических объектов — сфера и бесконечная плоскость. Интегрирование пока производится методом Эйлера, планируется поддержка метода Рунге-Кутты.

В представленной демке симулируется система из 6 шаров и плоскости. Красным шаром можно управлять с клавиатуры (клавиши-стрелки). Зеленый шар имеет повышенную массу, большой шар — пониженную.

Сборка для Linux:
physics-testbuild1-linux-glibc28-x86.tar.bz2

Эффект затенения

«Честные» динамические тени в аркадных 3D-играх не всегда бывают уместны. Как правило, разработчики ограничиваются статическими предрассчитанными тенями от неподвижных объектов и простым темным кружочком на земле под персонажем – дешево и сердито =)  Я решил дополнить этот нехитрый метод одной простой, но важной деталью: изменение яркости персонажа в зависимости от его местоположения – в тени или на свету. 

Цвет для яркости будет считываться из карты освещения, в которой «запечены» все статические тени на карте.

Допустим, у вас есть некий блок кода, в котором вы находите точку на поверхности полигона под ногами персонажа:

// Проверяем факт пересечения
IntrStatus istatus = character.downRay.intersectTriangle(tri);
if (istatus.hit)
{
  // Извлекаем точку пересечения
  Vector3f ipt = istatus.intersectionPoint;  
  
  if (ipt.y > currentFloorHeight)
  {
    currentFloorHeight = ipt.y;
    
    // Берем материал полигона
    Material mat = materialByIndex[tri.matIndex];
    
    // Если нет карты освещения (текстура 1), то ничего не делаем
    if (mat.textures[1])
    {
      // Берем изображение карты освещения
      Image lightmap = imageByIndex[mat.textures[1].imgIndex];
      
      // Находим текстурные координаты точки пересечения
      Vector2f tc = triObjSpaceToTexSpace(tri.vertices, tri.texCoords2, ipt);
      
      // Конвертируем текстурные координаты в дискретные
      uint imgX = cast(uint)(tc.x * lightmap.width - 0.5f);
      uint imgY = cast(uint)(tc.y * lightmap.height - 0.5f);
      
      // Считываем цвет пикселя c карты освещения
      Color lumel = lightmap[imgX, imgY];
      
      // Применяем полученный цвет к материалу персонажа
      chMaterial.ambientColor = lumel;
      chMaterial.diffuseColor = lumel;
      chMaterial.specularColor = lumel;
    }
  }
}

Осталось определить функцию triObjSpaceToTexSpace. Она будет использовать барицентрические координаты:

Vector2f triObjSpaceToTexSpace(
  Vector3f[3] vertices, 
  Vector2f[3] texCoords, 
  Vector3f point)
{ 
  Vector3f v0 = vertices[2] - vertices[0];
  Vector3f v1 = vertices[1] - vertices[0];
  Vector3f v2 = point - vertices[0];

  float dot00 = dot(v0, v0);
  float dot01 = dot(v0, v1);
  float dot02 = dot(v0, v2);
  float dot11 = dot(v1, v1);
  float dot12 = dot(v1, v2);

  float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01);
  float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
  float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
      
  Vector2f t2 = texCoords[1] - texCoords[0];
  Vector2f t1 = texCoords[2] - texCoords[0];

  return texCoords[0] + t1 * u + t2 * v;
}

Atrium собирается последней версией LDC

Совсем недавно вышла бета-версия готовящегося к релизу LDC 0.10.0 — компилятора D, использующего LLVM для генерации машинного кода.

Решив проверить LDC на практике, я только что собрал им Atrium. Результат очень обрадовал, при компиляции в релизном режиме и с уровнем оптимизаций -O3, LDC выдал весьма шустрый код: ~100 FPS против ~80 у DMD 2.060! При этом я всего один раз столкнулся с необходимостью поправить исходники — при использовании ассоциативного массива указателей.

Как вывод: LDC вполне созрел для использовании в качестве основного компилятора D под Linux — во всяком случае, для работы с OpenGL и графикой реального времени. К сожалению, я не в курсе, как у него обстоят дела c поддержкой Windows — надеюсь, со временем этот вопрос устаканится. 

Почему я выбираю Linux?

Последние два года часто приходится слышать о том, что Linux на десктопах «не выстрелил». И что место его – в нише серверов, суперкомпьютеров, встраиваемых систем и мобильных устройств (в качестве Android, MeeGo и др). Не хочется сейчас касаться бессмысленных холиваров а ля «под Линукс нету Фотошопа» – я не буду оправдывать систему перед геймерами, домохозяйками, «офисным планктоном» и прочим подобным контингентом, равно как и агитировать кого-либо переходить на нее. Я просто намерен объяснить, что именно в Linux привлекает среднестатистического хакера – компьютерного энтузиаста-«кулибина», которого, как это ни парадоксально, интересует не наличие прикладного софта, а именно его отсутствие – чтобы был стимул написать свой! В моем случае – отсутствие игр (малый ассортимент, если быть точным). Именно этот факт послужил первой причиной выбора Linux в качестве основной целевой платформы разработки.

Под Linux мало игр – следовательно, высока вероятность, что ваш проект будет оценен по достоинству и получит свою долю популярности. Сравните это с рынком Windows, который настолько перенасыщен, что у «новоприбывших» практически нет никаких шансов – конкуренция слишком высока. Это, конечно, не значит что качественные инди-проекты остаются совсем незамеченными (вспомните историю той же Portal), но факт остается фактом: мир Windows диктует свои правила, и не все в нем способны выжить. Кстати, это относится не только к играм…

В то же время, было бы некорректно утверждать, что мир Linux не диктует никаких правил. Диктует, и еще как. Это вселенная OpenSource, и вам придется так или иначе отдать дань сообществу СПО за то, что пользуетесь свободными программами в своей работе. Неважно, каким именно способом – открытием своих исходников, вкладом в другие открытые проекты, материальным пожертвованием и т. д. Разумеется, это правило неписанное, оно не значится в лицензионных соглашениях. Это скорее этический принцип. Всякий, кто приходит в этот мир, впечатлившись идеалами свободы, горит желанием стать частью движения, чтобы выразить свою благодарность сообществу. И, на мой взгляд, создание свободного игрового проекта – один из лучших способов сделать это.
Поскольку Linux создавался «программистами для программистов», в нем все ориентировано, в первую очередь, на разработку новых и совершенствование существующих инструментов. К примеру, почти все дистрибутивы идут в комлекте с компилятором GCC и рантаймом языка Python – пользователь может запросто, сразу после установки, начать программировать. Сравните это с Windows, где для написания даже простейшего «Hello, World» нужно устанавливать навороченные IDE – часто платные и весьма требовательные к ресурсам. Конечно, можно и в Windows обустроить себе уютное linux-like окружение: установить MinGW или другой набор свободных компиляторов, Posix-утилиты, все необходимые библиотеки – многие так и делают, особенно если нужен кроссплатформенный toolchain. Суть в том, что в Linux этот набор инструментов присутствует изначально. Linux дружественен к разработчику: это заметно везде, в любых мелочах. Вплоть до того, что все линуксовые текстовые редакторы, даже самые простые, поддерживают подсветку синтаксиса.

Есть еще один момент: по очевидным причинам, в Linux доступен только один трехмерный API – OpenGL. В среде программистов бытует устойчивое «суеверие», касающееся интерфейсов разработки 3D-приложений: о том, что для игр больше подходит DirectX, а ниша OpenGL – САПР, промышленная визуализация и научно-исследовательское моделирование. Это происходит из-за дилетантской попытки сравнивать OpenGL именно с DirectX, а не Direct3D. Как известно, DirectX – это не только трехмерная и двумерная графика, но и звук, сеть, взаимодействие с устройствами ввода, библиотеки вспомогательных функций и многое другое. Более корректное сравнение выглядит следующим образом: DirectX vs OpenGL+OpenAL+SDL+FreeType. А это уже, согласитесь, внушительный «арсенал». Причем, доступный не только под Windows и Linux, но и ряд других платформ. А кто станет спорить с тем, что кроссплатформеность – это хорошо?OpenGL в наши дни не просто идеально подходит для разработки игр – на мобильных платформах это и вовсе единственный выбор. Хотите поддержки Android или iOS? Можете забыть о Direct3D. OpenGL – ваш лучший друг.

Разумеется, нельзя забывать о том, что на программировании свет клином не сошелся. Нужны еще средства подготовки контента. Здесь опять на ум приходит вопрос «фотошопов» и «3ds max’ов», но, положа руку на сердце, скажите – неужели для создания моделей, текстур и спрайтов вам недостаточно Blender, GIMP, Inkscape и MyPaint? Photoshop всегда был и остается инструментом фотографов и специалистов по печати, а 3ds max – архитекторов и дизайнеров по интерьерам. Использование этих дорогих и тяжеловесных «монстров» для работы с маленькими изображениями и низкополигональными моделями явно неоправдано. Выходит, в миграции на оупенсорс художникам мешает только консерватизм и сила привычки.

Было бы несправедливо обойти стороной объективные недостатки Linux как десктопной игровой платформы. Если отставить в сторону всякие мифы, суеверия, психологические барьеры, тролль-аргументы вроде «1 процента», остается, на мой взгляд, всего два пункта:

1. Пресловутый «зоопарк дистрибутивов». Даже в рамках одного дистрибутива не так-то просто добиться идеальной совместимости бинарных релизов со всеми версиями ОС – что и говорить о десятках (!) разных операционок… Можно, конечно, нацелиться только на один популярный дистрибутив – скажем, на ту же Ubuntu – и говорить, что все остальное официально не поддерживается. Но это не в духе Linux, за такое пользователи вас добрым словом не помянут. Если ваша игра распространяется по свободной лицензии, можно посылать всех самостоятельно компилировать ее из исходников. Есть и третий вариант – как мне кажется, наиболее вменяемый: официально выпускать один универсальный бинарный релиз, собранный для старой версии Glibc (скажем, 2.7) и имеющий минимум зависимостей, а индивидуальные пакеты для всех популярных дистров поддерживать на базе сообщества. Так делают, например, разработчики Blender. И на протяжении 10 лет у них это успешно получается.

2. Ситуация с видеодрайверами. Производители видеокарт все еще ориентируются, в основном, на Windows. Драйверы для всего остального обычно запаздывают с выходом и уступают по качеству. Но поддержка Linuх не так плоха, как могла бы быть. Если у вас видеокарта от NVIDIA или Intel, можно радоваться, но ситуация с AMD значительно хуже…

Как видите, оба пункта отнюдь не смертельны и для большинства линуксоидов совершенно не критичны. Думаю, излишне упоминать о стабильности, надежности и безопасности Linux-систем, и в качестве хост-системы для различных разработок и экспериментов они не имеют равных.