WC3
Добавлен Vlod,
опубликован
Алгоритмы, Наработки и Способности
Способ реализации:
cJass
Тип:
Наработка
Версия Warcraft:
1.26a
Введение
Основные определения
Зачем это нужно?
Не редко случайный разброс используется при написании карт/игр. Начиная с выбора персонажа, дропа предмета, шанса крита, до генерации шума и создания карты высот.
Описание
Линейный конгруэнтный генератор
Использует простую формулу для получения последовательности:
Xn+1 = (a * Xn – c) mod M;
a, c, M – особые константы; X[0, M-1]; период <= M.
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 число битов в мантиссе вещественного числа.
В данной реализации 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
Используется один генератор, выбираемый при инициализации.
Lagged Fibonacci Generator.w3m
Используется один генератор, выбираемый при инициализации.
Multi Linear Congruent Generator.w3m
Multi Lagged Fibonacci Generator.w3m
Тут можно создать "объект" генератора. Подходит, если вам нужно несколько одинаковых генераторов или несколько разных генераторов.
Multi Lagged Fibonacci Generator.w3m
Тут можно создать "объект" генератора. Подходит, если вам нужно несколько одинаковых генераторов или несколько разных генераторов.
источники:
Дополнительно
исследование генераторов
Сначала пытались исследовать встроенный генератор.
посмотрели его начальные значения, сымитировали работу.
посмотрели его начальные значения, сымитировали работу.
Обход генератора оказался слишком долгим,
поэтому отказываемся от любых сравнительных тестов и для работы выбираем генератор поменьше.
поэтому отказываемся от любых сравнительных тестов и для работы выбираем генератор поменьше.
Каждое число в нашем генераторе внутри 1 периода встречается 1 раз, совпадений нету.
Качество генератора зависит от качества перемешивания чисел.
Поверим автору статьи и его источникам (таблица хороших констант)
и переходим к другим важным прикладным вопросам.
Качество генератора зависит от качества перемешивания чисел.
Поверим автору статьи и его источникам (таблица хороших констант)
и переходим к другим важным прикладным вопросам.
требования:
Хочу рандом, чтобы 25%, чтобы четверть из ста ударов, но не рандом который контролируешь, а рандом который рандом, но 25%, может наука есть которая рандом изучает я хз
Наши генераторы имеют равномерное распределение. Значение случайной величины на всем диапазоне равновероятно, в отличии от нормального распределения.
Смотрим на график - видим почти белый шум:
Реализуем первый вариант. Для r и f берем текущее и прошлое значение генератора.
Конечно, иногда может быть круто, задавая границы [0,50] получить в ответ 150.
Пробуем второй вариант:
Получаем слишком большой разброс, корректируем res=z1*z2 по примеру
Визуально величина схожа с нормальной.
Нужны точные границы!
Видим, что график смещает случайную величину определенным образом.
В формуле есть какая-то erf, нам такое не подходит.
Почему бы не заменить этот график на другой, достаточно точно совпадающий?
В формуле есть какая-то erf, нам такое не подходит.
Почему бы не заменить этот график на другой, достаточно точно совпадающий?
Самая простая функция такого вида что я видел была в статье о шуме Перлина, как сглаживающая функция. Smoothstep, открываем подраздел этих функций, берем первые 2 типа, смотрим:
Отлично, первая совпадает, строим графики:
Втф, что это. Шум явно изменился, и дело точно не в погрешности.
С помощью бумаги и ручки был создан набросок интересующей нас функции, которая должна сплющивать или стягивать значения к центру.
Сравнив это с тем, что мы делали, прояснилась ключевая ошибка.
Пошаманив над графиком, получилось.
Придется выражать обратную функцию, но со смузером это не прокатит.
Шел вечер пятницы, время поджимало.
Погрузившись в чертоги разума, вспомнились функции активации нейрона.
Подбираем за пару минут коэффициенты.
Погрузившись в чертоги разума, вспомнились функции активации нейрона.
Подбираем за пару минут коэффициенты.
С утреца, подготавливая эти материалы, обнаружил список функций класса сигмоид. Оно и хорошо, логарифма то в варкрафте нет!
Результаты порадовали, впереди еще предстояла проверка других генераторов.
Результаты:
Для преобразования равномерного распределения в близкое к нормальному предлагается следующая формула: y = 0.5 + tan( (x-0.5)*2.17391 )*0.25
где y/x - новое/старое значение сл. величины [0,1]
где 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Результаты:
| \ | native | LCG | MLCG | LFG | MLFG |
|---|---|---|---|---|---|
| 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 себе в карту.
`
ОЖИДАНИЕ РЕКЛАМЫ...
Чтобы оставить комментарий, пожалуйста, войдите на сайт.
Честно говоря, можете не отвечать, чтобы не тратить своё время. Всё равно сам автор делал это не для практического применения, а просто на cJass формулы решил попечатать.
Отредактирован prog
А генерация на действия.
Vlod,
Отредактирован Jack-of-shadow
Дабы имитировать переход с карты на карту.
На старте генератор выбирает с какого индекса начать, а далее идет смещение.
Так зная всего лишь начальный индекс, можно сгенерировать точно такую же карту.
Самое простое что приходит в голову, это:
Mod(A+C,B)
Где C это "случайное" число из таблицы. А - B диапазон.
ScorpioT1000, реализации криптостойких генераторов уже есть, при необходимости их можно проверить с помощью, например, NIST.
KingMaximax, как вариант - изменить распределение случайной величины
Jack-of-shadow, есть вариант конвертировать Rand в [0.,1.] и растягивать до [min,max]
min + ( Rand / (M-1) )*(max-min) для LCG
prog, шум - это же не генератор, для генерации карт использую мультиоктавный шум, но не выкладывать же один вид.
кстати, diamond-square мне вообще не зашел.
KingMaximax, быстрее нативного никак не получится, а насчет пользы, тут каждый решает сам: кому-то нужен отдельный генератор, кому-то - более надежный, а кто-то хотел написать сам, будет в помощь
8gabriel8, спасибо за лайк)
На самом деле подобный генератор реализовать для первого десятка целых чисел очень просто, конкретно в этом случае надо задать последовательность из четырёх значений, случайное из которых будет выделяться, типа 0010 или НетНетДаНет. Происходящее событие будет запускать триггер, он будет проверять значение рандома и делать нужные действия, если выпал шанс, потом сдвигать счётчик рандома, если значение счётчика выше максимального, то последовательность рандома формируется заново и счётчик сдвигается в её начало. Но всё не так просто, когда шанс дробный, например, 11/23 - это почти каждый второй шанс, то есть не должно быть так, чтобы из 23 раз все выпадения оказались в начале или в конце, нужно их распределить аккуратно через раз, сделав при необходимости в последовательности одно дополнительное невыпадение.
Отредактирован prog
В комменты все пишут, потому что все около-айти, а айтишных вещей на сайте появляется сейчас мало