Random hash and noise functions on Arduboy?

[quote=“ekem, post:45, topic:1802”]
Let’s try this. How many ideal variations of static would you like for your program? Knowing that much I can write a little something.
[/quote]I’m not trying to draw static on the screen. I’m trying to generate a map. Like for example I could start with grass everywhere and use Perlin noise to place water and white noise to place trees.

And ideally the player should be able to keep scrolling indefinitely and always get more map until the data types max out. Because we’re getting map data from a function, not from an array.

Haha cool!! This link here is actually my source http://nk3r.com/dmp/3/ - how many maps would you like? Like how many replays?

Well obviously it would be nice to have as many possibilities as we can.

The simplex algorithm is better suited to this process, then just pick a value on the gradient generated for land, water, sea etc. What you might do is use the white noise generate to generate values for “chunks”, then store those chunks as seeds for the simplex algorithm. Then each “chunk” will be a byte use that to seed a variation for the simplex. That part will be tricky, I’ll look around some.

Simplex is a replacement for Perlin.

Getting some 2D white noise is the most important thing IMO

I’ll try and be less explanatory here, and cut straight to the point.

Use any hash function to take strings and generate a hash of at least length 8192 bits, or 1024 bytes. Use the resulting hash like a bit array and walk through it for your pixel values.

djb2 will work. I would perform a few operations on the resulting long to fill portions of the screen in one go, as you get 32 bits.

    unsigned long
    hash(unsigned char *str)
    {
        unsigned long hash = 5381;
        int c;

        while (c = *str++)
            hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

        return hash;
    }

http://www.cse.yorku.ca/~oz/hash.html

To find the x and y value, simply use the reverse process for drawing the pixel data from the screen buffer, which can be deducted from the library itself, or from several posts on this board. Except treat the 32-bits like 4 bytes, to mimic the image buffer array in the Arduboy library.

http://community.arduboy.com/t/display-buffer-organization/411/8?u=ekem

One hashed string into a long gives you a heck of a lot of bits to work with, and you just need the one character string to create that data, but if the string is longer than the hash, you would just want to use the string. The image buffer for the Arduboy being a perfect or trivial hash gives you this advantage. This is the best method I can think of for generating repeatable “white-noise” for the Arduboy which is storeable and small.

Now you could perform some transformations on the resulting bit-array, like some fractal manipulations or something to further create the psuedo-random effect.

OK, I managed to get a sketch going that has a hash function. It’s just a crappy one. You can see visual artifacts https://codebender.cc/sketch:332942

I’d like to get a better hash function which doesn’t have those

xxHash would do the trick, but unfortunately it seems to be too complicated to be easily extracted in a nice self-contained way that would run on the Arduboy. :frowning:

I got a proof of concept running with the crappy hash function. https://codebender.cc/sketch:332958

Notice how the world is navigable, but never stored in an array anywhere?

I really need a better hash function.

(later edit) BTW, collision detection doesn’t work for negative coordinates. Will need to fix that.

1 Like

Remember to include EEPROM.h and SPI.h when using Codebender, and good work : ).

When we talk about walking arrays, or arrays of memory, it doesn’t imply that memory is stored anywhere for future use, just that the space is allocated in working memory to hold the information while it is being processed. The hash generation process allocates an array in memory to hold the chars, bytes or whatever, and usually returns a pointer to the base address in memory, where you decide what to do with the allocated array, keeping in mind the notion a string is an array of chars etc.

In particular, this line is generating your arrays.

