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

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

Я написал особую реализацию алгоритма такой выборки – она работает не с обычными массивами, а с перечислениями (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/

Фиксированный шаг времени

Доступна новая тестовая сборка Atrium: в физическом движке реализован новый таймер, который учитывает интерполяцию между кадрами с фиксированным шагом времени. Физика “не любит” нефиксированный шаг, поэтому время между двумя кадрами рендеринга разбивается на определенное количество шагов, а остаток просто линейно интерполируется.

atrium-physics-test5-linux-x86.tar.bz2

Atrium: интеграция физики

Доступна сборка Atrium со включенным физическим движком. Данная демонстрация показывает возможность создания игры от первого лица на основе физики: объект-игрок тоже представлен динамическим твердым телом (у которого просто отключена угловая скорость) массой в 80 кг. Перемещение игрока осуществляется путем приложения сил в нужных направлениях.

atrium-physics-test2-win32.zip (3.13 Мб)