flOw/main.cpp

#include <stdio.h> // printf, snprintf
#include <stdint.h> // uint16_t
#include <stdlib.h> // srand, rand
#include <time.h> // time
#include <math.h> // cos, sin

#include "glad.h"
#include "glfw3.h"


/*
    you can compile this (windows only, debug version, assuming you have cl.exe available) using:

        cl.exe glad.c main.cpp /nologo /W3 /MTd /Od /Zi /RTC1 /fsanitize=address /link /out:game.exe /incremental:no glfw3.lib

        the .exe will be around 1.5mb in this case.


    or, in release version with a smaller .exe size and better perf (181kb with clang-cl, dang just barely missed 128kb total size!), no debugging symbols etc.

        clang-cl.exe glad.c main.cpp /nologo /W3 /O2 /GS /clang:-fno-asynchronous-unwind-tables /link /out:game.exe /fixed /incremental:no /opt:icf /opt:ref libvcruntime.lib glfw3.lib

        OR

        cl.exe glad.c main.cpp /nologo /W3 /O2 /GS /link /out:game.exe /fixed /incremental:no /opt:icf /opt:ref libvcruntime.lib glfw3.lib


    the first 10-20 frames in debug mode are prone to run below 60fps on my machine, which I unfortunately wasn't able to fix in 16 hours
    - my computer is fairly weak though, it's about 10 years old and has no external GPU. You may fare better :). Subsequent frames perfome
    many times better.


   - [Y] - snake-like 0 player game
   - [Y] - need to support on the order of 8k+ snakes concurrently  (we're going to choose a max of 8192)
   - [Y] - if the head of a snake touches the tail of another, the snake who's head touched the tail will merge up with the 'eaten' snake.
   - [Y] - all snakes start with one segment
   - [Y] - when there is only one snake left, the game must restart
   - [Y?] - game data under 128kb - achieved if this means game state, not quite if it means .exe size (we're about ~1mb .exe size after trying to minimize size)
   - [Y] - 60fps minimum, or locked
   - [Y] - static memory allocation, avoid heap
   - [Y] - minimal or zero usage of libraries (except glfw and opengl)
*/

static GLFWwindow *Window;

inline bool checkError__(int line) {
    GLenum errorCode;
    while ((errorCode = glGetError()) != GL_NO_ERROR) {
        switch (errorCode) {
            case GL_INVALID_ENUM:
                printf("%d, INVALID_ENUM", line);
                break;
            case GL_INVALID_VALUE:
                printf("%d, INVALID_VALUE", line);
                break;
            case GL_INVALID_OPERATION:
                printf("%d, INVALID_OPERATION", line);
                break;
            case GL_OUT_OF_MEMORY:
                printf("%d, OUT_OF_MEMORY", line);
                break;
            case GL_INVALID_FRAMEBUFFER_OPERATION:
                printf("%d, INVALID_FRAMEBUFFER_OPERATION", line);
                break;
        }
        return true;
    }
    return false;
}
#define checkError() checkError__(__LINE__)


static const float PI = 3.14159f;

//--------------------------------------------------------------------------------
// game-data
// between QUADRANTS and pointBuffer, the only real data structures in use,
// you have 116.736kb of game state, assuming 8192 snakes.

int windowWidth;
int windowHeight;

struct Snake {
    // coordinates are normalized unsigned integers.
    // |numSegments| is just a count, where 0 indicates a dead snake.
    uint16_t numSegments, headX, headY, theta;
};
static constexpr float SNAKE_SEGMENT_RADIUS = 8; // glPointSize
static constexpr unsigned int NUM_SNAKES = 8192; // must be greater than 1

struct Rectangle {
    uint16_t left, bottom, right, top;
};
static constexpr uint32_t NUM_QUADRANTS = 64;
static constexpr unsigned int SNAKES_PER_QUADRANT = NUM_SNAKES/NUM_QUADRANTS;
struct Quadrant {
    Snake snakes[SNAKES_PER_QUADRANT];
    Rectangle rect;
};
static Quadrant QUADRANTS[NUM_QUADRANTS];

