evolution

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)