Как получить случайную последовательность чисел? Спойлер:«Никак»

Год назад я написал свою первую игру на контроллере Arduino. Игрок искал кубик и, проходя лабиринт, должен был успеть съесть его. Еда появлялась в «абсолютно случайном» месте, а время с каждым раундом все уменьшалось. Из-за своего распиздяйства того, что времени доделать игру было мало, она весила очень много, геймплей был никаким, а рандома не было. Последнее я заметил только тогда, когда показывал свою игру людям. Игру доделать хочется, поэтому нужно решить проблему с рандомом, начну с него.

В arduino есть готовая функция рандомизации, но семя не меняется, хоть и есть возможность использовать внутреннее время. Последовательность никогда не меняется. Я могу записывать последнее число в энергонезависимую память контролера, а потом просто начинать с него, но эта часть памяти просто прожигает нужное значение и долго играть будет нельзя, на год только хватит. Нужно писать свой алгоритм ГПСЧ.

СТОП!!! Скорее всего, вы не особо понимаете, что происходит, или думаете, что понимаете. Давайте я начну из далека и объясню некоторые основы рандома.

Как компьютер генерирует случайные числа

Компьютер не может выбрать случайное число, он вообще ничего выбирать не может, выполняя только наши указания. Поэтому нам нужно написать функцию, которая сгенерирует хоть какую-нибудь последовательность. Пусть она будет линейной.

R(x) = x + 1

Теперь наша последовательность будет такой:
0,1,2,3,4,5,6,7,8…
Не очено похоже на случайную последовательность. Пусть теперь R добавляет константу вместо 1.

1R(x) = x + c

Если с равняется, например, 7, то мы получим ряд 1, 8, 15, 22, … Всё ещё не то. Очевидно, что мы упускаем то, что числа не должны только увеличиваться, они должны быть разбросаны по какому-то диапазону. Нам нужно, чтобы наша последовательность возвращалась в начало — круг из чисел!

Посмотрим на циферблат часов: наш ряд начинается с 1 и идёт по кругу до 12. Но поскольку мы работаем с компьютером, пусть вместо 12 будет 0.

Теперь начиная с 1 снова будем прибавлять 7. Прогресс! Мы видим, что после 12 наш ряд начинает повторяться, независимо от того, с какого числа начать.

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

Теперь давайте переделаем функцию R так, чтобы она соответствовала нашей логике. Ограничить длину цикла можно с помощью оператора модуля или оператора остатка от деления.

R(x) = (x + c) % m

На этом этапе вы можете заметить, что некоторые числа не подходят для c. Если c = 4, и мы начали с 1, наша последовательность была бы 1, 5, 9, 1, 5, 9, 1, 5, 9, … что нам конечно же не подходит, потому что эта последовательность абсолютно не случайная. Становится понятно, что числа, которые мы выбираем для длины цикла и длины прыжка должны быть связаны особым образом.

Если вы попробуете несколько разных значений, то сможете увидеть одно свойство: m и с должны быть взаимно простыми.

До сих пор мы делали «прыжки» за счёт добавления, но что если использовать умножение? Умножим х на константу a.

R(x) = (ax + c) % m

Свойства, которым должно подчиняться а, чтобы образовался полный цикл, немного более специфичны. Чтобы создать верный цикл:

1. (а — 1) должно делиться на все простые множители m
2. (а — 1) должно делиться на 4, если m делится на 4

Но этого не достаточно, нам нужна случайность из вне, семя. Мы могли бы сделать его константой. Это может пригодиться в тех случаях, когда вам нужны случайные числа, но при этом нужно, чтобы при каждом запуске программы они были одинаковые. Например, создание одинаковой карты для каждой игры.

Еще один способ — это получать семя из нового источника каждый раз при запуске программы, как в системных часах. Это пригодится в случае, когда нужно общее рандомное число, как в программе с расположением кубика.

Но на самом деле, это все еще не рандом. Простая формула, предсказуемое семя. Через несколько миллионов итераций все повторится. Поэтому нам нужен алгоритм сложнее, но это уже будет и текст сложнее. Это все Генератор ПсевдоСлучайных Чисел, он использует единственное начальное значение, откуда и следует его псевдослучайность, в то время как Генератор Случайных Чисел всегда формирует случайное число, имея в начале высококачественную случайную величину, которая берется из различных источников энтропии.

Источник: m.vk.com

Комментарии: