Алгоритмы, Наработки и Способности
Способ реализации:
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
17
5 лет назад
0
Всем спасибо
ScorpioT1000,
например, генерация токенов
реализации криптостойких генераторов уже есть, при необходимости их можно проверить с помощью, например, NIST.
KingMaximax,
варовский порой выдаёт жестокую частоту, порой вообще шансовое молчание
как вариант - изменить распределение случайной величины
Jack-of-shadow,
как дальше использовать число, если нужен диапазон
есть вариант конвертировать Rand в [0.,1.] и растягивать до [min,max]
min + ( Rand / (M-1) )*(max-min) для LCG
prog,
Еще есть отдельный случай, не реализованный в этой наработке - другие типы рандома, например тот же перлин
шум - это же не генератор, для генерации карт использую мультиоктавный шум, но не выкладывать же один вид.
кстати, diamond-square мне вообще не зашел.
KingMaximax,
который будет очень полезен и более быстр
быстрее нативного никак не получится, а насчет пользы, тут каждый решает сам: кому-то нужен отдельный генератор, кому-то - более надежный, а кто-то хотел написать сам, будет в помощь
8gabriel8, спасибо за лайк)
PS Не ожидал столько комментов. Круто. Пока что я буду занят личными делами и поиском заработка, так что все, на что меня хватит - писать в оффтоп и ставить плюсы. Те, кого заинтересовала эта тема, давайте развивать её и дальше, всегда рад посодействовать по мере свободного времени.
0
26
5 лет назад
0
Сделай чёткий рандом, чтобы при 25% было точно 25%, а не около того)
На самом деле подобный генератор реализовать для первого десятка целых чисел очень просто, конкретно в этом случае надо задать последовательность из четырёх значений, случайное из которых будет выделяться, типа 0010 или НетНетДаНет. Происходящее событие будет запускать триггер, он будет проверять значение рандома и делать нужные действия, если выпал шанс, потом сдвигать счётчик рандома, если значение счётчика выше максимального, то последовательность рандома формируется заново и счётчик сдвигается в её начало. Но всё не так просто, когда шанс дробный, например, 11/23 - это почти каждый второй шанс, то есть не должно быть так, чтобы из 23 раз все выпадения оказались в начале или в конце, нужно их распределить аккуратно через раз, сделав при необходимости в последовательности одно дополнительное невыпадение.
1
24
5 лет назад
Отредактирован prog
1
8gabriel8, есть еще другой способ - сдвигать диапазон "попадания" по мере накопления вызовов, таким образом чтобы среднее кол-во попаданий на нужное кол-во вызовов было правильным. Грубо говоря - повышать реальный шанс срабатывания если среднее кол-во фактических попаданий ниже желаемого и снижать если выше. Но для этого нужен не особый генератор, а надстройка сверху генератора, которая позволяет хранить кол-во вызовов и попаданий для каждого контекста в котором используется.
0
26
5 лет назад
0
Есть готовый вариант, как эту надстройку реализовать?
0
24
5 лет назад
0
8gabriel8, на Lua - легко. На жассе даже пробовать не буду. А если ты конкретно про алгоритм корректировки шанса, то это или по экспериментировать с разными формулами надо будет или по искать статью в сети, близы этот способ в WoW использовали в какой-то момент и вроде кроме близов еще кто-то. Сам я планирую для своей карты такой рандом реализовать для критов и подобного, соответственно свою версию на Lua выложу, но это когда еще будет (не скоро).
0
37
5 лет назад
0
Vlod, причём тут питон?
В комменты все пишут, потому что все около-айти, а айтишных вещей на сайте появляется сейчас мало
0
32
5 лет назад
0
prog, GetRandomInt дает, киниматек бж смотри...
1
24
5 лет назад
1
quq_CCCP, т.е. последовательность SetRandomSeed(100500) GetRandomInt(0, 1000000) выдаст мне на выходе 100500, а не следующее число из потока после 100500?
Впрочем, это ничего не решает - всеравно придется жонглировать сидом туда-сюда постоянно, что не очень удобно.
0
17
5 лет назад
0
8gabriel8:
Сделай чёткий рандом, чтобы при 25% было точно 25%, а не около того)
если в последовательности 1000 неповторяющихся чисел [0,999], то четверть из них будет точно <=0.25, если дело в качестве последовательности, то юзай проверенные константы для генераторов (собственно одна из причин написания сего)
Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.