Help me with C++ for my game

(Pharap) #283

You could just flatten the two inputs into a single input.

If x and y are uint8_t then instead of trying to find a two-input hash, you can just combine them into a uint16_t and hash that.

I wrote a decent pretty decent hash function for Minesweeper, but it’s 32 bit:

I’m 80% certain that it’s bijective (i.e. it’s a ‘perfect hash function’).


I tried implementing it in GameMaker, but I get a very non random distribution. I thought bitshifting would work well to combine two values but it really doesn’t. It wasn’t obvious with my value noise but with my

var value = (argument0 << 16) + argument1;
value ^= (value << 13);
value ^= (value >> 17);
value ^= (value << 5);

I forgot to specify that I use it to set a seed. Maybe my problem isn’t my method to combine two numbers, but the pseudo random number generator (I get a very random layout if I don’t set the seed on the coordonates, but if I set the seed, it’s very non-random)

I’ll try implementing a known pseudo random number generator, it might end up working better for what I need

Edit: this seems to work very well, as long as the seed is equal to or higher than a 100:

var _x = ((xpos*seed*seed)/1337);
var _y = ((ypos*seed*seed)/501);

random_set_seed((_x << 16) + _y);

Not sure how slow or quick that would be on the Arduboy, but it shouldn’t matter as it is only for generating a room. I might try creating/implementing a pseudo random number generator. I don’t need anything with a long period as it’s only to generate a few elements

Anyway here’s how it looks so far:

(Pharap) #285

What is the PRNG?
Is it a linear congruential generator? A mersenne twister?

Also, how are you measurining random vs non-random?

Does gamemaker not have a | operator?

The Arduboy doesn’t have a barrel shifter, so shifting by 16 might be an issue, but it also might not be a major issue.

It can also only do 8 bit by 8 bit multiplication natively, the compiler has to inject a multiplication algorithm for larger multiplications, and it can’t do any division natively, the compiler always has to inject a division algorithm for that.

The point of having a long period is less chance of repetition.

A sequence with a period of 256 repeats after 256 elements.


My maze works vs it doesn’t (it was that obvious, my maze was just moving two tiles left). Maybe it has to do with even numbers, I’m honestly confused why it didn’t work)

If you set the seed everytime you’ll never go far in the period (picking a number for the room, then picking a few more numbers of variants). Since I pick the room layout, I call it only once. As long as the first number seems random compared to the previous seed, it’s good enough

Quick interesting thing: random i = 7 * i mod 11
i being the seed, this returns a random number between 1 and 10 and is very simple. It must have a period of 10, I just found it interesting how simple it is

It does, I’m just not very experience with bitwise operations. Thank you for suggesting it

Edit: well my method to set the seed seems to be working well, I’ll port this to the Arduboy and see how my rooms generate. I don’t care too much if I can’t reproduce the same results on PC as long as the results on the Arduboy are just as good. If it doesn’t work well, I’ll get back into the pseudo random number generator rabbit hole

(Pharap) #287

Now I’m not sure what you’re actually doing.

Are you doing the hash, seeding a PRNG and then only pulling one number from the PRNG?

If so you might want to stop thinking about the concept of a PRNG and just stick to thinking about hash functions.
A PRNG doesn’t make much sense unless its generating a sequence of values.
Practically all PRNG discussion is about the properties of the number sequences that they generate.

Hash function discusson concentrates more on 1:1 mappings and potential collisions than sequence generation.

The two ideas overlap a lot, but have slightly different goals.

Yes, the reason for that is because % 11 reduces the possible number of outputs to just 10 values (0 to 10).
So after the 10th value you’ll end up back at the start.

That’s why modulo operations are almost never used as part of a PRNG.

Just so you know, the reason I advise using | and not + is because of the following property:

1 | 1 == 1
1 + 1 == 2

So using + can cause bugs when trying to combine bits if you accidentally apply it more than once, or two groups of bits that overlap, whereas | does not have that problem.


I’m using a unique number to set the seed of the random number generator, so you’re absolutely correct that a hash function is what I really need. However it’s more complex. I went over xxHash source code and I get really confused

Also, if I need to generate other things in the room afterwards, I’ll need pseudo random numbers anyway. So a pseudo random number generator seems like a good option

(Pharap) #289

I’ve just looked at xxHash myself… that’s far too big to be useful on the Arduboy.

(And it’s written in C, so it would undoubtedly be bad C++ code.)

There are probably a lot of simpler hash functions out there.

For example, this one:

int hash = 13;
hash = (hash * 7) + field1.GetHashCode();
hash = (hash * 7) + field2.GetHashCode();
// ...
return hash;

In that case, why bother with hashing before seeding at all?
Why not just feed (x << 16) | (y << 0) in as the seed?


Do you mean this?