(if (hash(x, y, global_seed) % 2 == 0 && hash(x + 1, y, global_seed) % 2 == 0)
    return 1;

I couldn’t get you source to compile in Codebender I’ll take it to the IDE, codebender has older Arduino libs.

[quote=“ekem, post:54, topic:1802”]
Remember to include EEPROM.h and SPI.h when using Codebender
[/quote]How do I do that? Is there a tutorial anywhere?

Codebender’s font size is way too tiny for me to be able to see much. i just paste in there and then leave ASAP

I actually have vision problems, so when I use arduboy, it is basically, “APPLY DIRECTLY TO FACE”

[quote=“ekem, post:54, topic:1802”]
When we talk about walking arrays, or arrays of memory, it doesn’t imply that memory is stored anywhere for future use, just that the space is allocated in working memory to hold the information while it is being processed. The hash generation process allocates an array in memory to hold the chars, bytes or whatever, and usually returns a pointer to the base address in memory, where you decide what to do with the allocated array, keeping in mind the notion a string is an array of chars etc.
[/quote]Oh, you’re talking about the key being a char array. I getcha. Sorry about the misunderstanding.

Hehe, right on, I have comprehension problems personally.

Try adding

#include "SPI.h"
#include "EEPROM.h"

to the top of your sketches. Codebender can get a little tiring when you are using new lib functions for Arduino, but it’s helpful for small examples.

ha! I sort of guessed it was a misunderstanding, and I was getting worried I’d never pick out the language to convey the material correctly. I understand it enough just to confuse someone else.

I am writing my code in the Arduino IDE. Everything compiles fine on there, but not on Codebender. That’s very odd

Only your second sketch won’t compile. It’s because Codebender has 1.0.x Arduino libraries. The option is to hand include the missing functions in I guess ; )

To get the best results out of Codebender for longer sketches, I pull everything into an old version of the IDE and compile there. There are some gotchas, like all files must be in the project root, for things to work.

I discovered that the only thing stopping it from compiling on codebender was my use of String(). What should I have used instead?

1 Like

Try sprintf()

Here is the example in Codebender, https://codebender.cc/sketch:332978.

A solution that works is to convert the floating point to a string.

char* strbuf[24];
char* tmpbuf[2][7];

char *ftoa(char *a, double f, int precision)
{
 long p[] = {0,10,100,1000,10000,100000,1000000,10000000,100000000};
 
 char *ret = a;
 long num = (long)f;
 itoa(num, a, 10);
 while (*a != '\0') a++;
 *a++ = '.';
 long float_num = abs((long)((f - num) * p[precision]));
 itoa(float_num, a, 10);
 return ret;
}

loop()
{
  ...
  arduboy.setCursor(0, 0);
  ftoa((char*)tmpbuf[0], posX, 2);
  ftoa((char*)tmpbuf[1], posY, 2);
  sprintf(strbuf, "%s, %s", (char*)tmpbuf[0], (char*)tmpbuf[1]);
  arduboy.print(strbuf);
  arduboy.display();
}

Here is a solution that works for integers.

char* strbuf[24];
loop()
{
  ...
  arduboy.setCursor(0, 0);
  sprintf(strbuf, "%d, %d", posX, posY);
  arduboy.print(strbuf);
  arduboy.display();
}

I see what you are up to btw, pretty spiffy :smiley: :100:

And I see why the noise generation method is ideal, and not perlin here. You should totally look at the game of life algorithm, there are certain steps and seeds that will generate really great mazes, that generally connect from beginning to end.

1 Like

impressive ! Nice job so far :slight_smile:

While I try to understand this i first looked at wiki for perlin noise.
I have no idea about the complexity and i simply just want to understand.
In the Article is a pseudocode block which is super simple to translate to C, is this some kind of use and when not why?
I’m just curious here since i want to understand, pls not hate here for asking possibly dumb questions. xD

1 Like

Perlin gives you a result that is continuous / coherent. It flows like rolling hills. Adjacent coordinates make smooth transitions between high and low areas.

White noise is just crazy. No discernable pattern or tendency, no discernable relationship between adjacent coordinates.

Simplex and OpenSimplex are just nicer replacements for Perlin.

The hash function I am using is a crappy form of white noise – crappy because patterns are visible when you look at a 2D representation. xxHash would be a better hash to use because it doesn’t make humanly recognizable artifacts but I am not sure how to port it over to Arduboy

1 Like