Random hash and noise functions on Arduboy?

I would really like to get some nice random 2D noise functions on the Arduboy. The most important would be white noise and Perlin. Worley noise would also be nice.

This is different from just using the random() function. This would need to take in x and y coordinates and a seed, and always return the same random result given the same inputs. And it would need to be tiny enough to fit on the Arduboy but robust enough to not produce humanly recognizable repeating patterns.

The limited system resources of the Arduboy make this sort of math especially necessary, since storing level maps is going to severely limit map size, but procedural generation should let you have really big, perhaps psuedo-infinite maps / play spaces.

See this link to understand why “use random()” is not an answer to this query: http://blogs.unity3d.com/2015/01/07/a-primer-on-repeatable-random-numbers/

Quick question… Do you need the data to be reproducible on separate Arduboys with the same seed? Or just the same Arduboy?

Ideally any arduboy but I’d settle for the same arduboy.

I found this for Perlin noise:

Will try it after work

Still need to find a good 2D white noise

White noise can be generated by randomly setting pixels on and off in the image buffer.

That won’t work. I need the image buffer.

Ah, you can create an array, or just a page and during a tick, draw the offscreen array (buffer) to screen, or re-seed one page and loop over the buffer copying the page to the image buffer.

Generating a new random byte(integer) value and popping off the bits for that integer to be used in filling the image buffer, 8 pixels at a time, should do the trick.

I will need the image buffer for drawing images. Besides, what if I want more area than the image buffer holds? This really should be something which happens in a math function.

The image buffer is just a chunk of memory holding bytes. Any block of memory can be used to hold an ‘offscreen’ image buffer, space allowing of course.

One could also override the library itself to change how the size of the image buffer or add a second buffer into the main Arduboy class.

I have a few implementations of perlin around, it might be fun to just put a demo out with all these drawing techniques, or a demo per technique.

Both might be good. The one demo with every technique would be good to put on one’s arduboy to get a sense of what’s possible, but the demos for each technique would be good as educational code because you want code examples to be self contained and easy to interpret so as to distinguish relevant code from other stuff.

But as far as for what I am envisioning however, caching the play space at all would defeat the purpose. The purpose is to enable larger play spaces than storage capacity allows to be held in memory.

I always thought perlin was one of the greatest learning examples out there. Not only is it mathematically interesting, but it can be used to create all sorts of effects quickly.

Here’s some really simple terrain from a perlin function http://nk3r.com/dmp/3/

And the perlin algorithm in acttion http://nk3r.com/dmp/7/

Yeah for sure, but you will always need memory allocated to start to run your procedural generation. There will always be some overhear associated with generating your new scenery. The trick would be to use that memory cleverly. So when you go to generate a new int, you will be allocating a byte anyway. Simply use that integer byte as your “temp” buffer and right that straight to the arduboy image buffer.

You can also allocated an array for generation, then quickly deallocate it after you are done processing.

I found this which appears to be an example of xxHash done in pure C
ftp://ctan.tug.org/ctan%3A/dviware/dvisvgm/xxHash/xxhash.c

I am thinking I could use that to make the white noise maybe if I can get it to run on the arduboy.

Instead of looking up map data in an array, I would call some function which has this noise at the back of it determining what is there by rules.

@BenMclean, you can either use Ken Perlin’s implementation (he won an academy award for it) and port it, or try some of the more famous implementations as well. There are a handful of techniques that were published about 10-20 years ago, and they haven’t changed much.

The 2 and 3 dimension perlins are probably not needed if you are only doing 1-bit color.

http://paulbourke.net/libraries/perlin.c
http://mrl.nyu.edu/~perlin/noise/

There is also simplex noise. http://webstaff.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf
This algorithm is also by Perlin, but will be faster with O(n2) instead of O(2n) for the original perlin.

That should take care of the Perlin noise, but what about the white noise?

generate a random int, copy 8 bits of the byte to the first byte of the image array. gen new int in same memory space and fill the next 8 pixels. Repeat until image buffer array is filled.

You could optimize this by using bit values multiple places and random spots in the full image buffer array. The Fisher-Yates shuffle is an decent way to randomize a full set.

If you want an algorithm, and not an ad-hoc method, try Gaussian noise. I picked one implementation at random, there will be many out there :smiley:

http://musicdsp.org/showone.php?id=168

I am definitely looking for an algorithm, so I can create the illusion of a much larger space, not just another way of filling a fixed size array that I could have filled with a hand crafted level.

Can’t you just do some devision of some input, then convert it to bits? You could even XOR some of the data if you wanted, too.

int x := input( int ) //Input a user's number int y := input( int ) //Input a user's number int z := input( int ) //Input a user's number float bignumber := x ÷ ( y ÷ z ) //Save the output of an equation to a float bool binaryrepresentations[ sizeof( bignumber ) × 8 ] //Create an array of booleans for( int index < sizeof( bignumber ) × 8 ) { //For each bit in the float... binaryrepresentations[ i ] = ( ( 1 << i ) & bignumber ) ≠ 0 ? 1 : 0 //Save the bit into the array }

You could then grab data from that array… Or would this take too much RAM?

That’s what I’ve been suggesting as well (I think), except just copy the values as they are generated straight to the image buffer. it makes more sense to just fill 8-bits at a time with a random int. Or just use the Gaussian method, that’s pretty much as good as it gets, with the exception the Gaussian method uses floating points and generates way more fidelity than is needed for 1-bit images.

Popping bits off though will be slower than just copying the bit values onto the array, there shouldn’t be a need for bit wise operations. Every random integer is already 8 random bits.

/* Setup constants */
const static int q = 15;
const static float c1 = (1 << q) - 1;
const static float c2 = ((int)(c1 / 3)) + 1;
const static float c3 = 1.f / c1;

/* random number in range 0 - 1 not including 1 */
float random = 0.f;

/* the white noise */
float noise = 0.f;

for (int i = 0; i < numSamples; i++)
{
    random = ((float)rand() / (float)(RAND_MAX + 1));
    noise = (2.f * ((random * c2) + (random * c2) + (random * c2)) - 3.f * (c2 - 1.f)) * c3;
}

Theres the Gaussian for reference.

Yes, there are two methods provided in the post you are replying to that are algorithmic in nature and are procedural approaches to generating noise that only uses the buffer provided by the Arduboy library, and do not use any other arrays. The only memory in use will be the stack for function calls and a byte to hold the 8-bits while being worked.

But I don’t want to fill a buffer with noise. I want to calculate