Firestarter (WIP and a couple questions...)

Then unfortunately I have to reveal that you’ve never really understood how functions work.

I’ll attempt an explanation, but I’m very tired, so I might have to come back to provide a better one later if this one doesn’t make much sense.

When you write:

TileType building = generateRandomBuildingTile();

The function generateRandomBuildingTile() does whatever it does and then produces one single value, which is copied into the variable building. After that point, building will only ever have that one value, unless it is explicitly modified with another assignment later in the code.

Thus fill(building); passes that one value to the fill function and the fill function uses that one value to fill all the tiles.

When you do fill(generateRandomBuildingTile());, the same thing happens, but without the building variable as a middle-man. The generateRandomBuildingTile() is called once and produces precisely one value and that one value is passed to the fill function which uses that one value, bound to the parameter tileType*, to fill the array.

Note that parameters behave very similarly to variables. They also hold only a single value and that value does not change until you explicitly reassign it. (Though generally code is easier to read when you avoid modifying parameters.)

In a way you could consider parameters to be variables that are specially designated to receive function inputs because conceptually that’s how they behave to the programmer, though they aren’t completely the same.

Anyway, the crucial thing is that a variable stores a copy of a value. It does not magically call the function again every time you access it. There are languages where that does happen, but they’re uncommon because that kind of behaviour is expensive and often unnecessary.

Note also that because parameters are copies of the values passed in as arguments, modifying a parameter does not modify the original:

void modify(int parameter)
	parameter = 5;

void test()
	int variable = 10;
	// Prints 10
	std::cout << variable << '\n';

	// Still prints 10
	std::cout << variable << '\n';

However, there is a way to change this behaviour in C++ using things called references. But it’s generally a bad idea to use non-const reference arguments, there’s only a few circumstances where it would make sense to do so.

If you’re interested in the various different ways function parameters can behave in different languages you could have a read of this Wikipedia article, but it’s advanced academic stuff that you’re probably not going to need to know.

I only know about different ‘evaluation strategies’ because I have an interest in compiler design and have used a few languages that behave differently (in particular, Haskell, which uses ‘call by need’).

The overwhelming majority of languages use ‘call by value’ and ‘call by reference’. C and C++ have ‘call by const reference’, which is less common but very useful, and a few languages inspired by C++ have adopted it. Others like ‘call by copy-restore’ I’d never even heard of.

This reminds me of a joke about Niklaus Wirth, as recounted by Professor Brailsford of Nottingham University (and of Computerphile fame).

Supposedly Wirth once asked “Why is it that all the European students can pronounce my name correctly, but all the Americans call me “nickle’s worth”?”, to which someone replied " It’s because the Europeans call you by name, but the Americans call you by value."

(His name is supposed to be pronounced something along the lines of ‘ni-claus veert’, not “nickle’s worth” or “Nicholas Worth”.)


I’ll explain in more depth next time, but the easiest option is probably to stick a bunch of values in an array and use the rand function to pick a value from the array. Then if you stick multiple copies of a value in the array, that one will occur more often.

If you had an 8-element array and 4 copies of A, 3 copies of B and 1 copy of C then theoretically there would be a 4/8 (50%) chance of getting an A, 3/8 (37.5%) of getting a B and 1/8 (12.5%) of getting a C.

(Whether those theoretical odds are accurate depends on the implementation of rand and the size of the array when using % because of a thing called ‘modulo bias’. But you don’t really need to care about any of that because a tiny amount of bias probably isn’t going to make too much difference.)

Yeah, i knew that (and you were right i did kick myself once you pointed it out lol)

But i didnt know this (obviously)… i do remember learning about explicitly declaring/defining parameters during function declaration (or declaring then defining later when passing a value elsewhere), but for some reason i expected a function would work different (just because it returns a value), however i didnt realize that value is an explicit declaration/definition when used in this context. But that makes much more sense now, thanks!

I guess the simplest option usually does make the most sense lol. I was just thinking so i didnt need to duplicate the tile, but i suppose it might not really matter much memory-wise so ill just do that

I think you’re getting mixed up with (pre)declaring functions, which is something you have to do when a function is needed before it’s defined.

For example, in the map generation code generateHorizontalStep and generateVerticalStep are declared before they are defined because they’re referenced by other functions.

