Lost in (procedurally generated) forest. Memory constraints

TomJohnRiddle · March 25, 2018, 12:23pm

Hi Guys & Gals!

Disclaimer: please note that I am new to Arduboy and C++ programming therefore my questions and code are on a begginer level.

I am trying to make procedurally generated forest. Things I have:

Trees sprites
Idea to randomly generate one (128 x 64) background: create an array of random x, y positions, draw trees accoridingly to that array
Idea to generate more than one background: create many (128 x 64) backgrounds and draw them with shift of 128 px and 64 px.
Working pice of code

The problem:

If I would like to have more backgrounds, using abovementioned approach, I would need a larger array to keep x,y positions. I was thiniking of adding second dimenstion to an array, however such array would not fit in the memory. My approach is probably quite bad…any advices would be more than welcomed. Please find below full code:

#include <Arduboy2.h>


Arduboy2 arduboy;
Sprites sprites;


byte frame;


//buffers
byte abuffer;
byte bbuffer;
byte upbuffer = 0;
byte downbuffer = 0;
byte leftbuffer = 0;
byte rightbuffer = 0;




byte moving = 0;
byte mstate = 1;

//cursor variables
int crs_x = 0;
int crs_y = 0;


// Structure for x, y, frame

struct xy_point {
  byte x;
  byte y;
  byte z;
};

// Structure will keep 20 trees, however it seems that to procedurally generate more backgrounds I would need bigger array? (and I do not have memory for that)
xy_point xy_points[20];




const unsigned char PROGMEM trees[] =
{
  // width, height,
  8, 16,
  // FRAME 00
  0x80, 0x80, 0xd0, 0xfe, 0xb0, 0x08, 0x80, 0x00,
  0x08, 0x1d, 0x5d, 0xff, 0x1b, 0x1d, 0x0e, 0x02,
  // FRAME 01
  0x00, 0x80, 0xc0, 0xfe, 0xf0, 0x80, 0x00, 0x00,
  0x0e, 0x1f, 0x1f, 0xff, 0x1f, 0x1f, 0x0e, 0x00,
  // FRAME 02
  0x00, 0xb0, 0xf8, 0xfc, 0xfe, 0x6e, 0x07, 0x00,
  0x03, 0x07, 0x0f, 0xff, 0x0f, 0x07, 0x03, 0x00,
  // FRAME 03
  0x80, 0xd8, 0xb0, 0xfc, 0xff, 0xf2, 0xc0, 0x60,
  0x05, 0x0d, 0x0f, 0xff, 0x0f, 0x07, 0x06, 0x02,
};


const unsigned char PROGMEM foxr[] =
{
  // width, height,
  8, 8,
  // FRAME 00
  0x00, 0x00, 0x7c, 0x20, 0x60, 0x38, 0x10, 0x00,
  // FRAME 01
  0x00, 0x0c, 0x70, 0x20, 0x20, 0x78, 0x10, 0x00,
  // FRAME 02
  0x00, 0x0c, 0x30, 0x60, 0x20, 0x78, 0x10, 0x00,
  // FRAME 03
  0x00, 0x00, 0x3c, 0x60, 0x20, 0x78, 0x10, 0x00,
  // FRAME 04
  0x00, 0x00, 0x3c, 0x60, 0x60, 0x38, 0x10, 0x00,
  // FRAME 05
  0x00, 0x00, 0x7c, 0x20, 0x60, 0x38, 0x10, 0x00,
};

const unsigned char PROGMEM foxl[] =
{
  // width, height,
  8, 8,
  // FRAME 00
  0x00, 0x10, 0x38, 0x60, 0x20, 0x7c, 0x00, 0x00,
  // FRAME 01
  0x00, 0x10, 0x78, 0x20, 0x20, 0x70, 0x0c, 0x00,
  // FRAME 02
  0x00, 0x10, 0x78, 0x20, 0x60, 0x30, 0x0c, 0x00,
  // FRAME 03
  0x00, 0x10, 0x78, 0x20, 0x60, 0x3c, 0x00, 0x00,
  // FRAME 04
  0x00, 0x10, 0x38, 0x60, 0x60, 0x3c, 0x00, 0x00,
  // FRAME 05
  0x00, 0x10, 0x38, 0x60, 0x20, 0x7c, 0x00, 0x00,
};



void random_tree_pos() {




  for ( int i = 1; i < 20; i = i + 1 ) {
    xy_points[i].x = random(0, 128);
    xy_points[i].y = random(0, 64);
    xy_points[i].z = random(0, 4);
  }



}


