commit 9028e9f980cdf1c0905bcaf55b9a04c60aaa7c23
parent 74fff9c29c4e292f18d2231ecc38257426e108e1
Author: amin <dev@aminmesbah.com>
Date: Mon, 15 May 2017 07:39:16 +0000
Add a 'virtual star' for each cell.
There is now an array of special 'virtual' stars. Virtual stars can be
seen by toggling their visibility with the 'V' key. Every update, a
virtual star is created to represent the center of mass of all the stars
in each cell. The stars of each cell are then attracted to the virtual
stars of every other cell.
The whole point of this is to reduce the number of times star_attract()
needs to be called, while upholding a certain level of accuracy in the
simulation. More work needs to be done, as this currently isn't much
more efficient than the previous brute-force method. The accuracy also
leaves much to be desired.
There is also the problem that, when stars fly off the edge of the
screen, they are no longer attracted to other stars (because they aren't
in any cell of the quadtree). The root node's cell should be big enough
to enclose the two most distant stars in the simulation.
Finally, it's probably about time to clean up and organize the code so
it's easier to work with.
FossilOrigin-Name: c6fad5f33a34892500a355c2fcbff92b7ad54757ebba96cc7ca4780c7e3010f0
Diffstat:
| M | barnes_hut.h | | | 61 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++----- |
| M | main.c | | | 23 | +++++++++++++++++++++-- |
2 files changed, 77 insertions(+), 7 deletions(-)
diff --git a/barnes_hut.h b/barnes_hut.h
@@ -221,18 +221,62 @@ void quad_tree_free(struct QuadTree *qt)
}
-void quad_tree_stars_attract(struct QuadTreeNode *node)
+void quad_tree_set_virtual_stars(struct QuadTreeNode *node, struct Star virtual_stars[], int *current_num, int max_virtual_stars)
{
if (!node)
{
return;
}
+
+ if (!quad_tree_node_is_leaf(node))
+ {
+ quad_tree_set_virtual_stars(node->ne, virtual_stars, current_num, max_virtual_stars);
+ quad_tree_set_virtual_stars(node->nw, virtual_stars, current_num, max_virtual_stars);
+ quad_tree_set_virtual_stars(node->sw, virtual_stars, current_num, max_virtual_stars);
+ quad_tree_set_virtual_stars(node->se, virtual_stars, current_num, max_virtual_stars);
+ }
+ else if (*current_num < max_virtual_stars)
+ {
+ // TODO: handle mass more intelligently
+ float x_sum = 0;
+ float y_sum = 0;
+ float mass_sum = 0;
+
+ for (int i = 0; i < node->cell->num_stars; ++i)
+ {
+ x_sum += node->cell->stars[i]->x;
+ y_sum += node->cell->stars[i]->y;
+ mass_sum += node->cell->stars[i]->mass;
+ }
+
+ float x_avg = x_sum / node->cell->num_stars;
+ float y_avg = y_sum / node->cell->num_stars;
+
+ virtual_stars[*current_num].x = x_avg;
+ virtual_stars[*current_num].y = y_avg;
+ virtual_stars[*current_num].mass = mass_sum;
+ (*current_num)++;
+ }
+ else
+ {
+ printf("Virtual_stars buffer overflow.\n");
+ }
+}
+
+
+void quad_tree_stars_attract(struct QuadTreeNode *node, struct Star virtual_stars[], int num_virtual_stars)
+{
+ 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);
+ quad_tree_stars_attract(node->ne, virtual_stars, num_virtual_stars);
+ quad_tree_stars_attract(node->nw, virtual_stars, num_virtual_stars);
+ quad_tree_stars_attract(node->sw, virtual_stars, num_virtual_stars);
+ quad_tree_stars_attract(node->se, virtual_stars, num_virtual_stars);
}
else
{
@@ -243,6 +287,13 @@ void quad_tree_stars_attract(struct QuadTreeNode *node)
star_attract(node->cell->stars[i], node->cell->stars[j]);
}
+ for (int k = 0; k < num_virtual_stars; ++k)
+ {
+ if (!cell_contains_star(node->cell, &virtual_stars[k]))
+ {
+ star_attract(node->cell->stars[i], &virtual_stars[k]);
+ }
+ }
}
}
}
diff --git a/main.c b/main.c
@@ -22,12 +22,13 @@
#define FULLSCREEN
bool RENDER_GRID = false;
bool RENDER_TRAILS = false;
+bool RENDER_VIRTUAL_STARS = false;
#define TITLE "Stars"
#define SCREEN_WIDTH 640
#define SCREEN_HEIGHT 480
#define BYTES_PER_PIXEL 4
-#define NUM_STARS 2000
+#define NUM_STARS 200
#define DRAG 1
#define SECOND 1000.0f
@@ -80,6 +81,8 @@ struct SDLWindowDimension
static struct SDLOffscreenBuffer global_back_buffer;
+static struct Star virtual_stars[NUM_STARS];
+static int num_virtual_stars = 0;
struct SDLWindowDimension sdl_get_window_dimension(SDL_Window *window)
@@ -164,6 +167,10 @@ bool handle_event(SDL_Event *event)
RENDER_TRAILS = !RENDER_TRAILS;
clear_screen(&global_back_buffer, COLOR_BACKGROUND);
}
+ if (key_code == SDLK_v)
+ {
+ RENDER_VIRTUAL_STARS = !RENDER_VIRTUAL_STARS;
+ }
}
} break;
case SDL_WINDOWEVENT:
@@ -228,7 +235,11 @@ void update(struct Star stars[], int num_stars, struct QuadTree *qt)
quad_tree_node_insert_star(qt->root, &(stars[i]));
}
- quad_tree_stars_attract(qt->root);
+ num_virtual_stars = 0;
+ quad_tree_set_virtual_stars(qt->root, virtual_stars, &num_virtual_stars, NUM_STARS);
+ printf("num_virtual_stars: %d\n", num_virtual_stars);
+
+ quad_tree_stars_attract(qt->root, virtual_stars, num_virtual_stars);
for (int i = 0; i < num_stars; ++i)
{
@@ -277,6 +288,14 @@ void render(struct SDLOffscreenBuffer *buffer, float dt, struct Star stars[], in
stars[i].color);
}
+ if (RENDER_VIRTUAL_STARS)
+ {
+ for (int i = 0; i < num_virtual_stars; ++i)
+ {
+ set_pixel(buffer, virtual_stars[i].x, virtual_stars[i].y, COLOR_MAGENTA);
+ }
+ }
+
if (RENDER_GRID)
{
draw_grid(buffer, qt->root, COLOR_GREEN);
