Повторное базирование семян PCG

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

Приведу простой практический пример:

## Procedural racetrack ##
                                                         *
           | Track shape generation | Terrain generation | Surfaces generation | Assets picking |
RNG stream | 1 2 3                  | 4 5 6 7            | 8 9                 | 0              |
## User-overridden racetrack ##
                                                         *
           | Track shape generation | Terrain generation | Surfaces generation | Assets picking |
RNG stream | 1 2 3                  | provided by user   | 4 5                 | 6              |

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

Я ищу своего рода операцию синхронизации ГСЧ (вероятно, не самый исправленный термин для использования ...), который можно использовать между этапом Генерация ландшафта и этапом Создание поверхностей, чтобы получить тот же поток ГСЧ, начиная с *, независимо от того, предоставлен ли ландшафт пользователем или нет. Я подумал о чем-то вроде:

uint64_t seed = // initialized with racetrack ID
pcg32 rng(seed);

// Do Track shape generation step
// Do Terrain generation generation step

seed = seed + k; // where k is some constant
rng.seed(seed);

// Do Surfaces generation step
// Do Assets picking step

Но я не знаю, seed = seed + k; является допустимым подходом к пересеву (или есть что-то лучше), и если какое-то значение лучше других для k.

Ссылка на вопрос, изначально заданный в разделе Проблемы репозитория PCG: https://github.com/imneme/pcg-cpp/issues/72


person TaaTT4    schedule 10.05.2021    source источник
comment
Связанный: заголовок stackoverflow.com/questions/64965398/ Однако ваша проблема не относится к PCG; это не проблема с PCG в отличие от другого генератора псевдослучайных чисел.   -  person Peter O.    schedule 10.05.2021
comment
Действительно, у меня была бы такая же проблема с использованием другого ГСЧ (например, mt19937). Я использую PCG, потому что мои семена (которые соответствуют идентификаторам гоночных треков) являются uint32_t числами, и, насколько я понял, PCG - это ГСЧ, который дает наилучшие результаты, если засеять 32 бита данных.   -  person TaaTT4    schedule 10.05.2021


Ответы (1)


Это сводится к назначению отдельного ГПСЧ для каждого из ваших четырех (или более) этапов генерации (в вашем примере, генерации формы трека, генерации ландшафта, генерации поверхности и выбора ресурсов) и присвоения начального числа каждому из них. (В вашем случае один из способов, которым это может сработать, - сформировать хэш идентификатора ипподрома, идентификатор для каждого этапа генерации и фиксированную строку битов и использовать этот хеш в качестве начального числа для каждого ГПСЧ.)

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

Например, существует много ГПСЧ, для которых данная стратегия заполнения будет создавать коррелированные псевдослучайные числовые последовательности. Например, в большинстве версий PCG две последовательности, сгенерированные из начальных чисел, которые отличаются только старшими битами , будут быть сильно коррелированными (подпоследовательности из одного генератора).

Чтобы снизить риск коррелированных псевдослучайных чисел, вы можете использовать алгоритмы PRNG, такие как SFC и другие так называемые PRNG на основе счетчиков (Salmon et al., Parallel Random Numbers: As Easy as 1, 2, 3, 2011), что поддерживать независимые потоки псевдослучайных чисел, давая каждому начальному значению собственную независимую последовательность псевдослучайных чисел. (Обратите внимание, однако, что PCG имеет ошибочное представление о потоках.) есть и другие стратегии, и я объясню это подробнее в Заполнение нескольких процессов.

Смотрите также:

person Peter O.    schedule 10.05.2021
comment
Спасибо! Есть много информации, чтобы углубиться в эту тему. Я не знал о ГСЧ на основе счетчиков, которые кажутся наиболее полезным классом ГСЧ в моем сценарии. - person TaaTT4; 14.05.2021