Questions about optimizing code

Help & Information
21

Sorry, seemed it was just the emulator, sprites display fine on the actual arduboy.

Ive updated the github with separate header files (that i could still use to break up more yet) and some additional features such as a space station and player movement that simulate orbit, and two more game states for on foot and entering the space station (the latter i havent done anything with yet, but you can exit with the b button), and i updated the github with a readme for the controls. Surprisingly all of this still leaves me with 1208 bytes RAM and about 40% ROM.

Im hoping i can squeeze in a few additional features like a laser, a shop in the space station where you can maybe buy upgrades for your ship, jetpack, and laser, some enemies, then i can have the basis for a core gameplay loop and have ā€˜planetsā€™ you can go to that are just a slight variation in the gravity and difficulty levels of the enemies (damage, speed, etc)ā€¦ I know this may be awfully hopeful trying to fit in so much too, so im not trying to get too ahead of myself or anything yet, im just surprised ive been able to fit in as much as i have so far and thats just what i was hoping for, so if i need to trim things down or work it into something else i could always go a different route, just what i have in mind right now.

Next I need to figure out a way to spawn enemies (randomly) but in a way their locations persist so they can move around

22

Okay, ive gotten enemy locations to work and to get them to chase the player, the only issue is they also rely on the map movement per player input and are tied to just one square (so they move when it resets), and i need to figure out how to get them to only chase within a certain range, at this point they just flock :stuck_out_tongue:

1 Like
23

This is a bit of a different situation though.

The reason StarTerrain can get away with using only a hash function is because the stars donā€™t need any kind of pattern to them.
They can look completely random and nobody will notice.

I donā€™t know what you mean by ā€˜coordinate repetitionā€™.

Memory always seems to go up the quickest at the beginning for various reasons.
(Mainly due to functions being used for the first time.)
Then it slows down a bit afterwards.

I suddendly remembered I never got round to explaining how to do collisions.

The general idea is just that before you actually move something, you check where itā€™s going to end up and if that new position would make the object collide with something, you stop it colliding and move it to just before the collision would occur.

Depending on how you want the collision to be resolved, youā€™d possibly either remove both objects or youā€™d calculate a new velocity for one or more of the objects involved in the collision.

Have you looked at some of the larger Arduboy games?
Youā€™d be surprised what you can fit in.

If you havenā€™t played it, give Dark & Under a go sometime.
I was one of the three people working on it and my primary duty was to find ways to save memory.
(Iā€™d find some memory savings, and then @filmote would find ways to use up the memory Iā€™d just clawed back. :P)

Usually when someone says ā€˜persistā€™ they mean after the device is turned off.

If you just mean ā€˜between framesā€™, then the answer is RAM.

Allow me to introduce you to my friend, Euclid of Alexandria.

EuclideanDistance

int DistanceSquared(int x0, int y0, int x1, int y1)
{
	const int xDistance = (x1 - x0);
	const int yDistance = (y1 - y0);
	return ((xDistance * xDistance) + (yDistance * yDistance));
}

float Distance(int x0, int y0, int x1, int y1)
{
	return sqrt(DistanceSquared(x0, y0, x1, y1));
}

Using just the squared distance can be a good optimisation if youā€™re only doing a comparison because sqrt is an expensive operation.

2 Likes
24

Hoooo boy, have i seen some of the games you guys have put out, buddy i daydreamed about em for a good year and a half before I could finally play em :stuck_out_tongue: I just donā€™t know half as much to be able to really utilize things as best I can yet.

