Непрерывное взвешенное случайное распределение, смещенное к одному концу

28

В настоящее время я участвую в создании системы частиц для нашей игры и разрабатываю некоторые формы эмиттеров.

Мое равномерное случайное распределение вдоль линии или вдоль прямоугольной области работает нормально - нет проблем.

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

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

didito
источник
Никто не собирается упоминать исчисление?
Алек Тил

Ответы:

42

Посмотрите на эту картинку:

Кривая картирования

Он показывает процесс отображения (случайного) значения на кривую. Предположим, вы генерируете равномерно распределенное случайное значение X в диапазоне от 0 до 1. Посредством сопоставления этого значения с кривой - или, другими словами, используя f (X) вместо X - вы можете искажать свое распределение любым удобным вам способом. ,

На этом рисунке первая кривая делает более высокие значения более вероятными; второе делает более низкие значения более вероятными; и третий делает кластер ценностей в середине. Точная формула кривой не очень важна и может быть выбрана, как вам нравится.

Например, первая кривая выглядит как квадратный корень, а вторая - как квадрат. Третий немного похож на куб, только переведенный. Если вы считаете, что квадратный корень слишком медленный, первая кривая также выглядит как f (X) = 1- (1-X) ^ 2 - инверсия квадрата. Или гипербола: f (X) = 2X / (1 + X).

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

Эта общая техника очень проста и эффективна. Какое бы распределение вам ни понадобилось, просто представьте себе кривое отображение, и вы быстро разработаете формулу. Или, если у вашего движка есть редактор, просто создайте визуальный редактор для кривой!

Не берите в голову
источник
Большое спасибо за ваше очень подробное и понятное объяснение. все остальные посты тоже были очень полезны, но я действительно мог понять ваш пост самым простым и быстрым. это высунулось до н.э. это действительно попало в точку моего понимания вещей. и аспекты, которые вы объясняете, это именно то, что я искал (или бродил)! это позволит мне использовать это во многих случаях в будущем. так что спасибо снова !!! Кстати, я играл с некоторыми из ваших кривых из них, и это работает как шарм.
Didito
5
К вашему сведению: это так называемые квантильные функции: en.wikipedia.org/wiki/Quantile_function
Нил Г
8

Более длинное объяснение:

Если у вас есть желаемое распределение вероятностей, такое как запрашиваемый градиент @didito, вы можете описать его как функцию. Допустим, вы хотите треугольное распределение, где вероятность в 0 равна 0.0, и вы хотите выбрать случайное число от 0 до 1. Мы можем записать его как y = x.

Следующим шагом является вычисление интеграла этой функции. В этом случае это . Оценивается от 0 до 1, это ½. Это имеет смысл - это треугольник с основанием 1 и высотой 1, поэтому его площадь равна ½.Иксзнак равно1Икс2

Затем вы выбираете случайную точку равномерно от 0 до области (½ в нашем примере). Давайте назовем это z. (Мы выбираем равномерно из совокупного распределения .)

Следующий шаг - вернуться назад, чтобы найти, какое значение x (назовем его x̂) соответствует области z. Мы ищем , оцененный от 0 до x̂, равный z. Когда вы решите для , вы получите .Иксзнак равно1Икс21Икс̂2знак равноZИкс̂знак равно2Z

В этом примере вы выбираете z от 0 до ½, а затем требуемое случайное число равно . Упрощенно, вы можете написать это как - именно то, что рекомендовал электронный бизнес.2ZрaNd(0,1)

amitp
источник
спасибо за ваш ценный вклад. Мне всегда нравится слышать, как опытные люди решают проблемы. но я все еще должен обернуть голову вокруг этого, чтобы быть честным ...
Didito
это круто. Я всегда делал sqrt(random())всю свою жизнь, но я пришел к этому эмпирически. Попытка привязать случайное число к кривой, и это сработало. Теперь, когда я немного разбираюсь в математике, очень важно знать, почему это работает!
Густаво Масиэль
5

Вы, вероятно, получите близкое приближение к тому, что вы хотите, используя экспоненциальную систему.

