Обвързване на генериран терен със seed

Здравейте!
Отдавна не съм си правил игрички и сега правя нещо като coop dungeon crawler.

Генерирах си dungeon с n стаи, като всяка стая е една от m предварително създадени типове стая.

Въпросът е, че като се вкара multiplayer-a всеки клиент си генерира негов си свят, а на мене не ми се иска да синхронизирам 1000+ сложни обекта през мрежата всеки път като някой се log-не (а и като се добавят неща по картата ще трябва да се пипа логиката за синхронизиране ако имам мъдростта да не пращам всичко сериализирано като ненормален ).
Даже се получи, че всички играчи освен теб са като призраци и минават през стени

Как се нарича това нещо, което ми позволява от даден seed (да кажем 384792473829) да се генерира всеки път абсолютно едно и също нещо на която и да е машина?

Edit: Сега като гледам мъдрости из google-то се ползва псевдо random number generator и трябва да измисля каквато и да е логика за конвертиране от числа в смислени карти.
Има някаква логика, в която генерираш една поредица от numbers от seed и тези numbers са seed за второ ниво random numbers и така имаш достатъчно числа, за да запазиш всякакво количество информация.

Това мнение е било редактирано от CPPlus на 10-05-2018, 00:16

Ами навсякъде където съм генерирал random числа го замених с random числа от seed и нещата се сработиха идеално.

Все пак ще ми е интересно да видя някоя дискусия по темата "процедурно генериране" ако има заинтересовани

Този генератор за разлика от тези в .NET-a на различните хардуери не плюе различни sequences за един и същи seed.

ами така се прави да. в стандартната билиотека рандома е неудобен, аз лично ползвам рандом генератор който се инстанцира.
между другото рандом генераторите са толкова полезно нещо, че съм потресен как никой не ги ползва, вкл и колегите ми.

Пусни едно демо като има нещо

The best: http://xoshiro.di.unimi.it/

Всички PRNG-та "плюят" една и съща редица числа след като се инициализират с един и същ seed. В дотнета очевидно са решили да мислят вместо девелоперчетата и го "посяват" освен с подадения seed и с нещо друго, примерно системното време. В което има логика, в 99.9% от случаите идеята е да "изплюват" нещо което изглежда случайно - у вебаджийството това са сесийни id-та, разни CSRF токени, разни временни пароли, токени за активация, salt-ове за пароли и прочее - никак не искаш да са предсказуеми. Иронично обаче вебаджиите се предоверяват на "случайността", а генераторите в стандартните библиотеки са нескопосани за тази цел. Тези дето са базирани на LCG някакво почти винаги имат някакви нежелани bias-и, ако вадиш стойности примерно от 0 до 65535 и плотнеш така генерираната редичка от да речем първите един милион стойности като бели пиксели върху 256x256 черен битмап, ще видиш как части от тази картинка си остават черни и същите части си остават черни, независимо какъв seed избереш, което какво означава - определени стойности е силно невероятно да бъдат генерирани. Другият проблем е че ако наблюдаваш поредица от генерирани числа, можеш да познаеш какво е "състоянието" на генератора и да предсказваш следващите генерирани числа, всъщност от security гледна точка, това им е най-голямата драма. Дори по-"добри" генератори като mersenne twister-а не са мислени за това и за тях важи абсолютно същото. Дори от добро желание в почти всяка имплементация, генераторът е осакатен така че инициализацията да става за удобство от 32-битов seed, а всъщност началното състояние е далеч по-голямо. Вследствие на това, 32-битовия seed можеш да го познаеш само по първите 1-2 генерирани стойности и оттам да предсказваш следващите стойности. Това доста улеснява нещата - "класическото" му чупене с отгатване на вътрешното състояние (стига да беше инициализиран правилно) изисква да знаеш поредица от няколкостотин поредни генерирани стойности.

Ребата ще се окаже прав че мисленето е вредно

true story

java -> SecureRandom -> /dev/random or /dev/urandom

на тия целта им е да са бързи, а не криптографски сигурни

Всички PRNG-та "плюят" една и съща редица числа след като се инициализират с един и същ seed. В дотнета очевидно са решили да мислят вместо девелоперчетата и го "посяват" освен с подадения seed и с нещо друго, примерно системното време. В което има логика, в 99.9% от случаите идеята е да "изплюват" нещо което изглежда случайно - у вебаджийството това са сесийни id-та, разни CSRF токени, разни временни пароли, токени за активация, salt-ове за пароли и прочее - никак не искаш да са предсказуеми. Иронично обаче вебаджиите се предоверяват на "случайността", а генераторите в стандартните библиотеки са нескопосани за тази цел. Тези дето са базирани на LCG някакво почти винаги имат някакви нежелани bias-и, ако вадиш стойности примерно от 0 до 65535 и плотнеш така генерираната редичка от да речем първите един милион стойности като бели пиксели върху 256x256 черен битмап, ще видиш как части от тази картинка си остават черни и същите части си остават черни, независимо какъв seed избереш, което какво означава - определени стойности е силно невероятно да бъдат генерирани. Другият проблем е че ако наблюдаваш поредица от генерирани числа, можеш да познаеш какво е "състоянието" на генератора и да предсказваш следващите генерирани числа, всъщност от security гледна точка, това им е най-голямата драма. Дори по-"добри" генератори като mersenne twister-а не са мислени за това и за тях важи абсолютно същото. Дори от добро желание в почти всяка имплементация, генераторът е осакатен така че инициализацията да става за удобство от 32-битов seed, а всъщност началното състояние е далеч по-голямо. Вследствие на това, 32-битовия seed можеш да го познаеш само по първите 1-2 генерирани стойности и оттам да предсказваш следващите стойности. Това доста улеснява нещата - "класическото" му чупене с отгатване на вътрешното състояние (стига да беше инициализиран правилно) изисква да знаеш поредица от няколкостотин поредни генерирани стойности.

ти сега от гледна точка на секюрити го мислиш, а човека прави мазе за игричка. лцг е чудесен за такива неща, няма грижа. ако ще ползваш за секюрити какъвто и да е рандом генератор, ясно че сийда му трябва да е с тлъст брой битове, иначе просто си извъртам 4 милярда проби до нацелване на таргет поредицата, това става за секунди.

Бе няма да е баш секунди, LCG-то може и да го врътнеш за секунди все пак, но на mersenne twister-а инициализацията му е относително скъпа операция, сийдването "пипа" към 2-3 килобайта памет, вече генерацията на числа оттам нататък е евтина, та връткането на 4-те милиарда възможности може да отнесе доста повече, минути ако не и часове не знам. Ма пък това е силно склонно към паралелизация от друга страна, няма никакви зависимости между отделните инициализации. Единствено това че му требе памет е малко криво.

P.S ся между другото ми стана интересно, намерих някаква "бърза" имплементация на MT и му врътнах 10 милиона инициализации...отнема 13 секунди (на core i7-4810MQ @ 2.8GHz). Значи 4-те милиарда би следвало да се врътнат за по-малко от 2 часа...и тва на едно ядро. Бе не е толкова много.

Това мнение е било редактирано от gat3way на 10-05-2018, 11:55