Help me with C++ for my game

(Pharap) #123

Hash tables are too heavy for the Arduboy.

My approach basically is a map, but it maps with numeric ids instead of strings.

Here’s an improved version of what I posted earlier, which this time hopefully compiles:

#pragma once

#include <avr/pgmspace.h>

struct WarpPoint
	uint8_t roomId;
	uint8_t fromX;
	uint8_t fromY;
	uint8_t toX;
	uint8_t toY;

class Room
	constexpr uint8_t roomWidth = 16;
	constexpr uint8_t roomHeight = 16;

	const uint8_t * room;
	const WarpPoint * warps;
	uint8_t warpCount;
	constexpr Room(const uint8_t * room, const WarpPoint * warps, uint8_t warpCount)
		: room(room), warps(warps), warpCount(warpCount) {}
	template< uint8_t size >
	constexpr Room(const uint8_t * room, const WarpPoint (&warps)[size])
		: room(room), warps(warps), warpCount(size) {}
	uint8_t getWarpCount() const
		return this->warpCount;
	WarpPoint getWarpPoint(uint8_t index) const
		WarpPoint warpPoint;
		memcpy_P(&warpPoint, &this->warps[index], sizeof(warpPoint));
		return warpPoint;
	uint8_t getTile(uint8_t x, uint8_t y) const
		return pgm_read_byte(&this->room[y * roomWidth + x]);

const uint8_t room0Data[] PROGMEM = { /* blah blah blah*/ };
const WarpPoint room0Warps[] PROGMEM = { { 1, 0, 0, 16, 32 }, /* etc */ };

const uint8_t room1Data[] PROGMEM = { /* blah blah blah*/ };
const WarpPoint room1Warps[] PROGMEM = { { 0, 4, 4, 16, 32 }, /* etc */ };

const Room rooms[] PROGMEM =
	Room(room0Data, room0Warps),
	Room(room1Data, room1Warps)

Room getRoom(uint8_t roomNumber)
	Room room;
	memcpy_P(&room, &rooms[roomNumber]);
	return room;

You need an x and y in the source room and an x and y in the destination room, plus the room id of the destination.

Fair enough.
You can always treat interactable objects as entities if you have any.


I always forget to like posts that I enjoy or are helpful so I just went full serial liker for a minute.

I’m thinking about how I’m gonna design the game. Procedural generation, if I can do it right, would be a great way to have a huge world without having to store all of it. I think an overworld might be easier to design this way than the dungeons,

I’m gonna make a prototype of this in GameMaker first and see if it works well

I was thinking about how I could make a chunk system. (which I might need for my procedural generation anyway) and that could be a solution to having a camera that follows the player. But again a big disadvantage of a camera like that is that it can be harder to see obstacles and enemies that are close-by.

I’ve got a lot of prototyping to do, I’ll work on all that and when I get something decent (and feasible on the Arduboy) I’ll come back. (which might be today… don’t know how long I’ll take)

See ya!

(Pharap) #125

You can also bookmark comments to keep track of interesting/useful things.

Prepare to enter the rabbit hole:

I recommend learning how to use SDL2 at some point,
then you can reuse most of your prototype code because it’ll already be in C++.


I wrote more than I expected, it’s almost a blog post

I didn’t know, but I probably would have bookmarked many of your comments. (Fortunately CTRL+F works well on this website)

I already have this in mind!

There’s this pseudo random number generator that seems promising. I know there’s one with the Arduboy but I’ve been interested in getting more ‘hands-on’ with PRNGs. Also if I port the game to something else, I’ll need the same PRNG to get the same results.

If I “lerp” between different numbers I should get very nice terrain (I’m using 2 types of “grass/ground” tiles and one for paths between houses). Then I’ll need a way to generate houses, I suppose I could make a house class that holds different house layouts.

I don’t actually want an infinite terrain by the way (although, maybe?), all I need is an extremely tightly compressed overworld. An overworld can be pretty generic and still be fun to explore, caves and dungeons however, I think I’ll do them by hand. It’s easier to make a nice dungeon than a nice dungeon generator (or, is it?)

For traps, think Prince of Persia/Indiana Jones stuff. If you never played Prince of Persia, my blade trap in my game is an imitation of a trap in that game.
HTML5 prototype of my game I posted much earlier

Example of said trap in Prince of Persia:

I also got new ideas because, while trying to find this example I found this and this

