정적 의사 랜덤 필드 생성기

Question

게임용으로 작성한 난수 생성기에 문제가 있습니다. 빠른 pseudorandom 필드 생성기가 필요합니다. 암호로 보호 할 필요는 없으며 단지 벡터와 시드를 가져 와서 사람의 검열을 속일 정도로 충분히 해시 값을 부여하면됩니다.

그러나이 코드는 2 차원 벡터를 제공하고 결과를 2로 수정할 때 "의사 난수"출력을 생성하지 못합니다. 대부분 바둑판 패턴을 생성합니다.

나는 왜, 그리고 솔직히, 그것은 알고있는 것이 멋질 것입니다. 그러나 결코 그것을 이해하지 못하면 나는 그것을 땀꿀 것입니다. 대부분, 난 그냥 임의의 숫자를 생성하는이 방법은 너무 끔찍한 생각, 그래서이 문제를 접근하는 대체 방법을 알고 싶었어요. 즉, 나는 "내가 뭘 잘못하고 있니?"라고 묻는 대신에 이런 방식으로 난수를 생성하는 좋은 대체 방법이 무엇인지에 대한 자료 나 조언을 찾고있었습니다.

기본적으로 동일한 입력을 입력하면 기본적으로 "무한"2D 노이즈 필드 (생각하면 흰색 노이즈)를 생성하려고합니다.

필자가 작성한 코드는 (fnv 해시인데, 템플릿 내용을 용서해주십시오.) 코드에서이를 꺼 냈습니다. 나중에 조금씩 정리해 보겠습니다.)

//Static random number generator, will generate a random number based off of a seed and a coordinate 
template<typename T, typename... TL> 
uint32_t static_random_u32(T const& d, TL const&... rest) { 
    return fnv_hash32(d, rest..., 2938728349u); //I'm a 32-bit prime! 
} 

template<typename T, typename... TL> 
uint32_t fnv_hash32(T const& v, TL const&... rest) { 
    uint32_t hash; 
    fnv_hash32_init(hash); 
    fnv_hash32_types(hash, v, rest...); 
    return hash; 
} 

inline void fnv_hash32_init(uint32_t& hash) { 
    hash = 2166136279u; //another 32-bit prime 
} 

// Should produce predictable values regardless of endianness of architecture 
template<typename T, typename... TL> 
void fnv_hash32_types(uint32_t& hash, T const& v, TL const&... rest) { 
#if LITTLE_ENDIAN 
    fnv_hash32_bytes(hash, (char*)&v, sizeof(v), true); 
#else 
    fnv_hash32_bytes(hash, (char*)&v, sizeof(v), false); 
#endif 
    fnv_hash32_types(hash, rest...); 
} 

inline void fnv_hash32_types(uint32_t& hash) {} 

inline void fnv_hash32_bytes(uint32_t& hash, char const* bytes, size_t len, bool swapOrder = false) { 
    if (swapOrder) { 
    for (size_t i = len; i > 0; --i) 
     fnv_hash32_next(hash, bytes[i - 1]); 
    } else { 
    for (size_t i = 0; i < len; ++i) 
     fnv_hash32_next(hash, bytes[i]); 
    } 
} 

inline void fnv_hash32_next(uint32_t& hash, char byte) { 
    hash ^= byte; 
    hash *= 16777619u; 
} 

Answer 1

저는 전문가는 아니지만 여기에는 생각과 포인터가 있습니다.

기본 해시 혼합 기능인 fnv_hash32_next은 매우 간단하며 실제로 실제로 잘 어울리지 않습니다. 예를 들어 'byte'의 최하위 비트가 0이라는 것을 알고있는 경우 hash ^= byte 문은 hash의 최하위 비트를 변경하지 않습니다. 그리고 16777619u이 홀수 일 때, hash *= 16777619u은 항상 최하위 비트를 변경하지 않습니다. 홀수 (해시)는 홀수 (16777619u)는 홀수/짝수 (해시) × 홀수 (16777619u)는 짝수입니다.

그 인수를 조금 더 수행하면 결과의 최하위 비트가 입력의 모든 바이트에서 최하위 비트의 xor가됩니다. 글쎄, 실제로, 그 반대로, 당신은 hash의 초기 값으로 홀수로 시작하기 때문에 fnv_hash32_init에 있습니다. 이것은보고있는 패턴을 설명 할 수 있습니다. 실제로, 나는 당신이 가깝게 체크하면 꽤 바둑판이 아닌 것을 볼 수있을 것이다. 예를 들어, (x, 255)의 값은 모든 x에 대해 (x, 256)과 같아야합니다.

사용중인 구성표는 상당히 잘 작동하지만 더 나은 해시 기능이 필요합니다. 특히, 조금 더 잘 혼합해야합니다. 필자가 사용 해본 자원 중 하나는 http://www.concentric.net/~ttwang/tech/inthash.htm에 Thomas Wang의 자료입니다. 그는 몇 가지 예제 코드와 함께 기본적인 문제에 대한 간략한 설명을 제공합니다. 또한 Robert Jenkins의 기사 인 http://www.burtleburtle.net/bob/hash/doobs.html에 대한 링크도 놓치지 마세요.

모든 것이 라이브러리에서 MD5 또는 SHA1과 같은 암호화 해시를 사용하는 것이 훨씬 쉽습니다. 환상의 해를 끼치 지 않아도 암호화 해시를 사용해도 "암호로 안전하게"사용할 수는 없습니다. 하지만 암호화 해시 함수는 여기에서 찾고있는 유형의 믹싱 유형을 사용하는 경향이 있습니다.IMO가 잘 작동

Answer 2

당신이 열심히 확인되지 않은 사람을 바보 할 필요가, 난 그냥 표준 라이브러리에서 random_r() 및 srandom_r()을 사용합니다. 그것들을 사용하면 private 상태 객체를 유지할 수 있으므로 한 번에 여러 다른 (고유 한) 생성기를 활성화 할 수 있습니다. 원한다면 편의를 위해 수업에서 이것을 래핑 할 수 있습니다.

Answer 3

뭔가

int base[16][16]; // Random base tile 

int random_value(int x, int y) 
{ 
    return (base[y&15][x&15]^
      base[(y>>4)&15][(x>>4)&15]^
      base[(y>>8)&15][(x>>8)&15]^
      base[(y>>12)&15][(x>>12)&15]^
      base[(y>>16)&15][(x>>16)&15]); 
} 

아이디어는 (내가이 예에서 5 단계를 사용하고 있습니다) 여러 규모 수준의 기본 임의 타일에 xor입니다. 더 많은 레벨을 추가할수록 더 큰 기간이됩니다. 이 예에서 16 ** 5입니다.

Answer 4

이것은 펄린 노이즈의 원인입니다. Minecraft는 Perlin 노이즈를 사용합니다. 중간 지점을 먼저 계산할 필요없이 필드의 어느 지점에서나 즉시 값을 계산할 수 있습니다. 임의로 세계의 비트를 생성 한 다음이 임의의 점에 합치는 비트를 생성하면 모두 완벽하게 일치합니다.