nickhayashi
/
flOw
1
0
Fork 0
Code Issues Pull Requests Projects Releases Wiki Activity
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
2 Commits
1 Branch
0 Tags
216 KiB
 
 
Branch: master
Branches Tags
${ item.name }
Create tag ${ searchTerm }
Create branch ${ searchTerm }
from 'master'
${ noResults }
flOw/main.cpp

564 lines
21 KiB
Raw Permalink Blame History

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