The definitions are:

void generateHorizontalStep(std::uint8_t x, std::uint8_t y, std::uint8_t width, std::uint8_t height, std::uint8_t depth);
void generateVerticalStep(std::uint8_t x, std::uint8_t y, std::uint8_t width, std::uint8_t height, std::uint8_t depth);

And the declarations are:

void generateHorizontalStep(std::uint8_t x, std::uint8_t y, std::uint8_t width, std::uint8_t height, std::uint8_t depth)
	if(depth == 0)

	if(width < 2)

	if(height < 3)

	const std::uint8_t division = 1 + (std::rand() % (height - 2));

	fillHorizontalLine(x, y + division, width, road);

	const std::uint8_t upperY = y;
	const std::uint8_t upperHeight = division;

	const std::uint8_t lowerY = (y + division + 1);
	const std::uint8_t lowerHeight = (height - division - 1);

	// Note: Using generateVerticalStep before it is defined
	generateVerticalStep(x, upperY, width, upperHeight, depth - 1);
	generateVerticalStep(x, lowerY, width, lowerHeight, depth - 1);

void generateVerticalStep(std::uint8_t x, std::uint8_t y, std::uint8_t width, std::uint8_t height, std::uint8_t depth)
	if(depth == 0)

	if(height < 2)

	if(width < 3)

	const std::uint8_t division = 1 + (std::rand() % (width - 2));

	fillVerticalLine(x + division, y, height, road);

	const std::uint8_t leftX = x;
	const std::uint8_t leftWidth = division;

	const std::uint8_t rightX = (x + division + 1);
	const std::uint8_t rightWidth = (width - division - 1);

	generateHorizontalStep(leftX, y, leftWidth, height, depth - 1);
	generateHorizontalStep(rightX, y, rightWidth, height, depth - 1);

I don’t think parameters technically have distinct declarations/definitions because they’re always part of a function.

In some languages it would, and even in C++ there’s a way to actually pass a function as an argument to a function, though the function would still have to manually call the other function.

One such technique is to use function pointers (pointers that point to functions)…

// The parameter is a pointer to a function
void fill(TileType (*generateTileType)())
	// Because the parameter is a pointer, it can be null
	if(generateTileType == nullptr)

	for(size_t y = 0; y < 32; ++y)
		for(size_t x = 0; x < 32; ++x)
			// Call the function to which the other function points
			tileMap[y][x] = generateTileType();

Then you could do:


But in general you don’t want to do that because there are better ways of achieving the same thing.

I think you’re getting values, declarations and definitions muddled up.

The simplest way to explain a value is to say that it’s a pattern of bits. The important distinction between a value and a variable (or ‘object’, but that’s an entirely different can of worms) is that values aren’t tied to a particular storage location, they’re copied around. For example, in the code int a = 5;, 5 is a value that is assigned to the variable a. You could have multiple variables with a value of 5, in which case the values held by the variables (5) would all be the same value, but the variables would not be the same variable (variables are always distinct entities). That’s why it’s said that a function returns a value, which is then either assigned to a variable or used as part of an expression E.g. in f() + 5, 5 and the value returned by the call f() are both values, not variables.

(If you’re wondering “where are they stored?” the ‘legal’ answer according to C++ is that they aren’t ‘stored’ anywhere or at least the language doesn’t care where they’re stored. The practical/realistic answer is that they’re probably stored in CPU registers because that’s what most compilers would(indirectly, via machine code) tell the CPU to do with them - theoretically it doesn’t have to happen that way, but that’s how most computer setups work these days.)

A declaration is a certain block of code that declares that an entity (typically a function, struct or class) exists, but without defining the specifics. A declaration is enough to indirectly refer to the entity - i.e. enough to call a function, or to use a pointer or reference to a struct or class (but not to create an object/instance of said struct/class).

// Declaration
void functionA(int argumentA, char argumentB);

// Declaration that doesn't name the parameters
void functionB(int, char);

// Struct declaration
struct StructA;

// Henceforth 'StructA *' or 'StructA &' may be used, but not 'StructA'.

A definition fills in the remaining details. For a function that means the body of the function is written out in full. For a class or struct that means all the members of the class are listed. However, a class definition only needs to declare its member functions, it doesn’t have to define them until later.

