Learn C Games Programming

Progress on the Match Three game

Posted on June 1, 2020May 26, 2020 by David

Having a week off work has let me work on this game a bit more. I’ve put in about eight hours and it is now correctly dropping.

I’d never programmed one of these before so my first version used a board of pieces plus a secondary array for holding “transitions”. A transition was a struct that held information about two pieces being swapped and the current coordinates of each piece. It seemed to be quite messy code and was quite buggy with pieces on top of other pieces.

So I then switched to a system where each board cell had a pointer to a struct for a piece (held in an array). If the piece wasn’t moving the program calculated its pixel coordinates from the board coordinates and drew it there. If it was moving, it would no longer have board coordinates and would use the pixel coordinates to draw it.

That was better but then I thought why not just have the board just be a 2D array of structs with one struct for each piece.

This is the struct for each piece.

struct Cell {
	int piece;
	int moving;
	int scEndX, scEndY;
	float scCurrentX, scCurrentY;
	float velY, velX;
	int bdEndX;
	int bdEndY;
	int angle;
	int lock;  //1 = locked. Display padlock
	int size; // used when killing to diminish size
};

SDL2 does rotation very nicely; you don’t need to pre-render shapes just call SDL_RenderCopyEx instead of SDL_RenderCopy and specify the angle and one or two other parameters. When a piece is removed, it animates for about a half-second, rotating and shrinking in place. That’s the purpose of the angle and size fields.

If the lock value is 1 then the piece stays in place and won’t drop. You have to remove the lock by forming a line that includes the locked piece. When the line is removed, all locked pieces in the line remain but without the lock.

So far the game is currently about 800 lines of code. There’s no game level structure, high-score table, sounds, bonus pieces or even a basic piece matching algorithm. I’ve been testing by just randomly removing three vertical or horizontal pieces and then having unlocked pieces above fall down.

This 3rd version does not suffer from the Mexican-wave problem that the first and second version had. Sometimes when a column of pieces moved down, instead of all pieces moving together they moved one-by-one. New pieces get added in when the top row piece finishes dropping away.

So now on with the book and the next part of the game.

An interesting way to find a bug

Posted on May 30, 2020May 23, 2020 by David

Disassembly — Image by Free-Photos from Pixabay

Here’s a bit of code with a very subtle bug. It wasn’t ever setting the size file (an int field in a struct). So I took a look at the assembly generated and spotted it. In retrospect it was a bit obvious!

void DoRotateAndDie() {
	for (int i = 0; i < 10; i++) {
		while(1) {
			int x = Random(MAXBOARDWIDTH) - 1;
			int y = Random(MAXBOARDHEIGHT) - 1;
			pBoardPiece ppiece = board[y][x].ppiece;
			if (!ppiece) continue;
			if (ppiece->size != 0) continue; // Not this one
			ppiece->size == 64;
			break;
		}
	}
}

It’s somewhat stupid. The line just before the break is meant to be an assignment but there’s double ==. Stranbgely enough the C compiler In Visual Studio didn’t generate a warning or error. When I put a break point on the line, it hit the break instead.

I was curious to see what code was generated. Here’s the disassembly.


			if (ppiece->size != 0) continue; // Not this one
00124892  mov         eax,dword ptr [ebp-2Ch]  
00124895  cmp         dword ptr [eax+30h],0  
00124899  je          DoRotateAndDie+8Dh (012489Dh)  
0012489B  jmp         DoRotateAndDie+40h (0124850h)  
			ppiece->size == 64;
			break;
0012489D  jmp         DoRotateAndDie+91h (01248A1h)

So it doesn’t generate any code at all for that assignment of 64, it’s just two jmps with no assignment! But fixing it and checking the code this time produces this:

			if (ppiece->size != 0) continue; // Not this one
