srand() 和 rand() 的 C 替换

Question

我正在努力使 C 语言的游戏适合 3KB 的限制，为此我想删除所有标准库引用。我想在我的程序中唯一 header 是 windows.h，到目前为止我做得很好。

我仅有的外部参考是 rand()、srand()、time() 和 getch() 中的每一个调用。这对于 3KB 以下的游戏来说似乎很多，但是 time、rand 和 srand 函数只是为了在游戏开始时可以有一个随机种子。

rand 获取数字，srand 设置种子，time 获取随机种子。因此，如果我能找到一种方法来摆脱过多的随机生成过程，我就可以摆脱 3/4 std 库函数。虽然我不太确定如何处理 getch，但稍后我会专注于此。

有人推荐了xorshifts，但好像需要uint32_t类型，属于stdint.h。我也尝试使用整数代替，虽然生成的数字是随机的，但它是随机的，因为返回的数字是随机的，但你可以依赖它每次都给你那个随机数。我可以给它时间作为一种种子，但是 id 仍然必须使用时间函数。有没有我忽略的东西，或者我应该使用不同的方法？

编辑：根据要求，我的编译标志是 -ffunction-sections、-fdata-sections、-s 和 -Os。我唯一的链接器标志是 -Wl,--gc-sections，我不确定什么是动态链接库和静态链接库，但我有一个不错的主意。我的代码是 12KB，如果我使用 UPX，我可以将它降低到 7KB。我的代码在这里：

#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;
        }
    }
}

Answer 1

这在很大程度上取决于您对随机生成器的要求。如果您只是想要它，以便每次玩游戏时游戏都会有所不同并且不是完全确定的，那么几乎任何随机生成器都可以。只要在线查看，您就会找到原始随机生成器的示例。

最简单（但仍然相当不错）的是：

int seed = 123456789;

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

请注意，a、c 和 m 需要良好的值。在我找到它的地方进一步解释：https://whosebug.com/a/3062783/6699433

说到种子，有一些选择。如果可能，您可以将种子作为参数发送给程序。您可以使用用户输入和测量时间。

此外，请记住，可执行文件的大小不会（或至少通常不会）变大，因为如果您不使用它们，则包含 headers。尤其是如果您激活了优化。

Answer 2

您可以对可执行文件使用一个参数，并将 argv[1] 作为种子散列。这样人们就可以一遍又一遍地解决同一个问题并相互对抗。例如“仙女座”或“伦敦”。 :)

srand() 和 rand() 的 C 替换

C Replacements for srand() and rand()

c

random

function

shared-libraries