Алгоритмы, Наработки и Способности
Способ реализации:
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 себе в карту.
`
ОЖИДАНИЕ РЕКЛАМЫ...

Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
1
24
5 лет назад
1
8gabriel8, представь ситуацию, когда генерация происходит не мгновенно и в процессе генерации срабатывает триггер с получением случайного числа, не связанный с генерацией карты - в результате одно число из потока псевдослучайных чисел не попадает в генератор карты и результат генерации получается совсем другим, чем если бы этот сторонний триггер не сработал в этот момент.
0
27
5 лет назад
0
напомнило что то об генерации лабиринта, когда стены и проходы генерируются
0
29
5 лет назад
0
Жуть, пошла мапмейкерская политота, оные меня поймут, что я имел ввиду.
Vlod,
для Влода
люди хотят полезный рандом, а не научные работы, как высказался милорд Скорп Тысячный.    Отойди больше от стандартов и сделайте наподобие, который привёл мсье Скорп, или же сделайте свой, который будет очень полезен и более быстр для системы шансов и пуллинга. При этом не теряя такие качества скорости. Т.е. сделайте полезный псевдо-рандом, с любовью, слово от "Матери Программирования". Короче рандом с золотой серединный, а не с сундуком алчного графа.
заметка: Я считаю, что тем весьма интересная, и требует большего подхода и возможностей генерации, как их числа принципов и различных преимуществ.
0
17
5 лет назад
0
Я считаю, что тем весьма интересная, и требует большего подхода и возможностей генерации, как их числа принципов и различных преимуществ.
Да и на мимопроходящих это обсуждение оказывает благотворное влияние. Периодически появляются вопросы "Хочу рандом, чтобы 25%, чтобы четверть из ста ударов, но не рандом который контролируешь, а рандом который рандом, но 25%, может наука есть которая рандом изучает я хз". А теперь таким можно сюда ссылку дать.
0
25
5 лет назад
Отредактирован Jack-of-shadow
0
Тоже собирался писать псевдо рандом, для генератора карт.
Дабы имитировать переход с карты на карту.

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

Вот только не думал, как дальше использовать число, если нужен диапазон.
Самое простое что приходит в голову, это:
Mod(A+C,B)
Где C это "случайное" число из таблицы. А - B диапазон.
0
26
5 лет назад
0
quq_CCCP:
8gabriel8, ну генератор же линейный, любое событие с генерецией рандома - сдвигает счетчик. Но это побходится простым перебором RandomSeed
prog:
8gabriel8, представь ситуацию, когда генерация происходит не мгновенно и в процессе генерации срабатывает триггер с получением случайного числа, не связанный с генерацией карты - в результате одно число из потока псевдослучайных чисел не попадает в генератор карты и результат генерации получается совсем другим, чем если бы этот сторонний триггер не сработал в этот момент.
Да это понятно. Вот происходит генерация, например, каждую секунду выбор из четырёх вариантов, когда в первом нужно возвышеность сделать, во втором низину, в третьем дерево посадить, а в четвёртом зелёную лужайку. По действиям игрока за секунду произошло два выпадения рандома, потому при генерации выпала не возвышенность, а дерево. Так и что? Насколько это критичным оказалось для рандомной генерации? Если только рандом не используется в костыльной роли чёткого алгоритма, когда все "случайные" результаты должны быть точно известны.
0
32
5 лет назад
0
8gabriel8, вот для этого достаточно менять RandomSeed на лету и все будет норм.
0
26
5 лет назад
0
quq_CCCP, полностью согласен, но мне же пытаются объяснить, что разные реализации рандома важны и нужны)
1
24
5 лет назад
1
8gabriel8, позволь напомнить тебе постановку задачи - выдача одинакового ланда при одинаковом сиде и разного ланда при разном сиде. И это не костыль, это достаточно распространенная практика при случайной генерации, здорово помогающая при отладке.
достаточно менять RandomSeed на лету и все будет норм
Если бы была возможность получить текущий сид, еще можно было бы как-то плясать с бубном вокруг этого, но такой возможности нет, сид можно только задать. Да и заворачивать каждый вызов рандома в проверку на то какой из сидов должен использоваться, подставлять его, запоминать новый - не кажется ли вам что проще отдельный генератор потока случайных чисел написать, чем возиться с этим?
0
26
5 лет назад
0
prog:
выдача одинакового ланда при одинаковом сиде и разного ланда при разном сиде
Может просто не так понимаю значение в данном случае слова "одинаковый", но разве не имеется ввиду то, что одинаковым должен быть алгоритм генерации, состоя из определённых значений, последовательность которых могут нарушить действия игрока с рандомом, которые перетянут часть значений на себя? То есть рандом в данном случае аналогичен точному алгоритму?
0
24
5 лет назад
0
8gabriel8, в этом и фишка, что результат такой генерации зависит от одного единственного числа (сид), меняем это число и получаем другой результат, не меняем это число, получаем одинаковый результат. В результате получаем возможность зная сид получить результат который уже получали раньше и, соответственно, возможность тестировать что-то в одинаковых условиях, не смотря на рандомную природу генератора, а также возможность надежно воспроизвести какую-то ситуацию, если это нужно. Естественно, игрок получает случайный сид и, соответственно, случайный результат генерации, в отличии от разработчика в отладочном режиме.
Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.