// Definition
void functionA(int argumentA, char argumentB)
	// Does whatever

// Definition that doesn't name the parameters
void functionB(int, char)
	// A function can have parameters that it doesn't use,
	// though often that suggests that the function is unfinished
	// or has a bug somewhere.

	// The only time it's common to see unused parameters is with virtual functions.

// Struct definition
struct StructA
	// Member variables
	int x;
	int y;
	// Yet this member function is only declared, not defined
	void doSomething();

// Be it in the same header file or a .cpp file somewhere,
// here is an explicit member function definition
void StructA::doSomething()
	// Does whatever

These rules might seem odd, but if you knew how the compiler works and how they’re implemented in terms of machine code it would make sense.

To try to give a simplified explanation:

  • A function needs to be declared before it is called so the compiler knows it exists. But crucially, that declaration must include the number and types of parameters and the type of the return value (if there is one) because those things must be known before a function can be called. Without that information the compiler can’t generate a valid function call because it can’t verify that the right number of arguments and right types of arguments are being passed, and it can’t deal with the return value without knowing if there is one and what type it is.
    • Part of the reason the types are so important is because different types have different sizes, which means they have to be handled differently. Specifically, different code needs to be generated to move them around. Small values can often be passed directly in registers, while large values must be allocated in RAM (typically on the call stack), and each needs to be copied around differently as a result. If the compiler didn’t generate the proper code to do that, the program would fall apart at runtime and start misbehaving in unexpected ways. E.g. if the calling function is expecting 2 Points and it’s been passed 3 ints, it’s more or less guaranteed to start misinterpreting data. At best you’ll get some odd glitches, at worst the whole program might gradually unravel and start misinterpreting data as machine code or jumping into functions half way or other crazy shenanigans.
  • A struct needs to be declared before a reference or pointer to it can be used simply because the compiler needs to know that such a type exists. That’s why the declaration of a class or struct is so much shorter than that of a function. Pointers are generally* fixed size , so the size of a struct is not needed to be able to pass around a pointer to a struct. References are often implemented as pointers, so the same rule applies for them.
    • * There’s at least one exception: pointers to member functions. I won’t get into why.

I’ll try to keep this short because I ended up going into depth about some stuff I wasn’t expecting to above…

(This would be a lot easier to explain if you understood the basics of set theory, but I’ll try to explain without getting too mathsy.)

Basically rand generates a value between 0 and RAND_MAX (0x7FFF/32767 on AVR), and theoretically (if the implementation has been done correctly) each of those values has an equally likely chance of occurring.

If you were to divide that number space up into groups, the odds of a number in any of those particular groups being generated would depend on the size of the group. For example, if you split the full range (0 to 0x7FFF) into two equal ranges (0 to 0x3FFF and 0x4000 to 0x7FFF) then each range would have an equal chance of occuring - 50% for the first range and 50% for the second range. But if you shift the boundaries ever so slightly by moving one value out of one range and into another then you tip the odds in favour of the range that covers more values…

Let’s simplify life for a moment by ignoring half the values and pretending rand generates a value in the 0 to 255 range. If you partitioned that into two equal ranges: 0 to 127 and 128 to 255 (inclusive), then both ranges have a 128/256 (i.e. 1/2 or 50%) chance of ‘occuring’ (i.e. chance of a number generated falling into that range). The reason it’s 128/256 is because there are 256 possibilities (0 to 255 covers 256 numbers) and each range covers 128 of those numbers (0 to 127 is 128 numbers, 128 to 255 is 128 numbers).

So now if you were to remove a value from one of those ranges and give it to the other range, e.g. take 127 out of the first range (reducing it to 0 to 126, 127 numbers total) and give it to the second range (widening the range to 127 to 255, 129 numbers total), then suddenly you’ve tipped the scales - the first range now has a 127/256 chance of ‘occurring’ (about 49.8%) and the second range has a 129/256 (about 50.3%) chance of ‘occuring’.

So, one possibility for affecting the odds of how you select tiles is to very carefully choose particular ranges of values in such a way that you know what the odds of them occuring are.