I might add jumping now that I’ve thought about it. Wall collision wouldn’t change, but it would allow to jump over spikes or holes on the ground. All I’d need to make it work is a shadow blob that stays at the x and y of the player. If you fall on spikes, too bad for you and fine for me, I don’t need to code a system to make you slide away.


Hey I think I figured out a way to do a queue with an array, all I need is an index and the modulo operator

If I want to take what’s at the bottom of the queue and put it at the top, I can increment the “base_index” that is added to whatever index I’d pass in the getter.


That means If I want to have only one chunk in RAM, I can have a flat array of size ((SCREEN_WIDTH + TILE_WIDTH) / TILE_WIDTH) * ((SCREEN_HEIGHT + TILE_WIDTH) / TILE_WIDTH)

And have a base_index_x and base_index_y that would be the x of the camera divided by the number of tiles

I’m not sure if I’m explaining myself clearly, but in short, instead of having a bunch of chunks around the player, I could load just the tiles I need and do (base_index_x + xindex) % TILES_PER_SCREEN_SECTION.

TLDR modulo operator = 2D queue structure without pointers. Not sure if there’s a name for that

(Pharap) #128

The code provided isn’t valid. init_rng has no return type, the arguments have no type, a, b and c aren’t declared anywhere and there’s a missing semicolon after the return in randomize.
Also if b is signed then the behaviour is implementation-specific.

I decided to check the period (the number of values generated before encountering a duplicate).
Its best case scenario period is 256, which is good,
but its worst case scenario is a period of 1, which is really bad.

You may also want to look into hash functions.
Hash functions aren’t stateful, so they’re more commonly used for on-the-fly terrain generation (as opposed to pre-generating whole rooms/dungeons).

Lerping usually uses floats, which can be quite heavy on the Arduboy.
Something to be aware of.

There’s lots of different articles on dungeon generation, and lots of different algorithms.
The mystery dungeon series has all its dungeons procedurally generated.

It is easier to make dungeons by hand, but the issue is space and compression.
If you can procedurally generate then you can fit more in, but they might look a bit more generic, or have some oddities.

I think mario got there first with its spinning bars of lava.

You’re probably better off looking at 2D legend of zelda games.

For example, the first dungeon of Oracle of Seasons:

Which is also an excellent example of what I was talking about earlier where the rooms are bigger than the screen but the camera clamps when you approach the edges of the rooms.

You might want to start with implementing some of these things before you get carried away with what traps you’re going to have.
Progmem runs out pretty fast if you keep piling new features in.
Every extra feature is potentially another room or sprite that you can’t have. There must be balance.

Why would you want/need a 2D queue?


Instead of having 9 chunks loaded, I can have just have a 2D array of [TILES_PER_SCREEN_WIDTH + 1][TILES_PER_SCREEN_HEIGHT + 1] and update just one row and one column at a time. Less RAM needed

Apparently it’s either a 2D queue or a queue of queues and it doesn’t have a specific name

EDIT: it can’t be a 2D queue, because I’m pretty sure you can’t interate through a queue.

(Pharap) #130

That’s not really a queue, that’s just a 2D buffer.

Queues are specifically ‘first in first out’, but because you could walk backwards to reload the row/column you just unloaded (a ‘last in first out’ behaviour) what you’ve got is more comparable to a double-ended queue (or ‘deque’, e.g. std::deque).
But even then, it’s still just a kind of 2D tile buffer with deque-like behaviour rather than an actual deque.

It depends on your viewpoint.
Purists would probably argue that a queue is strictly the interface of being able to enqueue/dequeue data and anything else makes it not a queue, or is at least irrelevant to its existance as a queue.
Other people would say ‘of course you can iterate a queue, it’s just a special way of looking at a list’.

C++'s stdlib doesn’t allow iteration through a std::queue, but usually the underlying container allows it.
C#'s Queue can be enumerated through, I don’t know about Java without checking.


Hey I’ll be back later, I really need to think through what I said to explain what I meant, and it’s almost as difficult as just trying it out

I’ll show whatever works later instead


I will look into this, thank you!

Found what I needed!

Edit2: Maybe another one, this one needs a lookup table
Edit3: 256 bytes in a lookup table for the whole overworld? Might actually be an extremely good deal, I’ll be trying it out

(Simon) #133

A ‘Queue’ in Java is just an interface. The ‘LinkedList’ class implements this and has an iterator. So … yes.

(Pharap) #134

There’s no rush, I’ll be gone within the next hour or two.

If you’ll excuse the number of tiles being off (this is a modification of a graphic I made for explaining something similar with the Pokitto):

