From 442bb01af8b9cbf88189a4d2368548f41149413f Mon Sep 17 00:00:00 2001 From: Leo Tenenbaum Date: Sat, 12 Dec 2020 20:38:04 -0500 Subject: evolution --- main.cpp | 1 + math.cpp | 14 ++++++ platforms.cpp | 146 ++++++++++++++++++++++++++++++++++++++++++++++++++++++---- setup.cpp | 56 ++++++++++++++++++++-- sim.cpp | 97 +++++++++++++++++++++++++++++--------- sim.hpp | 6 ++- 6 files changed, 283 insertions(+), 37 deletions(-) diff --git a/main.cpp b/main.cpp index 08cbfd7..7d0c9ab 100644 --- a/main.cpp +++ b/main.cpp @@ -229,6 +229,7 @@ int main(void) { SDL_GL_SetSwapInterval(1); // vsync frame.memory_size = (size_t)16 << 20; + frame.memory_size = (size_t)250L << 20; // @TODO @TEMPORARY #if DEBUG { diff --git a/math.cpp b/math.cpp index 534438a..0050d7a 100644 --- a/math.cpp +++ b/math.cpp @@ -82,6 +82,12 @@ static float randf(void) { return (float)rand() / (float)((ulong)RAND_MAX + 1); } +static float rand_gauss(void) { + // https://en.wikipedia.org/wiki/Normal_distribution#Generating_values_from_normal_distribution + float U = randf(), V = randf(); + return sqrtf(-2 * logf(U)) * cosf(TAUf * V); +} + static u32 rand_u32(void) { return ((u32)rand() & 0xfff) | ((u32)rand() & 0xfff) << 12 @@ -694,5 +700,13 @@ static void gl_quad(float x1, float y1, float x2, float y2) { glVertex2f(x2, y2); glVertex2f(x1, y2); } + +static float rects_intersect(Rect r1, Rect r2) { + if (r1.pos.x >= r2.pos.x + r2.size.x) return false; // r1 is to the right of r2 + if (r2.pos.x >= r1.pos.x + r1.size.x) return false; // r2 is to the right of r1 + if (r1.pos.y >= r2.pos.y + r2.size.y) return false; // r1 is above r2 + if (r2.pos.y >= r1.pos.y + r1.size.y) return false; // r2 is above r1 + return true; +} #endif diff --git a/platforms.cpp b/platforms.cpp index 8658aae..843672a 100644 --- a/platforms.cpp +++ b/platforms.cpp @@ -1,5 +1,5 @@ -#define PLATFORM_RADIUS_MIN 0.2f -#define PLATFORM_RADIUS_MAX 5.0f +#define PLATFORM_RADIUS_MIN 0.5f +#define PLATFORM_RADIUS_MAX 2.0f #define PLATFORM_MOVE_SPEED_MIN 0.1f #define PLATFORM_MOVE_SPEED_MAX 5.0f #define PLATFORM_ROTATE_SPEED_MIN -3.0f @@ -10,26 +10,58 @@ #define PLATFORM_MOVE_SPEED_COST 1.0f #define PLATFORM_ROTATE_SPEED_COST 1.0f -// how far right could any part of this platform possibly go? -static float platform_rightmost_x(Platform const *platform) { +// some horrible code to figure out the rightmost x coordinate or the topmost y coordinate a platform can reach +static float platform_highest_coordinate(Platform const *platform, bool y) { float angle; if (platform->rotates) - angle = 0; // for rotating platforms, the maximum x coordinate is achieved when the platform has an angle of 0 + angle = y ? HALF_PIf : 0; else - angle = platform->angle; - float x_past_center = platform->radius * fabsf(cosf(angle)); // width of platform to the right of the center + angle = platform->start_angle; + float past_center = platform->radius * fabsf((y ? sinf : cosf)(angle)); // width/height of platform to the right of the center v2 center; if (platform->moves) { v2 p1 = platform->move_p1, p2 = platform->move_p2; // pick the point with the higher x coordinate - if (p1.x > p2.x) + if ((y ? p1.y : p1.x) > (y ? p2.y : p2.x)) center = p1; else center = p2; } else { center = platform->center; } - return center.x + x_past_center; + return (y ? center.y : center.x) + past_center; +} + +static float platform_lowest_coordinate(Platform const *platform, bool y) { + float angle; + if (platform->rotates) + angle = y ? HALF_PIf : 0; + else + angle = platform->start_angle; + float before_center = platform->radius * -fabsf((y ? sinf : cosf)(angle)); + v2 center; + if (platform->moves) { + v2 p1 = platform->move_p1, p2 = platform->move_p2; + if ((y ? p1.y : p1.x) < (y ? p2.y : p2.x)) + center = p1; + else + center = p2; + } else { + center = platform->center; + } + return (y ? center.y : center.x) + before_center; +} + +static Rect platform_bounding_box(Platform const *platform) { + float x1 = platform_lowest_coordinate(platform, false); + float y1 = platform_lowest_coordinate(platform, true); + float x2 = platform_highest_coordinate(platform, false); + float y2 = platform_highest_coordinate(platform, true); + return rect4(x1, y1, x2, y2); +} + +static float platform_rightmost_x(Platform const *platform) { + return platform_highest_coordinate(platform, false); } // where the ball's distance traveled should be measured from @@ -294,3 +326,99 @@ static void platform_read_from_file(Platform *p, FILE *fp) { p->rotate_speed = fread_float(fp); } } + +static v2 setup_rand_point(void); + +#define PLATFORM_MOVE_CHANCE 0.5f // chance that the platform will be a moving one +#define PLATFORM_ROTATE_CHANCE 0.5f // chance that the platform will be a rotating one (platforms can be moving and rotating) + +static void platform_random(Platform *platform) { + platform->color = rand_u32() | 0xFF; + platform->radius = rand_uniform(PLATFORM_RADIUS_MIN, PLATFORM_RADIUS_MAX); + platform->center = setup_rand_point(); + platform->start_angle = rand_uniform(0, PIf); + + if (randf() < PLATFORM_MOVE_CHANCE) { + platform->moves = true; + platform->move_speed = rand_uniform(PLATFORM_MOVE_SPEED_MIN, PLATFORM_MOVE_SPEED_MAX); + platform->move_p1 = platform->center; + platform->move_p2 = v2_add(platform->move_p1, v2_scale(v2_rand_unit(), 2 * rand_gauss())); + } + + if (randf() < PLATFORM_ROTATE_CHANCE) { + platform->rotates = true; + platform->rotate_speed = rand_uniform(0.1f, PLATFORM_ROTATE_SPEED_MAX); + if (rand() % 2) + platform->rotate_speed = -platform->rotate_speed; // clockwise + } +} + +static void mutate_position(v2 *p) { + if (randf() < 0.2f) + *p = setup_rand_point(); // randomize completely + else + *p = v2_add(*p, v2_scale(V2(rand_gauss(), rand_gauss()), 0.1f)); +} + +static void platform_mutate(State *state, Setup *setup, Platform *platform) { + Platform original = *platform; + int i; + int max_attempts = 100; + for (i = 0; i < max_attempts; ++i) { // make at most max_attempts attempts to mutate the platform + *platform = original; + + if (randf() < 0.2f) { + // completely randomize platform + platform_random(platform); + } else { + // partially randomize platform +#define FEATURE_MUTATE_RATE 0.3f + if (randf() < FEATURE_MUTATE_RATE) { + platform->start_angle += 0.3f * rand_gauss(); // mutate angle + platform->start_angle = fmodf(platform->start_angle, TAUf); + } + if (platform->moves) { + if (randf() < FEATURE_MUTATE_RATE) { + platform->move_speed += 0.1f * rand_gauss(); // mutate move speed + platform->move_speed = clampf(platform->move_speed, PLATFORM_MOVE_SPEED_MIN, PLATFORM_MOVE_SPEED_MAX); + } + if (randf() < FEATURE_MUTATE_RATE) + mutate_position(&platform->move_p1); // mutate p1 + if (randf() < FEATURE_MUTATE_RATE) + mutate_position(&platform->move_p2); // mutate p2 + } else if (randf() < FEATURE_MUTATE_RATE) { + // mutate position + mutate_position(&platform->center); + } + if (platform->rotates) { + if (randf() < FEATURE_MUTATE_RATE) { + // mutate rotate speed + platform->rotate_speed += 0.3f * rand_gauss(); + platform->rotate_speed = clampf(platform->rotate_speed, PLATFORM_ROTATE_SPEED_MIN, PLATFORM_ROTATE_SPEED_MAX); + } + } + if (randf() < FEATURE_MUTATE_RATE) { + // mutate radius + platform->radius += 0.1f * rand_gauss(); + platform->radius = clampf(platform->radius, PLATFORM_RADIUS_MIN, PLATFORM_RADIUS_MAX); + } + } + + Rect bbox = platform_bounding_box(platform); + bool intersects_any = false; + for (Platform *platform2 = setup->platforms, *end = platform2 + setup->nplatforms; + platform2 != end; ++platform2) { + if (platform != platform2) { + if (rects_intersect(bbox, platform_bounding_box(platform2))) { + intersects_any = true; + break; + } + } + } + if (!intersects_any && bbox.pos.x > state->left_x) break; // doesn't intersect anything; we're good. + } + if (i == max_attempts) { + // we tried so many times but we couldn't mutate the platform ): + *platform = original; // give up on mutation + } +} diff --git a/setup.cpp b/setup.cpp index 378076f..c6bc2dd 100644 --- a/setup.cpp +++ b/setup.cpp @@ -2,7 +2,7 @@ #define SETUP_MIN_X 1.0f #define SETUP_MAX_X 10.0f #define SETUP_MIN_Y 1.0f -#define SETUP_MAX_Y 10.0f +#define SETUP_MAX_Y 15.0f static v2 setup_rand_point(void) { return V2( @@ -10,9 +10,7 @@ static v2 setup_rand_point(void) { rand_uniform(SETUP_MIN_Y, SETUP_MAX_Y) ); } - -#define PLATFORM_MOVE_CHANCE 0.5f // chance that the platform will be a moving one -#define PLATFORM_ROTATE_CHANCE 0.5f // chance that the platform will be a rotating one (platforms can be moving and rotating) +#if 0 static void setup_random(Setup *setup, float cost_allowed) { // how much "money" we have to spend float cost_left = cost_allowed; @@ -57,6 +55,38 @@ static void setup_random(Setup *setup, float cost_allowed) { } assert(cost_left >= 0); } +#endif + +static void setup_random(State *state, Setup *setup) { + u32 i, j, t; + u32 const max_failed_attempts = 100; + Platform *platforms = setup->platforms; + for (i = 0; i < MAX_PLATFORMS; ++i) { + for (t = 0; t < max_failed_attempts; ++t) { + Platform *platform = &platforms[i]; + memset(platform, 0, sizeof *platform); + platform_random(platform); + Rect bbox = platform_bounding_box(platform); + for (j = 0; j < i; ++j) { + Rect bbox_other = platform_bounding_box(&platforms[j]); + if (rects_intersect(bbox, bbox_other)) { + break; + } + } + if (bbox.pos.x > state->left_x // ensure that platform is to the right of left wall + && j == i) { + // we successfully placed a platform! + break; + } + } + if (t == max_failed_attempts) { + // if we failed enough attempts to make a non-intersecting platform, give up + break; + } + } + + setup->nplatforms = i; +} // make this setup the active one static void setup_use(State *state, Setup *setup) { @@ -172,3 +202,21 @@ static bool setup_read_from_file(Setup *setup, char const *filename) { } } +// meant for use with qsort, to sort by descending score +static int setup_compare_scores(void const *a_void, void const *b_void) { + Setup const *a = (Setup const *)a_void, *b = (Setup const *)b_void; + if (a->score > b->score) { + return -1; + } else if (a->score < b->score) { + return +1; + } + return 0; +} + +static void setup_mutate(State *state, Setup *setup, float mutation_rate) { + for (Platform *platform = setup->platforms, *end = platform + setup->nplatforms; + platform != end; ++platform) { + if (randf() < mutation_rate) + platform_mutate(state, setup, platform); + } +} diff --git a/sim.cpp b/sim.cpp index f16d7cd..0b9d9ac 100644 --- a/sim.cpp +++ b/sim.cpp @@ -170,13 +170,18 @@ void sim_frame(Frame *frame) { frame->close = true; return; } - State *state = (State *)frame->memory; - Ball *ball = &state->ball; i32 width = frame->width, height = frame->height; Input *input = &frame->input; - GL *gl = &state->gl; maybe_unused u8 *keys_pressed = input->keys_pressed; maybe_unused bool *keys_down = input->keys_down; + State *state = (State *)frame->memory; +#if DEBUG + if (state->magic_number != MAGIC_NUMBER || keys_pressed[KEY_F5]) { + memset(state, 0, sizeof *state); + } +#endif + Ball *ball = &state->ball; + GL *gl = &state->gl; state->ctrl = input->keys_down[KEY_LCTRL] || input->keys_down[KEY_RCTRL]; state->shift = input->keys_down[KEY_LSHIFT] || input->keys_down[KEY_RSHIFT]; @@ -194,6 +199,7 @@ void sim_frame(Frame *frame) { state->aspect_ratio = state->win_width / state->win_height; state->dt = (float)frame->dt; + if (width == 0 || height == 0) return; // set up GL glEnable(GL_BLEND); @@ -204,11 +210,6 @@ void sim_frame(Frame *frame) { glClearColor(0, 0, 0, 1); glClear(GL_COLOR_BUFFER_BIT); -#if DEBUG - if (state->magic_number != MAGIC_NUMBER || keys_pressed[KEY_F5]) { - memset(state, 0, sizeof *state); - } -#endif if (!state->initialized) { logln("Initializing..."); @@ -281,35 +282,68 @@ void sim_frame(Frame *frame) { left_wall_shape.SetAsBox(0.5f, 1000); left_wall_body->CreateFixture(&left_wall_shape, 0); - - #if 1 + for (size_t i = 0; i < arr_count(state->setups); ++i) { + // randomize initial setups + Setup *setup = &state->setups[i]; + setup_random(state, setup); + setup_score(state, setup); + } + + qsort(state->setups, arr_count(state->setups), sizeof(Setup), setup_compare_scores); + + for (size_t i = 0; i < TOP_KEPT; ++i) { + printf("%zu. %f\n", i, state->setups[i].score); + } + + for (int g = 0; g < 100; ++g) { + printf("---Generation %d---\n",g); + for (size_t i = 0; i < GENERATION_SIZE; ++i) { + // create new generation from TOP_KEPT + Setup *setup = &state->setups[i + TOP_KEPT]; + *setup = state->setups[rand() % TOP_KEPT]; // select one of the top setups to mutate from + setup->mutated = true; + switch (i / 20) { + case 0: setup_mutate(state, setup, 0.05f); break; // 5% mutation rate group + case 1: setup_mutate(state, setup, 0.10f); break; // 10% mutation rate group + case 2: setup_mutate(state, setup, 0.20f); break; // 20% mutation rate group + case 3: setup_mutate(state, setup, 0.30f); break; // 30% mutation rate group + case 4: memset(setup, 0, sizeof *setup); setup_random(state, setup); break; // completely random group + } + setup_score(state, setup); + } + + qsort(state->setups, arr_count(state->setups), sizeof(Setup), setup_compare_scores); + + for (size_t i = 0; i < TOP_KEPT; ++i) { + Setup *setup = &state->setups[i]; + char filename[64] = {0}; + snprintf(filename, sizeof filename - 1, "setups/%03zu.b2s", i); + printf("%zu. %f%s\n", i, setup->score, setup->mutated ? " (mutated)" : ""); + setup_write_to_file(setup, filename); + } + + setup_use(state, &state->setups[0]); + } + + #if 0 Setup *best_setup = &state->generation[0]; for (size_t i = 0; i < GENERATION_SIZE; ++i) { Setup *setup = &state->generation[i]; - setup_random(setup, 50); + setup_random(state, setup); char filename[64] = {0}; snprintf(filename, sizeof filename-1, "setups/%03zu.b2s", i); setup_write_to_file(setup, filename); setup_score(state, setup); - logln("Setup %zu: %.2f m", i, setup->score); + printf("Setup %zu: %.2f m\n", i, setup->score); if (setup->score > best_setup->score) { best_setup = setup; } } - logln("Best: setup %ld", (long)(best_setup - state->generation)); + printf("Best: setup %ld\n", (long)(best_setup - state->generation)); setup_use(state, best_setup); assert(state->nplatforms == best_setup->nplatforms); #endif - #if 0 - Setup *setup = &state->generation[0]; - //setup_random(state, setup, 50); - //setup_write_to_file(setup, "setups/test.b2s"); - setup_read_from_file(setup, "setups/test.b2s"); - setup_use(state, setup); - #endif - - { Platform *b = &state->platform_building; b->radius = 1.5f; @@ -488,6 +522,7 @@ void sim_frame(Frame *frame) { if (mouse_platform) { // edit platform *platform_building = *mouse_platform; + platform_building->body = NULL; platform_delete(state, mouse_platform); platform_building->color = (platform_building->color & 0xFFFFFF00) | 0x7F; } else { @@ -522,6 +557,22 @@ void sim_frame(Frame *frame) { if (state->building) { // turn platform under mouse blue if (mouse_platform) mouse_platform->color = 0x007FFFFF; + + #if 0 + glMatrixMode(GL_MODELVIEW); + glLoadIdentity(); + glMultMatrixf(state->transform.e); + + glBegin(GL_QUADS); + glColor4f(1, 1, 1, 0.5f); + rect_render(platform_bounding_box(&state->platform_building)); + for (u32 i = 0; i < state->nplatforms; ++i) { + rect_render(platform_bounding_box(&state->platforms[i])); + } + glEnd(); + glMatrixMode(GL_MODELVIEW); + glLoadIdentity(); + #endif } platforms_render(state, state->platforms, state->nplatforms); if (state->building) { @@ -606,12 +657,14 @@ void sim_frame(Frame *frame) { } +#if 0 { // cost char text[64]; snprintf(text, sizeof text - 1, "Cost: %.1f", platforms_cost(state->platforms, state->nplatforms)); glColor3f(1, 1, 0.5f); text_render(state, font, text, V2(-0.95f, -0.95f)); } +#endif { // details in the bottom right char text[64] = {0}; diff --git a/sim.hpp b/sim.hpp index 1a93566..7de7a9a 100644 --- a/sim.hpp +++ b/sim.hpp @@ -167,6 +167,7 @@ typedef struct { #define MAX_PLATFORMS 32 typedef struct { float score; // distance this setup can throw the ball + bool mutated; u32 nplatforms; Platform platforms[MAX_PLATFORMS]; } Setup; @@ -218,8 +219,9 @@ typedef struct { u32 nplatforms; Platform platforms[MAX_PLATFORMS]; -#define GENERATION_SIZE 1000 - Setup generation[GENERATION_SIZE]; +#define GENERATION_SIZE 100 +#define TOP_KEPT 10 // keep top this many setups after every generation + Setup setups[TOP_KEPT + GENERATION_SIZE]; u32 tmp_mem_used; // this is not measured in bytes, but in MaxAligns #define TMP_MEM_BYTES (4L<<20) -- cgit v1.2.3