Алгоритмы, Наработки и Способности
Способ реализации:
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
28
5 лет назад
Отредактирован PT153
0
Какая разница, что ты имеешь на руках его принцип работы, если смысл в СЛУЧАЙНОМ результате?
Большая, потому рандом может быть разный. Мат. ожидание и дисперсия у разных распределений разные. Вдруг мне нужно normal, а варик использует uniform, или наоборот.
0
26
5 лет назад
0
Можно конкретный, а не абстрактный пример в существующей карте?
0
17
5 лет назад
0
оффтоп
Рандом есть рандом
"Генерация случайных чисел слишком важна, чтобы оставлять её на волю случая" Robert Coveyou
Какая разница, что ты имеешь на руках его принцип работы, если смысл в СЛУЧАЙНОМ результате?
Случайные числа — искусственно полученная последовательность реализаций случайной величины с заданным законом распределения (см. Основные определения -> Случайные числа)
PS Если комьюнити xgm посчитает, что этот ресурс каким-то образом вредит сайту, то я его немедленно удалю. Не нужно судить о работе по дате регистрации аккаунта. Прошу вас оставить свою личную неприязнь
0
26
5 лет назад
0
Vlod, дело не в неприязни или вреде сайту, которых нет. Задал простой вопрос:
Vlod, какая была необходимость создавать генератор?
Конкретный пример просто укажи, если его нет, то теоретически что-нибудь приведи, чтобы точно понимать, когда потребуется эта наработка.
2
29
5 лет назад
2
Vlod, никто ничего не имеет против вашей наработки, просто опишите её полезность более подробно, если такая есть.
На сколько эффективен ваш рандом в плане выпадания шансов для способный, т.к. стандартный варовский порой выдаёт жестокую частоту, порой вообще шансовое молчание. Когда ожидаешь иного итога, с направление в среднестатистическое выпадание рандома для опр. задач.
0
26
5 лет назад
0
KingMaximax, даже немного помогаем ответить на вопрос)))
0
28
5 лет назад
Отредактирован PT153
0
KingMaximax, полезность в том, что ты прекрасно знаешь, как работает генерация, гугл в помощь.
Если тебе не особо важно, то забей, используй обычный вариковский (как я, но с небольшими улучшениями).
0
26
5 лет назад
Отредактирован ScorpioT1000
0
Не сочтите за хейт, этот ресурс мне сразу понравился, когда под ним было всего три комментария. В подтверждение лайка скрин:
Но рассчитывал на то, что автор хоть как-то осветит случаи практического применения этих аналогов функции рандома. Потому что вижу необходимость в разных способах реализации только у казино/лотерей, когда обязательно нужно остаться в плюсе при большом количестве разных случайных выпадений. Либо при малом количестве выпадений рандома, которые должны как можно реже повторяться. Но в реализации не увидел заточенности под эти случаи, либо любые другие. Это как умножение реализовать несколькими способами, ты будешь знать, как именно у тебя умножает, во сколько раз это медленнее стандартного умножения, а потому можешь со своим умножением делать что угодно под свою задачу. И если типа это некорректный пример, ведь умножение всегда одинаковый результат выдаёт, а рандом разный, то вы ни одного конкретного примера не указали, когда требуется рандом, который отличен от стандартного.
Загруженные файлы
2
24
5 лет назад
2
8gabriel8, одно из применений кастомного рандома - когда нужен рандомный поток не связаный со стандартным, к которому привязаны нативные криты и прочие случайные события.
Также - в определенных ситуациях у стандартного рандома есть проблемы с распределением и один из вариантов решения этой проблемы это кастомный рандом. Хотя, конечно, есть и другие способы решения этой проблемы, например масштабирование диапазона на котором берется рандом.
Еще есть отдельный случай, не реализованный в этой наработке - другие типы рандома, например тот же перлин, который кроме линейного может быть двух и трех-мерным (можно и больше, но практическое применение под большим вопросом).
0
37
5 лет назад
Отредактирован ScorpioT1000
0
Кастомный рандом нужен, если требуется защита от атак по времени. Если бы автор замутил аналог OpenSSL random, в этом был бы какой-то смысл (например, генерация токенов), а так просто научная работа =)
1
26
5 лет назад
1
prog:
8gabriel8, одно из применений кастомного рандома - когда нужен рандомный поток не связаный со стандартным, к которому привязаны нативные криты и прочие случайные события.
Что за нужда, например? Хочется же "пощупать" в карте, насколько представленные кастомные виды рандома будут лучше стандартного)
Честно говоря, можете не отвечать, чтобы не тратить своё время. Всё равно сам автор делал это не для практического применения, а просто на cJass формулы решил попечатать.
Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.