0

I'm trying to make a game in C fit under a 3KB limit, and to do so I want to remove all standard library references. The only header I want to have in my program is windows.h and so far I'm doing pretty good.

The only external references I have are one call each of rand(), srand(), time(), and getch(). This may seem like a lot for a game under 3KB, but the time, rand, and srand functions are only so that when the game starts it can have a random seed.

rand to get the numbers, srand to set the seed, and time to get random seeds. So if I could find a way to get rid of the excessive random generation procedure, I could get rid of 3/4 std library functions. I'm not so sure what to do about getch though, but ill focus on that later.

Some people have reccomended xorshifts, but it seems like that requires the type uint32_t, which belongs to stdint.h. I also tried using integers instead, and while the resulting number was random, it was random in the sense that the number given back was random, yet you could depend on it giving you that random number each time. I could give it time as a sort of seed, but then id still have to use the time function. Is there something I'm overlooking, or should I use a different method?

EDIT: as per request, my compilation flags are -ffunction-sections, -fdata-sections, -s and -Os. my only linker flags are -Wl,--gc-sections and I am not sure what dynamically linked and statically linked libraries are completely, but I have a decent idea. My code as is comes out to 12KB, and if i use UPX i can get it down to 7KB. my code is here:

#include <windows.h>

#define WIDTH 100
#define HEIGHT 100
#define BOMBS 800

struct xorshift_state {
  int a;
};

int xorshift(struct xorshift_state *state)
{
    int x = state->a;
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return state->a = x;
}

void ExpandGrid(int fullGrid[WIDTH][HEIGHT], int knownGrid[WIDTH][HEIGHT], int blankPos[2])
{
    int neighbors[8][2] = {{0,1}, {1,0}, {1,1},
                          {0,-1},        {-1,0},
                          {-1,-1},{-1,1},{1,-1}};
    int curTile[2];

    knownGrid[blankPos[0]][blankPos[1]] = 1;
    if(fullGrid[blankPos[0]][blankPos[1]] != 0) return;

    for(int blck = 0; blck < 8; ++blck)
    {
        curTile[0] = blankPos[0]+neighbors[blck][0];
        curTile[1] = blankPos[1]+neighbors[blck][1];
        if(curTile[0] > WIDTH-1 || curTile[1] > HEIGHT-1 || curTile[0] < 0 || curTile[1] < 0) continue;

        if(fullGrid[curTile[0]][curTile[1]] == 0 && knownGrid[curTile[0]][curTile[1]] == 0)
        {
            knownGrid[curTile[0]][curTile[1]] = 1;
            ExpandGrid(fullGrid, knownGrid, curTile);
        }
        else if(fullGrid[curTile[0]][curTile[1]] > 0) knownGrid[curTile[0]][curTile[1]] = 1;
    }
}