However, to make life easier, you can reduce the range of values produced by rand so that it’s easier to partition by using the modulo operator. But the catch is that due to the aforementioned ‘modulo bias’, if you care about that tiny amount of probably imperceivable bias then you should only reduce the range to a power of two (e.g. 1024, 512, 256, 128, 64, 32, 16, 8). I won’t go into the maths unless you’re particularly interested, but the general idea is that (for values that aren’t a power-of-two) it slightly skews the results so that some values are more likely than others. If you don’t care, use % with wild abandon.

When you’ve settled on your ranges, you can either use ifs together with < to test if a value is in a particular range, or you can use the array approach I mentioned earlier. Sometimes the array approach is cheaper or easier to work with, but ‘your mileage may vary’. Personally I find the if approach more cumbersome because it’s easier to forget that when you take a value from one range you’re giving it to another, and it forces the ranges to be consecutive, whereas with the array approach it’s easier to think that each element of the array represents a certain percentage (e.g. 12.5% for an 8-element array) and that by putting the same value in N slots you are multiplying that value’s share of the range (e.g. by assigning ‘road’ to 4 elements of an 8-element array you’re giving it a 4*12.5% share of the full range).

No, I do know the difference between values, declarations, and definitions, as well as function prototyping (also knew about passing by value/reference but still getting to understand that a more intuitively, definitely didn’t know a good bit of what you said) I was just using it as a (loose) means of comparison for how it treated the function as an argument, rather than calling it every time it treated the variable it returned more like the default argument (which can be either defined and undeclared or both defined and declared). But seeing it done using pointers like that actually makes much more sense now in the context of passing by value/reference (as far as whats going on under the hood) and now i also see why thats not quite the case, thanks!

Also, i seem to be having a bit of an odd issue when I try to add a secondary blank tile to my tileTypes… a section of the map appears to work ok, then the rest (most) of the map shows junk… the minimap appears to display ok, but there alsp doesnt seem to be any discernable difference in output between using one vs two blank tiles, so im not sure if maybe it is displaying incorrectly too and I just can’t tell. I actually started trying to add it in last night after I saw your comment (before I’d even replied) then figured I was probably just getting too tired, but after walking myself through each change again today, commenting it out line by line, and checking through all the code to make sure I didn’t miss something I still couldn’t figure it out.

The second to last commit has these changes, but the most recent commit has them commented out and the lines they replaced uncommented to have it in a working version (because im not sure if it makes sense to go that route, might make more sense to just fix the road subdivision, maybe both)…

But I’ve definitely gotten stuck trying to figure this out, sorry :sweat_smile: I thought I was able to follow along with what was going on but apparently not well enough to know what to change to what end (and experimenting with a couple things I thought might be on track still didn’t really help give me any better of an idea)

Loose language gets you shot in programmer land. :P

Precision and pedantry are important purely for the sake of making sure people are on the same page about what’s going on, otherwise we might end up talking about completely different things and then wondering what’s gone wrong.

The function is called and produces a value. That value is the argument, the function is not the argument.

“Treating the function as an argument” would mean literally passing the entire function (or a pointer to that function) as an argument to the other function. A seemingly tiny but very important difference.

Default arguments are something else entirely.

That’s when you do something like:

// 5 is the default argument for parameter x
void f(int x = 5)
  std::cout << x << '\n';

// Henceforth `f()` is equivalent to `f(5)`

To clarify: you actually can’t pass a function by reference.

You can pass a pointer to a function by value or by reference, but not the function itself.

Passing a function by value would literally mean passing the entire function (as in the actual machine code that the function compiles to) to another function, which is illegal, mostly because it’s useless (at least, useless for any sane purpose).

Non-function types are fine though…

// Pass 'by value'
void fByValue(int copiedValue)
	// Modifies the value of the parameter,
	// which previously held a copy of whatever argument
	// was passed to the function
	copiedValue = 5;

// Pass 'by reference'
// 'int &' literally means 'reference to int'
void fByReference(int & referenceToOriginal)
	// Modifies the original variable/object
	// that was passed to the function
	referenceToOriginal = 5;

// Pass 'by const reference'
// 'const int &' literally means 'reference to const (i.e. readonly) int'
void fByConstReference(const int & referenceToOriginal)
	// Compiler error - cannot modify a const reference
	referenceToOriginal = 5;

