Help me with C++ for my game


Okay so Perlin noise with floats seem to be hard to do/impractical for the Arduboy. Random number generators could work, one type I’m fairly interested in are linear feedback shift register but I’d have to think of a way for it to require a seed (for it to work like a hash function or perlin noise; two inputs == one seemingly random output)

If worst comes to worst I’ll just use a shuffle bag but but a shuffle bag doesn’t feel right to me, but who knows?

(Pharap) #144

Of course…

I didn’t realise that before.
I wonder if that’s strictly true or just relatively true.
Usually there’s some obscure rule about which unicode characters are accepted that break these sorts of assumptions.

Hopefully none of those are GPL’ed then, or things get messy.

I have almost the same problem with Netbeans.
The only reason I keep it installed is because one day I might need to write Java for some strange reason.

Pure perlin noise would be. Deviating from it slightly might help, but then it depends what kind of terrain you end up with.

These are always awkward to understand because they’re typically explained with polynomials.

Also I’m not sure these are very fast, they’re typically used as part of a cryptographically secure PRNG.

Also remember that the Arduboy has no barrel shifter so shifts aren’t as cheap as they usually are on other platforms.
There’s a ‘shift left’ instruction and a ‘shift right’ isntruction, both of which only perform a single shift.
(The ‘shift left’ instruction is actually implemented as x = x + x;.)

Any pseudorandom number generator that relies on a state can be expressed as a function accepting a state and returning a new state and a resulting value.
(As I learned from Haskell.)

For example, an LCG can be expressed as:

class LCG
	// Settings chosen at random
	static constexpr uint32_t modulus = 0x0100;
	static constexpr uint32_t multiplier = 5;
	static constexpr uint32_t increment = 3;
	static uint32_t transform(uint32_t state)
		return (((state * multiplier) + increment) % modulus);
	uint32_t state;
	LCG(uint32_t seed) : state(seed) {}
	uint32_t next()
		this->state = transform(this->state);
		return this->state;

transform can translate any LCG state to its next value, so theoretically it can be treated as a hash function (although it wasn’t intended to be used that way, so it may not have desirable properties).

Aside from sounding like a lot of extra processing, that sounds even more stateful.
The point of a hash function is to be stateless (with the exception of maybe a pre-initialised table of values, since that’s a constant state that doesn’t change).

Unless you’re planning on just using that to initialise a table to be used for a hash function?

To be honest though, you don’t really need a uniform distribution, you just need something that’s fast, useful, and doesn’t have too many ugly patterns (in some cases patterns are good, because landscapes do have patterns).

Also I think the kind of shuffle they use there is a Fisher-Yates shuffle.
I didn’t read the whole thing, but I saw the ‘starting from the end’ part, which usually means Fisher-Yates.

(Simon) #145

Good question … I might look at that. Its possibly like saying HTML can be validated or parsed as XML.

It takes four minutes to start the application within Eclipse. Not to start Eclipse or Netbeans itself. In the old days, my AS/400 programs would take 15 - 30 minutes to compile (they were batched and queued with other processes - the compilation time was a portion of this), so we used to go get coffee (I drank a lot back then). As there was minimal syntax checking, I would challenge myself to write programs with less and less errors.

(Pharap) #146

XHTML could be parsed as XML,
but HTML has been based on SGML (a superset of XML) for quite some time,
which means it also hasn’t been valid XML for that amount of time.

As of HTML5, it’s now a superset of SGML because they broke the rules of SGML.
So now it’s XHTML ⊂ XML ⊂ SGML ⊂ HTML5.

What a mess!

Obligatory xkcd:

I do the same with C++.

This is why I like Notepad++ - just syntax highlighting and really basic autocomplete.
(I.e. it fills in words you’ve already typed).

Using that has forced me to get better at not making mistakes,
which means it’s become easier for me to just write something without assistance from an editor and for that something to compile without error.


