commit 87575446101b1e1a876db71da920575c839f8db6
parent dae1556fb2bddc878d24ad9be766e83a0a4fcea8
Author: amin <dev@aminmesbah.com>
Date: Sun, 14 May 2017 07:32:43 +0000
Store stars in quadtree. Update cells internally.
Before this commit, the quadtree was only used as a visualization. The
update logic didn't take advantage of it. This commit utilizes the
quadtree to enable the simulation of ~2000 bodies rather than 100.
The quality of the simulation has regressed because stars are only
attracted to other stars in the same cell. Once they are also attracted
to 'virtual' stars (representing the center of mass of each other cell),
performance will go down a bit, but accuracy should go back up.
It should be noted that the quadtree root node is based around the
window size. It will need to be changed so that it always encompasses
the full simulation space, since stars outside the tree experience no
gravitational attraction.
FossilOrigin-Name: 796f105b3c6f085270e0444d22fd0705ddac97ef3461718e915bdc7a59aefe58
Diffstat:
| M | barnes_hut.h | | | 117 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---- |
| M | main.c | | | 34 | ++++++++++++++++++---------------- |
2 files changed, 130 insertions(+), 21 deletions(-)
diff --git a/barnes_hut.h b/barnes_hut.h
@@ -5,15 +5,21 @@
#ifndef BARNES_HUT_H
#define BARNES_HUT_H
-#define MAX_STARS_PER_CELL 1
+// TODO: Remove this.
+#include "star.h"
+
+#define MAX_STARS_PER_CELL 10
// TODO: Limit tree depth
struct Cell
{
+ int num_stars;
float center_x;
float center_y;
float distance_x;
float distance_y;
+ // TODO: Make this a void*.
+ struct Star *stars[MAX_STARS_PER_CELL];
};
struct QuadTreeNode
@@ -40,6 +46,11 @@ struct Cell *cell_init(float center_x, float center_y, float distance_x, float d
cell->center_y = center_y;
cell->distance_x = distance_x;
cell->distance_y = distance_y;
+ cell->num_stars = 0;
+ for (int i = 0; i < MAX_STARS_PER_CELL; ++i)
+ {
+ cell->stars[i] = NULL;
+ }
}
return cell;
}
@@ -54,15 +65,37 @@ void cell_free(struct Cell *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_insert_star(struct Cell *c, struct Star *s)
+{
+ bool star_inserted = false;
+ if (c)
+ {
+ if (c->num_stars < MAX_STARS_PER_CELL)
+ {
+ c->stars[c->num_stars] = s;
+ c->num_stars += 1;
+ star_inserted = true;
+ }
+ }
+ return star_inserted;
+}
+
+
int cell_count_stars_contained(struct Cell *c, struct Star stars[], int num_stars)
{
int count = 0;
for (int i = 0; i < num_stars; ++i)
{
- if (stars[i].x <= c->center_x + c->distance_x
- && stars[i].x >= c->center_x - c->distance_x
- && stars[i].y <= c->center_y + c->distance_y
- && stars[i].y >= c->center_y - c->distance_y)
+ if (cell_contains_star(c, &(stars[i])))
{
count++;
}
@@ -100,6 +133,53 @@ void quad_tree_node_free(struct QuadTreeNode *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_insert_star(struct QuadTreeNode *node, struct Star *star)
+{
+ if (node && cell_contains_star(node->cell, star))
+ {
+ bool inserted = cell_insert_star(node->cell, star);
+ if (!inserted)
+ {
+ if (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);
+
+ for (int i = 0; i < node->cell->num_stars; ++i)
+ {
+ quad_tree_node_insert_star(node->ne, node->cell->stars[i]);
+ quad_tree_node_insert_star(node->nw, node->cell->stars[i]);
+ quad_tree_node_insert_star(node->sw, node->cell->stars[i]);
+ quad_tree_node_insert_star(node->se, node->cell->stars[i]);
+ node->cell->stars[i] = NULL;
+ }
+ }
+
+ 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);
+ }
+ }
+}
+
+
+// TODO: Get rid of this
void quad_tree_node_subdivide(struct QuadTreeNode *node, struct Star stars[], int num_stars)
{
if (node && cell_count_stars_contained(node->cell, stars, num_stars) > MAX_STARS_PER_CELL)
@@ -141,4 +221,31 @@ void quad_tree_free(struct QuadTree *qt)
}
+void quad_tree_stars_attract(struct QuadTreeNode *node)
+{
+ if (!node)
+ {
+ return;
+ }
+ if (!quad_tree_node_is_leaf(node))
+ {
+ quad_tree_stars_attract(node->ne);
+ quad_tree_stars_attract(node->nw);
+ quad_tree_stars_attract(node->sw);
+ quad_tree_stars_attract(node->se);
+ }
+ else
+ {
+ for (int i = 0; i < node->cell->num_stars; ++i)
+ {
+ for (int j = i + 1; j < node->cell->num_stars; ++j)
+ {
+ star_attract(node->cell->stars[i], node->cell->stars[j]);
+
+ }
+ }
+ }
+}
+
+
#endif
diff --git a/main.c b/main.c
@@ -20,14 +20,14 @@
#endif
//#define TRAILS
-//#define FULLSCREEN
+#define FULLSCREEN
bool SHOW_GRID = false;
#define TITLE "Stars"
#define SCREEN_WIDTH 640
#define SCREEN_HEIGHT 480
#define BYTES_PER_PIXEL 4
-#define NUM_STARS 100
+#define NUM_STARS 2000
#define DRAG 1
#define SECOND 1000.0f
@@ -209,28 +209,30 @@ void clear_screen(struct SDLOffscreenBuffer *buffer, uint32_t pixel_value)
void update(struct Star stars[], int num_stars, struct QuadTree *qt)
{
+ // TODO: either limit the bounds of the simulation, or base these values on
+ // the smallest bounding rectangle
+ int center_x = global_back_buffer.width / 2;
+ int center_y = global_back_buffer.height / 2;
+ int dist_x = global_back_buffer.width / 2;
+ int dist_y = global_back_buffer.height / 2;
+
+ quad_tree_node_free(qt->root);
+ qt->root = quad_tree_node_init(center_x, center_y, dist_x, dist_y);
+ for (int i = 0; i < num_stars; ++i)
+ {
+ quad_tree_node_insert_star(qt->root, &(stars[i]));
+ }
+
+ quad_tree_stars_attract(qt->root);
+
for (int i = 0; i < num_stars; ++i)
{
- for (int j = i + 1; j < num_stars; ++j)
- {
- star_attract(&stars[i], &stars[j]);
- }
stars[i].x += sinf(stars[i].angle) * stars[i].speed;
stars[i].y -= cosf(stars[i].angle) * stars[i].speed;
- //printf("%d: (%f, %f)\n", i, stars[i].x, stars[i].y);
-
stars[i].speed *= DRAG;
- //printf("%f, %f\n", stars[i].x, stars[i].y);
}
- int center_x = global_back_buffer.width / 2;
- int center_y = global_back_buffer.height / 2;
- int dist_x = global_back_buffer.width / 2;
- int dist_y = global_back_buffer.height / 2;
- quad_tree_node_free(qt->root);
- qt->root = quad_tree_node_init(center_x, center_y, dist_x, dist_y);
- quad_tree_node_subdivide(qt->root, stars, num_stars);
}