int main(int argc, char *argv[])
{

    COORD characterBufferSize = { WIDTH, HEIGHT };
    COORD characterPosition = { 0, 0 };
    SMALL_RECT consoleWriteArea = { 0, 0, WIDTH - 1, HEIGHT - 1 };
    CHAR_INFO consoleBuffer[WIDTH][HEIGHT];
    HANDLE wHnd = GetStdHandle(-11);

    int startGrid[WIDTH][HEIGHT] = { 0 };
    int knownGrid[WIDTH][HEIGHT] = { 0 };
    int arrowPos[2] = {0, 0};
    int bomb[2] = {0};
    struct xorshift_state seed = {argc == 2 ? (int) argv[1] : 1};

    for (int i = 0; i < BOMBS; i++)
    {
        while (startGrid[bomb[0]][bomb[1]] < -1 || bomb[0] <= 0 || bomb[1] <= 0 || bomb[0] >= WIDTH-1 || bomb[1] >= HEIGHT-1)
        {
            bomb[0] = (xorshift(&seed) % WIDTH-1) + 1;
            bomb[1] = (xorshift(&seed) % HEIGHT-1) + 1;
        }

        startGrid[bomb[0]][bomb[1]] = -9;

        startGrid[bomb[0] + 1][bomb[1] + 1]++;
        startGrid[bomb[0] + 1][bomb[1]]++;
        startGrid[bomb[0]][bomb[1] + 1]++;
        startGrid[bomb[0] - 1][bomb[1] + 1]++;
        startGrid[bomb[0]][bomb[1] - 1]++;
        startGrid[bomb[0] + 1][bomb[1] - 1]++;
        startGrid[bomb[0] - 1][bomb[1] - 1]++;
        startGrid[bomb[0] - 1][bomb[1]]++;
    }


    while(1)
    {
        if (arrowPos[0] > WIDTH-1) arrowPos[0] = WIDTH-1;
        if (arrowPos[0] < 0) arrowPos[0] = 0;
        if (arrowPos[1] > HEIGHT-1) arrowPos[1] = HEIGHT-1;
        if (arrowPos[1] < 0) arrowPos[1] = 0;

        for (int x = 0; x < WIDTH; ++x)
        {
            for (int y = 0; y < HEIGHT; ++y)
            {

                if (knownGrid[x][y] == 1)
                {
                    if (startGrid[x][y] > 0)
                    {
                        consoleBuffer[x][y].Char.AsciiChar = '0' + startGrid[x][y];
                        consoleBuffer[x][y].Attributes = 10;
                    }
                    else
                    {
                        consoleBuffer[x][y].Char.AsciiChar = 'o';
                        consoleBuffer[x][y].Attributes = startGrid[x][y] < 0 ? 4 : 17;
                    }
                }
                else
                {
                    consoleBuffer[x][y].Char.AsciiChar = 00;
                    consoleBuffer[x][y].Attributes = 0;
                }

                if(arrowPos[0] == x && arrowPos[1] == y)
                {
                    consoleBuffer[x][y].Attributes = 112;
                }
            }
        }

        WriteConsoleOutputA(wHnd, *consoleBuffer, characterBufferSize, characterPosition, &consoleWriteArea);

        switch(getch())
        {
            case 72:
                arrowPos[0]--;
                break;
            case 80:
                arrowPos[0]++;
                break;
            case 75:
                arrowPos[1]--;
                break;
            case 77:
                arrowPos[1]++;
                break;
            case '\r':
                ExpandGrid(startGrid, knownGrid, arrowPos);
                break;
        }
    }
}
TryingMyBest
  • 63
  • 10
  • 1
    Can you use the user to make a seed? You could ask the user to type a few characters and then measure the timing of typing. – Yunnosch Aug 23 '20 at 18:56
  • I could, but I think getting the input would require the use of standard library functions as well. – TryingMyBest Aug 23 '20 at 19:00
  • I'm a little confused - is there an operating system under your game? And if so, how is this 3k limit coming to eist? Just curious, as if the game requires an entire operating system to run, saying the executable itself is under 3k seems a bit misleading, doesn't it? – erik258 Aug 23 '20 at 19:02
  • 1
    How is it a game if you don't have any user input? – klutt Aug 23 '20 at 19:03
  • 3
    Just by including the header, such as `stdint.h`, you aren't increasing the size of compiled binary (unless you call any function, declared in the header, of course) – qrdl Aug 23 '20 at 19:05
  • In an interactive game with frequent user input, I would read `clock()` after every input and dial that into the RNG algorithm. Or if you have non-blocking input, increment a counter instead. You can also dial in screen coordinates, the score, anything that changes which can't be easily predicted. – Weather Vane Aug 23 '20 at 19:13
  • The executable would be that of minesweeper, and I'm getting input via `getch`. But that by itself is already another external function I have to use, so I wouldn't want to have to use another to get a string of text. And lumping together character retrieved one-by-one with getch seems redundant. And the reason i need the game to be under 3KB is so that i can fit it into a qr code. – TryingMyBest Aug 23 '20 at 19:42
  • If you are using Windows(?) `getch()` then you also have `kbhit()` which you can monitor before calling `getch()` while incrementing a counter. – Weather Vane Aug 23 '20 at 20:04
  • Are you 1) dinamically linknig, 2) statically linking, or 3) don't know the difference between the two? This is very important to answer your question. Also, which compilation flags are you using, and what is the size of your current program? Add all this info in your question please. – Marco Bonelli Aug 23 '20 at 20:40
  • got it @MarcoBonelli . Also, i am using windows in case you needed to know. =) – TryingMyBest Aug 23 '20 at 20:59

2 Answers2

3

It depends a lot on your requirement on the random generator. If you just want it so that the game will be a bit different every time you play it and not be perfectly deterministic, then just about any random generator will do. Just look online and you'll find examples of primitive random generators.

Among the simplest (but still reasonably good) is this:

int seed = 123456789;

int rand()
{
  seed = (a * seed + c) % m;
  return seed;
}

Note that you need good values for a, c and m. It is explained further here where I found it: https://stackoverflow.com/a/3062783/6699433

When it comes to the seed, there are some options. If possible, you could send the seed as an argument to the program. You could use user input and measure timing.

Also, remember that the size of the executable does not (or at least not in general) get bigger because you're including headers if you're not using them. Especially not if you have activated optimizations.

klutt
  • 30,332
  • 17
  • 55
  • 95
  • So, I tried your version, but for some reason the values were very big and uncontrolled, most likely because I set the wrong numbers. But, you gave me an idea by mentioning how I could take in arguments from command line, so I tried the Wikipedia version like that except with normal ints instead of uint32_t, and it worked!!!! So is this technically the answer I should accept? – TryingMyBest Aug 23 '20 at 21:01
  • @TryingMyBest Well, the answer helped, end there are no other answers to choose :) – klutt Aug 24 '20 at 05:27
0

You could use an argument to the executable, and hash argv[1] as seed. That way people can play the same problem over and over and against each other. For instance "Andromeda" or "London". :)

stderr
  • 143
  • 5