Логотип проекта Программирование

Генератор массивов псевдослучайных чисел

Предыстория

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

Для игры нужно было добавлять генерируемую часть матрицы текстур, каждый раз когда игрок разведывал карту. Проще: мы добавляли случайные текстуры в сетку карты, каждый раз когда игрок исследовал неоткрытые зоны карты.
По началу мы использовали штатный для Python random.choise(iter), это создавала нормально распределенные карты. Нам это не подошло и мы перешли на numpy.random.choise(iter, v), который распределял элементы из iter по вероятностям из списка v. Позже мы нашли проблему.

Проблема была в самом ГПСЧ, а именно в его последовательности чисел. Выходило что при одном и том же зерне seed карта генерировалась в зависимости от поведения игрока. Например, если игрок исследует карту строго влево, то при следующей игровой сессии игрок исследуя карту направо, получал туже самую карту текстур, но зеркально отраженную, тоже самое и с другими направлениями. Такое поведение генерации карты меня не устроило. Получается не важно где игрок исследует карту, генератор будет расставлять элементы последовательность [a, b, c, d, e, ...] полученную от ГПСЧ последовательно. Таким образом игрок будет видеть одни те жы объекты везде куда не сунется.

Такие ГПСЧ создают объекты с зерном и статусом. Часто в данных статуса лежит текущий указатель множества, именно в зависимости от него, внутренних статичных данных и зерна генератор выдает случайное число (подробнее на wikipedia). Метод choise(iter, v) получает новое число с преобразованием к минимальному максимальному как в методе random.randint(min_, max_) и сверяет его с вероятностями из массива v, так выбирается элемент из iter. для генерации одномерного массива [0, oo+) этого достаточно, но у нас двухмерная матрица, и это выдает не правильное заполнение.

Решением могло стать пересоздания объекта random для каждого заполнения, но мы получаем одно и тоже число. Можно изменять зерно, но это вновь строительство велосипеда, проще создать свой алгоритм не следующий закономерности Xn = f(Xn-1) + C, которой в той или иной формуле следует классический рандомайзер.

Мне пришла иная идея, которая базировалась на хеш-функциях. Хеш-алгоритмы не должны базироваться на их предыдущей итерации, но они могут базироваться на предыдущих входных данных. MD5 из таких алгоритмов. (подробнее на wikipedia)

Реализация

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

В этой задаче нам достаточно создать объект MD5 и один раз передать этому объекту структуру из точки (x, y) и зерна в виде бинарного массива. Пересоздавать объект нужно, так как на преобразование вносимого нового сообщения влияют предыдущие данные, если не пересоздавать объект MD5 то мы вернемся к той же проблеме с последовательностью данных. Тут нам не нужна вся мощь алгоритма в его цикличности.

Ниже представлен код класса который служит оберткой типа random для MD5. Применение такого кода помогло мне решить описанную выше проблему.

Python
import hashlib
import datetime
import pickle


class HashRandom:
    def __init__(self, seed=None, data=None):
        self.seed = seed if seed else int(datetime.datetime.now().timestamp())
        self.data = self._hash_data = self._result = None
        self.m = 6893*2**9 # это число может быть у каждого свое, оно нужно для более большого многообразия псевдочисел для генерации
        if data:
            self.set_data(data)

    # Устанавливаем данные и генерируем результат
    def set_data(self, *data):
        self.data = data
        self._hash_data = hashlib.md5()
        self._hash_data.update(pickle.dumps(tuple(data) + tuple([self.seed])))
        self._result = int(self._hash_data.hexdigest(), 16) % self.m

    # Получаем результат и преобразуем к большее меньшее
    def get_value(self, min_, max_):
        return self._result % (max_ + 1 - min_) + min_

    # Случайно выбираем элемент из массива или генератора в соответствии с вероятностями
    def choice(self, iter_, data=None, p=None):
        if not (self.data or data): raise ValueError("data is not fold")
        if data: self.set_data(data)
        if p:
            pass
        else:
            return iter_[self.get_value(0, len(iter_)-1)]

Применение

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

Также решается проблема динамических матриц. Такие матрицы выглядят как структуры из подматриц, которые могут пересекаться, а могут и не пересекаться или удалены друг от друга на бесконечное расстояние. Суть в том что мы храним кусочки одной матрицы, а пустоты между ними не учитываем вовсе, их в памяти нет. В Python это можно достичь при помощи словарей {(1,1): 1, (5,5): 2, (-10,-10): 3 ...}, да мы можем использовать отрицательные координаты [Да это же Майнкрафт!!!]