void tree(int a, int b) {


  for ( int i = 1; i < 20; i = i + 1 ) {
    sprites.drawSelfMasked(xy_points[i].x + a, xy_points[i].y + b, trees, xy_points[i].z);
  }




}



void buttons() {


  if (arduboy.pressed(LEFT_BUTTON)  and leftbuffer == 0) {

    moving = 1;
    crs_x = crs_x + 1;
    mstate = 0;

  }
  if (arduboy.pressed(RIGHT_BUTTON)  and rightbuffer == 0 ) {

    moving = 1;
    crs_x = crs_x - 1;
    mstate = 1;



  }
  if (arduboy.pressed(UP_BUTTON)  and upbuffer == 0) {

    moving = 1;
    crs_y = crs_y + 1;


  }
  if (arduboy.pressed(DOWN_BUTTON)  and downbuffer == 0) {

    moving = 1;
    crs_y = crs_y - 1;


  }

  if (arduboy.pressed(B_BUTTON) and bbuffer == 0) {


  }

  if (arduboy.pressed(A_BUTTON) and abuffer == 0) {
    abuffer = 1;
    random_tree_pos();

  }





}





void setup() {
  // put your setup code here, to run once:


  arduboy.begin();
  arduboy.clear();
  arduboy.setFrameRate(60);


  random_tree_pos();


  arduboy.initRandomSeed()

  ;
}

void loop() {

  if (!arduboy.nextFrame()) {
    return; // go back to the start of the loop
  }

  arduboy.clear();
  tree(crs_x, crs_y);

  if (mstate == 1) {
    sprites.drawSelfMasked(60, 28, foxr, frame);
  } else {
    sprites.drawSelfMasked(60, 28, foxl, frame);
  };



  if (arduboy.everyXFrames(2)) {

    buttons();

    if (moving == 1 or frame > 0) {
      frame = frame + 1;


    }


    if (frame > 5) {
      frame = 0;
    };






  }





  if ( arduboy.notPressed(A_BUTTON) == true) {
    abuffer = 0;

  }


  if ( arduboy.notPressed(B_BUTTON) == true) {
    bbuffer = 0;

  }
  if ( arduboy.notPressed(DOWN_BUTTON) == true ) {
    downbuffer = 0;
    moving = 0;
  }
  if ( arduboy.notPressed(UP_BUTTON) == true ) {
    upbuffer = 0;
    moving = 0;
  }


  if ( arduboy.notPressed(RIGHT_BUTTON) == true ) {
    rightbuffer = 0;
    moving = 0;

  }
  if ( arduboy.notPressed(LEFT_BUTTON) == true ) {
    leftbuffer = 0;
    moving = 0;
  }

  arduboy.display();

}

Pharap · March 25, 2018, 1:11pm

(TL;DR: just draw your trees on the screen, don’t worry about making ‘backgrounds’.)

The Arduboy has 2560 byes of RAM.

One Arduboy background in native image format (1 bit per pixel) takes (128 * 64) / 8 bytes, which is 1024 bytes.

The Arduboy already has 1024 bytes allocated to the screen buffer by Arduboy2, leaving you room for precisely one ‘background’ and 512 bytes left over for everything else (some of which is taken by variables used by Arduboy2 and some of which is needed to be able to call functions).

In other words, you won’t be doing much else if you try to write the background to a different buffer instead of directly to the screen buffer.

That would work.

A bit of advice:
It’s better to start with the trees aligned and then ‘nudge’ them randomly

(I have a diagram illustrating this somewhere but I can’t remember where - someone asked this once before.)

Some code functionality tips:

Looking at what you’re using it for, z ought to be called index or type.
At first I was expecting z to be some kind of indicator for the relative ‘depth’ of the tree.

Otherwise that’s all fine.

You don’t need the buffer variables, you can use arduboy.justPressed(RIGHT_BUTTON).

Arrray indices start at 0.
Unless you’re intentionally skipping the first tree, that should be:

  for ( int i = 0; i < 20; i = i + 1 ) {
    xy_points[i].x = random(0, 128);
    xy_points[i].y = random(0, 64);
    xy_points[i].z = random(0, 4);
  }

Also i = i + 1 can be turned into ++i for simplicity.

  for ( int i = 0; i < 20; ++i ) {
    xy_points[i].x = random(0, 128);
    xy_points[i].y = random(0, 64);
    xy_points[i].z = random(0, 4);
  }

A couple of ‘stylistic’ tips:

The == true bit is redundant. You’re basically saying if(true == true) or if(false == true), which iself evaluates to true or false.
Just stick to if(arduboy.notPressed(LEFT_BUTTON))

