• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Narf the Mouse

Looking for a good, quick spatial hash...

13 posts in this topic

Looking for a single-function pRNG with a reasonably long period. That is to say, something I can just call .Generate(seed) on. Speed is also a requirement.

Purpose is generating terrain heights in pseudo-perlin value noise.

Thanks.
0

Share this post


Link to post
Share on other sites
I use something like this, simple and fast but of course you have to test if it is good enough for your situation (I think I got the algo from wikipedia, lookup PRNG)

For the first time set XORValue to your seed value.

[code]
XORValue = ( XORValue * 1664525 + 1013904223 ) & 0xFFFF;
[/code]
Or in x86 assembly:
[code]
mov eax,1664525
mov edx,XORValue
mul edx ; result in edx:eax (
add eax,1013904223
mov XORValue,eax
[/code]
1

Share this post


Link to post
Share on other sites
The method given above by Ron AF Greve is generally called the [url="http://en.wikipedia.org/wiki/Linear_congruential_generator"]Linear Congruential Method[/url].

It is one of the simplest mechanism to use, and I can't think of a much faster method. Several C library implementations of rand() use it. There are lots of arguments in favor and against. Some say the lowest order bits have poor randomness, and while true for some instances of the LCG method, it is not a true fact in general. Knuth treats this in detail. There exists a battery of randomness tests by George Marsaglia you can use to test the randomness of different generators.
0

Share this post


Link to post
Share on other sites
Typically, the "generators" used in a Perlin noise implementation are implemented more like a hash rather than a typical PRNG. That is, they are not seeded explicitly, but rather are seeded using the integer parts of the coordinate components, in order that the values be deterministic. So while an LCG or some type of XOR generator are commonly used, they are used in-place and without an external seed function, meaning that Mersenne or other generators that have a very involved seeding process are probably unsuitable due to the overhead of populating tables during the SetSeed process. Given that the coordinate hash tends to not have any kind of correlation between adjacent coordinate locations, it provides the illusion of randomness and is commonly considered to be "random enough". If desired, an optional seed can be considered as an additional coordinate component, so that a generator can be seeded, and the seed will be folded into the hash along with the coordinates in order to provide multiple variants.

My implementation uses [url="http://isthe.com/chongo/tech/comp/fnv/"]FNV-1A[/url] hashing.
2

Share this post


Link to post
Share on other sites
I use this to generate floats +-1

[code]float sfrand( int *seed ) {
float res;
seed[0] *= 16807;
*((unsigned int *) &res) = ( ((unsigned int)seed[0])>>9 ) | 0x40000000;
return( res-3.0f );
}[/code]

[url=http://www.iquilezles.org/www/articles/sfrand/sfrand.htm]Source[/url]
1

Share this post


Link to post
Share on other sites
If you're using C++, investigate the rich PRNG library you get with #include <random>, but I imagine one of the LCG generators is what you're going to want for Perlin generation. Try [font="Courier New"]std::minstd_rand[/font] for a good LCG, or for a faster lagged Fibonacci generator with discards (LFG is nuch faster than LCG at the expense of initialization time and memory footprint) try [font="Courier New"]std::ranlux24[/font].
0

Share this post


Link to post
Share on other sites
I'll tackle your replies in order:

@ApochPiQ: Thanks, but as it would be seeded once for every single coordinate check (see JTippetts' post), Mersenne is not suitable.

@Ron AF Greve: Thanks, but the pseudo-random number needs to rely only on the coordinate seed value (JTippetts probably explained it well enough).

@clb: Thanks, but see above.

@JTippets: Thanks; that's the sort of information I should have provided with my post and probably would have if I weren't literally falling asleep in my chair when I posted. :) I may well use that; will have to test it against the one I'm using now (which is something of a hack). :)

@Typedef Struct: Thanks, I may well use that. Don't know yet if it's better than the one I'm using now. :)

@Bregma: I'm using C#, but thanks. :) (I really should have posted that, but, well, was literally falling asleep in my chair)
0

Share this post


Link to post
Share on other sites
[quote name='JTippetts' timestamp='1316872322' post='4865469']
very involved seeding process are probably unsuitable due to the overhead of populating tables during the SetSeed process[/quote]
They have large state. Mersenne's internal state (seed) is 19937 bits. A coordinate will be 32 bits or so. Ideally, size of internal state would be same as number of bits in coordinate, allowing them to be used interchangeably.

[url="http://www.math.sci.hiroshima-u.ac.jp/%7Em-mat/MT/TINYMT/index.html"]TinyMT[/url] could be used instead, even though it has still comparatively large state.
0

Share this post


Link to post
Share on other sites
There are several operations you can do with 64-bit integers that are invertible (which means they don't lose data):
* Multiply by any odd constant: x *= ODD_CONSTANT;
* Add any constant: x += CONSTANT;
* XOR with any constant: x += CONSTANT;
* Swap the high and low 32-bit parts: x = (x<<32) | (x>>32);

Concatenating a few of them will twists bits around in ways that are hard to predict, which is probably what you want. For instance, you could do:
[code] unsigned long long x = x_coordinate;
x *= 0x0c88be9b660ae531ull;
x += 0x6e8ff6fab43479c7ull;
x = (x<<32) | (x>>32);
x += y_coordinate;
x *= 0x6ea2d3951e64c421ull;
x ^= 0xa7080d55f4cc1186ull;
x = (x<<32) | (x>>32);
x *= 0xcce2e2c89c6892bfull;
[/code]

It might be faster to break the long dependency chain by computing a hash for x, a hash for y and then combining them.
0

Share this post


Link to post
Share on other sites
Just for reference, as JTippets alluded to, what you really want is a spatial hash, not a PRNG [img]http://public.gamedev.net/public/style_emoticons/default/smile.gif[/img]
0

Share this post


Link to post
Share on other sites
[quote name='ApochPiQ' timestamp='1316912639' post='4865620']
Just for reference, as JTippets alluded to, what you really want is a spatial hash, not a PRNG [img]http://public.gamedev.net/public/style_emoticons/default/smile.gif[/img]
[/quote]
Good to know, thanks. Is it possible to rename the thread?
0

Share this post


Link to post
Share on other sites
[quote name='ApochPiQ' timestamp='1316920968' post='4865642']
Done :-)


(For the record, I have no idea if regular users can do that, heh. If you do find a way to do it, let me know - I'm curious!)
[/quote]
Yep. Edit, then "Use full editor".
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0