Сделайте x основанным на чем-то вроде 1- (значение rnd ^) (при условии, что значение rnd находится в диапазоне от 0 до 1), и вы получите несколько различных вариантов поведения перекоса слева направо в зависимости от того, что вы используете. Более высокое значение даст вам более искаженное распределение

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

РЕДАКТИРОВАТЬ

Для чего-то вроде системы частиц, где время ЦП на частицу очень важно, использование Math.Pow (или языкового эквивалента) напрямую может привести к снижению производительности. Если требуется больше производительности и значение не изменяется во время выполнения, рассмотрите возможность переключения на эквивалентную функцию, такую ​​как x * x вместо x ^ 2.

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

Лунин
источник
1
Вместо того, чтобы использовать графическую программу, вы можете просто построить распределение бета-версии, поскольку это особый случай. Для данного value, это бета (значение, 1).
Нил Дж
Спасибо. Я попытался построить некоторые графики, и я думаю, что это может привести меня туда, куда я хочу.
Didito
@Neil G спасибо за совет с «бета-дистрибуцией» - это звучит интересно и полезно ... я
проведу
3

Вы ищете Weighted Random Numbersискомый термин: большинство алгоритмов, которые я видел, используют функции триггера, но я думаю, что я нашел способ, который будет эффективен:

Создайте таблицу / массив / список (что угодно), который содержит значение множителя для случайной функции. Заполните это вручную или программно ...

randMulti= {.1,.1,.1,.1,.1,.1,.2,.2,.3,.3,.9,1,1,1,} 

... затем умножьте randomна случайно выбранный randMultiи, наконец, на максимальное значение распределения ...

weightedRandom = math.random()*randMulti[Math.random(randMulti.length)]*maxValue

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

AttackingHobo
источник
2
Если вы можете пожертвовать памятью, таблица из 100 предварительно вычисленных значений будет быстрее (и немного более точной). Я сомневаюсь, что пользователь сможет различить полную и предварительно вычисленную версии.
Даниэль Блезек
@Daniel это будет быстрее, но с 100 случайными значениями, довольно легко увидеть повторяющиеся шаблоны.
AttackingHobo
Тот факт, что существует повторяющаяся модель, не означает, что она не случайна. Сущность случайности заключается в ее непредсказуемости, что буквально означает, что если нельзя предсказать, что не будет шаблона, нельзя также предсказать, что он может быть (по крайней мере, на короткое время). Вам придется провести некоторое тестирование, но если вы обнаружите шаблоны с несколькими тестами, использующими разные начальные числа, тогда ваш алгоритм генерации псевдослучайных чисел может потребоваться пересмотреть.
Рэндольф Ричардсон
@ AttackingHobo спасибо за этот трюк. Мне нравится использование LUT. и формула довольно легко понять. я не думал об этом раньше. не видя дрова для деревьев ... :) также я думаю, что следует избегать повторяющихся узоров, но в любом случае, вероятно, их не узнают. тем не менее, предварительное вычисление всех значений повредит визуальному восприятию. в любом случае, спасибо за напоминание о том, что это фактор, который нужно учитывать на тему случайности ...
Didito
также спасибо за то, что подняли термин «Случайные числа»!
Didito
2

Я думаю, что вы просите распределение, полученное с помощью функции квадратного корня.

[position] = sqrt(rand(0, 1))

Это даст распределение в одномерном поле, [0, 1]где вероятность позиции эквивалентна этой позиции, то есть «треугольное распределение».

Альтернативное поколение без корней:

[position] = 1-abs(rand(0, 1)-rand(0, 1))

