Лучшая случайная функция в JavaScript

В настоящее время я делаю воспроизведение Conway Game of Life в JavaScript, и я заметил, что функция Math.random() всегда возвращает определенный шаблон. Здесь образец рандомизированного результата в сетке 100x100:

Кто-нибудь знает, как получить лучшие рандомизированные числа?

ApplyRandom: function() {

    var $this = Evolution;

    var total = $this.Settings.grid_x * $this.Settings.grid_y;
    var range = parseInt(total * ($this.Settings.randomPercentage / 100));

    for(var i = 0; i < total; i++) {
      $this.Infos.grid[i] = false;
    }

    for(var i = 0; i < range; i++) {
      var random = Math.floor((Math.random() * total) + 1);
      $this.Infos.grid[random] = true;
    }

    $this.PrintGrid();
  },

[ОБНОВЛЕНИЕ]

Я создал jsFiddle здесь: http://jsfiddle.net/5Xrs7/1/

[ОБНОВЛЕНИЕ]

Кажется, что Math.random() был в порядке после всех (спасибо raina77ow). Извините, народ!:( Если вас интересует результат, здесь обновленная версия игры: http://jsfiddle.net/sAKFQ/

(Но я думаю, что там остались некоторые ошибки...)

Ответ 1

Эта строка в вашем коде...

var position = (y * 10) + x;

... это то, что вызывает эту "неслучайность". Это действительно должно быть...

var position = (y * $this.Settings.grid_x) + x;

Я полагаю, что 10 был исходным размером этой сетки, поэтому он здесь. Но это явно неправильно: вы должны выбрать свою позицию на основе текущего размера сетки.

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

var bias = $this.Settings.randomPercentage / 100;
for (var i = 0; i < total; i++) {
  $this.Infos.grid[i] = Math.random() < bias;
}

С этим изменением вы больше не будете страдать от побочного эффекта повторного использования одних и тех же чисел в строке var random = Math.floor((Math.random() * total) + 1);, которая снизила фактическую заполняемость ячейки в исходном коде.

Ответ 2

Math.random - это псевдослучайный метод, поэтому вы получаете эти результаты. A by pass часто используется для того, чтобы поймать позицию курсора мыши, чтобы добавить соль к результатам Math.random:

Math.random=(function(rand) {
  var salt=0;
  document.addEventListener('mousemove',function(event) {
    salt=event.pageX*event.pageY;
    });
return function() { return (rand()+(1/(1+salt)))%1; };
})(Math.random);

Это не совсем случайно, но немного больше;)

Ответ 3

Лучшее решение, вероятно, не случайным образом выбирает очки и нарисовывает их черными, но чтобы пройти через каждую точку, решить, какие шансы они должны быть заполнены, а затем заполнить соответственно. (То есть, если вы хотите, чтобы он в среднем на 20% превышал вероятность его заполнения, генерируйте свое случайное число r и заполните, когда r < 0.2 я видел симулятор Life в WebGL и тот, что он делает для инициализации...IIRC.

Изменить: Здесь еще одна причина, чтобы рассмотреть альтернативные методы живописи. В то время как случайный выбор пикселей может закончиться меньшим количеством работы и меньшим вызовом вашего генератора случайных чисел, что может быть хорошо, в зависимости от того, что вы хотите. Как бы то ни было, вы, похоже, выбрали способ, в котором будет заполнен не более процентов ваших пикселей. ЕСЛИ вы следили за заполняемыми пикселями и выбрали заполнение другого пикселя, если он уже был заполнен, по сути, все ваши действия перетасовывают точный процент черных пикселей среди ваших белых пикселей. Сделайте это по-своему, и процент выбранных пикселей будет соответствовать биномиальному распределению. Иногда процент заполняется будет немного больше, иногда немного меньше. Набор всех перетасовки является строгим подмножеством возможностей, порождающих подобный выбор (который, строго говоря, содержит все возможности для рисования доски, просто с астрономически низким шансом получить большинство из них). Проще говоря, случайный выбор для каждого пикселя позволит увеличить дисперсию.

Затем я мог бы изменить алгоритм перетасовки, чтобы выбрать процент пикселей, основанный на числах, генерируемых функцией биномиального распределения вероятности с определенным ожидаемым/средним значением вместо самого ожидаемого/среднего значения, и я честно не знайте, что это будет по-другому, по крайней мере теоретически, чем выполнение коэффициентов для каждого пикселя с ожидаемым/средним значением. Там многое можно сделать.

Ответ 4

Вы можете попробовать

JavaScript Crypto Library (лицензия BSD). Предполагается, что он имеет хороший генератор случайных чисел. См. здесь пример использования.
Стэнфордская криптографическая библиотека JavaScript (лицензия BSD или GPL). См. документация для случайных чисел.

Для обсуждения силы Math.random() см. этот вопрос.

Ответ 5

Реализация Math.random, вероятно, основана на линейном конгруэнтном генераторе , одна слабость которой заключается в том, что случайное число зависит от более раннего значение, создавая предсказуемые шаблоны, подобные этому, в зависимости от выбора констант в алгоритме. Известный пример эффекта плохого выбора констант можно увидеть в RANDU.

Генератор случайных чисел Mersenne Twister не обладает этой слабостью. Вы можете найти реализацию MT в JavaScript, например здесь: https://gist.github.com/banksean/300494

Обновление: Увидев ваш код, у вас есть проблема в коде, который отображает сетку. Эта строка:

var position = (y * 10) + x;

Должно быть:

var position = (y * grid_x) + x;

При этом исправлении нет заметного шаблона.