// Pass 'by value'
// The pointer is passed by value
void fPointerByValue(int * pointerToOriginal)
	// Modifies the original pointed-to value
	*pointerToOriginal = 5;
	// Modifies the value of the parameter,
	// which previously held a copy of whatever argument
	// was passed to the function, and doesn't affect
	// the original pointer
	pointerToOriginal = nullptr;

// Pass 'by reference'
// The pointer is passed by reference
// 'int * &' is a 'reference to a pointer to int'
void fPointerByReference(int * & pointerToOriginal)
	// Modifies the original pointed-to value
	*pointerToOriginal = 5;
	// Modifies the actual pointer that was passed to the function
	pointerToOriginal = nullptr;

// It just gets crazier from here on in

But none of that is the same as actually passing a function or a pointer to a function and then evaluating the function when it’s used.

I’m tempted to give you an example of a language where the variable genuinely does represent the entire expression and the expression isn’t evaluated until the function being called needs the result (so-called ‘call by need’/‘call by name’), but I think perhaps that’s a can of worms you don’t need to worry about.

For now, only care about the languages you’re using and what they do, which for the most part is pass-by-value and occasionally pass-by-reference.

For the record: contrary to what some places will have you believe, Python only uses pass-by-value, not pass-by-reference. People get confused because Python passes references to objects by value, and some people don’t understand the difference.

I haven’t looked into the problem much, but I would presume if that commit fixes things then the problem is that you ended up moving roadTile further down the enum class, which of course gives it a different value, which probably affects your sprite list (tileSprites), which it looks like you didn’t change at any point, so your enumeration values were probably desynchronised from your sprite indices, so you were probably drawing roads in place of blankTile1 values and junk data in place of roads.

(While you’re at it, you should probably scrap that useless road variable and replace references to it with TileType::road.)

You’ll have to wait a day or two before I can produce any demo code.

Yeah, we’re both on the same page now (and this is what I was trying to articulate, just not very well apparently lol). But the info/code examples above about pointers and passing by reference also makes much more sense now… I had seen ‘&’ used (and remembered you needed it when using pointers) but didn’t know what it meant, so seeing all that really helps fits everything in place for me mentally, thanks!

Ahh, I suspected that had something to do with it- initially I tried added a duplicate blank tile to the enum (the same way I did to my tileType), but this gave me an error and i remembered I hadn’t actually added a duplicate sprite (so I changed it back)

I don’t know why but I keep forgetting to use the :: operator in place of creating extra variables so ill definitely fix that, thanks!

No worries, appreciate you taking the time, just whenever you can get around to it. In the meantime I’ll keep thinking on it

Just to clarify: that’s actually a different context to the context used in the ‘pass by reference’ case.

& in front of an expression is the ‘address of’ operator. E.g. &x is ‘address of x’. So if x were a variable of type int then the expression &x produces a value of type int *

Note that a (raw) pointer is basically a memory address, which is why this is the ‘address of’ operator, not the ‘pointer to’ operator. (So called ‘smart pointers’ are a different story, though they are usually just a wrapper around a ‘raw’ pointer with some extra voodoo to enforce certain behaviour.)

An & in the context of a type (e.g. int &) or a variable declaration (e.g. int & variable) (which are technically different contexts because of a really stupid rule inherited from C) means ‘reference’. E.g. the function int & f() returns an int & (a reference to an int), and the variable int & r would be a reference to an int.

The fact these are different contexts might not be immediately obvious unless you’ve had a peek at C++'s grammar rules, but the ‘address of’ operator occurs at the expression level and the ‘reference’ modifier occurs as the declaration level.

I don’t have the exact code so I can only guess based on what you’re describing but…

If you did what I presume you did, that was an error because it violates the one definition rule (commonly abbreviated ODR). I.e. you would have ended up trying to give two different values (and thus two different meanings) to the same identifier: TileType::blankTile.

Remember that every enumerator of an enumeration (enum class) has a value, and each enumerator can have only one value.

The code:

// Shoved onto a single line for the sake of brevity
enum class A { a, b, c, };

Implicitly gives A::a an underlying value of 0, A::b an underlying value of 1 and A::c an underlying value of 2.

To write:

enum class A { a, b, c, c, };

Would attempt to give A::c a value of both 2 and 3, and that violates the ODR, because the two definitions of A::c conflict: A::c cannot be both 2 and 3, those are incompatible definitions.