00144895  cmp         dword ptr [eax+30h],0  
00144899  je          DoRotateAndDie+8Dh (014489Dh)  
0014489B  jmp         DoRotateAndDie+40h (0144850h)  
			ppiece->size = 64;
0014489D  mov         eax,dword ptr [ebp-2Ch]  
001448A0  mov         dword ptr [eax+30h],40h

Those last two lines assign 64 (40h in assembly).

Normally I pick up these type of bugs just by visual inspection. If it isn’t obvious then there are two other techniques to try. The first is get a colleague, or if one isn’t handy a teddy bear or toy duck will do. Now explain to the colleague/teddy bear/duck how the code works. Explicitly say it out loud, do not just think it. It’s amazing how often that works. The process of explaining it forces your brain to do a bit more work then if you just mentally walked the code.

The other method is to disassemble the code and look at it from a different point of view. If the compiler sees the code differently than how you think it should be, it might provide a clue. Here I found out that putting an expression in code instead of a statement, generates no code. Normally with =/== it’s the opposite, putting in an assignment instead of a comparison.

Working on the Match Three game

Posted on May 29, 2020May 20, 2020 by David

The second game is Match Three and I’d made some good progress. You can view some .mp4s from earlier this month here. The first one (MatchThree) shows rotations, something I’d never realised SDL is very good at doing. Graphics are from the excellent Dutch website (it’s in English) Kenney.nl.

The second mp4 (transitions) shows some animations. And the MatchThreeDropping shows pieces both being removed (first rotating and shrinking) and pieces dropping. However it also shows a flaw. Sometimes all the pieces move together, other times (and this is the flaw) it shows them dropping one by one- Mexican wave-like, rather than all moving together.

My original algorithm, which I am now scrapping, had a transitions table. When the space or spaces below a piece became blank, a transition was created which had start and end positions. The piece was removed from the board (a simple 2d array) and reinstated in the board when it had finished moving to the end pixel position.

I think I have a much better method now, I still use a board but each element has a pointer to a piece in a big array of piece structs. I track both the coordinates in the board (0-9,0-9) and in pixels as each piece is 64 x 64. When a space is created in the board, all the pointers are shuffled and each piece is told to move from it’s old pixel position to its new one.

The move algorithm operates purely on the all pieces in the piece array not the board. The flawed algorithm worked on both the board and transition array and was quite messy. Sometimes you have to start with a clean slate than try and fix code that is working correctly.

Array vs pointer in C

Posted on May 28, 2020May 19, 2020 by David

Grid array — Image by Anja🤗#helpinghands #solidarity#stays healthy🙏 from Pixabay

A common pattern (I use the word loosely) in my C programs is to have an array of structs to hold things like asteroids and bullets in the game. There are two ways to process an array:

As an array e.g. asteroids[index].
As a pointer to an individual array element. Asteroid * pAsteroid = &(asteroids[index]); then refer to pAsteroid ->

One of the tents of software design though not that often said is that the easier the code is to read, the easier it is to understand. Programmers spend a lot of time reading code. Anything that lightens the cognitive load is good. I suspect it might also be faster, but not by a great deal.

Of course pointers make some programmers nervous. To me though they simplify the code. There is however another way to simplify the code. Use #define so you might have something like this:

#define table asteroids[index]