Ниже код с примером использования

Python
_array = {}
_counts = {}

for x in range(2000):
    for y in range(2000):
        r = HashRandom(879202, (x, y)) # Закидываем зерно, и данные генерации - тут это точки. Пересоздавать объект HashRandom необязательно, его код сам пересоздает объект MD5
        _array[(x, y)] = r.get_value(0, 5)

_counts = {x: 0 for x in range(0, 5+1)}
for i in _array:
    _counts[_array[i]] += 1
print(_counts)

Он заполняет индексам текстур матрицу и считает сколько текстур было задействовано на карте

Вот пример программы генерирующая карты высот на PyGame

Python
from random import randint
from RandArray import HashRandom
import pygame

fps = 60
h, w = 256, 256
size = 2
pygame.init()
sc = pygame.display.set_mode((w*size, h*size))


def generate(seed):

    rand = HashRandom(seed)
    height_map = []
    for x in range(w):
        height_map.append([])
        for y in range(h):
            rand.set_data((x, y))
            height_map[x].append(rand.get_value(0, 255))
    return height_map


pygame.display.update()

while True:
    pygame.time.delay(fps)
    for i in pygame.event.get():
        if i.type == pygame.QUIT: exit()
    height_map = generate(randint(1, 10000))
    for x in range(w):
        for y in range(h):
            c = height_map[x][y]
            pygame.draw.rect(sc, (c, c, c), (x*size, y*size, size, size))

А если уменьшить h и w до 40, а size увеличить до 10, то работа станет более заметной

Теперь посмотрим на полученное распределение чисел:

from RandArray import HashRandom
import pygame
from collections import defaultdict

fps = 60
h, w = 150, 40
size = 2
pygame.init()
sc = pygame.display.set_mode((256*size, h))


def generate(seed):

    rand = HashRandom(seed)
    height_map = []
    for x in range(w):
        height_map.append([])
        for y in range(h):
            rand.set_data((x, y))
            height_map[x].append(rand.get_value(0, 255))
    return height_map


def count(iter_):
    counter = defaultdict(int)
    for a1 in iter_:
        for a2 in a1:
            counter[a2] += 1
    return dict(counter)


while True:
    pygame.time.delay(fps)
    sc.fill((255, 0, 0))
    for i in pygame.event.get():
        if i.type == pygame.QUIT: exit()
    counts = count(generate(904))
    for x in sorted(counts):
        l = counts[x]
        pygame.draw.rect(sc, (x, x, x), (x*size, h-l, size, l))
    pygame.display.update()
Генератор массивов псевдослучайных чисел — Программирование — DevTribe: Разработка игр (md5, python, генерация чисел, хеш-функции)


Крутота, спасибо! Результат кст выглядит даже очень неплохо и похоже подпадает под нормированное распределение. Интересно было бы еще на гистограмму распределения глянуть... Но ладно, пожалуй сам попробую с этим разобраться

alexprey,

Крутота, спасибо! Результат кст выглядит даже очень неплохо и похоже подпадает под нормированное распределение. Интересно было бы еще на гистограмму распределения глянуть... Но ладно, пожалуй сам попробую с этим разобраться

Python
from RandArray import HashRandom
import pygame
from collections import defaultdict

fps = 60
h, w = 150, 40
size = 2
pygame.init()
sc = pygame.display.set_mode((256*size, h))


def generate(seed):

    rand = HashRandom(seed)
    height_map = []
    for x in range(w):
        height_map.append([])
        for y in range(h):
            rand.set_data((x, y))
            height_map[x].append(rand.get_value(0, 255))
    return height_map


def count(iter_):
    counter = defaultdict(int)
    for a1 in iter_:
        for a2 in a1:
            counter[a2] += 1
    return dict(counter)


while True:
    pygame.time.delay(fps)
    sc.fill((255, 0, 0))
    for i in pygame.event.get():
        if i.type == pygame.QUIT: exit()
    counts = count(generate(904))
    for x in sorted(counts):
        l = counts[x]
        pygame.draw.rect(sc, (x, x, x), (x*size, h-l, size, l))
    pygame.display.update()

VessTER, ооо, ваще огонь, ну кст почти похоже на нормальное :)

alexprey,

это распределение по используемому оттенку в матрице 256 на 256, высота 1 пиксель = 1 единица в матрице

VessTER, добавил в статью это

притом, матрица спокойно обрабатывается за 0.1-0.2 секунды