uint8_t Dungeon::getRoomLayout(int16_t xpos, int16_t ypos) {
    int16_t currentSeed = (xpos << 8) | ypos;

    return random(5, 10);

If so, simply because it wasn’t working (in GameMaker). It was the exact same maze layout, but shifted two tiles left when using a different seed. Maybe it will work on the Arduboy, but if not, this works in GameMaker for my dungeon:

var _x = ((argument0*seed*seed)/1337);
var _y = ((argument1*seed*seed)/501);

random_set_seed((_x << 16) + _y);

(Pharap) #291

Yes, like that.

Although now I’m confused as to how big your x and y values are.
If they’re going to be less than 256 then << 8 will be enough, but then you don’t need to use int16_t for them.
If they are going to be 256 or greater then you’d need a larger shift than that, or you’d have to do some masking.

Also, like I say, if you’re only using the one value then you shouldn’t be using a random number generator, you should just be using a hash function.

More importantly, if you need the sequence to be the same every time then you really shouldn’t use random, you should pick and PRNG and include it in your code.
The implementation of random could change without warning.

Were you using GameMaker’s built-in random number generator?

If so, I’m guessing they’re using a bad PRNG.
E.g. a linear congruential generator with some bad parameters:


Maybe, but in general PSRNGs are made to have a good distribution compared to the last and future outputs, but they’re not necessarely made to have a uniform first output from a consecutive set of seeds.

Also, could have been the modulo bias. I don’t know how their irandom() function is implemented

I’m almost done porting this to the Arduboy, I’ll be able to test everything very soon

Correct, I should bitshift by 16

(Pharap) #293

This is kind of the crux of the issue.

To use a PRNG in this way you have to know what kind of PRNG you’re using or your results are going to be very different between implementation.

You could get some very good results in GameMaker and some very bad results on Arduboy (or vice versa) and it could be down to the PRNG.

If you pick a PRNG and implement it so you know you’ve got the same PRNG on each system (even if it’s a bad PRNG to start with) then you can at least have a more controlled environment for figuring out if the code is behaving incorrectly.
If the PRNGs aren’t the same and one of the two is behaving badly, you won’t know if you’ve made a mistake in the code or if it’s just the PRNG acting differently.


Which is why I’ll probably end up in the PRNG rabbit hole once again

I’m almost done with the Arduboy prototype, I can’t believe it’s already so late. I might go sleep before I finish, depending on my energy levels


I’m getting an error message, which I’m assuming is because of the way I try to return a reference to an array.
Source code:

I’ll go to bed, I’ll continue tomorrow

Error message
sketch\DungeonGenerator.cpp: In function 'uint8_t getRoomImage(uint8_t)':

sketch\DungeonGenerator.cpp:80:41: warning: invalid conversion from 'const uint8_t (*)[10] {aka const unsigned char (*)[10]}' to 'uint8_t {aka unsigned char}' [-fpermissive]

             return &RoomWallLayoutData::Zero;


sketch\DungeonGenerator.cpp:84:41: warning: invalid conversion from 'const uint8_t (*)[10] {aka const unsigned char (*)[10]}' to 'uint8_t {aka unsigned char}' [-fpermissive]

             return &RoomWallLayoutData::OneLeft;


sketch\DungeonGenerator.cpp:87:41: warning: invalid conversion from 'const uint8_t (*)[10] {aka const unsigned char (*)[10]}' to 'uint8_t {aka unsigned char}' [-fpermissive]

             return &RoomWallLayoutData::OneRight;


sketch\DungeonGenerator.cpp:90:41: warning: invalid conversion from 'const uint8_t (*)[10] {aka const unsigned char (*)[10]}' to 'uint8_t {aka unsigned char}' [-fpermissive]

             return &RoomWallLayoutData::OneUp;


sketch\DungeonGenerator.cpp:93:41: warning: invalid conversion from 'const uint8_t (*)[10] {aka const unsigned char (*)[10]}' to 'uint8_t {aka unsigned char}' [-fpermissive]

             return &RoomWallLayoutData::OneDown;


sketch\DungeonGenerator.cpp:97:41: warning: invalid conversion from 'const uint8_t (*)[10] {aka const unsigned char (*)[10]}' to 'uint8_t {aka unsigned char}' [-fpermissive]

             return &RoomWallLayoutData::TwoLeftRight;


sketch\DungeonGenerator.cpp:100:41: warning: invalid conversion from 'const uint8_t (*)[10] {aka const unsigned char (*)[10]}' to 'uint8_t {aka unsigned char}' [-fpermissive]

             return &RoomWallLayoutData::TwoLeftUp;


sketch\DungeonGenerator.cpp:103:41: warning: invalid conversion from 'const uint8_t (*)[10] {aka const unsigned char (*)[10]}' to 'uint8_t {aka unsigned char}' [-fpermissive]

             return &RoomWallLayoutData::TwoLeftDown;


sketch\DungeonGenerator.cpp:106:41: warning: invalid conversion from 'const uint8_t (*)[10] {aka const unsigned char (*)[10]}' to 'uint8_t {aka unsigned char}' [-fpermissive]

             return &RoomWallLayoutData::TwoUpDown;


sketch\DungeonGenerator.cpp:109:41: warning: invalid conversion from 'const uint8_t (*)[10] {aka const unsigned char (*)[10]}' to 'uint8_t {aka unsigned char}' [-fpermissive]

             return &RoomWallLayoutData::TwoRightUp;


sketch\DungeonGenerator.cpp:112:41: warning: invalid conversion from 'const uint8_t (*)[10] {aka const unsigned char (*)[10]}' to 'uint8_t {aka unsigned char}' [-fpermissive]

             return &RoomWallLayoutData::TwoRightDown;


sketch\DungeonGenerator.cpp:116:41: warning: invalid conversion from 'const uint8_t (*)[10] {aka const unsigned char (*)[10]}' to 'uint8_t {aka unsigned char}' [-fpermissive]

             return &RoomWallLayoutData::ThreeLeftRightDown;


sketch\DungeonGenerator.cpp:119:41: warning: invalid conversion from 'const uint8_t (*)[10] {aka const unsigned char (*)[10]}' to 'uint8_t {aka unsigned char}' [-fpermissive]

             return &RoomWallLayoutData::ThreeLeftRightUp;


sketch\DungeonGenerator.cpp:122:41: warning: invalid conversion from 'const uint8_t (*)[10] {aka const unsigned char (*)[10]}' to 'uint8_t {aka unsigned char}' [-fpermissive]

             return &RoomWallLayoutData::ThreeLeftUpDown;


sketch\DungeonGenerator.cpp:125:41: warning: invalid conversion from 'const uint8_t (*)[10] {aka const unsigned char (*)[10]}' to 'uint8_t {aka unsigned char}' [-fpermissive]

             return &RoomWallLayoutData::ThreeRightUpDown;


sketch\DungeonGenerator.cpp:129:41: warning: invalid conversion from 'const uint8_t (*)[10] {aka const unsigned char (*)[10]}' to 'uint8_t {aka unsigned char}' [-fpermissive]

             return &RoomWallLayoutData::Four;


sketch\DungeonGenerator.cpp: In member function 'void Dungeon::draw()':

sketch\DungeonGenerator.cpp:139:65: warning: invalid conversion from 'uint8_t {aka unsigned char}' to 'const uint8_t* {aka const unsigned char*}' [-fpermissive]

             Sprites::drawSelfMasked((i)*8, (j)*8, layoutImage, 0);


In file included from C:\Users\Alex\Documents\Arduino\libraries\Arduboy2\src/Arduboy2.h:14:0,

                 from sketch\DungeonGenerator.cpp:3:

C:\Users\Alex\Documents\Arduino\libraries\Arduboy2\src/Sprites.h:241:17: note:   initializing argument 3 of 'static void Sprites::drawSelfMasked(int16_t, int16_t, const uint8_t*, uint8_t)'

     static void drawSelfMasked(int16_t x, int16_t y, const uint8_t *bitmap, uint8_t frame);


sketch\DungeonGenerator.cpp: In function 'uint8_t getRoomImage(uint8_t)':

sketch\DungeonGenerator.cpp:132:1: warning: control reaches end of non-void function [-Wreturn-type]



In file included from C:\Users\Alex\Documents\Arduino\libraries\Arduboy2\src/Arduboy2.h:11:0,

                 from C:\Users\Alex\Documents\Arduino\tutorial projects\dungeonGenerator\dungeonGenerator.ino:6:

C:\Program Files (x86)\Arduino\hardware\arduino\avr\libraries\EEPROM\src/EEPROM.h:145:20: warning: 'EEPROM' defined but not used [-Wunused-variable]

 static EEPROMClass EEPROM;


In file included from C:\Users\Alex\Documents\Arduino\libraries\Arduboy2\src/Arduboy2.h:11:0,

                 from sketch\DungeonGenerator.cpp:3:

sketch\DungeonGenerator.cpp: At top level:

C:\Program Files (x86)\Arduino\hardware\arduino\avr\libraries\EEPROM\src/EEPROM.h:145:20: warning: 'EEPROM' defined but not used [-Wunused-variable]

 static EEPROMClass EEPROM;


C:\Users\Alex\AppData\Local\Temp\ccSwhAzH.ltrans0.ltrans.o: In function `draw':

sketch/DungeonGenerator.cpp:138: undefined reference to `Dungeon::getRoomImage(unsigned char)'

collect2.exe: error: ld returned 1 exit status

exit status 1
Error compiling for board Arduboy.

(Pharap) #296

Firstly, getRoomImage is supposed to return a uint8_t, not a pointer.

Secondly, to get a pointer from an array you’d have to write either &array[0] or array.

Personally I prefer the first version because it makes it clearer that the resulting pointer points to the first byte of the array, and you don’t have to worry about type decay rules.
But sometimes the second version looks better or makes more sense.

Secondly, I’d like to point out that instead of casting in each case,
you could just cast the variable you’re testing.

So your function becomes this:

const uint8_t * Dungeon::getRoomImage(uint8_t roomLayout) {
    RoomWallLayoutID layout = static_cast<RoomWallLayoutID>(roomLayout);
    switch(layout) {
        case RoomWallLayoutID::Zero:
            return &RoomWallLayoutData::Zero[0];
        case RoomWallLayoutID::OneLeft:
            return &RoomWallLayoutData::OneLeft[0];
        case RoomWallLayoutID::OneRight:
            return &RoomWallLayoutData::OneRight[0];
        case RoomWallLayoutID::OneUp:
            return &RoomWallLayoutData::OneUp[0];
        case RoomWallLayoutID::OneDown:
            return &RoomWallLayoutData::OneDown[0];
        case RoomWallLayoutID::TwoLeftRight:
            return &RoomWallLayoutData::TwoLeftRight[0];
        case RoomWallLayoutID::TwoLeftUp:
            return &RoomWallLayoutData::TwoLeftUp[0];
        case RoomWallLayoutID::TwoLeftDown:
            return &RoomWallLayoutData::TwoLeftDown[0];
        case RoomWallLayoutID::TwoUpDown:
            return &RoomWallLayoutData::TwoUpDown[0];
        case RoomWallLayoutID::TwoRightUp:
            return &RoomWallLayoutData::TwoRightUp[0];
        case RoomWallLayoutID::TwoRightDown:
            return &RoomWallLayoutData::TwoRightDown[0];

        case RoomWallLayoutID::ThreeLeftRightDown:
            return &RoomWallLayoutData::ThreeLeftRightDown[0];
        case RoomWallLayoutID::ThreeLeftRightUp:
            return &RoomWallLayoutData::ThreeLeftRightUp[0];
        case RoomWallLayoutID::ThreeLeftUpDown:
            return &RoomWallLayoutData::ThreeLeftUpDown[0];
        case RoomWallLayoutID::ThreeRightUpDown:
            return &RoomWallLayoutData::ThreeRightUpDown[0];
        case RoomWallLayoutID::Four:
            return &RoomWallLayoutData::Four[0];

But, if you want to save progmem, there’s a better way.
Instead of hoping the compiler will generate a lookup table instead of a chain of ifs,
you can just make your own lookup table:

const uint8_t * const roomLookup[] PROGMEM =

const uint8_t * Dungeon::getRoomImage(uint8_t roomLayout)
	if(roomLayout >= 0x10)
		return nullptr;
	return reinterpret_cast<const uint8_t *>(pgm_read_ptr(&roomLookup[roomLayout]));

Same result, 114 bytes cheaper.

Also, you’re going to need to change your draw function to use a pointer too:

void Dungeon::draw() {
    for(int16_t i = 0; i < 16; i++) {
        for(int16_t j = 0; j < 8; j++) {
            uint8_t layout = this->rooms[16 * j + i];
            const uint8_t * layoutImage = this->getRoomImage(layout);
            Sprites::drawSelfMasked((i)*8, (j)*8, layoutImage, 0);

(Pharap) #297

I made quite a number of changes for you to look over.
Everything is itemised and explained.

There was one more change I was going to make,
but I decided this is probably overwhelming enough without getting into const-correctness.

Before the code took about 8300 bytes of progmem,
now it’s down to 8136 with improved speed and type safety,
and importantly the final result is still the same.

I get the impression that a lot of people believe that things like scoped enumerators or small, simple functions incur some kind of memory or performance cost, but in reality they rarely do.

Hopefully these commits will serve as an example of that fact.


First of all, thank you so much

I’m looking over the changes and I think I understand why arrays are passed this way

I think you’ve mentioned this before, and this is gonna be my simplified version of things, but an array doesn’t actually “exists,” it’s just a block of data of the same type that are all hugging each other. If you know the first index of the array, then you know of the whole array (assuming you know the size of it)

Which is why you return &array[0] like this. Did I get this part right?

So, the same way you can cast an enum class to it’s “original/hidden” data type, you can cast a variable to an enum class this way?


I should probably do some reading on pointers to understand this better.

const uint8_t * layoutImage = this-&gt;getRoomImage(layout);
Sprites::drawSelfMasked((i)*8, (j)*8, layoutImage, 0);

Here’s what I think I understand.

  1. Pointers are automatically cleaned up (no need to delete them or do weird things) if they are declared inside a function, just like most things. The end of the function is the end of their scope.
  2. If you make a constant pointer, then it always makes it ‘safe’ as you can’t screw up and modify the original value accidentally or because you were sleepy and did your function wrong.
  3. We’re not doing that, but if we were using “new” for dynamic memory, then you’d have to delete the instance that was assigned to it before the end of the function

Quick question, was I right to do a static_cast to 32 integer here to avoid overflows and weird implicit casting?
I’m honestly surprised how far I got with my Arduboy port before I couldn’t go any further. A month or two ago I would have been stuck much earlier. And all this past my usual bedtime too

RoomWallLayoutID Dungeon::getRoomLayoutFromSeed(int16_t xpos, int16_t ypos) {
int32_t currentSeed = (static_cast&lt;int32_t&gt;(xpos) &lt;&lt; 16) static_cast&lt;int32_t&gt;(ypos);

layout |= RoomWallLayoutID::OneLeft;
Nice, that means we can do |= and &= just like we can do *=, /=, += etc

I’m not sure if this is working as intended, so I’ll explain in plain English what I need and you might be able to confirm if this is correct. It probably is, but without seeing the binary it’s a bit harder for me to check. Edit: by binary I mean “0b0010” for example

My plain English explaination

If I want info on the room at index x=10,y=10, and it’s a room that needs to be generated from adjacent rooms, it goes about it this way:
If the room to the right, has a wall to the left, then I need a wall to the right. (the two rooms sharethe same wall). I tried to do this by using the 4 bits each representing a wall. The higher bit represents a wall on the left, the second highest bit represents the wall on the right. So, if they were booleans, it’d be like this

isThereAleftWall isThereArightWall isThereAnupperWall isThereAbelowWall

This is how I tried encoding my rooms to work with bitwise operation (and it seems you kept it that way, based on the order from the look up table)

The function to check for this passes an x and a y position, that’s the room we check the walls for. Then, based on what is learned from that room, we find what fits.

The code I'm referring to
constexpr inline RoomWallLayoutID operator (RoomWallLayoutID left, RoomWallLayoutID right)
return static_cast&lt;RoomWallLayoutID&gt;(static_cast&lt;uint8_t&gt;(left) static_cast&lt;uint8_t&gt;(right));

inline RoomWallLayoutID &amp; operator =(RoomWallLayoutID &amp; left, RoomWallLayoutID right)
left = (left right);
return left;

constexpr inline RoomWallLayoutID operator &amp;(RoomWallLayoutID left, RoomWallLayoutID right)
return static_cast&lt;RoomWallLayoutID&gt;(static_cast&lt;uint8_t&gt;(left) &amp; static_cast&lt;uint8_t&gt;(right));

inline RoomWallLayoutID &amp; operator &amp;=(RoomWallLayoutID &amp; left, RoomWallLayoutID right)
left = (left &amp; right);
return left;

constexpr inline RoomWallLayoutID operator ^(RoomWallLayoutID left, RoomWallLayoutID right)
return static_cast&lt;RoomWallLayoutID&gt;(static_cast&lt;uint8_t&gt;(left) ^ static_cast&lt;uint8_t&gt;(right));

inline RoomWallLayoutID &amp; operator ^=(RoomWallLayoutID &amp; left, RoomWallLayoutID right)
left = (left ^ right);
return left;

I’m going for a walk I’ll be back
Edit: I’m back I’ll finish looking through the changes

I didn’t know constexpr could work with constant member variables. Maybe it’s only when they’re static variables? (the same constant member variable representing all instances of this class?)

class Dungeon {
        RoomWallLayoutID rooms[16*8] = {};
        static constexpr uint8_t tileWidth = 8;
        static constexpr uint8_t tileHeight = 8;
         static constexpr uint8_t width = 16;
        static constexpr uint8_t height = 8;
        static constexpr uint8_t roomCount = width * height;
        RoomWallLayoutID rooms[roomCount] = {};
        int16_t x = 0;
        int16_t y = 0;

Here you switched some int16_t to uint16_t. I had picked a signed integer to avoid problems when converting signed value to unsigned values. For example if the player goes towards negative x and y coordinates, and therefore the dungeon is in negative coordinates

What are your thoughts on this?

I like all of this and now that I know about preincrement vs post increment, I like those too

I’m not entirely sure if this is gonna work properly

Ohhhh, it returns a pointer, so you can modify it directly?

this->getRoomLayoutAt(i, j) = getRoomLayoutFromNeighbours(i, j);

Also, it seems like a line of code is missing a line after the if statement. It should be along the lines if “if i%2 == j%2 getLayoutFromSeed(i, j) else getLayoutFromNeighbours”

for(uint16_t i = xpos; i < xpos + width; ++i) {
    for(uint16_t j = ypos; j < ypos + height; ++j) {
        if ((i % 2) != (j % 2)) {
        else {
            this->getRoomLayoutAt(i, j) = getRoomLayoutFromNeighbours(i, j);

Seperation of concerns I’ve heard about this concept before, this is great, I’ll be able to use this as an example to understand it

I wasn’t sure how to name those without taking too many words but making them clear enough to underrstand, thank you

bool hasWallLeft(uint16_t xpos, uint16_t ypos);
bool hasWallRight(uint16_t xpos, uint16_t ypos);
bool hasWallUp(uint16_t xpos, uint16_t ypos);
bool hasWallDown(uint16_t xpos, uint16_t ypos);

Done! I think I looked through everything. I’ll merge it, there’s only one thing I’m not 100% will work but it’s an easy fix if it doesn’t

Thank you so much, this was a great learning opportunity

(Pharap) #299

Strictly speaking, in C++ you can pass them by reference if you include the size of the array.
As of C++11 the ‘proper’ way is to pass a std::array or a reference to a std::array,
but Arduino doesn’t have that facility.

Passing arrays as a pointer to the first element is a C-ism,
but it’s one of the few that’s still sometimes useful in C++.

Actually it does. If you wrap an array in a struct then you can pass it around like any other type.


struct MyArray
    char data[4];

void myFunc(MyArray myArray)
   // Array copied normally[0];

And in fact, this is (a very simplified version of) how std::array works.

It’s only when you try to pass a bare array that it won’t be copied.
Instead the array “decays” and becomes a pointer instead.

Like I said before, this is an unfortunate C-ism.
If C++ had broken away from C early on in development then we might have been spared this headache.

Scoped enumerations can be converted to and from any integer type.
This is because when the compiler has finished processing them, they effectively are just plain integer types.
All the magic happens at compile time.

This is one of the reasons I strongly advocate using them, you get added type-safety and protection from bugs for no added cost.
The compiler does all the heavy lifting for you and you end up with the same machine code.

Not quite… Prepare yourself for a text wall.

Firstly a pointer is basically just an integer.
Imagine RAM is a giant array - a pointer is an index into that array.
Strictly speaking, you could have a language that used integers instead of pointers (and in fact, that’s exactly what assembly does),
but the reason for having pointers is our friend ‘type-safety’.
char * is different from int *, and that’s a good thing!

(Technically it’s a bit more complicated than that, because a pointer can point to things other than RAM depending on the computer. And when I say ‘computer’, I’m including games consoles, watches, phones, toasters etc)

As for ‘cleaning up’, because pointers are just integers, they behave like integers in terms of how they ‘live’.
They’re cheap to create and cheap to destroy.

However, a pointer’s lifetime is different from the lifetime of the thing it points to.
Now we’re getting into dynamic memory, so I’ll mention that in a moment.

Yes… and no.

A const pointer can’t be used to modify the data that the pointer points to.
However, that doesn’t mean that the data can’t be modified.

const is a promise that “I won’t modify this data”,
it’s not a promise that someone else won’t.


int a = 5;
const int * p = &p;

// a is 5, *p is 5

// Compiler error, can't modify a const object
*p = 6;

a = 10;

// a is 10, thus *p is also 10

But hopefully you’ll never work with anyone who would do something as awful as that.

You won’t have to worry about this too much on the Arduboy,
but ‘dynamic allocation’ is where an object (when I say ‘object’, I’m including char, int, float etc) can be created at runtime in an area of memory called the heap (or the ‘free store’, but if I explain the ‘free store’ this is going to get too technical).
The object exists on the heap until it is deallocated,
and deciding when to deallocate it can be a very difficult problem to solve.

When people talk about ‘memory leaks’, that’s what they mean - some data on the heap hasn’t been deallocated when it should have been and the pointer to it has been destroyed, so now it’s stuck there until the program ends.

Ah, here is the ‘no’.

If you allocated some memory and then deallocated it before the end of the function, then 8 or 9 times out of 10 you would have been better off just using a local variable, .

(There are precisely two cases that I can think of where it makes sense to allocate on the heap for the duration of a function.)

Yes. If you hadn’t added the casts then this is what would have happened:

int32_t currentSeed = static_cast<int32_t>((static_cast<int>(xpos) << 16) | (static_cast<int>(ypos) << 0));

On a 32-bit system you’d be fine, but on Arduboy’s 8-bit system, int is 16 bits (because int must be at least 16 bits, but can be larger).

The rules of integer promotion take a bit of learning,
but the simplified version is:

  • Any arithmetic or bitwise operations on types smaller than int promote to int
  • Any arithmetic or bitwise operations on int continue to use int
  • Any arithmetic or bitwise operations on types larger than int continue to use the larger types
  • Any arithmetic or bitwise operations involving float promote integer types to floats
  • Any arithmetic or bitwise operations involving double promote integer types and floats to doubles
  • Any arithmetic or bitwise operations involving long double promote integer types, floats and doubles to long doubles

On the Arduboy, float, double and long double are all the same (which I think technically breaks the rules of the standard, but makes sense given how limited the AVR chips are).

Yep. In C++, almost every operator is overloadable.
(This is part of why my FixedPoints library works so well.)

If you vaguely know how references work and you read through my code it should hopefully make sense how the operators work.

I’ve thought of pretty much the same approach once before,
but I think I used a different bit order.

Aha, found the image in my archive:

And while I was there I found these :

I’ll have a look for the code at some point.

Yep, I can’t think of any reason why one arrangement would be better than any other.
(I could probably think of one eventually, but I’m not sure it’s worth worrying about.)

The code you posted is just the type safety stuff that I added.
Other than being safer, it behaves exactly the same as before.

Yep, only when they’re static.

I don’t know what you mean by this,
or why you’ve added two sets of rooms.

While I think of it though, I’d like to point out that writing:

int array[10] = { 0 };

Does not fill the array with zeroes.

You do end up with an array of zeroes, but for a different reason.
If you’d written:

int array[10] = { 1 };

You’d be left with an array with a 1 and index 0, and everything else would be 0.

That’s one of the reasons I changed the initialisation to = { };.

I would suggest avoiding negative coordinates if you can.
The processor gets on much better with unsigned integers.

If you use signed integers, the CPU occaisionally has to do some extra processing when performing calculations.

If negative values are necessary for some reason, then stick with them for coordinates, but make sure you use unsigned values for array indexing.

How you convert signed integers to unsigned integers will depend on what you’re trying to do, but if you’re trying to do array indexing, do not just cast to unsigned integers or you could end up with a buffer overflow.

Oddly I don’t think the shfting thing is in my style guide yet, but ‘spaces around binary operators’ and ‘prefer preincrement’ are.

I want to stress that for the most basic types the compiler will optimse i++ into ++i,
but it’s good to get used to ++i because if you ever start writing C++ for desktop you’ll encounter things called ‘iterators’,
and when you’re using those the difference really will matter because the compiler won’t be able to help you.

Better than a pointer, a reference.
A reference is a bit like a pointer in that it refers to another object,
but the way you use it is more similar to how you’d use a normal object.

Personally I think references should be taught before pointers because in the majority of cases references are the better option.

You don’t have to worry about them being nullptr, they can only be assigned once, and in some cases they can be optimised better than pointers can.

Taking the address of an object forces it to exist in RAM somehow, but making a reference to an object doesn’t, so even if you’ve made a reference to an object, it’s allowed to exist in a register rather than RAM.
The reason for this is that the compiler is allowed to replace the use of a reference with the use of the actual object that the reference refers to if it’s able to do so.

I.e. I could write this:

int & itemRef = array[x, y];
itemRef = itemRef * itemRef;

And the compiler could translate it to the equivalent of:

array[x, y] = array[x, y] * array[x, y];

It is there?

The idea is the you should keep code modular and limit the amount of responsibility each function/class/namespace has.

If you keep things small and individual then it’s easier to compose those small pieces together to create more complex logic.

It’s also a lot easier to debug code that’s only doing a few things rather than trying to do lots at once.

Also, people often think that having lots of functions means having lots of code, but the compiler is so good at inlining and analysing functions that actually using lots of small functions is better for it.

Writing longer functions actually makes it harder for the compiler to optimise the code because it has to keep more context in memory, and it struggles to see the bigger picture, so it starts making bad decisions.
If the functions are kept small then it can ‘understand’ the code better and thus make better decisions.

There’s an old programming joke:

There are only two difficult problems in Computer Science:
Naming things, cache invalidation and off by one errors.

Naming is always difficult.
It’s the sort of thing that only experience can improve.
(Although having a few rules like ‘functions names should describe actions’, ‘variable names should be nouns’ and ‘names should follow the rules of the English language’ can really help.)

If you have some time free one day, have a quick look at some different libraries to see how they chose to name things.
Not all libraries are good at naming things,
but it helps a bit to see what everyone is doing,
so you can see what works and what doesn’t.

Also, it helps to try to read your code out loud (or in your head) as if it was English.
Aim to make your code sound like how you would describe the process to another programmer in plain English.
For example (taking an example from Minesweeper):

if (!tile.isVisible())
	if (tile.getMineCount() == 0)
		stack.push(Point(x, y));

Can be thought of as:

if tile is not visible then
	show tile

	if tile mine count is zero then
		push the point (x, y) onto the stack

It’s never going to be exact, but if the code looks similar to how you would explain it out loud then it’s more likely to be readable by other programmers.

This is also why it’s important to do rubber duck debugging.
If your explanation of how your code works doesn’t match up with how your code is written, then either your code, your explanation or both (your code and your explanation) need revising.

I’ve tested everything and it was giving me the exact same output as before I started changing things.

Being able to rewrite code in a smaller/faster/better way without affecting the functionality is something I’m quite well practised in.
Most of the time, if there’s a game out there that I’ve contributed to behind the scenes, that’s the sort of thing I will have been doing (along with providing advice and explaining the concepts).

If you’ve learnt something then the time I’ve spent has been worthwhile.

If you ever need any of your code looked at again, don’t hesitate to ask.
I’ve made behind the scenes contributions to far more games than I’ve published.

I always try to make sure I explain any of my changes in the commit message, regardless of whose project I’m working on.

The end… at last.


I’m always learning a ton with you.

Thank you. This might sound weird and I don’t think you’d need it, but if there’s ever a game you’d like to make but you don’t have the time/you’d rather spend time helping others, I’d love to make the game for you. You’d help someone while getting a game you want made

I know this is a weird idea because you could do it faster just by yourself, but it’s the only thing I can think of to give back. i.e learning while making your game instead of learning while making mine

I had forgotten how you phrased this, so I was gonna jump and say “wrong!!” but you’re not wrong, the problem I’m getting was probably there before, I hadn’t run the game yet when I uploaded the source (most tiles are wrong and don’t fit with the others but not that the “engine” is done it should be easy to fix this)

One way to explain it is, walls should be 2 pixels wide, otherwise it shouldn’t be a wall.

I’ll try drawing all the rooms to see if they’re the right sprites, maybe I just put the wrong images (or maybe I need to use my seed system…) I got things to try

Wow. This looks exactly like mine. When you said you had looked into Wang tiles before, I think you didn’t do just that. I think you went all in and did the whole thing. (if you didn’t need it for a game, the only difference might be whether you used the chess board system or not to make tiles deterministic in isolation)

As for the bits, you used almost the same thing, the difference is you went YX instead of XY

I don’t remember if I showed a screenshot before of the latest version, but here it is:

I’ll be doing some tests to find out what the rooms don’t generate properly. Either it’s the seed or it’s something else

Edit: found the first bug. This was saying - 1 instead of +1

bool belowRoomHasUpperWall = DungeonGenerator::hasWallUp(xpos, ypos + 1);

Edit: I set this up to verify that all the images are correct:
Edit: the first 8 images are correct so far. By the way I’m using Google’s binary to decimal conversion tool
Edit: the sprites match their numbers correctly, this means the culprit has to be from the getLayoutFromNeighbours function
As a note, the symbols it gives is an actually valid number system. It’s quite interesting.
I could reuse those sprites for a puzzle/decoding thing in the game…

void Dungeon::draw() {
    for(uint16_t i = 0; i < width; ++i) {
        for(uint16_t j = 0; j < height; ++j) {
            if (arduboy.pressed(A_BUTTON) && (!(i % 2) == (j % 2))) {
            if (arduboy.pressed(B_BUTTON) && ((i % 2) == (j % 2))) {
            RoomWallLayoutID layout = this->getRoomLayoutAt(i, j);
            const uint8_t * layoutImage = this->getRoomImage(layout);
            Sprites::drawOverwrite(i * tileWidth, j * tileHeight, layoutImage, 0);
    arduboy.fillScreen (WHITE);
    uint8_t j = 1;
    uint8_t margin = tileWidth+4;
    for(uint8_t i = 0; i < 8; i++) {
        Sprites::drawOverwrite(i * margin + margin, j * margin, getRoomImage(static_cast<RoomWallLayoutID>(i)), 0);
    for(uint8_t i = 8; i < 16; i++) {
        Sprites::drawOverwrite(i * margin - 8*margin + margin, j * margin, getRoomImage(static_cast<RoomWallLayoutID>(i)), 0);


(I edit/added a few of comments in my last post)

I found the one source of the problem. I’m doing +1, -1 twice. Once when calling the function, and again inside the function.

Problematic code
RoomWallLayoutID DungeonGenerator::getRoomLayoutFromNeighbours(uint16_t xpos, uint16_t ypos) {
    bool leftRoomHasRightWall = DungeonGenerator::hasWallRight(xpos - 1, ypos);
    bool rightRoomHasLeftWall = DungeonGenerator::hasWallLeft(xpos + 1, ypos);
    bool aboveRoomHasDownWall = DungeonGenerator::hasWallDown(xpos, ypos - 1);
    bool belowRoomHasUpperWall = DungeonGenerator::hasWallUp(xpos, ypos + 1);

    RoomWallLayoutID layout = RoomWallLayoutID::Zero;
    if (leftRoomHasRightWall) {
        layout |= RoomWallLayoutID::OneLeft;
    if (rightRoomHasLeftWall) {
        layout |= RoomWallLayoutID::OneRight;
    if (aboveRoomHasDownWall) {
        layout |= RoomWallLayoutID::OneUp;
    if (belowRoomHasUpperWall) {
        layout |= RoomWallLayoutID::OneDown;

    return layout;

bool DungeonGenerator::hasWallLeft(uint16_t xpos, uint16_t ypos) {
    RoomWallLayoutID leftRoom = DungeonGenerator::getRoomLayoutFromSeed(xpos - 1, ypos);
    return ((leftRoom & RoomWallLayoutID::OneRight) != RoomWallLayoutID::Zero);
bool DungeonGenerator::hasWallRight(uint16_t xpos, uint16_t ypos) {
    RoomWallLayoutID rightRoom = DungeonGenerator::getRoomLayoutFromSeed(xpos + 1, ypos);
    return ((rightRoom & RoomWallLayoutID::OneLeft) != RoomWallLayoutID::Zero);
bool DungeonGenerator::hasWallUp(uint16_t xpos, uint16_t ypos) {
    RoomWallLayoutID aboveRoom = DungeonGenerator::getRoomLayoutFromSeed(xpos, ypos - 1);
    return ((aboveRoom & RoomWallLayoutID::OneDown) != RoomWallLayoutID::Zero);
bool DungeonGenerator::hasWallDown(uint16_t xpos, uint16_t ypos) {
    RoomWallLayoutID belowRoom = DungeonGenerator::getRoomLayoutFromSeed(xpos, ypos + 1);
    return ((belowRoom & RoomWallLayoutID::OneUp) != RoomWallLayoutID::Zero);

Might be better for “hasWallDown/etc” to return whether or not the room at the specified index has a wall down, and offset only using the calling function

I uploaded my version to GitHub, I don’t know where the bug is coming from. (The tiles generated from getLayoutFromNeighbours are not correct - this can be seen easily from the 1pixel wide walls, all walls should be 2 pixels wide). It has to be from the getLayoutFromNeighbours function but I can’t find why


In case this can help with debugging, here’s my code in GameMaker (my bug isn’t in GameMaker, but on the Arduboy)

///@arg roomLayout
///@arg wallType

var _roomLayout = argument0;
var _wallType = argument1;

// Left
if (_wallType = e_dungeonWall.left) {
	switch (_roomLayout) {
	    case sprRoom1WallsLeft:
	    case sprRoom2WallsLeftDown:
	    case sprRoom2WallsLeftRight:
	    case sprRoom2WallsLeftUp:
	    case sprRoom3WallsLeftRightDown:
	    case sprRoom3WallsLeftRightUp:
	    case sprRoom3WallsLeftUpDown:
	    case sprRoom4Walls:
	        return true;
	        return false;

// Right
if (_wallType == e_dungeonWall.right) {
	switch (_roomLayout) {
	    case sprRoom1WallsRight:
	    case sprRoom2WallsLeftRight:
	    case sprRoom2WallsRightDown:
	    case sprRoom2WallsRightUp:
	    case sprRoom3WallsLeftRightDown:
	    case sprRoom3WallsLeftRightUp:
	    case sprRoom3WallsRightUpDown:
		case sprRoom4Walls:
	        return true;
	        return false;

// Up
if (_wallType == e_dungeonWall.up) {
	switch (_roomLayout) {
	    case sprRoom1WallsUp:
	    case sprRoom2WallsLeftUp:
	    case sprRoom2WallsRightUp:
	    case sprRoom2WallsUpDown:
	    case sprRoom3WallsLeftRightUp:
	    case sprRoom3WallsLeftUpDown:
	    case sprRoom3WallsRightUpDown:
		case sprRoom4Walls:
	        return true;
	        return false;

// down
if (_wallType == e_dungeonWall.down) {
	switch (_roomLayout) {
	    case sprRoom1WallsDown:
	    case sprRoom2WallsLeftDown:
	    case sprRoom2WallsRightDown:
	    case sprRoom2WallsUpDown:
	    case sprRoom3WallsLeftRightDown:
	    case sprRoom3WallsLeftUpDown:
	    case sprRoom3WallsRightUpDown:
	    case sprRoom4Walls:
	        return true;
	        return false;

show_debug_message("Problem in roomLayoutContainsThisWallType() script.\nWall type == " + string(_wallType) + "\n Room Layout ==" + string(_roomLayout));
///@arg leftWall
///@arg rightWall
///@arg upWall
///@arg downWall

var _wallLeft, _wallRight, _wallUp, _wallDown;

_wallLeft = argument0;
_wallRight = argument1;
_wallUp = argument2;
_wallDown = argument3;

var _wallCount = _wallLeft + _wallRight + _wallUp + _wallDown;
var _wallLeftAndRight = (_wallLeft && _wallRight);
var _wallUpAndDown = (_wallUp && _wallDown);

switch (_wallCount) {
    case 4:
        return sprRoom4Walls;
    case 3:
        if (!_wallLeft) {
			return sprRoom3WallsRightUpDown;
		} else if (!_wallRight) {
			return sprRoom3WallsLeftUpDown;
		} else if (!_wallUp) {
			return sprRoom3WallsLeftRightDown;
		} else {
			return sprRoom3WallsLeftRightUp;
    case 2:
        if (_wallLeftAndRight) {
			return sprRoom2WallsLeftRight;
		} else if (_wallUpAndDown) {
			return sprRoom2WallsUpDown;
		} else if (_wallLeft) {
			if (_wallUp) {
				return sprRoom2WallsLeftUp;
			} else {
				return sprRoom2WallsLeftDown;
		} else if (_wallRight) {
			if (_wallUp) {
				return sprRoom2WallsRightUp;
			} else {
				return sprRoom2WallsRightDown;
    case 1:
        if (_wallLeft) {
			return sprRoom1WallsLeft;
		} else if (_wallRight) {
			return sprRoom1WallsRight;
		} else if (_wallUp) {
			return sprRoom1WallsUp;
		} else {
			return sprRoom1WallsDown;
        return sprRoom0Walls;