And sorry, to clarify I essentially have my map set up using four different 128x64 backgrounds in the quadrants of a larger rectangle, and since the player input moves the map and not the player, the tiles of the map itself actually repeat (not just the background sprite but anything thatā€™s tied to them also (unless I have it set to update the position like with the launchpad).

I have the player set to spawn in the top left quadrant now because anything would be drawn down from there so I can also use the map itself as my coordinate systemā€¦ And i set up the enemies to spawn similarly to how I set it up for the rocks to spawn in my very first program, using a for loop to iterate through two arrays (one for x, one for y) and populate with random values within the range of my Iā€™ve overall map size (until the specified number of enemies) only this time i added an additional for loop inside to check if the values were greater or less than player location (and set it to reset the value of the initializer so it just keeps updating). I figure this may not be the best way to do it, just figured Iā€™d try and hey, it worked :stuck_out_tongue:

I just got the enemy sprites set up on their own coordinate system now though (independent of the map tiles but still moving with them), so now I move on to setting the chase parameters using what you just posted (and figuring out the collision detection after that), thanks a lot!

EDIT: Actually nevermind, still having some difficulty figuring out how i would work the euclidean distance into what I haveā€¦ updated the code in my Github but will have to keep thinking on it (its a bit of a mess).

25

My instinct is that it should be cheaper the other way around,
but I canā€™t think what the maths involved would be like.

If I had time to sit down and think about it then I think I could probably think of a way around it,
but it would take me a while to process all those if (background1.y < -64)-style conditions and figure out how the backgrounds are actually moving.

I originally misunderstood what you meant by this.

Looking at the code, instead of doing:

uint16_t alienX[50];
uint16_t alienY[50];

You could just do:

Point alienPositions[50];

And then instead of:

  for (int x = 0; x < 20; x++) {
    alienX[x] = random(0, 252);
    alienY[x] = random(0, 124);
}

Do:

for (uiny8_y index = 0; index < 20; ++index)
	alienPositions[index] = Point(random(0, 252), random(0, 124));

Iā€™d offer a solution, but Iā€™m actually not sure how what youā€™ve got works at the moment.

You have an Alien struct, but only one alien?
Yet you store enough coordinates for 50 aliens?

I would have expected youā€™d just have an array of Aliens.

26

Sorry, how do you mean?

Sorry, yeah I actually meant to remove that struct after I ended up just using the arrays, didnt mean to make things more confusing than necessary.

And as for the rest of it, I have it set up so that when each quadrant reaches its respective limits it resets the backgrounds coordinates so the backgrounds continually alternate in each axis (and by association whatever may be tied to them). I got the alien positions to work correctly by just increment them per player movement alongside the map, rather than their positions being set by adding the map increment during the draw (if that makes any more sense). But I also wasnt sure how to move from two one dimensional arrays to using a two dimensional array so ill fix that, thanks!

So basically, at the start (before any backgrounds reach their limits and reset), the player is in the top left quadrant with the backgrounds drawing down and right, and the alien locations fit within that same 2x2 rectangle now (but also dont repeat with the backgrounds). The player draw command is reflective of the same coordinate system (at this point) because it also draws from the top left, but since the player stays in the center of the screen I made the secondary object ardunautMapPos in order to keep track of it where it is in relation to the the map and alien coordinates.

I get the idea of the euclidean distance because im pretty familiar with geometry and trig, and i would think that inputting the alienX and Y and the player X and Y would just give the distance (and you could say if the distance is shorter than whatever specified distance then close that distance to chase), im just not sure how to tell it to shorten that distance in turn.

27

The camera and player move, the world stays where it is.

Then the backgrounds donā€™t move until itā€™s time to draw them.

At which point they temporarily ā€˜moveā€™ so they can be drawn,
but they donā€™t actually move, youā€™re just calculating their screen coordinates.

Thatā€™s what I did in the StarTerrain demo.

Oh hang on, I think I know.
Youā€™re using the Egyptian log trick.

EgyptianLogs

As the block moves off the back log, the back log is moved to the front.

Except the logs are your background(s).

Nope, still donā€™t get it.

The example I gave isnā€™t a two dimensional array.
Itā€™s a one dimensional array of Point instead of int.

Thatā€™s good. When I started programming Iā€™d forgotten everything and had to relearn it all.

Yes, precisely.

Vectors!

Except I donā€™t have time to explain them because itā€™s late,
so hereā€™s (rather oddly for me) a Youtube playlist explaining various aspects of vectors:

(If itā€™s not showing up, click here.)

You donā€™t necessarily have to listen to the whole of each video, you can skip through every few seconds and still make sense of it.

1 Like
28

Ah, yeah, thats why I was initially trying to do what you did in the star terrain demo for this part, figured it was probably more sensible, was still just a bit too far over my head yet though, sorry.

And yeah, thats essentially what im doing, I just saw some benefits in doing it that way over just drawing the backgrounds in a different location because the egyptian log trick still retains the map values for objects tied to it (and I wasnt sure if the star terrain demo was similar).

I just meant that I was initially having issues with the alien sprites because they were tied to the background coordinates so when they got egyptian loggā€™d the enemy coordinates did too, so now I have them on the own coordinate system (basically overlaying the backgroundā€™s) which i increment the same way I move the map via player input.

And sorry, id just gotten myself more confusing thinking the points would have two values for the arrayā€¦ im still not too strong on arrays and i think ive been subconsciously avoiding them so ill just go ahead and get myself better read on that too, and points for that matter.

And i forgot about vectors, but i already have some idea of that from my old job field too, luckily. Just been getting rusty with my old skillset and kind of forget since its not right in front of me. But ill definitely look more into that and get a better idea of the math involved, thanks!

And no worries, appreciate the help as it is, sorry i seem to make more of a mess than i can clean up but hopefully that should help get things straightened out more here :stuck_out_tongue: thanks again!

29

Which part?

If youā€™re still worrying about what goes on in the hash function, donā€™t worry about it.
You donā€™t have to understand how it works to understand what it does.

It could just as easily be:

uint32_t hash(uint32_t value)
{
	// 127 and 8191 are prime numbers
	// (specifically 'mersenne primes')
	return ((value + 127) * 8191);
}

uint32_t hash(uint16_t x, uint16_t y)
{
	const uint32_t x2 = x;
	const uint32_t y2 = y;
	const uint32_t value = ((x2 << 16) | (y2 << 0));

	return hash(value);
}

uint32_t hash(int16_t x, int16_t y)
{
	return hash(static_cast<uint16_t>(x), static_cast<uint16_t>(y));
}

The important thing is the job that the hash function does:

  • It takes a pair of coordinates (x and y) and returns a seemingly random value (i.e. there should be no obvious pattern to the output)
  • It provides a valid output for all possible combination of input values (i.e. itā€™s a ā€˜surjectiveā€™ function)
  • It always provides the same output for the same pair of inputs and it has no side effects (i.e. itā€™s a ā€˜pureā€™ function)

Any function that meets those three criteria could be used for the hash,
the only difference would be in the quality of the result.

Iā€™m not sure what you mean by this.

Or this.

I think you might be getting the meaning of ā€˜coordinate systemā€™ mangled.

Usually for a 2D game there are only two coordinate systems that need to be taken into account: world coordinates and view/camera/screen coordinates.
(For a 3D game thereā€™s usually two other systems to take into account.)

The typical way to handle a 2D world is to give all the terrain static coordinates (i.e. non-changing coordinates),
and all movable objects/entities dynamic coordinates (i.e. changing coordinates).

Then thereā€™s a ā€˜cameraā€™ object which represents the screen,
and that object moves around the map.

Then when itā€™s time to render, the world coordinates are translated to screen coordinates by subtracting the cameraā€™s position.

CameraSmall
(Excuse the hand-drawn diagrams, I find hand drawing quicker and easier than digital drawing.)

For example, if the camera object is at (16, 16) (top left coordinate), and an enemy is at (64, 64),
then when theyā€™re translated into camera/view/screen space,
the camera will be at (0, 0) (so the cameraā€™s top left coincides with the screenā€™s top left),
and the enemy will be at (48, 48) ((64 - 16) == 48).

Theyā€™re literally just a block of memory with values laid end to end.
For example, int array[4] would be 8 bytes.
In memory it would look something like this:

[0x0400] array[0], low byte
[0x0401] array[0], high byte
[0x0402] array[1], low byte
[0x0403] array[1], high byte
[0x0404] array[2], low byte
[0x0405] array[2], high byte
[0x0406] array[3], low byte
[0x0407] array[3], high byte

The hex values represent RAM addresses, I made up the address values.
The low byte comes first because AVR is ā€˜little endianā€™ (like x86),
which means lower valued bytes are stored first.

A Point consists of 2 int16_t, which are two bytes.
In memory a Point looks something like this:

[0x0500] x, low byte
[0x0501] x, high byte
[0x0502] y, low byte
[0x0503] y, high byte

So an array of two points, Point points[2], would look like this in memory:

[0x0600] points[0].x, low byte
[0x0601] points[0].x, high byte
[0x0602] points[0].y, low byte
[0x0603] points[0].y, high byte
[0x0604] points[1].x, low byte
[0x0605] points[1].x, high byte
[0x0606] points[1].y, low byte
[0x0607] points[1].y, high byte

Thatā€™s literally all there is to it,
the data is just stored in memory contiguously,
and the compiler handles all the maths needed for moving the data around.

2 Likes
30

Iā€™m still trying to determine that :stuck_out_tongue: just because there are a lot of parts that are new to me, so I can follow up to a point but like I said, then it just kind of starts to blend together, but I didnā€™t want you to have to break it down for me step by step so to spare you a lengthy explanation Iā€™m trying to better inform myself on whatā€™s going on at each step by breaking down and identifying each part I donā€™t know.

But that definitely helps a bit knowing that about hash functions- I remember you mentioning that before but sometimes I canā€™t see the forest for the trees when being faced with a lot of new information (an unfortunate byproduct of adhd, like I said, but something Iā€™m working on), but I also forgot that somewhere along the lines so when I give it another look Iā€™ll know that I shouldnā€™t need to follow along with that part as much. I just want to be able to follow along with the rest of it so I can change it to use for the other part without having to ask you to change it (and because Iā€™m trying to do as much of the work myself so Iā€™m not asking others to do it).

And as for my looser definition of coordinate system I suppose it isnā€™t in the usual sense then (as is in camera and word coordinates), I just canā€™t help but think of it in those terms because itā€™s still confined to some sort of coordinate system based off the screen x/y draw origin- all my map tile coordinates are based (and placed) in relation to it and so are my objects- only initially, since I move the map coordinates for player movement, other objects were tied to the map also (because, for example, during the draw command for my launchpad or enemies the x and y values were their x and y + background x and y so they would move with it).

Although effectively there are multiple actual coordinate systems at play (for the backgrounds, player position, and enemy locations), more so now that I changed the enemy coordinates to be their own coordinate system (so when player inputs left rather than just background x + and enemy x drawn with that, player inputs left and both background x + and enemy x+).

But given how much more complicated (and convoluted) my method gets I can see the benefits of the static world and camera method, so Iā€™ll try to review again and implement it.

Also I better organized my game by further breaking it down into more header files (one for in flight, one for on foot, one for the menu, etc) to make it easier to look at/read. Not sure why I was having difficulty with that before

31

My advice would be to write it down as you go.

Draw some diagrams too.
(The stacks of paper on my desk are getting ridiculous.)

CameraStuffSmall
CameraStuffSmall.png824Ɨ827 978 KB

Every time you understand something, give yourself a biscuit.
(Perhaps not a biscuit, youā€™d get through at least 100 by the end, and that canā€™t be good for your health. But you get the idea - keep the reward loop running.)

Ah, ok, in that case technically the enemy coordinates are local to the background coordinates,
which does sort of mean thatā€™s a separate coordinate system.

But thatā€™s a cause for concern because that means thereā€™s no such thing as ā€˜globalā€™ coordinates,
because everything keeps moving.

Yeah.
I think really you need to separate the background rendering from the world itself.

At some point Iā€™ll try to sit down and figure out a way to render your backgrounds infinitely without actually ā€˜movingā€™ the backgrounds as such.

Iā€™ve put it off because I donā€™t like maths.
(Saying ā€œI donā€™t like mathsā€ is probably a terrible thing for a programmer to say given the amount of maths involved in programming.)

Do you need all four backgrounds or are you happy with having just one background tiled infinitely?
(The parallax is going to complicate things, that much Iā€™m sure of.)

1 Like
32

Well thatā€™s another reason why I did it the way I did it- was to restrict/repeat the actual playable area, too (via the local background coordinates) so rather than just repeating the background tile the map itself repeats, (so that flying in the x direction always brings the player back to the launchpad and so the space station can ā€˜orbitā€™, and so on foot the player comes back around the other side of the map Iā€™m x or y like theyā€™re running around a small sphere/planet).

But this is also something I could just define for each part based off the same coordinate system (once I get that set up) rather than it being that way by association, so if I need to just start again from the ground up to structure everything different (because trying to change everything would make too big a mess) then Iā€™m fine with that too, will probably do that anyway so Iā€™m not trying to sort out a mess.

33

There are multiple ways of doing that, some easier than others.

In fact wrapping the playerā€™s coordinates is easy, the hard part is actually the rendering.

Technically it would be a torus.

TorusWorldSmall
TorusWorldSmall.jpg960Ɨ504 213 KB

(Thereā€™s an article about this quirk here.)

You probably donā€™t need to tear everything up,
but I think having a global coordinate system will make everything easier.
Especially later when youā€™ve got projectiles flying across the screen.

1 Like
34

Iā€™ll have to think on that a bit then, not sure how Iā€™d go about everything now

35

Havenā€™t got parallax in, but hereā€™s an infinitely tiling background:

The important bit is around here in drawBackground():

(Ignore the <<, Iā€™ll explain that another time.
Itā€™s just me being too lazy to write a long list of print calls.)

Iā€™ll explain the maths tomorrow if you canā€™t figure it out.

Referring back to my diagram in this post should help:

1 Like
36

Sorry, Iā€™m still lost.

37

Iā€™ve started on a diagram, Iā€™ll probably finish it tomorrow.

If in doubt, read the code as if you were the Arduboy,
and manually calculate some of values with some example inputs.

1 Like
38

Ah, yeah, sorry, probably should have occurred to me sooner to try to trace out what itā€™s doing step by step the same way on paper as trying to read it like I was the compiler, hopefully thatā€™ll help me to compartmentalise whatā€™s going on a bit better, thanks!

EDIT: Sorry, got a bit tied up elsewhere since and am just now able to get back to itā€¦ Im sure you dont mind the wait/have other things to do, just didnt want you to take the time/energy going too in depth if i havent done what i can yet to do the same, myself. But just now getting back to it.

39

Hmā€¦ so I can understand up until the first few blocks of drawBackground(), more specifically here:

	const int16_t left = (camera.getLeft() / tileWidth);
	const int16_t leftOffset = (camera.getLeft() % tileWidth);
	
	const int16_t top = (camera.getTop() / tileHeight);
	const int16_t topOffset = (camera.getTop() % tileHeight);

I can see how you make the camera object then just increment it via player input, I just dont understand the use of the modulo operator here.

Then I dont understand from here down either:

        const int16_t yStart = (top > 0) ? 0 : -1;
	const int16_t xStart = (left > 0) ? 0 : -1;

I understand how this evaluates if the first expression is true or false and then evaluates one of the following two depending on the result, i just dont quite understand what comes after it (ignoring the debug draw, of course) or just how it relates to whats above, either.

40

Sorry, Iā€™ve been busy the last two days so I havenā€™t had chance to finish all of that diagram.
I did a few bits, then I went over them in pen because the pencil looked a bit faint,
but the pen wasnā€™t very good so now itā€™s a bit of a mess.

Hereā€™s two parts from it that might help:

OffsetsSmall TileIndicesSmall

Basically modulo produces the remainder after division.
Dividing the cameraā€™s x by tileWidth tells you the index of the cell that the camera is in.
Using modulo on the cameraā€™s x by tileWidth gives you the remainder of that,
which is the offset of the cameraā€™s x into the tile itā€™s currently in.

Likewise for y and tileHeight.

The reason the condition is there in the first place is because 0 and the negatives need to start from -1 rather than 0 otherwise the rendering doesnā€™t work properly because itā€™s off by one tile/cell.

Iā€™ll explain that another day, but the (rather scruffy) diagrams I posted above might help.

(I really need to find some coloured pens. Iā€™ve only got

1 Like