Apparently a sine function is incredibly useful for procedural terrain generation. So, I’ve been working on a lightweight sine function that works for the Arduboy using only integers. It’s a work in progress and it doesn’t compile

Error message:

In file included from sketch\WorldGen.cpp:3:0:

WorldGen.h:13:9: error: too many initializers for 'const uint8_t [22] {aka const unsigned char [22]}'



WorldGen.cpp:5:15: error: 'WorldGen' has not been declared

 static int8_t WorldGen::sin(int16_t n) {


sketch\WorldGen.cpp: In function 'int8_t sin(int16_t)':

WorldGen.cpp:7:13: error: expected unqualified-id before '=' token

     int16_t = i = (n % (sineTableSize * 2));


WorldGen.cpp:9:9: error: 'sineTableSize' was not declared in this scope

     if (sineTableSize <= i) {


WorldGen.cpp:9:26: error: 'i' was not declared in this scope

     if (sineTableSize <= i) {


WorldGen.cpp:12:5: error: 'i' was not declared in this scope

     i = (i % sineTableSize);


WorldGen.cpp:12:14: error: 'sineTableSize' was not declared in this scope

     i = (i % sineTableSize);


WorldGen.cpp:19:14: error: 'sineTable' was not declared in this scope

     result = sineTable[i];


sketch\WorldGen.cpp: At global scope:

sketch\WorldGen.cpp:5:15: warning: 'int8_t sin(int16_t)' defined but not used [-Wunused-function]

 static int8_t WorldGen::sin(int16_t n) {


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

                 from C:\Users\Alex\Documents\Arduino\tutorial projects\game_prototype\game_prototype.ino:7:

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;


exit status 1
too many initializers for 'const uint8_t [22] {aka const unsigned char [22]}'


#pragma once

#include <Arduino.h>

class WorldGenerator {
        static int8_t sin(int16_t n);
        static const uint8_t sineTableSize = 22;
        static constexpr uint8_t sineTable[22] = {
            0, 7, 14, 21, 28, 34, 41, 47, 53, 59, 64, 69, 74, 79, 83, 87, 90, 93, 95, 97, 98, 99, 100, 


#include <Arduino.h>
#include "WorldGen.h"

static int8_t WorldGen::sin(int16_t n) {
    bool positive = (0 <= n);
    int16_t = i = (n % (sineTableSize * 2));
    uint8_t secondQuadrant = false;
    if (sineTableSize <= i) {
        secondQuadrant = true;
    i = (i % sineTableSize);

    int8_t result = 0;
    if (secondQuadrant) {
        i = (sineTableSize - 1 - i);
    result = sineTable[i];
    if (!positive) {
        result *= -1;

    return result;

(Pharap) #148

If you’re fine with using brads instead of radians then I already have a sine and cosine implementation for fixed points:

It uses 128 bytes of progmem for the lookup table (64 * 2).

(Matt) #149

too many initializers means you said this array is 22 items long: sineTable[22], but you put more than 22 things in it.

(Felipe Manga) #150

You might want to have a look at “Hello, Commander” it has a procedurally generated terrain based on an integer sine table.
Pseudo-Random numbers were also discussed, with results that might be of use.


I found a way to give every tile a unique ID that can be used for noise generation

Using two 16bits integers. I put the X coordonate the left side and the y coordonates on the right side. That gives me a number I can use as a seed with my own random number function or any other pseudo random number function

All I need to do is set the seed to that number, and then use the function for whatever number I need.

I don’t know how fast or how slow AND (&) is on the Arduboy but I guess I’ll find out very soon. I don’t know what happens if I use negative numbers but I can always use even and non even indexes to act as positive and negative values, if I need to world to generate in all directions

(Pharap) #152

Make sure to experiment with the properties of the functions.
For this, you ideally want a function that’s bijective.

(Which also means that if the function were used as the state changing transform in a PRNG then the PRNG would have a full period.)

Extremely cheap, 1 CPU cycle per byte.

For & they behave the same as unsigned numbers.
Where you have to be careful is with >> and signed numbers.
The C++ language rules state that >> is technically implementation defined for signed integers, but 90% of the time it copies the sign bit when it shifts.

This is why I always shift before masking. E.g.

int value = 0xF355;
int a = (value & 0xFF00) >> 8;
int b = (value >> 8) & 0xFF;

In the case of a, the result changes depending on how >> behaves.
If it copies the sign, you end up with 0xFFF3, if it doesn’t copy the sign you end up with 0x00F3.
In the case of b, it behaves as intended regardless of how >> behaves.
Because the shift happens first and the masking second, the result is always 0x00F3.


I’m learning new words today.

I understand bijective thanks to the article you linked. That’s gonna be a new keyword useful for googling thank you. I suppose we could describe my method of combining two numbers as a thing to make non bijective random functions turn bijective?

Thank you for educating me (side question, does it sound dis-genuine when I say this? English isn’t my first language so I don’t know if it sounds sarcastic)

TIL exactly what ‘masking’ actually means. Take two values or two sets of values, and only the values flagged in set A get read from set B, to create C result.

Shift first, ask questions later. Got it

I think I’m on the right path for either procedural generation or very compact world (if I decide to go that route - it’s still possible that I don’t, or only use procedural generation for dungeons only)

If I decide to have a handmade world that is very compact, I can use my procedural generation for trees and a mix of floor tiles, and use a different set that only stores houses and special tiles/rarer stuff. This would result in big areas of just blank space, so the “tileIndex, copiesOfSaidTilesInARow” compression method would work really well there.

Alternatively if I get really smart about it, I might be able to make good village generation. I can make house doors teleport to a “house” that’s procedural generated based on the same seed that is just concatenated x,y of the door of said house. I can then put the player back at those same coordinates, and because it’s procedural, it will load the exact part of the world.

Quick question, is the source for the Arduboy2 random function available? I tried looking through here but I didn’t find anything except the seed initialization code

(Pharap) #154

Don’t worry about remembering the word for it, it took me several minutes to remember it.
(Dammit Jim, I’m a programmer, not a mathematician!)

The important thing is the idea of a 1-to-1 mapping of possible values.

Not exactly. Combining the two numbers is a different matter to the jectiveness (that’s not a real word) of the function.

A hash function is bijective if every unique input maps to a unique output.
If two inputs result in the same output then the function is not bijective.

(If a bijective function is used as the transform/step function of a PRNG then that PRNG would have a full period. Don’t worry if this doesn’t make sense, this is creeping into the realms of abstract maths.)

I understood how you meant it.
But yes, in most circumstances it would seem sarcastic.
Especially on the internet, where it’s hard to convey the ‘tone’/‘intent’.
(It’s kind of hard to explain why it sounds that way though.)

Instead of trying to explain why I’ll say that something like “thank you for explaining this” or “thank you, I didn’t know that” or “thanks for the info” sound better.

(Also, ungenuine or disingenuous.)

Ah, tu est un Canadien français?

Ah, sorry, I assumed you already knew about bitwise operations and bitmasks.

If not, the wikipedia article is quite good. (OR = |, AND = &, XOR = ^ in C++.)

Even if you don’t use procedural generation, you can use your new bitmasking powers to fit two tiles per byte if you only have 16 tiles.

Procedural generation can be difficult to do well.

random isn’t from Arduboy2, it’s from avr-libc, which is the library that the Arduino library is built on top of.
The documentation is here.

The actual implementation (for avr-libc 2.0.0) is:

 * Copyright (c) 1990, 1993
 *	The Regents of the University of California.  All rights reserved.
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 * Posix rand_r function added May 1999 by Wes Peters <>.
 * $Id: random.c 1944 2009-04-01 23:12:20Z arcanum $

 * From:
static char sccsid[] = "@(#)rand.c	8.1 (Berkeley) 6/14/93";

#include <stdlib.h>
#include "sectionname.h"

static long
do_random(unsigned long *ctx)
	 * Compute x = (7^5 * x) mod (2^31 - 1)
	 * wihout overflowing 31 bits:
	 *      (2^31 - 1) = 127773 * (7^5) + 2836
	 * From "Random number generators: good ones are hard to find",
	 * Park and Miller, Communications of the ACM, vol. 31, no. 10,
	 * October 1988, p. 1195.
	long hi, lo, x;

	x = *ctx;
	/* Can't be initialized with 0, so use another value. */
	if (x == 0)
		x = 123459876L;
	hi = x / 127773L;
	lo = x % 127773L;
	x = 16807L * lo - 2836L * hi;
	if (x < 0)
		x += 0x7fffffffL;
	return ((*ctx = x) % ((unsigned long)RANDOM_MAX + 1));

random_r(unsigned long *ctx)
	return do_random(ctx);

static unsigned long next = 1;

	return do_random(&next);

srandom(unsigned long seed)
	next = seed;

But, I would advise against using the default implementation because it might change.
You’re better off writing a different function, because you know that won’t change.
Also, using a different function will make porting to other systems easier (if you want to port it at any point).

By the way, do you know exactly what kind of game you want to make?
Do you want to do a Zelda-like game, or more of a roguelike?
Would there be a story?

If you want to do something Zelda-like, you’re probably better off crafting the world by hand.
If you want to do a hash-&-slash/roguelike then I think you should make the overworld by hand and just procedurally generate the dungeons.

But again, it depends what kind of game you want to make.
(E.g. Should there be a story? Does it make sense to have the same overworld on every game? etc.)


Oui! Enchanté de te connaître

I had heard and read about it but not enough to understand them, and I had never put them into practice. I spent a lot of time yesterday learning about them. I understand how AND(&) and OR(|) work, I’m still confused abou XOR and NXOR and the oter stuff with OR in it that isn’t just a simple OR, but I learned a lot yesterday

Yep now I would know how to. I would still have to learn how to make something that turns my raw levels into levels compressed like that however. I know you suggested Lua and that I have some experience with it, but still doing the research and taking the time to figure it out would… well it’s more efforts again. I’d prefer to do it in C++ to avoid having to learn a whole other thing.

(I know it sounds like a contradiction because I’m spending all this time learning about pseudo random number generators and procedural generation, but I’ve been wanting to learn these two things for a while)

My thoughts exactly

There’s 99% chance of having zero text based story. I’m thinking having NPCs give quests using only images would be more interesting. Maybe some 8x8 emojies for letting the player know that they’re grateful or sad… but I wouldn’t go further than that.

The main aspect of the game will be the combat and avoiding traps in the dungeons. But, villages are cool, and NPCs are cool too. So I will probably put them in.

At worst I’ll make a smaller game first with only the dungeons and make a second bigger game later.

I agree, and a bigger world isn’t necessarily more fun.

I might do this. Dungeons however are gonna be a big part of the gameplay, and I think I can store each 16x8 section in less than 20 bytes. I’d use a wall tileset with autotiling to have nice looking dungeons but I’d have only “floor” or “wall” (0 or 1), so I could use 16 bytes as if they are 16 arrays of lengh of 8. I’d use 4 more bytes to store what entities there are in that sections and their positions. (if I use tileable dungeon sections I could make it even more compact)

So if need be, I think I have a good solution for handcrafted dungeons.

Speaking of which, if I want to pass an array which is a section of a dungeon, how would I go about it? Pointers/references?

The dungeons will be Prince-of-Persia-like or Indiana-Jones-like. I might even implement a simple jumping mechanic to jump over holes or spikes, I know how to do that.

Combat from player to enemy, it’s gonna be Zelda like and maybe Dark Souls like (the key to Dark Souls gameplay is telegraphing the attacks, and on such a tiny screen I don’t know if I’ll pull it off). I hate turned based combat and I love real-time combat so there’s gonna be a big focus on that.

I could remove everything from the game and make it only a gladiator Arena and it would have to still be fun, that’s how much focus I’ll put on the combat. (I’m exaggerating a bit, the dungeons and the traps are a big part too because enemies are fun, but throwing traps into the mix is even better.)

I could make the whole thing handcrafted and linear and it’d still be fun, the difference is there’d be no separation between the overworld and the dungeons, but I think that’d be harder to pull off. (both design-wise and storing-it-in-PROGMEM-wise)

(Pharap) #156

@Vampirics et @dpelletier05 aussi.

Mais, je suis Anglais.

&, |, ^ and ~ (‘and’, ‘or’, ‘xor’ and ‘not’) are the only ones you have to worry about when programming.

The others are useful if you want to do circuitry/electronics,
or if you’re trying to figure out which expressions are equivalent and/or how to reduce the number of bitwise/logic operations used in an expression (e.g. (a & ~b) | (~a & b) == a ^ b).

Before it was used in computers, this kind of logic was made famous by an English mathematician called George Boole, and it was called Boolean logic/Boolean algebra.

(Fun fact: George Boole died because of his stubbornness and his wife’s belief in homeopathy.)

It depends how you are designing/creating your levels.

Either would work.
The available operators are pretty much the same (Lua 5.3 uses &, |, ^ and I think ~),
and both have ‘arrays’ (but Lua’s ‘arrays’ start at ‘1’ instead of ‘0’ and are actually more than just arrays).

The biggest difference would be the file API.

This makes me think of the villagers in Minecraft.
They don’t talk or communicate with the player, but you can trade with them.

I’m sure there are other games that do that, but I can’t think of any at the moment.

That’s probably a good idea. Focus on the mechanics and gameplay and then figure out the dungeon generation afterwards.

Also, if there’s no plot then you don’t have to have a massive overworld, you could just have a small ‘hub world’.
You could make the village the ‘hub world’, with a few shops.
You could collect treasure in the dungeons, sell it to the shops,
and then maybe build more shops/houses or upgrade the existing shops, so then you can buy better equipment, visit larger dungeons etc.

Or you could just make the whole thing one large dungeon and have the villages inside the dungeons (a bit like Barony).

The dangerous way:

void someFunction(const uint8_t * array, uint8_t size)
	// Do something

The better way:

template< uint8_t size >
void someFunction(const uint8_t (&array)[size])
	// Do something

But if ‘the better way’ eats too much memory, you can have the best of both worlds:

void someFunction(const uint8_t * array, uint8_t size)
	// Do something

template< uint8_t size >
void someFunction(const uint8_t (&array)[size])
	someFunction(&array[0], size);

Realtime combat is usually more difficult because you have to figure out the physics involved.


I think turned based is more difficult, but maybe that’s just because I have no experience with it

I suppose it’s time I learned about templates. But I assume templates aren’t necessary, and all I need to worry about is doing &array?

By the way, when should I use const vs constexpr ? const is an actual variable, and constexpr is basically a better #define ?

(Pharap) #158

The only hard parts are the timing, the animation (if there are animations) and figuring out some good damage formulas/equations.

Not many people use templates, and even fewer know how templates work, so there’s no rush to learn about them.

I think they are an advanced topic because they require a bit of abstract thinking to understand,
but I also don’t think they’re as difficult as some people say they are.

They’re a lot easier to use than they are to write, but they’re still not that hard to understand at a basic level.
What is hard is to do more advanced things with them.

I’m very experienced with templates,
and I’d dare say I possibly know more about templates than almost anyone else here,
so if you do want to learn about templates then let me know.

If you’re only planning to pass one size of array then they aren’t.
If you’re planning to pass more than one size of array then they are the best option in this case because you only have to write one function (as opposed to writing one function for every array size).

const means “this variable cannot be modified”.
constexpr means “if possible, this value will be evaluated at compile time”.
constexpr implies const, so any constexpr variable is automatically const as well.

There’s quite a good answer about the differences here.

You can also mark functions as constexpr which means “if possible, this function will be evaluated at compile time”,
but there are rules about what you’re allowed to do in a constexpr function.

In C++11 (which is what the Arduino IDE is set to use), the rules for what you’re allowed to do in a constexpr function are a bit complicated, but the general idea is that the contents must be a single return statement and there must be no ‘side effects’.
(In C++14 the rules were relaxed quite a bit, so more complex stuff is allowed.)


(Practicing terminology in 3… 2… 1…)

So it can either be a value like 4, 57 or a string or anything that’s “already there” and if not, it needs to be a pure function ?

(I like that you’re using the proper terminology and both testing me and teaching me)

This is unfortunately out of my competence-league so I can’t see how experienced you are, but I will take your word for it

If I need more than 3 functions for entities I’ll probably spend some time learning about templates, but for now everything’s planned to be 8x8 so it should be good to go.

Can I use references if I need the reference to ‘point’ to a different sprite later?
If not, I’d use pointers and I’d never need to delete them or what they point towards (it’d be for a sprite variable of my entities in my entities array). Or I could stick with my switch statement.
Quick edit: or I could have a Entity::getSprite() function which contains the switch statement that returns the correct sprite, as a reference. That should result in pretty clean code

I guess I’ll just go ahead and try with references and see

Edit for my getSprite function idea, apparently it’d go something like this?

I’ve read this link a few times over but I’m still confused,here’s how I think it should work:

uint8_t Entity::getSprite(EntityType type) {
    switch (type) {
        case EntityType::Player:
            return &spr_player;

(Pharap) #160

I specifically avoided using the term ‘pure function’ because I didn’t know if you knew what it meant,
but if you do know what a pure function is then yes,
a constexpr function in C++11 must be a ‘pure function’ - no side effects, no state.

It’s allowed to use other constant expressions, including other constexpr functions and predeclared constexpr variables (but it’s not allowed to declare its own local constexpr variables for some reason).

(It’s also allowed to contain using declarations, using directives and type aliases.)

The first link links to some more basic template usage -
declaring some container types (arrays, queues, stacks) that are templated,
along with a more advanced example -
an implementation of type_traits from the C++ standard library.

The second link is the really crazy stuff - proof that the template system is effectively a functional language in its own right, by implementing various constructs inspired by Haskell’s standard library.

In this case you don’t really need to understand templates as a whole to understand this particular usage:

template< uint8_t size >
void someFunction(const uint8_t (&array)[size])
	someFunction(&array[0], size);

Essentially all you need to know to use this is that this template allows the function to match every size of array and the array’s size gets captured as a constant expression with the name size and a type of uint8_t.
(The correct name for the constant expression is a ‘template parameter’.)

No, references cannot be ‘repointed’.
A reference can only be assigned once.
To be able to ‘repoint’ you have to use a pointer.

You never have to use delete unless you’ve used new to dynamically allocate memory.

(And dynamic allocation should be avoided on the Arduboy.)

It depends on whether you’re using animated sprites and whether your entity sprites are all going to be the same size or not.

The function says it returns a uint8_t, but &spr_player has the type * decltype(spr_player) (decltype means ‘the type of’), which I’m guessing is const uint8_t * const * (“a pointer to a const pointer to const uint8_t”).

Returning a reference to an array probably won’t be of much benefit.
It depends on what you’re planning to do with it.

Remember that the code’s structure always depends on what the end goal is.
You don’t fit a game to the code, you fit the code to the game.


So… I decided to just compress my level like you suggested. 4bits per tile instead of a byte.

I don’t know how to go about writing the script or application that actually takes care of that. I could do it in GameMaker but it’s sandboxed so it’d be an annoyance to use.

How can I learn how to do this with C++ or Lua?

(Pharap) #162

How are you editing your levels?
Do you already have an editor with an established format?