Also if moving is only going to be 1 or 0 then you’d be better off using bool and having true and false instead. It makes the intent clearer.

Try to get used to using && instead of and and || instead of or. The ‘wordy’ versions only exist for historical reasons.

Out of interest, how much memory are you using at the moment?
I can’t see anything particularly large here.

If you just keep the trees in an array and loop through them to draw them then you should be fine.

TomJohnRiddle · March 26, 2018, 7:47am

Hello @Pharap, thank you very much for detailed answer and advices. It seemed to me that if I would like to achieve density of 20 trees on 128x64 area and have a whole game map being 20*(128x64)=2560x1280 I would need store trees x and y’s in array xy_points[400]; or xy_points[20][20]; Unfortunatelly such approach will result in not sufficent memory. I guess that if my array was not generated randomly I could just put it in PROGMEM.

Other things:

Great idea. Will definiately try that.

I will check today in the evening and reply. Edit:

Sketch uses 8814 bytes (30%) of program storage space. Maximum is 28672 bytes.
Global variables use 1300 bytes (50%) of dynamic memory, leaving 1260 bytes for local variables. Maximum is 2560 bytes.

I am using z as a tree type indicator to make forest look more ‘foresty’

Pharap · March 26, 2018, 11:05am

Yeah, I understood that after I read the later code, but I was expecting it to be a ‘z coordinate’. It’s confusing name.
It would make more sense if it was called treeType or type or index.

That would be 20 trees per pixel.

The whole screen is 128x64 pixels, but each tree image is larger than 1 pixel.

If you just want to have 20 trees across the whole screen then you can just draw them onto the screen and it will only cost you 20 trees and the screen buffer (which is already allocated anyway - it’s needed for drawing).

If you wanted a grid of 20x20 trees then yes, that’s 400 trees, but I don’t think you’d fit that many on the screen anyway, it depends how big your trees are.

If you don’t need all the trees at once then you could generate them a bit at a time so you only have to put a few in memory.

Ultimately it depends what your goal is.

If you just want a forest for a game, then it would be easier to put all the tree locations in progmem.

If you specifically want to procedurally generate the trees then you will probably want to look into some PRNGs (pseudo-random number generators) or some hash functions.

TomJohnRiddle · March 26, 2018, 1:48pm

Once again thank you for advices. You are absolutely right about the ‘z’. I will change it to something less confusing.