struct Point {
    uint16_t x, y;
    uint16_t weight;
};
static Point pointBuffer[NUM_SNAKES]; // each snake starts as one segment which is represented as a point, so you can have at most NUM_SNAKES points.

uint32_t numDead = 0;
uint32_t longest = 0;
uint32_t numPoints = 0;

double msPerFrame         = 0.0;
double deltaTime          = 0.0;
double lastFrameCountTime = 0.0;
double lastFrameStartTime = 0.0;
bool doFancyRestart = false;

long long int numFramesInLastSecond = 0;
long long int frameCounter          = 0;
//--------------------------------------------------------------------------------

static inline uint16_t normalizeUint(uint16_t input, uint32_t oldMax) {
    return input * USHRT_MAX / oldMax;
}

static inline float invlerp(float a, float b, float v) {
    return (v - a) / (b - a);
}
static inline float lerp(float a, float b, float t) {
    return a + t * (b - a);
}

static inline float snakeThetaToRadians(uint16_t a) {
    return ((float)a/(float)USHRT_MAX)*2.f*PI;
}
static inline uint16_t radiansToSnakeTheta(float r) {
    return (uint16_t) ((r + (0.f*PI)) / (2.f*PI) * (float)USHRT_MAX);
}

static inline void splitRectangleIntoQuadrants(Rectangle input, Rectangle quadrants[4]) {
    auto centerX = (input.left + input.right) / 2;
    auto centerY = (input.top + input.bottom) / 2;

    // top-left quadrant, proceeding clockwise
    quadrants[0].left = input.left;
    quadrants[0].right = centerX;
    quadrants[0].top = input.top;
    quadrants[0].bottom = centerY;

    quadrants[1].left = centerX;
    quadrants[1].right = input.right;
    quadrants[1].top = input.top;
    quadrants[1].bottom = centerY;

    quadrants[2].left = centerX;
    quadrants[2].right = input.right;
    quadrants[2].top = centerY;
    quadrants[2].bottom = input.bottom;

    quadrants[3].left = input.left;
    quadrants[3].right = centerX;
    quadrants[3].top = centerY;
    quadrants[3].bottom = input.bottom;
}

static inline uint16_t randInRange(unsigned int min, unsigned int max) {
    const unsigned int range = max - min + 1;
    return (uint16_t) (min + (unsigned int)((double)rand() / (RAND_MAX + 1.0) * range));
}

static inline void calculateSegment(Snake* snake, uint16_t segmentNumber, Point* outPoint) {
    const float weight = (float)segmentNumber / (float)snake->numSegments;
    const float radians = snakeThetaToRadians(snake->theta);
    const float dx = cos(radians);
    const float dy = sin(radians);

    outPoint->x      = snake->headX + dx * segmentNumber * SNAKE_SEGMENT_RADIUS;
    outPoint->y      = snake->headY + dy * segmentNumber * SNAKE_SEGMENT_RADIUS;
    outPoint->weight = (uint16_t) (weight * USHRT_MAX);
}