So everywhere you have a asteroids[index]., you put in table instead.
This for example from Chapter 36 DrawAsteroids()

	for (int i = 0; i<MAXASTEROIDS; i++) {
		if (asteroids[i].active) {
			numAsteroids++;                    // keep track of how many onscreen
			int sizeIndex = asteroids[i].size; // 0-3
			int asize = sizes[sizeIndex];      // asteroid size 280,140, 70,35
			target.h = asize;
			target.w = asize;
			asteroidRect.h = asize;
			asteroidRect.w = asize;
			asteroidRect.x = asize * asteroids[i].rotdir;
			target.x = (int)asteroids[i].x;
			target.y = (int)asteroids[i].y;

Would become

	for (int i = 0; i<MAXASTEROIDS; i++) {
		if (table.active) {
			numAsteroids++;                    // keep track of how many onscreen
			int sizeIndex = table.size; // 0-3
			int asize = sizes[sizeIndex];      // asteroid size 280,140, 70,35
			target.h = asize;
			target.w = asize;
			asteroidRect.h = asize;
			asteroidRect.w = asize;
			asteroidRect.x = asize * table.rotdir;
			target.x = (int)table.x;
			target.y = (int)table.y;

What do you think?

On apt vs apt-get

Posted on May 27, 2020May 17, 2020 by David

Linux — Image by Donald Clark from Pixabay

This is the command you use to update your system, fetch and install software. Some people use apt-get, others plain apt and the two appear interchangeable but they are NOT the same. As it’s making a change to the system, you almost always have to run it via sudo.

They are different?

Well yes. Try these.

apt --help

apt-get --help

Those give different help messages. And as for these:

apt check

apt-get check

It’s curious that apt-get check works, but apt check gives an invalid operation! I’m not sure why they are so similar yet subtly different. If anyone knows, drop me a line.

Having created this post, I subsequently did find out the differences- explained on this page. The simplified version is the apt is a simpler subset and also shows a progress bar when you do sudo apt upgrade. Try sudo apt-get upgrade next time to see it without the progress bar!

My encryption code is now live on GitHub

Posted on May 26, 2020May 15, 2020 by David

Crptography Word list — Image by tumbledore from Pixabay

I developed Pivot initially on Windows, (a Linux version will follow) though the differences are fairly small. I used the Windows _sopen_s for reading and writing files. There shouldn’t be too much differen otherwise, though I guess I’ll find out when I compile it on Ubuntu or Raspberry Pi.

The program itself is around 450 lines of C in just one file. It can encrypt around 6 MB/s on my five year old i7 5930K PC and decrypt at around 10 MB/s.

If anyone could try this, I’d be very happy. It has one minor issue that I will resolve. Because it processes files in blocks of 64 bytes, it tends to round the output file when decrypting and adds a few 0s on the end. I will get it sorted

I’ve given it a very liberal MIT license, you can do what you want with it. Instructions on using it are provided on that link to GitHub.

This BTW is the encryption code at the heart of it.

        int bit = 128;
        for (int bi = 0; bi < 8; bi++) {
            for (int b = 0; b < NUMSTREAMS; b++) {
                dataout[b] = (dataout[b] >> 1) | (data[b] & bit);
                data[b] <<= 1;
            }
        }
             
        // Now alter the order of bytes according to the key
        for (int i = 0; i < NUMSTREAMS; i++) {
           data[i] = dataout[_key[i]];
        }

The first double for loop slices 64 bytes into 64 bit streams. It’s pivoting the bits if you like, hence the name. The second for loop is what does the donkey work of encrypting it. It uses a 64 byte key (made up of 64 numbers 0-63- shuffled). As there are 1.2688693e+89 different ways of arranging these 64 numbers, if you lose the key it might take you a while to brute force it!

So I believe that it is an original encryption algorithm, but I am not an expert in cryptography so I might be making a fool of myself! Whether there are any possible attacks against it, I don’t know, but it will be interesting to see!

Hex Editor for Raspberry-Pi

Posted on May 25, 2020May 14, 2020 by David

Sometimes you just need to view or maybe a binary file and here I’ve done that on the compiled file for asteroids.

I can’t recommend doing that, but I wanted to try hexedit on the Raspberry Pi. I ran it against the asteroids compiled program and found the text.

If you look I’ve changed the d in starfield (first line of text) to an e. Then I saved it. The program, not unreasonably crashed when run with an error in the errolog.txt file: Couldn’t open images/starfiele.png

You install hexedit with

sudo apt install hexedit

and run with the file you want to view/edit.

hexedit asteroids

To view all the command press F1. It displays the man page for hexedit. Have fun!

A fast random number generator in C

Posted on May 24, 2020May 14, 2020 by David

If you are using RNGs (Random Number Generators) for cryptography then you need one that has been validated for sufficient randomness. For example the libsodium library.

But if you want a fast one for general purpose use, then xoshiro256++ is a fast one. It’s actually that short that I can list it here. Just call next() and mod it (%) with the highest value+1. E.G. for a dice roll,

int diceroll= (next() %6) +1;

This algorithm is very fast, typically on the order of nano-seconds 10^-9 seconds.

#include <stdint.h>
uint64_t rngstate[4];

static inline uint64_t rotl(const uint64_t x, int k) {
    return (x << k) | (x >> (64 - k));
}

// Returns a Uint64 random number
uint64_t next(void) {
    const uint64_t result = rotl(rngstate[0] + rngstate[3], 23) + rngstate[0];
    const uint64_t t = rngstate[1] << 17;
    rngstate[2] ^= rngstate[0];
    rngstate[3] ^= rngstate[1];
    rngstate[1] ^= rngstate[2];
    rngstate[0] ^= rngstate[3];
    rngstate[2] ^= t;
    rngstate[3] = rotl(rngstate[3], 45);
    return result;
}

Binary editors – Useful tools

Posted on May 23, 2020May 11, 2020 by David

At some time or other you are going to need a binary editor, to let you look in files and see what they contain.

One I can recommend is HxD which is shown here.

This not only lets you look at the contents of a binary file (in hex and decoded as text) but you can change them.

It also includes file tools so you can split files, combine them (i.e. append) and securely wipe them. And very handy, the ability to compare two binary files, shown below.

It also lets you export binary files as data for any of these languages (Pascal,C C#, Java, VisualBasic.net, HTML, rich text and some other formats). Here’s what the top file looks like exported into C.

/* D:\development\pivot\pivot\Debug\l.key (11/05/2020 12:03:32)
StartOffset(h): 00000000, EndOffset(h): 0000003F, Length(h): 00000040 */

unsigned char rawData[64] = {
0x18, 0x3C, 0x2B, 0x11, 0x24, 0x1E, 0x17, 0x26, 0x1C, 0x15, 0x04, 0x19,
0x23, 0x28, 0x08, 0x07, 0x35, 0x0F, 0x34, 0x37, 0x32, 0x05, 0x20, 0x27,
0x3E, 0x0A, 0x3B, 0x2E, 0x1F, 0x29, 0x21, 0x25, 0x2F, 0x14, 0x2D, 0x1A,
0x1D, 0x0C, 0x33, 0x01, 0x39, 0x2A, 0x1B, 0x00, 0x36, 0x06, 0x22, 0x31,
0x38, 0x3A, 0x3D, 0x2C, 0x16, 0x0D, 0x03, 0x00, 0x09, 0x12, 0x13, 0x02,
0x0B, 0x0E, 0x30, 0x10
};

In truth there are many binary file editors. You can find them under hex editors as well. But this is a particularly nice one; recommended.

A remarkable piece of C code

Posted on May 22, 2020May 11, 2020 by David

What do you think this outputs?

unsigned char c = 241;
long bits = (c * 01001001001ULL & 042104210421ULL) % 017;
printf("Bits = %lu\n",bits);

Remarkably it calculates the number of bits in c and should output “Bits = 5”.

If you don’t believe me, try this program to show all 256 values and the count. If you use c in the for loop instead of i, it never finishes. Well not with Visual C++ 2019!

#include <stdio.h>

int main()
{
    for (int i = 0; i < 256; i++){
        unsigned char c = i % 256;
        long bits = (c * 01001001001ULL & 042104210421ULL) % 017;
        printf("c %d #Bits = %lu\n",c, bits);
    }
    return 0;
}

You can try this out online on one of the various online C compilers.
Here’s it on repl.it.