BG Development


Страници: (2) [1] 2   ( Първото ново мнение ) Reply to this topicStart new topicStart Poll

> Обвързване на генериран терен със seed
CPPlus
Публикувано на: 10-05-2018, 00:08
Quote Post



Име: Людмил Григоров
Група: Потребител
Ранг: Почетен член

Мнения: 1097
Регистриран на: 22.06.11



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

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

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

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

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

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


--------------------
Нищо не е свършило, докато не е свършило! Не се предавай и ще постигнеш целта си!
PMEmail Poster
Top
CPPlus
Публикувано на: 10-05-2018, 04:02
Quote Post



Име: Людмил Григоров
Група: Потребител
Ранг: Почетен член

Мнения: 1097
Регистриран на: 22.06.11



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

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


--------------------
Нищо не е свършило, докато не е свършило! Не се предавай и ще постигнеш целта си!
PMEmail Poster
Top
CPPlus
Публикувано на: 10-05-2018, 05:34
Quote Post



Име: Людмил Григоров
Група: Потребител
Ранг: Почетен член

Мнения: 1097
Регистриран на: 22.06.11



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


--------------------
Нищо не е свършило, докато не е свършило! Не се предавай и ще постигнеш целта си!
PMEmail Poster
Top
Дон Реба
Публикувано на: 10-05-2018, 06:09
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 6805
Регистриран на: 11.11.06



ами така се прави да. в стандартната билиотека рандома е неудобен, аз лично ползвам рандом генератор който се инстанцира.
между другото рандом генераторите са толкова полезно нещо, че съм потресен как никой не ги ползва, вкл и колегите ми.
PM
Top
akrachev
Публикувано на: 10-05-2018, 08:39
Quote Post



Име: акрачев
Група: Потребител
Ранг: Редовен член

Мнения: 557
Регистриран на: 27.11.09



Пусни едно демо като има нещо
PMEmail Poster
Top
Gamma Goblin
Публикувано на: 10-05-2018, 08:49
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 1093
Регистриран на: 21.02.18



QUOTE (CPPlus @ 10-05-2018, 04:02)
Ами навсякъде където съм генерирал random числа го замених с random числа от seed и нещата се сработиха идеално.

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


--------------------
Напред! Живота е сраженье!
Напред! И прав всегда ходи!
Напред, макар към поражение!
Ако ще паднеш, прав падни!
---
Axis of faith; Raw, and untamed in spirit
To do and undo...
We chew this world; And Spit it out
PMEmail PosterUsers Website
Top
gat3way
Публикувано на: 10-05-2018, 09:39
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 2750
Регистриран на: 22.06.12



QUOTE (CPPlus @ 10-05-2018, 05:34)
Този генератор за разлика от тези в .NET-a на различните хардуери не плюе различни sequences за един и същи seed.

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



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 1093
Регистриран на: 21.02.18



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

QUOTE
а генераторите в стандартните библиотеки са нескопосани за тази цел.
true story

QUOTE
окени за активация, salt-ове за пароли и прочее - никак не искаш да са предсказуеми.
java -> SecureRandom -> /dev/random or /dev/urandom

QUOTE
Другият проблем е че ако наблюдаваш поредица от генерирани числа, можеш да познаеш какво е "състоянието"
на тия целта им е да са бързи, а не криптографски сигурни


--------------------
Напред! Живота е сраженье!
Напред! И прав всегда ходи!
Напред, макар към поражение!
Ако ще паднеш, прав падни!
---
Axis of faith; Raw, and untamed in spirit
To do and undo...
We chew this world; And Spit it out
PMEmail PosterUsers Website
Top
Дон Реба
Публикувано на: 10-05-2018, 11:13
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 6805
Регистриран на: 11.11.06



QUOTE (gat3way @ 10-05-2018, 09:39)
QUOTE (CPPlus @ 10-05-2018, 05:34)
Този генератор за разлика от тези в .NET-a на различните хардуери не плюе различни sequences за един и същи seed.

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

ти сега от гледна точка на секюрити го мислиш, а човека прави мазе за игричка. лцг е чудесен за такива неща, няма грижа. ако ще ползваш за секюрити какъвто и да е рандом генератор, ясно че сийда му трябва да е с тлъст брой битове, иначе просто си извъртам 4 милярда проби до нацелване на таргет поредицата, това става за секунди.
PM
Top
gat3way
Публикувано на: 10-05-2018, 11:31
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 2750
Регистриран на: 22.06.12



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

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

Това мнение е било редактирано от gat3way на 10-05-2018, 11:55
PMEmail Poster
Top
1 потребители преглеждат тази тема в момента (1 гости, 0 анонимни потребители)
Потребители, преглеждащи темата в момента:

Topic Options Страници: (2) [1] 2  Reply to this topicStart new topicStart Poll

 


Copyright © 2003-2018 | BG Development | All Rights Reserved
RSS 2.0