You should really try to take note of what these errors say and under what scenarios they occur, it might help you learn what they actually mean. Errors always tell you the exact cause of the problem. The exact cause isn’t always the root of the problem (e.g. the compiler will never tell you “missing semicolon”), but it gets you at least halfway there in most cases.

(I would guess in the enum class case it was something like error: redefinition of 'blankTile'.)

Try doing it manually on paper and writing down the steps you take in plain English as a list of instructions.

After all, programming is actually about problem solving.
Programming languages are merely how programmers express solutions to problems in a way that both humans and machines can understand.
There’s no program that a computer can run that a human can’t do by hand given enough time and resources.

Ahh ok, will definitely keep all that in mind, thanks!

Actually no, when i added a second blank tile to my tile types i did change the naming from blankTile to blankTile0 and blankTile1, but ill go back and see what the error actually says (and what caused it because now that i try to think about it i honestly cant even remember at this point), either way i had a feeling the problem likely had to do with two different enums and only one sprite (because of how everything else is set up)

Ill also go back and look here though, thanks!

Will also try this to see if it can maybe shed a bit more light, thanks!

Sorry, ive still been struggling with this- honestly just been so sapped of energy i can feel my brain isnt even working right anymore, i know i should be able to break it down more simply but it feels like im at a point where im rubbing my last two brain cells together trying to make a spark and its just not happening lol.

Sorry for the delay in replying, between sorting out the EEPROM API and the other things I’ve got going on it slipped my mind. I’ll have a quick look when I next have time, but that might not be for a few days.

No worries, ive been juggling a bunch of bullshit thats come up anyways- just whenever you get around to it, thanks, i appreciate it!

1 Like

Sorry, still no rush on this or anything, just wanted to keep it from getting buried :sweat_smile:

I did briefly start thinking about it the other day, but had to put it down again because I realised I’d have to reread quite a lot of stuff to remember what the actual issue was.

On a quick skim, was the bit you were struggling with this bit?

Or was it the bit about increasing the probability of certain tiles occurring?

No worries, sorry lol. I appreciate it though. And it was an issue with the subdivision- it mostly looks ok except it can only subdivide a certain number of times then youre left with some blocks that are still a bit too large, i wasnt sure how to fix this.

Whoops, i found it, sorry- yes, i forgot that pertained to what i was having issues with, thought you had offered that as a previous solution to something else. I was just having trouble figuring out where i would implement in the code since im still struggling a bit to understand everything step by step, sorry

The only places Im seeing where you did anything randomly are in generateHorizontalStep/generateVerticalStep, lines 104 and 129 respectively:

const uint8_t division = 1 + (rand() % (height - 2));

(or width instead of height for the vertical step)… But im not sure what this is actually doing so im not sure how i might change it like you described.

The short version is that it’s recursively partitioning the space using the roads as the partition line.

  • It starts with the whole rectangular map filled with houses
  • Then it picks a random position along the X axis and draws a vertical line of road tiles at that X coordinate from top to bottom (this is a ‘vertical step’).
  • Then it considers the building tiles to the left of that road/partition line to be one rectangular space and the building tiles to the right of that road/partition line to be a second rectangular space.
  • On each rectangular partition it performs a ‘horizontal step’, which is the same thing as a ‘vertical step’, except the road/partition line is drawn along the X axis from left to right (i.e. the random value is chosen along the Y axis). This also causes a partition, which means there are then effectively 4 rectangular building zones.
  • More vertical and horizontal steps are performed repeatedly until either a certain ‘depth’ of partitioning steps or the rectangular partition is smaller than a particular size.

(This whole thing is basically axis-aligned alternating-step binary space partitioning, and the partitions could effectively be described with a binary tree.)

The overall effect is a bit like this:

Where the white space represents the buildings and the lines represent the roads.

That’s the best explanation I can manage at the moment.
I’m having less and less spare time these days.

Here’s a hastily throw-together diagram that should give a better idea of how the space is divided:

Each successive image is an extra level of ‘depth’ (i.e. one more partitioning step).

The actual algorithm as presented would fill in an entire side before progressing to the other half, but hopefully this is enough to help you understand what the actual effect on the map is.

If in doubt, read through the code and run it manually with a pencil, paper and calculator.