Jusper Jusper

По требованию Яндекса, разбили на 2 отдельные странички.
Вторая часть переехала сюда: https://devtribe.ru/p/indie-kitchen/podcast_devgamm_volume_2

Jusper Jusper

Вообще, я делал замер производительности, но вот этот застрявший в мече мужик сделал мой вечер.

Jusper Jusper

Мелочь, но - новая поза персонажа в главном меню. Да, он даже чешет себе задницу.

...
Dreaman Dreaman

IDALGAME,

Действительно оригинально и интересно игра выглядит ;)

Rummy_Games Rummy_Games

Saturated Outer Space #saturdayscreenshot

...
Razz Razz

Мясной шторм в исполнении Юрия Маркова

Stabilitron Stabilitron

Метроидвания в мире славянских сказок. Разбойникам тоже нужно отдыхать.
https://twitter.com/SlavaniaGame/status/1292048996115120128

TheDarkestRed TheDarkestRed

Заброшенный город - концепт арт The Darkest Red 🎮 🕸 🏚
https://vk.com/the_darkestred

IDALGAME IDALGAME

Геймплей беты и создания кофейных пятен.

Следите за разработкой игры: https://vk.com/pt_game

...
Jusper Jusper

У издателей инди-проектов как раз берут либо готовую команду, либо соло-разработчика. Потому что там чем больше хард-скиллов у тебя есть, тем лучше. Я не умею в арт, я не умею в толковый оптимальный код...

Jusper Jusper

GenElCon,

HypeTrain издают в основном инди-разрабочиков, а мне там особо делать нечего, потому что я на данном этапе не инди (точнее инди-мобильник).

GenElCon GenElCon

Ну вот, например, если бы ты в какую-нибудь игру вписаться типо тех, что выходят из под издательского крыла TinyBuild или HypeTrain Digital (такие типичные небольшие крепкие и не очень ПК проекты), как думаешь...

GenElCon GenElCon

Jusper,

А ты пробовал в такие подобные места идти: это были прям гиганты или не только? Просто если это что-то акромя этих гигантов, например, какая-нибудь студия делающая крпепкие не ААА, например Endless Space...

alexprey alexprey

GenElCon, ну это почти тоже самое, что сказать, что я сверх спец по юнити, т.к. C# знаю уже 9 лет, но опыт веб разработки на нем не тоже самое, что скрипты под юньку писать. Тоже самое и с мобилками, там немного другие задачи решаются...

...
Jusper Jusper

GenElCon, в большинстве мест крупных типа Blizzard прямо написано: опыт разработки игры AAA PC проекта, поэтому мобилка там нерелевантна, меня несколько раз развернули.

По личным ощущениям приходится делать конкретное усилие...

GenElCon GenElCon

Jusper,

Хм, а были конкретные кейсы? Ты просто не первый знакомый, кто про это говорит. Любопытно..

Jusper Jusper

Xakkar, lol

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

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

Предыстория

На сервере 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 секунды

Справка