static inline void initializeQuadrants(int windowWidth, int windowHeight) {
    Rectangle windowQuad = { 0, 0, normalizeUint(windowWidth, windowWidth), normalizeUint(windowHeight, windowHeight) };
    Rectangle topLevelQuads[4];
    splitRectangleIntoQuadrants(windowQuad, topLevelQuads);

    // there's probably a better way to iteratively construct a quadtree...
    for (int i = 0; i < 4; i++) {
        Rectangle iquads[4];
        splitRectangleIntoQuadrants(topLevelQuads[i], iquads);

        for (int j = 0; j < 4; j++) {
            Rectangle jquads[4];
            splitRectangleIntoQuadrants(iquads[j], jquads);

            for (int k = 0; k < 4; k++) {
                QUADRANTS[i*16+j*4+k].rect = jquads[k];
            }
        }
    }

    for (int i = 0; i < NUM_QUADRANTS; i++) {
        Quadrant* q= &QUADRANTS[i];
        for (int j = 0; j < SNAKES_PER_QUADRANT; j++) {
            Snake* snake = &q->snakes[j];
            snake->numSegments = 1;
            snake->headX = randInRange(q->rect.left,   q->rect.right);
            snake->headY = randInRange(q->rect.bottom, q->rect.top);
            //printf("Snake #%d, quadrant %d - head (x/y): %u/%u, numSegments: %u\n", j+1, i, snake->headX, snake->headY, snake->numSegments);
        }
    }
}

static inline unsigned int computeQuadrant(int x, int y, int left, int top, int bottom, int right) {
    if (x < left || y < bottom || x > right || y > top) {
        printf("outside rect!\n");
        return -1;

    } else if (x < right/2 && y < top/2) {
        return 0;

    } else if (x >= right/2 && y < top/2) {
        return 1;

    } else if (x < right/2 && y >= top/2) {
        return 2;

    } else {
        return 3;
    }
}

static inline bool findNearestSnakeInQuad(
    Quadrant* quad,
    Snake* snake,
    int searchingSnakeIndex,
    float& nearestD,
    uint16_t& nearestX,
    uint16_t& nearestY,
    bool* outHadLiveSnake
) {
    for (int j = 0; j < SNAKES_PER_QUADRANT; j++) {
        if (searchingSnakeIndex == j) continue;

        Snake* other = &quad->snakes[j];
        if (other->numSegments == 0) continue; // dead snake, can't bite it

        // if we have at least one snake that has a segment, that means this quad has at least one other live snake.
        if (outHadLiveSnake) *outHadLiveSnake = true;

        // find tail coordinates for this snake
        Point tail;
        calculateSegment(other, other->numSegments-1, &tail);

        // compute distance, check if it's closer than previously recorded
        float dx = ((float)snake->headX - (float)tail.x);
        float dy = ((float)snake->headY - (float)tail.y);
        float distance = sqrt(dx*dx + dy*dy);
        if (distance < nearestD) {
            nearestD = distance;
            nearestX = tail.x;
            nearestY = tail.y;

            if (distance < SNAKE_SEGMENT_RADIUS*3) {
                // if we're close enough, we can call it a bite and early-out.
                snake->numSegments += other->numSegments;
                other->numSegments = 0;
                return 1;
            }
        }
    }
    return 0;
}