Green tiles are visible, blue tiles are the ‘buffer’ rows and columns.
A 2D buffer of tiles where the loading and unloading is ‘deque-like’.

This is what you meant, yes?

Usually people refer to Perlin noise.

Hadn’t heard of Pearson hashing, but it looks interesting.

template< uint8_t size >
uint8_t hash(const uint8_t (&message)[size])
	uint8_t result = 0;
	for(uint8_t i = 0; i < size; ++i)
	  result = lookupTable[result ^ message[i]];
	return result;

uint8_t hash(const uint8_t * message, uint8_t size)
	uint8_t result = 0;
	for(uint8_t i = 0; i < size; ++i)
	  result = lookupTable[result ^ message[i]];
	return result;

Depends whether it works out or not.
You may have to toy around quite a bit before finding something suitable.
Decent pseudorandom terrain generation requires either luck or the ability to analyse and understand the patterns of different sequences.

For example, if you analyse the output of a linear congruential generator with certain settings you find that:

all points fall mainly in the hyperplanes. There are actually more than one set of parallel hyperplanes if seeing the k-dimensional space from a different orientation
(As mentioned here.)

Or to put it in a non-mathsy way:

Straight lines aren’t random. :P

I really hope other classes implement it too.
Linked lists are slow enough with bare pointers, I dread to think how slow they are with Java’s “everything’s a reference” approach to OOP.

(Simon) #135

Yes …

AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue

I don’t even know what half of these are. Not all of them implement the ‘Iterable’ interface though.

Everythings slow in Java land. Layer on top of that things like Hibernate, Spring and a myriad other open-source libraries and it just performs badly at all levels of operation. Hibernate is appropriately named … sneds your code of for a winter slumber.

(Pharap) #136

This is probably the equivalent to C++'s std::deque. And it’s iterable, as expected.

This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

Probably because the JVM’s bytecode is terribly designed.

I can’t remeber which talk it was, but I once watched a talk Bjarne Stroustrup gave where he explained how C++ stores objects directly in an array compared to how languages like Java have an “everything’s a reference” approach and what kind of horrible things that does to your CPU’s cache.

One more and you get to shout ‘bingo’. :P

(Simon) #137

In an epic departure from the OP … Lucene … Bingo !!

Look at this list of dependencies for the current project I am working on. The company that distributes the application must spend half of its development budget on testing upgrades of the dependencies rather than working on the actual application itself.

This is why most people’s approach to performance issues is to simply throw more processing power at it. Don’t waste time optimising code …


I’m still here!! Kind of… I’m in the noise function rabbit hole


@Pharap I found out how to explain my lerp thing without floats: if x is closer to index 0 than it is to index 1, then it takes the value of index 0.

I’m not sure how that will work in 2D, but that’s my idea

(Simon) #140

Sorry to hijack the thread!

(Pharap) #141

I’m not sure what’s more upsetting, the fact there’s at least three different versions of more than one of those dependencies, or the fact that one of the dependencies is version 0.9.

Also using antlr (a parser generator) with what is presumably a non-standard regular expressions library raises a few eyebrows.
Also what kind of project uses both YAML and JSON at the same time?
I’m guessing they’re trying to glue together data from different vendors or something.

And isoparser is aparently either an mp4 parser or a parser for ISO disk images, both of which seem to be completely irrelevant to everything else that’s going on here.

It’s a sad world out there. In the face of an ever-changing world, one quote has always stuck with me:

Your scientists were so preoccupied with whether or not they could,
they didn’t stop to think if they should.

That’s becoming ever more relevant as people find new ways to abuse phones and the ‘internet of things’.
I’d love to know what bright spark thought up hello barbie, and/or why all the washing machines and fridges now ‘connect to your smart phone’.
I don’t want to text my washing machine, I just want it to clean clothes.

Just a heads up, I’d be wary of downloading stuff from sourceforge after the 2015 incident.
They’re under new management, but I’m still reluctant to use them.

The article is somewhat interesting regardless.

I have no idea what the context is, but it sounds reasonable.

Failing that, fixed points are an option.

At least it solves the “this place is too quiet” problem. :P

(Simon) #142

Any application written that uses open source … half of these libraries will have configuration files using YAML, the other using JSON. YAML is a superset of JSON, which means you can parse JSON with a YAML parser but that would require the authors of the various library to coordinate and use one library …

Just trying to get the open source libraries to coexist.

God knows what that is for.

My application takes 4 minutes to start and I can rarely change code in place so I have to start and stop regularly. This allows me to get distracted regularly …