commit be8ddc4eafb6188774cfded32c9906c61083c320
parent f0a4ca67aeb9df3f1073781b126909123db0aa7b
Author: amin <dev@aminmesbah.com>
Date: Sun, 30 Jul 2017 00:55:08 +0000
Split star and barnes_hut into .c and .h files.
FossilOrigin-Name: bd560d085c07be0feed42baeb6ab66382ebce5466d413c737b1c26a5d82b0203
Diffstat:
| M | Makefile | | | 4 | ++-- |
| A | barnes_hut.c | | | 207 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | barnes_hut.h | | | 217 | ++++++------------------------------------------------------------------------- |
| A | star.c | | | 55 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | star.h | | | 58 | ++++++---------------------------------------------------- |
5 files changed, 284 insertions(+), 257 deletions(-)
diff --git a/Makefile b/Makefile
@@ -7,7 +7,7 @@ SDL_LDFLAGS := $(shell sdl2-config --libs)
override CFLAGS += $(SDL_CFLAGS)
-SRC = main.c
+SRC = main.c star.c barnes_hut.c
EXE = star-garden
DBGDIR = debug
@@ -23,7 +23,7 @@ RELCFLAGS = -O2 -Os
all: debug release
clean:
- rm -f $(RELEXE) $(DBGEXE)
+ rm -f $(RELDIR)/* $(DBGDIR)/*
debug: prep
$(CC) $(CFLAGS) $(DBGCFLAGS) $(SRC) -o $(DBGEXE) $(LDFLAGS)
diff --git a/barnes_hut.c b/barnes_hut.c
@@ -0,0 +1,207 @@
+#include "barnes_hut.h"
+
+
+struct Cell *cell_init(float center_x, float center_y, float distance_x, float distance_y)
+{
+ struct Cell *cell = (struct Cell *)malloc(sizeof(struct Cell));
+ if (cell)
+ {
+ cell->center_x = center_x;
+ cell->center_y = center_y;
+ cell->distance_x = distance_x;
+ cell->distance_y = distance_y;
+ cell->mass_center_x = center_x;
+ cell->mass_center_y = center_x;
+ cell->mass_total = 0;
+ cell->stars_sum_x = 0;
+ cell->stars_sum_y = 0;
+ cell->star = NULL;
+ }
+ return cell;
+}
+
+
+void cell_free(struct Cell *c)
+{
+ if (c)
+ {
+ free(c);
+ }
+}
+
+
+bool cell_contains_star(struct Cell *c, struct Star *s)
+{
+ return (s->x <= c->center_x + c->distance_x
+ && s->x >= c->center_x - c->distance_x
+ && s->y <= c->center_y + c->distance_y
+ && s->y >= c->center_y - c->distance_y);
+}
+
+
+bool cell_is_empty(struct Cell *c)
+{
+ return !(c->star);
+}
+
+
+struct QuadTreeNode *quad_tree_node_init(float center_x, float center_y, float distance_x, float distance_y)
+{
+ struct QuadTreeNode *node = (struct QuadTreeNode *)malloc(sizeof (struct QuadTreeNode));
+ if (node)
+ {
+ node->cell = cell_init(center_x, center_y, distance_x, distance_y);
+ node->ne = NULL;
+ node->nw = NULL;
+ node->sw = NULL;
+ node->se = NULL;
+ }
+ return node;
+}
+
+
+void quad_tree_node_free(struct QuadTreeNode *node)
+{
+ if (node)
+ {
+ quad_tree_node_free(node->ne);
+ quad_tree_node_free(node->nw);
+ quad_tree_node_free(node->sw);
+ quad_tree_node_free(node->se);
+ free(node->cell);
+ free(node);
+ }
+}
+
+
+bool quad_tree_node_is_leaf(struct QuadTreeNode *node)
+{
+ if (!node)
+ {
+ return false;
+ }
+ return !(node->ne && node->nw && node->sw && node->se);
+}
+
+
+void quad_tree_node_subdivide(struct QuadTreeNode *node)
+{
+ if (node && quad_tree_node_is_leaf(node))
+ {
+ float child_distance_x = node->cell->distance_x / 2;
+ float child_distance_y = node->cell->distance_y / 2;
+
+ node->ne = quad_tree_node_init(node->cell->center_x + child_distance_x, node->cell->center_y + child_distance_y, child_distance_x, child_distance_y);
+ node->nw = quad_tree_node_init(node->cell->center_x - child_distance_x, node->cell->center_y + child_distance_y, child_distance_x, child_distance_y);
+ node->sw = quad_tree_node_init(node->cell->center_x - child_distance_x, node->cell->center_y - child_distance_y, child_distance_x, child_distance_y);
+ node->se = quad_tree_node_init(node->cell->center_x + child_distance_x, node->cell->center_y - child_distance_y, child_distance_x, child_distance_y);
+ }
+}
+
+
+void quad_tree_node_insert_star(struct QuadTreeNode *node, struct Star *star)
+{
+ if (node && cell_contains_star(node->cell, star))
+ {
+ if (quad_tree_node_is_leaf(node))
+ {
+ if (cell_is_empty(node->cell))
+ {
+ node->cell->star = star;
+ }
+ else
+ {
+ quad_tree_node_subdivide(node);
+
+ quad_tree_node_insert_star(node->ne, node->cell->star);
+ quad_tree_node_insert_star(node->nw, node->cell->star);
+ quad_tree_node_insert_star(node->sw, node->cell->star);
+ quad_tree_node_insert_star(node->se, node->cell->star);
+
+ quad_tree_node_insert_star(node->ne, star);
+ quad_tree_node_insert_star(node->nw, star);
+ quad_tree_node_insert_star(node->sw, star);
+ quad_tree_node_insert_star(node->se, star);
+
+ node->cell->star = NULL;
+ }
+ }
+ else
+ {
+ node->cell->mass_total += star->mass;
+ node->cell->stars_sum_x += star->x * star->mass;
+ node->cell->stars_sum_y += star->y * star->mass;
+
+ float x_avg = node->cell->stars_sum_x / node->cell->mass_total;
+ float y_avg = node->cell->stars_sum_y / node->cell->mass_total;
+
+ node->cell->mass_center_x = x_avg;
+ node->cell->mass_center_y = y_avg;
+
+ quad_tree_node_insert_star(node->ne, star);
+ quad_tree_node_insert_star(node->nw, star);
+ quad_tree_node_insert_star(node->sw, star);
+ quad_tree_node_insert_star(node->se, star);
+ }
+ }
+}
+
+
+struct QuadTree *quad_tree_init(void)
+{
+ struct QuadTree *qt = (struct QuadTree *)malloc(sizeof (struct QuadTree));
+ if (qt)
+ {
+ qt->root = NULL;
+ }
+ return qt;
+}
+
+
+void quad_tree_free(struct QuadTree *qt)
+{
+ if (qt)
+ {
+ quad_tree_node_free(qt->root);
+ free(qt);
+ }
+}
+
+
+bool node_is_sufficiently_far(struct QuadTreeNode *node, struct Star *star)
+{
+ float s = node->cell->distance_x * 2;
+ float dx = node->cell->mass_center_x - star->x;
+ float dy = node->cell->mass_center_y - star->y;
+ float d = hypotf(dx, dy);
+
+ return s / d < THETA;
+}
+
+
+void quad_tree_calc_force_on_star(struct QuadTreeNode *node, struct Star *star)
+{
+ if (!star || !node)
+ {
+ return;
+ }
+
+ if (quad_tree_node_is_leaf(node) && !cell_is_empty(node->cell) && !cell_contains_star(node->cell, star))
+ {
+ star_attract(node->cell->star, star);
+ }
+ else if (node_is_sufficiently_far(node, star))
+ {
+ star_attract_to_mass(star,
+ node->cell->mass_total,
+ node->cell->mass_center_x,
+ node->cell->mass_center_y);
+ }
+ else
+ {
+ quad_tree_calc_force_on_star(node->ne, star);
+ quad_tree_calc_force_on_star(node->nw, star);
+ quad_tree_calc_force_on_star(node->sw, star);
+ quad_tree_calc_force_on_star(node->se, star);
+ }
+}
diff --git a/barnes_hut.h b/barnes_hut.h
@@ -5,6 +5,7 @@
#ifndef BARNES_HUT_H
#define BARNES_HUT_H
+#include <stdbool.h>
// TODO: Remove this.
#include "star.h"
@@ -43,210 +44,20 @@ struct QuadTree
};
-struct Cell *cell_init(float center_x, float center_y, float distance_x, float distance_y)
-{
- struct Cell *cell = (struct Cell *)malloc(sizeof(struct Cell));
- if (cell)
- {
- cell->center_x = center_x;
- cell->center_y = center_y;
- cell->distance_x = distance_x;
- cell->distance_y = distance_y;
- cell->mass_center_x = center_x;
- cell->mass_center_y = center_x;
- cell->mass_total = 0;
- cell->stars_sum_x = 0;
- cell->stars_sum_y = 0;
- cell->star = NULL;
- }
- return cell;
-}
-
-
-void cell_free(struct Cell *c)
-{
- if (c)
- {
- free(c);
- }
-}
-
-
-bool cell_contains_star(struct Cell *c, struct Star *s)
-{
- return (s->x <= c->center_x + c->distance_x
- && s->x >= c->center_x - c->distance_x
- && s->y <= c->center_y + c->distance_y
- && s->y >= c->center_y - c->distance_y);
-}
-
-
-bool cell_is_empty(struct Cell *c)
-{
- return !(c->star);
-}
-
-
-struct QuadTreeNode *quad_tree_node_init(float center_x, float center_y, float distance_x, float distance_y)
-{
- struct QuadTreeNode *node = (struct QuadTreeNode *)malloc(sizeof (struct QuadTreeNode));
- if (node)
- {
- node->cell = cell_init(center_x, center_y, distance_x, distance_y);
- node->ne = NULL;
- node->nw = NULL;
- node->sw = NULL;
- node->se = NULL;
- }
- return node;
-}
-
-
-void quad_tree_node_free(struct QuadTreeNode *node)
-{
- if (node)
- {
- quad_tree_node_free(node->ne);
- quad_tree_node_free(node->nw);
- quad_tree_node_free(node->sw);
- quad_tree_node_free(node->se);
- free(node->cell);
- free(node);
- }
-}
-
-
-bool quad_tree_node_is_leaf(struct QuadTreeNode *node)
-{
- if (!node)
- {
- return false;
- }
- return !(node->ne && node->nw && node->sw && node->se);
-}
-
-
-void quad_tree_node_subdivide(struct QuadTreeNode *node)
-{
- if (node && quad_tree_node_is_leaf(node))
- {
- float child_distance_x = node->cell->distance_x / 2;
- float child_distance_y = node->cell->distance_y / 2;
-
- node->ne = quad_tree_node_init(node->cell->center_x + child_distance_x, node->cell->center_y + child_distance_y, child_distance_x, child_distance_y);
- node->nw = quad_tree_node_init(node->cell->center_x - child_distance_x, node->cell->center_y + child_distance_y, child_distance_x, child_distance_y);
- node->sw = quad_tree_node_init(node->cell->center_x - child_distance_x, node->cell->center_y - child_distance_y, child_distance_x, child_distance_y);
- node->se = quad_tree_node_init(node->cell->center_x + child_distance_x, node->cell->center_y - child_distance_y, child_distance_x, child_distance_y);
- }
-}
-
-
-void quad_tree_node_insert_star(struct QuadTreeNode *node, struct Star *star)
-{
- if (node && cell_contains_star(node->cell, star))
- {
- if (quad_tree_node_is_leaf(node))
- {
- if (cell_is_empty(node->cell))
- {
- node->cell->star = star;
- }
- else
- {
- quad_tree_node_subdivide(node);
-
- quad_tree_node_insert_star(node->ne, node->cell->star);
- quad_tree_node_insert_star(node->nw, node->cell->star);
- quad_tree_node_insert_star(node->sw, node->cell->star);
- quad_tree_node_insert_star(node->se, node->cell->star);
-
- quad_tree_node_insert_star(node->ne, star);
- quad_tree_node_insert_star(node->nw, star);
- quad_tree_node_insert_star(node->sw, star);
- quad_tree_node_insert_star(node->se, star);
-
- node->cell->star = NULL;
- }
- }
- else
- {
- node->cell->mass_total += star->mass;
- node->cell->stars_sum_x += star->x * star->mass;
- node->cell->stars_sum_y += star->y * star->mass;
-
- float x_avg = node->cell->stars_sum_x / node->cell->mass_total;
- float y_avg = node->cell->stars_sum_y / node->cell->mass_total;
-
- node->cell->mass_center_x = x_avg;
- node->cell->mass_center_y = y_avg;
-
- quad_tree_node_insert_star(node->ne, star);
- quad_tree_node_insert_star(node->nw, star);
- quad_tree_node_insert_star(node->sw, star);
- quad_tree_node_insert_star(node->se, star);
- }
- }
-}
-
-
-struct QuadTree *quad_tree_init(void)
-{
- struct QuadTree *qt = (struct QuadTree *)malloc(sizeof (struct QuadTree));
- if (qt)
- {
- qt->root = NULL;
- }
- return qt;
-}
-
-
-void quad_tree_free(struct QuadTree *qt)
-{
- if (qt)
- {
- quad_tree_node_free(qt->root);
- free(qt);
- }
-}
-
-
-bool node_is_sufficiently_far(struct QuadTreeNode *node, struct Star *star)
-{
- float s = node->cell->distance_x * 2;
- float dx = node->cell->mass_center_x - star->x;
- float dy = node->cell->mass_center_y - star->y;
- float d = hypotf(dx, dy);
-
- return s / d < THETA;
-}
-
-
-void quad_tree_calc_force_on_star(struct QuadTreeNode *node, struct Star *star)
-{
- if (!star || !node)
- {
- return;
- }
+struct Cell *cell_init(float center_x, float center_y, float distance_x, float distance_y);
+void cell_free(struct Cell *c);
+bool cell_contains_star(struct Cell *c, struct Star *s);
+bool cell_is_empty(struct Cell *c);
- if (quad_tree_node_is_leaf(node) && !cell_is_empty(node->cell) && !cell_contains_star(node->cell, star))
- {
- star_attract(node->cell->star, star);
- }
- else if (node_is_sufficiently_far(node, star))
- {
- star_attract_to_mass(star,
- node->cell->mass_total,
- node->cell->mass_center_x,
- node->cell->mass_center_y);
- }
- else
- {
- quad_tree_calc_force_on_star(node->ne, star);
- quad_tree_calc_force_on_star(node->nw, star);
- quad_tree_calc_force_on_star(node->sw, star);
- quad_tree_calc_force_on_star(node->se, star);
- }
-}
+struct QuadTreeNode *quad_tree_node_init(float center_x, float center_y, float distance_x, float distance_y);
+void quad_tree_node_free(struct QuadTreeNode *node);
+bool quad_tree_node_is_leaf(struct QuadTreeNode *node);
+void quad_tree_node_subdivide(struct QuadTreeNode *node);
+void quad_tree_node_insert_star(struct QuadTreeNode *node, struct Star *star);
+struct QuadTree *quad_tree_init(void);
+void quad_tree_free(struct QuadTree *qt);
+bool node_is_sufficiently_far(struct QuadTreeNode *node, struct Star *star);
+void quad_tree_calc_force_on_star(struct QuadTreeNode *node, struct Star *star);
#endif
diff --git a/star.c b/star.c
@@ -0,0 +1,55 @@
+#include "star.h"
+
+// TODO: Test whether making this function return a struct (rather than a
+// struct pointer) makes a significant performance difference.
+struct Vec2d *vec2d_add(float angle1, float length1, float angle2, float length2)
+{
+ float x = sinf(angle1) * length1 + sinf(angle2) * length2;
+ float y = cosf(angle1) * length1 + cosf(angle2) * length2;
+
+ struct Vec2d *new_vec = (struct Vec2d*)malloc(sizeof(struct Vec2d));
+ new_vec->angle = 0.5 * M_PI - atan2f(y, x);
+ new_vec->length = hypotf(x, y);
+ return new_vec;
+}
+
+void star_accelerate(struct Star *s, float angle, float acceleration)
+{
+ struct Vec2d *new_vec = vec2d_add(s->angle, s->speed, angle, acceleration);
+ s->angle = new_vec->angle;
+ s->speed = new_vec->length;
+ free(new_vec);
+}
+
+float star_calc_size(float mass)
+{
+ return 0.5 * (powf(mass, 0.5));
+}
+
+void star_attract(struct Star *s1, struct Star *s2)
+{
+ float dx = s1->x - s2->x;
+ float dy = s1->y - s2->y;
+ float distance = hypotf(dx, dy);
+
+ if (distance > s1->size + s2->size)
+ {
+ float theta = atan2f(dy, dx);
+ float force = GRAVITATION * (s1->mass * s2->mass / powf(distance, 2));
+ star_accelerate(s1, theta - (0.5 * M_PI), force / s1->mass);
+ star_accelerate(s2, theta + (0.5 * M_PI), force / s2->mass);
+ //printf("%f\n", force);
+ }
+}
+
+void star_attract_to_mass(struct Star *star, float mass, float mass_x, float mass_y)
+{
+ float dx = star->x - mass_x;
+ float dy = star->y - mass_y;
+ float distance = hypotf(dx, dy);
+
+ float theta = atan2f(dy, dx);
+ float force = GRAVITATION * (star->mass * mass / powf(distance, 2));
+ star_accelerate(star, theta - (0.5 * M_PI), force / star->mass);
+ //printf("%f\n", force);
+}
diff --git a/star.h b/star.h
@@ -3,6 +3,7 @@
#include <math.h>
#include <stdint.h>
+#include <stdlib.h>
#ifndef M_PI
#define M_PI (3.14159265358979323846264338327950288)
@@ -27,57 +28,10 @@ struct Vec2d
float length;
};
-// TODO: Test whether making this function return a struct (rather than a
-// struct pointer) makes a significant performance difference.
-struct Vec2d *vec2d_add(float angle1, float length1, float angle2, float length2)
-{
- float x = sinf(angle1) * length1 + sinf(angle2) * length2;
- float y = cosf(angle1) * length1 + cosf(angle2) * length2;
-
- struct Vec2d *new_vec = (struct Vec2d*)malloc(sizeof(struct Vec2d));
- new_vec->angle = 0.5 * M_PI - atan2f(y, x);
- new_vec->length = hypotf(x, y);
- return new_vec;
-}
-
-void star_accelerate(struct Star *s, float angle, float acceleration)
-{
- struct Vec2d *new_vec = vec2d_add(s->angle, s->speed, angle, acceleration);
- s->angle = new_vec->angle;
- s->speed = new_vec->length;
- free(new_vec);
-}
-
-float star_calc_size(float mass)
-{
- return 0.5 * (powf(mass, 0.5));
-}
-
-void star_attract(struct Star *s1, struct Star *s2)
-{
- float dx = s1->x - s2->x;
- float dy = s1->y - s2->y;
- float distance = hypotf(dx, dy);
-
- if (distance > s1->size + s2->size)
- {
- float theta = atan2f(dy, dx);
- float force = GRAVITATION * (s1->mass * s2->mass / powf(distance, 2));
- star_accelerate(s1, theta - (0.5 * M_PI), force / s1->mass);
- star_accelerate(s2, theta + (0.5 * M_PI), force / s2->mass);
- //printf("%f\n", force);
- }
-}
-
-void star_attract_to_mass(struct Star *star, float mass, float mass_x, float mass_y)
-{
- float dx = star->x - mass_x;
- float dy = star->y - mass_y;
- float distance = hypotf(dx, dy);
+struct Vec2d *vec2d_add(float angle1, float length1, float angle2, float length2);
+void star_accelerate(struct Star *s, float angle, float acceleration);
+float star_calc_size(float mass);
+void star_attract(struct Star *s1, struct Star *s2);
+void star_attract_to_mass(struct Star *star, float mass, float mass_x, float mass_y);
- float theta = atan2f(dy, dx);
- float force = GRAVITATION * (star->mass * mass / powf(distance, 2));
- star_accelerate(star, theta - (0.5 * M_PI), force / star->mass);
- //printf("%f\n", force);
-}
#endif