static inline bool updateQuadrant(unsigned int quadIndex) {
    Quadrant* quad = &QUADRANTS[quadIndex];

    for (int i = 0; i < SNAKES_PER_QUADRANT; i++) {
        // update each snake in the quad. there are only really a few things to do:
        // - find nearest neighbour to snake
        // - check if bite
        // - move and rotate snake
        bool foundAtLeastOneOtherLiveSnakeInQuad = false;
        Snake* snake = &quad->snakes[i];

        uint16_t numSegments = snake->numSegments;
        if (numSegments == 0) continue;

        if (numSegments > longest) {
            longest = numSegments; // just for fun.
        }

        // we now linear search for nearest tail to bite, early-outing on dead snakes,
        // and very-close snakes (we technically do not always garuntee finding the 'nearest')
        const uint16_t headX = snake->headX;
        const uint16_t headY = snake->headY;
        float nearestD = 999999.f; // arbitrary large-ish number
        uint16_t nearestX = 0;
        uint16_t nearestY = 0;
        if (findNearestSnakeInQuad(quad, snake, i, nearestD, nearestX, nearestY, &foundAtLeastOneOtherLiveSnakeInQuad)) {
            numDead++;
            goto nextSnake; // we killed another snake, we can move on to the next snake.
        };

        if (!foundAtLeastOneOtherLiveSnakeInQuad) {
            // we found 0 snakes in this quad (besides ourselves)
            // this circumstance can only arise when there are a small number of snakes left
            // , less than 2k at least, so we can just lazily iterate the rest of the quadrants.
            for (int j = 0; j < NUM_QUADRANTS; j++) {
                if (quadIndex == j) continue;

                if (findNearestSnakeInQuad(&QUADRANTS[j], snake, -1, nearestD, nearestX, nearestY, &foundAtLeastOneOtherLiveSnakeInQuad)) {
                    numDead++;
                    goto nextSnake; // we killed another snake, we can move on to the next snake, after appending our draw data
                }
            }
        }
        if (!foundAtLeastOneOtherLiveSnakeInQuad) {
            // we must be the only snake left!
            return true;
        }

        // do the movement and rotation for this snake.
        const float angle = atan2f((float)headY - (float)nearestY, (float)headX - (float)nearestX);
        // it probably makes more sense for the smaller guys to be faster, but the simulation gets quite slow towards the end of it, so I do the opposite.
        const float dx = -cos(angle) * 500.f*log(0.25f*snake->numSegments + 1) * deltaTime;
        const float dy = -sin(angle) * 500.f*log(0.25f*snake->numSegments + 1) * deltaTime;
        snake->headX += dx;
        snake->headY += dy;
#if 1
        // move the snake's angle towards angle |angle|, with some fixed radial speed, smoothly
        const float snakeAngle = snakeThetaToRadians(snake->theta);
        const float angleDelta = angle - snakeAngle;
        //snake->theta = radiansToSnakeTheta(snakeAngle + ((2.f*PI*angleDelta)*0.0015f/(2.f*PI));
        //snake->theta = radiansToSnakeTheta(fmin(snakeAngle + (2.f*PI*angleDelta)*(deltaTime/snake->numSegments)/(2.f*PI), angle));
        snake->theta = radiansToSnakeTheta(snakeAngle + (angleDelta+2.f*PI)*deltaTime*100.f/snake->numSegments);
#else
        snake->theta = radiansToSnakeTheta(angle);
#endif
        // at this point, we know everything we need to know about this snake to populate the draw data for it.
        // we have the head position, an angle, and a count of the number of segments, so we use this to generate
        // points from head --> tail.
        for (uint16_t p = 0; p < snake->numSegments; p++) {
            Point* point = &pointBuffer[numPoints++];
            calculateSegment(snake, p, point);
        }
nextSnake: continue;
    }

    return false;
}