That is exactly my main problem. Sorry for misguiding you with 20*(128x64) - I had in mind 20 areas with width of 128 and height 64. Each tree is 8x16 sprite. To clarify: I need density of 20 trees at the time on the screen - this is what my code does at the moment. However, I would like to move my ‘hero’ around the forest. To do this I am keeping my ‘hero’ at the center of the screen and moving whole forest instead (sprites.drawSelfMasked(xy_points[i].x + a, xy_points[i].y + b, trees, xy_points[i].z);. If there would not be a memory issue I would just create very large array of xy_points which would keep all trees including those which are not visible on the screen at the moment (for example tree with inital x = -200 would become visible if I ‘move’ left enough). In theory such approach seems to work quite well: I would have large procedurally generated forest.

I could probably generate randomly forest ‘on the fly’ when I move, however this means that your map would constantly change (you would not be able to comeback to place from where you started).

I guess this is a great idea. If I could generate sequence of numbers which does not have to be stored in the memory and can be called when needed it would probably solved my issue. Will definitiale look into that.

Summing up: Thank you for your patience

FManga · March 26, 2018, 3:19pm

You might want to look up 1D Value/Perlin Noise. Implementations for graphics cards often use a pseudo-random hash function, like you mentioned above, but they’re meant to work with floats. “Hello, Commander” has a 2D 8-bit-specific implementation for generating terrain that you might also want to have a look at.

TomJohnRiddle · March 26, 2018, 3:23pm

Interesting. Will definitely look into that.

Pharap · March 26, 2018, 5:46pm

Good plan.

Yes, this is why I mentioned “hash functions”.
PRNGs are ‘stateful’ - they require that an internal state is maintained.
Hash functions can just rely on the tree’s coordinates (perhaps combined with an initial seed), they don’t need to maintain a ‘state’.

The “Perlin Noise” that @FManga mentioned is an example of a hash function, but that needs a 256 element array so it’s not ideal.
A derived version like the one used in “Hello, Commander” might work though. (I presume it uses less memory too.)

Another alternative would be to base your function on a PRNG.
Most PRNGs are actually the same function repeatedly applied to a state value.
For example, the LCG (linear congruential generator) uses:

state = ((state * multiplier) + increment) % modulo;

Where multiplier, increment and modulo are constant values selected at the start.

So it could be described with the function:

uint16_t lcgStep(uint16_t state)
{
  return ((state * multiplier) + increment) % modulo;
}

Being fed back into itself:

state = lcgStep(state);

You could use a function like lcgStep applied to the trees’ start coordinates to generate their offset.
For example:

xy_point point = /* initialise somehow */;

// Combine the 8 bit coords into a 16-bit number
uint16_t combinedCoords = static_cast<uint16_t>(point.x) << 8 + point.y;
uint16_t xOffsetBase = lcgStep(combinedCoords);
uint16_t yOffsetBase = lcgStep(xOffsetBase);

// No more than 8 pixels in either direction
const int8_t offsetMax = 8;
const int8_t offsetMin = -offsetMax;
const uint8_t difference = offsetMax * 2;

int8_t xOffset = offsetMin + static_cast<int8_t>(xOffsetBase % difference);
int8_t yOffset = offsetMin + static_cast<int8_t>(yOffsetBase % difference);

point.x += xOffset;
point.y += yOffset;

Obviously that will need a bit of testing and changing before it works how you want, but it’s a start.

No problem.
You seem to already know quite a bit about this,
I assume you’ve done a lot of reading or research (which is a good thing - programming involves lots of reading and research).

If you don’t know what int8_t, uint8_t or uint16_t are, they’re basically fixed size types.
uint8_t is the same as byte, but byte is an Arduino-only thing.
Using fixed size types makes your code more portable, so if you ever decide you want to make your game work on a computer or a different system, it’s easier to get it working.
I.e.

struct xy_point {
  byte x;
  byte y;
  byte z;
};

Can’t just be pasted into a program written for Windows, but

struct xy_point {
  uint8_t x;
  uint8_t y;
  uint8_t z;
};

Could be, (as long as the compiler was C++11 and the right header (#include <cstdin>t) was used.)

You can read more about the types here.

FManga · March 26, 2018, 7:03pm

Perlin Noise can use a hash (the formal definition doesn’t specify where the randomness comes from), but there’s more to it. Instead of simply returning “random” numbers (White Noise), you get Brown Noise… which is great for terrain and tree lines (and textures for wood, marble, fire…). It’s a really versatile algorithm, and you’ve probably seen its applications in things like Tron (the 1982 movie), No Man’s Sky, and many others.

In 2D, White Noise looks like this:

Boring. Compare that to Brown Noise:

If you consider the light points as mountains and the darks as valleys, Just Add Water and you get something that looks like pretty good terrain:

That’s 2D… in your case, you want 1D (Value Noise algorithm, final outline in the bottom-right):

Add some trees, grass, sky…

If you make your implementation based on a hash function instead of a PRNG, you’ll be able to walk back and fourth, always getting the same skyline.

There are a lot of articles on the subject, including some that go into the really deep end of the math pool. Others are more practical and you’ll see that it doesn’t have to be all that complicated, especially if you look into Value Noise instead of Perlin.

(images randomly lifted off google)

Pharap · March 26, 2018, 9:32pm

Perlin noise isn’t quite the same as Brownian noise.
Perlin noise explicitly requires the use of normalised gradiants like so:

Using the dot product of those ‘gradients’ is the defining feature.
Granted the hash function used to generate the ‘gradients’ could be changed, but the gradients themselves are the defining feature.

(I’ve just realised that the one I linked to with the 256 element grid was most likely simplex noise, Perlin’s ‘improved’ version of his original noise algorithm, the original C implementation of Perlin noise (without the precomputed values) is here.)

Brownian noise as I understand it is just a way of combining noise of different amplitude and frequency.
I could be wrong there though, pseudorandom noise is unfortunately a bit of an awkard and confused topic.

Hugo Elias’s well known article (a wayback machine link since the original is dead) really didn’t help when it claimed to be Perlin noise but actually described fractal noise/brownian noise.

@TomJohnRiddle
Those images look like they’re probably a 1D implementation of the Diamond Square Algorithm if you want a specific term to search for.

@FManga’s right that it could be a good approach to adapt for your trees, but it does depend how fast the CPU can do all the steps.

Ultimately noise generation is more of an art than a science if you’re not particularly good at maths or don’t have the patience to read the papers about it. (I’m both, but more the latter than the former :P )

@FManga +1 for linking to Lode Vandevenne, his demonstrations are very good, especially the one about raycasting.
(I once emailed him because his flood fill algorithm had a typo. He fixed it and replied with a rather nice ‘thank you’. Awkwardly it was much less formal than the email I sent him.)

FManga · March 26, 2018, 9:45pm

You are correct, I oversimplified. You need various layers of Perlin Noise at different resolutions to get it to look like Brownian noise.

It’s kinda hard to call it Diamond Square in 1D, while the principle is the same, there are no diamonds or squares!

Pharap · March 26, 2018, 9:55pm

Fair enough.
Like I say, it’s a bit of a confused topic all around.
One of the ones where the papers haven’t had many ‘normal person’ explanations.

True, but if @TomJohnRiddle wants to go searching for more information it will be easier if he has the proper terminology.

A lot of shapes seem odd with their 1D counterparts - a 1D sphere is just a line (a number and a radius spanning each direction).
Perhaps ‘binary search noise’ would have been a better name?

TomJohnRiddle · March 27, 2018, 9:53am

@FManga, @Pharap thank you very much guys. This post escalated quickly

Me: I need more trees in my forest
Also me: Mhmm I think that I have to think about inner workings of linear congruential generator

Pharap · March 27, 2018, 10:49am

LCGs are actually not very good PRNGs because the numbers sometimes have patterns and can be predictable depending on the chosen settings.

But for your forest that won’t matter much because your aim is just to have a convincing forest, and you’d be using it like a hash instead of a PRNG.

Dreamer2345 · March 27, 2018, 1:32pm

If you use a LFSR with a hard coded seed you can get random sequences with long periods.

http://courses.cse.tamu.edu/walker/csce680/lfsr_table.pdf

Depending on your pickup points

Pharap · March 27, 2018, 1:38pm

A long period wouldn’t really help.
The point is to avoid having a stateful PRNG and just use the PRNG function like a hash.

Like I demonstrated earlier:


// Example settings, might be terrible
const uint16_t multiplier = 7;
const uint16_t increment = 13;

uint16_t lcgStep(uint16_t state)
{
  return ((state * multiplier) + increment); // % modulo;
}

// No more than 8 pixels in either direction
const int8_t offsetMax = 8;
const int8_t offsetMin = -offsetMax;
const uint8_t difference = offsetMax * 2;

xy_point processPoint(xy_point point)
{
  // Combine the 8 bit coords into a 16-bit number
  uint16_t combinedCoords = static_cast<uint16_t>(point.x) << 8 + point.y;
  uint16_t xOffsetBase = lcgStep(combinedCoords);
  uint16_t yOffsetBase = lcgStep(xOffsetBase);

  int8_t xOffset = offsetMin + static_cast<int8_t>(xOffsetBase % difference);
  int8_t yOffset = offsetMin + static_cast<int8_t>(yOffsetBase % difference);

  point.x += xOffset;
  point.y += yOffset;

  return point;
}

The step function for an LFSR would work as a hash though:

uint16_t lsfr(uint16_t state)
{
 uint16_t bit  = ((state >> 0) ^ (state >> 2) ^ (state >> 3) ^ (state >> 5) ) & 1;
 return  (state >> 1) | (bit << 15);
}

But it might not work well on the Arduboy because the Arduboy doesn’t have a barrel shifter.

Dreamer2345 · March 27, 2018, 1:41pm

So something like this is off the table?

static uint16_t rng_state;
uint16_t rng_next() {
  rng_state ^= rng_state << 5;
  rng_state ^= rng_state >> 7;
  rng_state += 28383;

  return rng_state;
}

Pharap · March 27, 2018, 1:51pm

Not if you ‘remove’ the state (i.e. the state becomes the argument), so it’s just the function:

uint16_t rng_next(uint16_t state)
{
  state ^= state << 5;
  state ^= state >> 7;
  return state + 28383;
}

(Though again, lack of barrel shifter could make it larger/slower than on other systems.)

(Fun fact: a function that doesn’t rely on state is known as a ‘pure’ function. In functional languages, all functions must be ‘pure’.)

Yet again, it depends on what works best.
For something simple like forest generation it won’t need to be very complex.

The point is to be able to regenerate the forest ‘on-the-fly’, rather than generating the whole forest at once. Hence why state wouldn’t be a good idea (unless the map was chunked, then it might work).

TomJohnRiddle · March 29, 2018, 10:13pm

Hmm. It seems I’ve got it! Certainly needs some additional work, however I am quite happy with the result!

Big thanks go to @Pharap and @FManga

Pharap · March 29, 2018, 10:21pm

Strange sounds in the background.
(Forrest Gump? An intentional pun?)

I like the fox sprite. (I assume it’s a fox, maybe it’s a cat?)

Secret 20% off Arduboy Coupon!

Use coupon code "ERRORCOUPON" at checkout!

Buy Arduboy Now!

Arduboy

Lost in (procedurally generated) forest. Memory constraints