Алгоритмы, Наработки и Способности
Способ реализации:
cJass
Тип:
Наработка
Версия Warcraft:
1.26a

Введение

Зачем это нужно?
Не редко случайный разброс используется при написании карт/игр. Начиная с выбора персонажа, дропа предмета, шанса крита, до генерации шума и создания карты высот.

Описание

Линейный конгруэнтный генератор
Использует простую формулу для получения последовательности:
Xn+1 = (a * Xn – c) mod M;
a, c, M – особые константы; X[0, M-1]; период <= M.
Запаздывающий генератор Фибоначчи
Позволяет получить более высокое "качество" псевдослучайных чисел.
В данной реализации Ki:
{ Ki-a – Ki-b, если Ki-a >= Ki-b
{ Ki-a – Ki-b + 1, если Ki-a < Ki-b
a, b – особые константы; K[0, 1]; период = (2^max(a,b) - 1) * 2^l, где l число битов в мантиссе вещественного числа.

Функционал

  • получить/установить зерно (для линейного конгруэнтного генератора);
  • случайный real в диапазонах: [0,1], [0,max], [min,max];
  • случайный int в диапазонах: [0,max], [min,max].
Linear Congruent Generator.w3m
Lagged Fibonacci Generator.w3m
Используется один генератор, выбираемый при инициализации.
Multi Linear Congruent Generator.w3m
Multi Lagged Fibonacci Generator.w3m
Тут можно создать "объект" генератора. Подходит, если вам нужно несколько одинаковых генераторов или несколько разных генераторов.
источники:

Дополнительно

исследование генераторов
Сначала пытались исследовать встроенный генератор.
посмотрели его начальные значения, сымитировали работу.
Обход генератора оказался слишком долгим,
поэтому отказываемся от любых сравнительных тестов и для работы выбираем генератор поменьше.
Каждое число в нашем генераторе внутри 1 периода встречается 1 раз, совпадений нету.
Качество генератора зависит от качества перемешивания чисел.
Поверим автору статьи и его источникам (таблица хороших констант)
и переходим к другим важным прикладным вопросам.
требования:
Хочу рандом, чтобы 25%, чтобы четверть из ста ударов, но не рандом который контролируешь, а рандом который рандом, но 25%, может наука есть которая рандом изучает я хз
Наши генераторы имеют равномерное распределение. Значение случайной величины на всем диапазоне равновероятно, в отличии от нормального распределения.
Смотрим на график - видим почти белый шум:
Реализуем первый вариант. Для r и f берем текущее и прошлое значение генератора.
Конечно, иногда может быть круто, задавая границы [0,50] получить в ответ 150.
Пробуем второй вариант:
Получаем слишком большой разброс, корректируем res=z1*z2 по примеру
Визуально величина схожа с нормальной.
Нужны точные границы!
Видим, что график смещает случайную величину определенным образом.
В формуле есть какая-то erf, нам такое не подходит.
Почему бы не заменить этот график на другой, достаточно точно совпадающий?
Самая простая функция такого вида что я видел была в статье о шуме Перлина, как сглаживающая функция. Smoothstep, открываем подраздел этих функций, берем первые 2 типа, смотрим:
Отлично, первая совпадает, строим графики:
Втф, что это. Шум явно изменился, и дело точно не в погрешности.
С помощью бумаги и ручки был создан набросок интересующей нас функции, которая должна сплющивать или стягивать значения к центру.
Сравнив это с тем, что мы делали, прояснилась ключевая ошибка.
Пошаманив над графиком, получилось.
Придется выражать обратную функцию, но со смузером это не прокатит.
Шел вечер пятницы, время поджимало.
Погрузившись в чертоги разума, вспомнились функции активации нейрона.
Подбираем за пару минут коэффициенты.
С утреца, подготавливая эти материалы, обнаружил список функций класса сигмоид. Оно и хорошо, логарифма то в варкрафте нет!
Результаты порадовали, впереди еще предстояла проверка других генераторов.

Результаты:

Для преобразования равномерного распределения в близкое к нормальному предлагается следующая формула: y = 0.5 + tan( (x-0.5)*2.17391 )*0.25
где y/x - новое/старое значение сл. величины [0,1]

Заключение

почему не jass
Перегрузка функций;
Компактность и прозрачность кода.
об integer
Из-за отсутствия беззнакового типа допущение переполнения int может привести к неопределенному поведению, что накладывает некоторые ограничения на реализацию линейного конгруэнтного генератора.
тест на скорость
Тест оценивает, во сколько раз текущие генераторы сильнее нагружают лимит операций
относительно оригинальной функции. Эксперимент проводился с помощью:
code
integer INT = 0
function MyCode takes nothing returns nothing
	// ...initialization
	TriggerSleepAction(0.)
  loop
    //q = LCG_randr(g,20.,100.)
    //i = LCG_randi(g,2,20)
    INT++
  endloop
endfunction

function PostMyCode takes nothing returns nothing
  TriggerSleepAction(0.3)
  printi(INT)
endfunction
Результаты:
\nativeLCGMLCGLFGMLFG
int(0,max) 23076 (1) 5172 (4.4) 3896 (5.9) 5660 (4) 4225 (5.4)
int(min,max) 21428 (1) 4545 (4.7) 3529 (6) 4918 (4.3) 3796 (5.6)
real(0,1) 23076 (1) 6382 (3.6) 4545 (5) 7142 (3.2) 5000 (4.6)
real(0,max) 21428 (1) 5882 (3.6) 4285 (5) 6520 (3.2) 4688 (4.5)
real(min,max) 18750 (1) 5084 (3.6) 3846 (4.8) 5555 (3.3) 4225 (4.4)
native GetRandom_() легче в 3.2 - 6 раз.

Установка

список изменений:
  • добавлен LCG, Введение, Описание;
  • добавлен LFG, Заключение, тесты на скорость;
  • добавлено Дополнительно, изменена работа LFG, подкорректированы тесты на скорость, уменьшен размер файлов.
Скопировать папку LCG/LFG себе в карту.
`
ОЖИДАНИЕ РЕКЛАМЫ...

Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
0
37
5 лет назад
Отредактирован ScorpioT1000
0
Кастомный рандом нужен, если требуется защита от атак по времени. Если бы автор замутил аналог OpenSSL random, в этом был бы какой-то смысл (например, генерация токенов), а так просто научная работа =)
1
26
5 лет назад
1
prog:
8gabriel8, одно из применений кастомного рандома - когда нужен рандомный поток не связаный со стандартным, к которому привязаны нативные криты и прочие случайные события.
Что за нужда, например? Хочется же "пощупать" в карте, насколько представленные кастомные виды рандома будут лучше стандартного)
Честно говоря, можете не отвечать, чтобы не тратить своё время. Всё равно сам автор делал это не для практического применения, а просто на cJass формулы решил попечатать.
2
24
5 лет назад
2
8gabriel8, приведу пример того когда мне понадобился отдельный от стандартного поток рандома - в одной из моих карт давным давно использовалась процедурная генерация уровня, причем не один раз заранее, а постоянно по мере движения игрока по карте. Все бы ничего, но я хотел чтобы одинаковый сид всегда выдавал одинаковую результирующую карту, независимо от действий игрока во время генерации и чтобы генерация никак не влияла на действия игрока, кроме невозможности пройти в еще не готовый участок карты. На одном только стандартном рандоме это практически невыполнимо ведь поток рандомных чисел один на все операции.
2
32
5 лет назад
2
prog, нет, у анимаций и визуалок свой, несвязный рандом генератор, а у всего остального другой.
0
24
5 лет назад
Отредактирован prog
0
quq_CCCP, не суть важно сколько там нативных потоков рандома под капотом, суть в том что коду карты доступен только один нативный поток рандома, даже если мне показалось и он не зависит от других действий кроме ручного вызова связанных с ним функций - в условиях когда игровой процесс не прерывается на время работы генератора это чревато засорением рандомного потока либо генератора либо игрового процесса.
0
26
5 лет назад
0
Все бы ничего, но я хотел чтобы одинаковый сид всегда выдавал одинаковую результирующую карту, независимо от действий игрока во время генерации и чтобы генерация никак не влияла на действия игрока, кроме невозможности пройти в еще не готовый участок карты.
Можно поподробнее, а то плохо представляю, как действия игрока влияют на генерацию карты?
А генерация на действия.
0
32
5 лет назад
0
8gabriel8, ну генератор же линейный, любое событие с генерецией рандома - сдвигает счетчик. Но это побходится простым перебором RandomSeed
1
24
5 лет назад
1
8gabriel8, представь ситуацию, когда генерация происходит не мгновенно и в процессе генерации срабатывает триггер с получением случайного числа, не связанный с генерацией карты - в результате одно число из потока псевдослучайных чисел не попадает в генератор карты и результат генерации получается совсем другим, чем если бы этот сторонний триггер не сработал в этот момент.
0
27
5 лет назад
0
напомнило что то об генерации лабиринта, когда стены и проходы генерируются
0
29
5 лет назад
0
Жуть, пошла мапмейкерская политота, оные меня поймут, что я имел ввиду.
Vlod,
для Влода
люди хотят полезный рандом, а не научные работы, как высказался милорд Скорп Тысячный.    Отойди больше от стандартов и сделайте наподобие, который привёл мсье Скорп, или же сделайте свой, который будет очень полезен и более быстр для системы шансов и пуллинга. При этом не теряя такие качества скорости. Т.е. сделайте полезный псевдо-рандом, с любовью, слово от "Матери Программирования". Короче рандом с золотой серединный, а не с сундуком алчного графа.
заметка: Я считаю, что тем весьма интересная, и требует большего подхода и возможностей генерации, как их числа принципов и различных преимуществ.
0
17
5 лет назад
0
Я считаю, что тем весьма интересная, и требует большего подхода и возможностей генерации, как их числа принципов и различных преимуществ.
Да и на мимопроходящих это обсуждение оказывает благотворное влияние. Периодически появляются вопросы "Хочу рандом, чтобы 25%, чтобы четверть из ста ударов, но не рандом который контролируешь, а рандом который рандом, но 25%, может наука есть которая рандом изучает я хз". А теперь таким можно сюда ссылку дать.
Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.