int main(void) {
    glfwInit();
    glfwWindowHint(GLFW_CONTEXT_VERSION_MAJOR, 3);
    glfwWindowHint(GLFW_CONTEXT_VERSION_MINOR, 3);
    glfwWindowHint(GLFW_OPENGL_PROFILE, GLFW_OPENGL_CORE_PROFILE);
    glfwWindowHint(GLFW_VISIBLE, false); // hide window initially - while we set up stuff. show after.
    glfwWindowHint(GLFW_RESIZABLE, false); // don't allow the user to re-size the window
    glfwWindowHint(GLFW_CENTER_CURSOR, true); // center the cursor in the window when opening a fullscreen window
    glfwWindowHint(GLFW_FOCUS_ON_SHOW, true); // focus the window when glfwShowWindow is called

    #ifdef __APPLE__
    // removes all deprecated opengl functionality from older opengl versions, required on MacOSX
    glfwWindowHint(GLFW_OPENGL_FORWARD_COMPAT, GL_TRUE); 
    #endif

    GLFWmonitor* primaryMonitor = glfwGetPrimaryMonitor();
    const GLFWvidmode* primaryMonitorMode = glfwGetVideoMode(primaryMonitor);
    float initialWidth = 1138.0f;
    float initialHeight = 640.0f;
    // scale up the dimensions of the initial size of the window until it exceeds the size of the screen, then go with the one just before that
    while (1) {
        if ((initialHeight * 1.2f > primaryMonitorMode->height) || (initialWidth * 1.2f) > primaryMonitorMode->width) {
            break;
        }
        initialHeight *= 1.2f;
        initialWidth *= 1.2f;
    }
    windowWidth  = (int) initialWidth;
    windowHeight = (int) initialHeight;

    Window = glfwCreateWindow(windowWidth, windowHeight, "flOw MMo", nullptr, nullptr);
    if (Window == nullptr) {
        printf("%s", "Failed to initialize GLFWwindow\n");
        return 1;
    }

    glfwMakeContextCurrent(Window);

    //-------------------------------------------------------------------------------- 
    // initialize glad, resolve OpenGL function pointers
    if (!gladLoadGLLoader((GLADloadproc) glfwGetProcAddress)) {
        printf("%s", "Failed to initialize GLAD\n");
        return 1;
    }

    //-------------------------------------------------------------------------------- 
    // compile and link our shader.
    // my apologies if this fails compilation on your machine.
    // My main computer's OpenGL driver has been known to allow compilations where others fail it.
    int success;
    char infoLog[512];
    // vertex...
    const char* vertexShaderCode = R"(
        #version 330 core
        layout (location = 0) in vec2 aPos;
        layout (location = 1) in float aWeight;

        flat out float vWeight;

        void main() {
            vWeight = aWeight;
            gl_Position = vec4(aPos*2.0-1.0, 0.0, 1.0);
            gl_PointSize = 10 + (1.0f - aWeight)*10;
        }
    )";
    unsigned int vertexShaderId = glCreateShader(GL_VERTEX_SHADER);
    glShaderSource(vertexShaderId, 1, &vertexShaderCode, nullptr);
    glCompileShader(vertexShaderId);
    glGetShaderiv(vertexShaderId, GL_COMPILE_STATUS, &success);
    if (!success) {
        glGetShaderInfoLog(vertexShaderId, 512, nullptr, infoLog);
        printf("Failure compiling vertex shader!\n%s\nSource: %s\n", infoLog, vertexShaderCode);
        return 1;
    }

    // fragment...
    const char* fragmentShaderCode = R"(
        #version 330 core

        flat in float vWeight;

        out vec4 FragColor;

        void main() {
            FragColor = vec4(vWeight + 0.5, 0.5f * vWeight, 0.2f / (vWeight+0.01), 1.0f);
        }
    )";
    unsigned int fragmentShaderId = glCreateShader(GL_FRAGMENT_SHADER);
    glShaderSource(fragmentShaderId, 1, &fragmentShaderCode, nullptr);
    glCompileShader(fragmentShaderId);
    glGetShaderiv(fragmentShaderId, GL_COMPILE_STATUS, &success);
    if (!success) {
        glGetShaderInfoLog(fragmentShaderId, 512, nullptr, infoLog);
        printf("Failure compiling fragment shader!\n%s\nSource: %s\n", infoLog, fragmentShaderCode);
        return 1;
    }

    unsigned int shaderId = glCreateProgram();
    glAttachShader(shaderId, vertexShaderId);
    glAttachShader(shaderId, fragmentShaderId);
    glLinkProgram(shaderId);
    glGetProgramiv(shaderId, GL_LINK_STATUS, &success);
    if (!success) {
        glGetProgramInfoLog(shaderId, 512, nullptr, infoLog);
        printf("Failure linking shader!\n%s\n", infoLog);
        return 1;
    }
    checkError();

    // use it, we only have one shader
    glUseProgram(shaderId);
    checkError();

    //-------------------------------------------------------------------------------- 
    srand(time(nullptr));
    for (int i = 0; i < rand(); i++) rand(); // discard first few calls, randomly. 'rand()' has poor entropy

    // initialize the game state. set up all the initial snake positions, etc.
    initializeQuadrants(windowWidth, windowHeight);

    //-------------------------------------------------------------------------------- 
    // setup the VAO/VBO
    unsigned int VAO, VBO;
    glGenVertexArrays(1, &VAO);
    glBindVertexArray(VAO);
    glGenBuffers(1, &VBO);
    glBindBuffer(GL_ARRAY_BUFFER, VBO);
    glEnableVertexAttribArray(0);
    glVertexAttribPointer(0, 2, GL_UNSIGNED_SHORT, GL_TRUE, sizeof(Point), (void*)offsetof(Point, x));
    glEnableVertexAttribArray(1);
    glVertexAttribPointer(1, 1, GL_UNSIGNED_SHORT, GL_TRUE, sizeof(Point), (void*)offsetof(Point, weight));

    //-------------------------------------------------------------------------------- 
    // set global opengl state
    glClearColor(0.25f, 0.52f, 0.54f, 1.0f);
    glEnable(GL_PROGRAM_POINT_SIZE);
    glEnable(GL_DEPTH_TEST);
    glDepthFunc(GL_LESS);
    glEnable(GL_CULL_FACE);

    glfwShowWindow(Window); // make window visible before entering main loop
    glfwRequestWindowAttention(Window);

    while (!glfwWindowShouldClose(Window)) {
        glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

        // calculate timing metrics, delta time, etc.
        double currentTime = glfwGetTime();
        frameCounter++;
        if (currentTime - lastFrameCountTime >= 1.0) {
            msPerFrame = 1000.0/frameCounter;
            numFramesInLastSecond = frameCounter;
            frameCounter = 0;
            lastFrameCountTime += 1.0;

            static char windowTitle[256];
            snprintf(windowTitle, 256, "flOw MMo - %.2f ms per frame, %lld fps, delta %.2f, num snakes: %u, num alive: %u, dead: %u, longest boi: %u", msPerFrame, numFramesInLastSecond, deltaTime, NUM_SNAKES, NUM_SNAKES-numDead, numDead, longest);
            glfwSetWindowTitle(Window, windowTitle); // <-- this call is very slow :(
        }
        deltaTime = currentTime - lastFrameStartTime;
        lastFrameStartTime = currentTime;

        // set ourselves to close if you press escape
        if (glfwGetKey(Window, GLFW_KEY_ESCAPE) == GLFW_PRESS) {
            glfwSetWindowShouldClose(Window, true);
            continue;
        }

        static double lastUpdateTime = 0.0f;
        if ((currentTime - lastUpdateTime) < 0.0167f) {
            continue; // we already updated in the last 16ms, skip to next frame
        }

        if (doFancyRestart) {
            initializeQuadrants(windowWidth, windowHeight);
            doFancyRestart = false;

        } else {
            // update game state:
            bool gameOver = false;
            for (int q = 0; q < NUM_QUADRANTS; q++) {
                gameOver = updateQuadrant(q);
                if (gameOver) break;
            }
            if (gameOver) {
                printf("game over!\n");
                doFancyRestart = true;
                continue;
            }
        }

        // upload draw data and render
        glBufferData(GL_ARRAY_BUFFER, sizeof(Point)*NUM_SNAKES, nullptr, GL_DYNAMIC_DRAW);
        glBufferData(GL_ARRAY_BUFFER, sizeof(Point)*NUM_SNAKES, pointBuffer, GL_DYNAMIC_DRAW);
        glDrawArrays(GL_POINTS, 0, numPoints);
        numPoints = 0;
        checkError();

        glfwSwapBuffers(Window);
        glfwPollEvents(); // performs better on windows at the end of frame vs. start
    }

    glDeleteShader(vertexShaderId);
    glDeleteShader(fragmentShaderId);
    glDeleteProgram(shaderId);

    glfwTerminate();

    return 0;
}