Квадратный корень в оптимальной реализации - это всего лишь несколько команд умножения и суммирования без ветвей. (См .: http://en.wikipedia.org/wiki/Fast_inverse_square_root ). Какая из этих двух функций быстрее, зависит от платформы и случайного генератора. Например, на платформе x86 потребуется всего несколько непредсказуемых ветвей в генераторе случайных чисел, чтобы замедлить второй метод.

AAAAAAAAAAAA
источник
Вероятность позиции не будет равна позиции (это математически невозможно - тривиально, область и диапазон функции включают как 0,50, так и 0,51), а также треугольное распределение. ( en.wikipedia.org/wiki/Triangular_distribution )
1
Несмотря на то, что sqrt дает некоторые интересные шаблоны, системы частиц, как правило, должны быть очень легкими для процессора на частицу, поэтому я рекомендовал бы по возможности избегать квадратных корней (которые являются вычислительно медленными). Иногда вы можете сойти с рук, просто предварительно вычислив их, но это может сделать ваши частицы со временем заметными.
Лунин
1
@Joe Wreschnig, вы читали эту статью в Википедии сами, напишите a = 0, b = 1, c = 1 в формуле генерации, и вы получите формулу в моем посте.
аааааааааааа
3
@ Лунин, почему ты жалуешься на квадратный корень, когда у тебя есть показатель в ответе?
аааааааааааа
1
@Lunin: Теория производительности - довольно заброшенная область, многое из того, что люди думают, что они знают, где-то приблизительно 30 лет назад, когда ALU были большими, дорогими и медленными. Даже функция экспоненты, которая, как вы только что обнаружили, является довольно медленной арифметической функцией, редко является очень существенным фактором снижения производительности. Ветвление (с использованием оператора if) и пропадание кеша (чтение части данных, которые в данный момент не находятся в кеше) - это обычно то, что стоит больше всего производительности.
аааааааааааа
1

Просто используйте бета-дистрибутив:

  • Бета (1,1) является плоской
  • Бета (1,2) является линейным градиентом
  • Бета (1,3) является квадратичной

и т.п.

Два параметра формы не обязательно должны быть целыми числами.

Нил Г
источник
спасибо за вашу помощь. как указано выше, бета-версия звучит интересно. но я пока не могу понять содержание страницы википедии. или формула / код. ну, у меня и сейчас нет времени на дальнейшие исследования: я вижу, что у boost есть код для бета-дистрибутивов, но это было бы излишним. ну, я думаю, мне нужно сначала пройти через это, а затем написать свою упрощенную версию.
Didito
1
@didito: Это не так сложно. Вы просто заменяете свой uniform_generator()звонок на gsl_ran_beta(rng, a, b). Смотрите здесь: gnu.org/software/gsl/manual/html_node/…
Нил Г,
спасибо за подсказку. Я не использую GSL (на самом деле не слышал об этом раньше), но хороший звонок. я проверю источник!
Didito
@didito: В этом случае я бы пошел с решением Лунина. Удачи.
Нил Дж
0

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

Или, еще проще, где X является результатом ГСЧ, во- первых double y = double(1/x);, x = y*[maximum return value of rng];. Это будет взвешивать числа в геометрической прогрессии до более низких чисел.

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

Конечно, это работает только для стандартных распределений кривых колокольчиков или их «свернутых» версий *, но с быстрым генератором это может быть быстрее и проще, чем использование различных математических функций, таких как sqrt.

Вы можете найти все виды исследований по этому вопросу для кривых колокольчиков. На самом деле, Anydice.com является хорошим сайтом, который генерирует графики для различных методов бросания костей. Хотя вы используете ГСЧ, предпосылка такая же, как и результаты. Так что это хорошее место для просмотра дистрибутива еще до того, как его кодировать

* Кроме того, вы можете «сложить» распределение результатов по оси, взяв ось и вычтя усредненный результат, а затем добавив ось. Например, вы хотите, чтобы более низкие значения были более распространенными, и допустим, что вы хотите, чтобы 15 было вашим минимальным значением, а 35 - вашим максимальным значением, диапазон 20. Таким образом, вы генерируете и усредняете вместе два значения с диапазоном 20 ( в два раза больше желаемого диапазона), что даст колокольчик с центром в 20 (мы вычитаем пять в конце, чтобы сместить диапазон с 20 до 40, с 15 до 35). Возьмите сгенерированные числа X и Y.

Финальный номер,

z =(x+y)/2;// average them
If (z<20){z = (20-z)+20;}// fold if below axis
return z-5;// return value adjusted to desired range

Если ноль - ваш минимум, даже лучше, сделайте это вместо этого,

z= (x+y)/2;
If (z<20){z = 20-z;}
else {z = z - 20;}
return z;
TheAlicornSage
источник