+#include <math.h>
+
#include "random.h"
#include "planet.h"
#include "utils.h"
+struct quadtree_ops planet_ops;
+
+static int draw_lines = 0;
+
static void putpixel(struct SDL_Surface *screen, const int x, const int y,
const unsigned char r, const unsigned char g,
const unsigned char b)
buf[offset] = r;
}
-void init_planet(const SDL_Surface *screen, struct planet *p)
+static void draw_line(SDL_Surface *screen, const struct vector *p1,
+ const struct vector *p2,
+ const unsigned char r, const unsigned char g,
+ const unsigned char b, const struct camera *cam)
+{
+ struct vector dir, v;
+ float len;
+ int i;
+
+ vector_sub(p2, p1, &dir);
+
+ len = vector_abs(&dir);
+ vector_scale(&dir, 1 / len, &dir);
+ len *= cam->zoom;
+
+ vector_sub(p1, &cam->pos, &v);
+ vector_scale(&v, cam->zoom, &v);
+
+ v.x += screen->w / 2;
+ v.y += screen->h / 2;
+
+ for (i = 0; i < len ; i++) {
+ if (v.x >= 0 && v.x < screen->w &&
+ v.y >= 0 && v.y < screen->h)
+ putpixel(screen, v.x, v.y, r, g, b);
+ vector_add(&v, &dir, &v);
+ }
+}
+
+static void reshape_planet(struct planet *p)
{
- p->speed.x = 0;
- p->speed.y = 0;
- p->pos.x = get_random() % screen->w;
- p->pos.y = get_random() % screen->h;
- p->mass = get_random() % 1000 + 100;
- p->size = p->mass / 100;
+ p->radius = pow(p->mass / 100, 1 / 3.0);
+}
+
+void init_planet(struct planet *p)
+{
+ memset(p, 0, sizeof(*p));
+ reshape_planet(p);
p->r = get_random() % 256;
p->g = get_random() % 256;
p->b = get_random() % 256;
+
+ INIT_LIST_HEAD(&p->list);
+ init_quadtree(&p->tree);
}
-void draw_planet(SDL_Surface *screen, struct planet *p)
+/**
+ * setup_planet - set the planet on a "solarsystem"
+ * @p: pointer to struct planet to set up
+ * @mass: mass of the planet to set up
+ * @total_mass: total mass of the system
+ * @radius: maximum radius of the system
+ */
+
+static void setup_planet(struct planet *p, double mass, double total_mass,
+ double radius)
{
- int size = p->size / 2;
- int x, x_start, y, x_end, y_end;
+ double angle = M_PI * 2 * get_random_double();
+ double velocity;
+ double distance;
- x_start = MAX(p->pos.x - size, 0);
- y = MAX(p->pos.y - size, 0);
+ distance = radius * pow(get_random_double(), 2);
+ velocity = sqrt(total_mass / radius);
- x_end = MIN(p->pos.x + size, screen->w);
- y_end = MIN(p->pos.y + size, screen->h);
+ velocity *= pow(distance / radius, 0.2);
- for (; y < y_end; y++)
- for (x = x_start; x < x_end; x++)
- putpixel(screen, x, y, p->r, p->g, p->b);
+ p->tree.pos.x = cos(angle) * distance;
+ p->tree.pos.y = sin(angle) * distance;
+
+ p->speed.x = -sin(angle) * velocity;
+ p->speed.y = cos(angle) * velocity;
+
+ p->mass = mass;
+
+ reshape_planet(p);
}
-void gravitize_planets(struct planet *a, struct planet *b, const double time)
+void create_planets(struct planet *p, int num, double total_mass, double radius)
+{
+ int i;
+ double sum = 0;
+ struct planet *new_planet;
+
+ setup_planet(p,
+ total_mass / num * 2 * get_random_double(),
+ total_mass,
+ radius);
+
+ for (i = 0; i < num; i++) {
+ new_planet = malloc(sizeof(*new_planet));
+ init_planet(new_planet);
+
+ list_add(&new_planet->list, &p->list);
+
+ setup_planet(new_planet,
+ total_mass / num * 2 * get_random_double(),
+ total_mass,
+ radius);
+
+ quadtree_add(&p->tree, &new_planet->tree, &planet_ops);
+
+ sum += new_planet->mass;
+ }
+}
+
+void draw_circle(SDL_Surface *screen, const struct vector *pos,
+ const double radius,
+ char r, char g, char b, int transparent)
+{
+ int x, x_start, y, x_end;
+ float r2 = radius * radius;
+
+ y = MAX(pos->y - radius, 0);
+
+ if (radius * 2 <= 1) {
+ if (pos->x >= 0 && pos->x < screen->w &&
+ pos->y >= 0 && pos->y < screen->h)
+ putpixel(screen, (int)pos->x, (int)pos->y,
+ r, g, b);
+ return;
+ }
+
+ for (; y < MIN(pos->y + radius, screen->h); y++) {
+ int offset;
+ unsigned char *buf = screen->pixels;
+ float y2 = (y - pos->y);
+
+ y2 = sqrt(r2 - y2 * y2);
+ x_start = pos->x - y2;
+ x_end = pos->x + y2;
+ x_start = MAX(0, x_start);
+ x_end = MIN(x_end, screen->w);
+
+ offset = y * screen->pitch + x_start * 4;
+ if (transparent) {
+ for (x = x_start; x < x_end; x++) {
+ buf[offset++] += b;
+ buf[offset++] += g;
+ buf[offset++] += r;
+ offset++;
+ }
+ } else {
+ for (x = x_start; x < x_end; x++) {
+ buf[offset++] = b;
+ buf[offset++] = g;
+ buf[offset++] = r;
+ offset++;
+ }
+ }
+ }
+}
+
+void draw_planet(SDL_Surface *screen, struct planet *p,
+ const struct camera *cam)
+{
+ struct vector pos;
+ float radius = p->radius * cam->zoom;
+ int i;
+
+ vector_sub(&p->tree.pos, &cam->pos, &pos);
+ vector_scale(&pos, cam->zoom, &pos);
+ pos.x += screen->w / 2;
+ pos.y += screen->h / 2;
+
+ if (draw_lines) {
+ for (i = 0; i < 4; i++) {
+ if (!p->tree.child[i])
+ continue;
+
+ struct planet *q = tree_to_planet(p->tree.child[i]);
+
+ draw_line(screen, &p->tree.pos, &q->tree.pos,
+ p->r, p->g, p->b, cam);
+ }
+ }
+
+ draw_circle(screen, &pos, radius, p->r, p->g, p->b, 0);
+}
+
+int gravitize_planets(struct planet *a, struct planet *b, const double time)
{
struct vector distance, sum;
double dist, f, acc;
- vector_sub(&a->pos, &b->pos, &distance);
+ vector_sub(&a->tree.pos, &b->tree.pos, &distance);
dist = vector_abs(&distance);
+
+ /* Return true in case of a collision */
+ if (dist < (a->radius + b->radius))
+ return 1;
+
vector_div(&distance, dist, &distance);
- f = a->mass * b->mass / (dist * dist + 5) * time;
+ f = a->mass * b->mass / (dist * dist) * time;
acc = f / b->mass;
vector_scale(&distance, acc, &sum);
acc = f / a->mass;
vector_scale(&distance, acc, &sum);
vector_sub(&a->speed, &sum, &a->speed);
+
+ return 0;
+}
+
+/*
+ * Merge planets a and b into planet a
+ *
+ * It is left for the caller to deal with the scrap planet b
+ */
+static struct planet *_merge_planets(struct planet *a, struct planet *b)
+{
+ struct quadtree *parent = &a->tree;
+ struct vector pa, pb, p;
+ float mass;
+
+ vector_scale(&a->speed, a->mass, &pa);
+ vector_scale(&b->speed, b->mass, &pb);
+ vector_add(&pa, &pb, &p);
+ mass = a->mass + b->mass;
+
+ if (a->mass < b->mass)
+ parent = quadtree_move(&a->tree, b->tree.pos, &planet_ops);
+
+ a->r = (a->r * a->mass + b->r * b->mass) / mass;
+ a->g = (a->g * a->mass + b->g * b->mass) / mass;
+ a->b = (a->b * a->mass + b->b * b->mass) / mass;
+
+ a->mass = mass;
+ reshape_planet(a);
+ vector_div(&p, a->mass, &a->speed);
+
+ return tree_to_planet(quadtree_find_parent(parent));
+}
+
+/*
+ * Merge planets a and b into a the new planet a, which pointer is
+ * returned to the caller. Planet b is removed from the linked list
+ * and it's memory is freed. The merged planet will retain in the
+ * list.
+ */
+struct planet *merge_planets(struct planet *a, struct planet *b)
+{
+ struct quadtree *p;
+ _merge_planets(a, b);
+
+ list_del(&b->list);
+ p = quadtree_del(&b->tree, &planet_ops);
+
+ free(b);
+ return tree_to_planet(p);
}
-void move_planet(struct planet *p, const double time)
+struct planet *move_planet(struct planet *p, const double time)
{
- struct vector tmp;
+ struct vector tmp, new_pos;
+
vector_scale(&p->speed, time, &tmp);
- vector_add(&p->pos, &tmp, &p->pos);
+ vector_add(&p->tree.pos, &tmp, &new_pos);
+
+ return tree_to_planet(quadtree_move(&p->tree, new_pos, &planet_ops));
}
void print_planet(const struct planet *p)
{
- printf("pos: (%f.%f), speed: (%f.%f), mass: %f\n",
- p->pos.x, p->pos.y, p->speed.x, p->speed.y, p->mass);
+ printf("pos: (%f,%f), speed: (%f,%f), mass: %f, radius %f\n",
+ p->tree.pos.x, p->tree.pos.y, p->speed.x, p->speed.y, p->mass, p->radius);
+}
+
+int planet_search_rectangular(struct quadtree *node,
+ struct quadtree_iterator *itr)
+{
+ struct planet_search_iterator *it = qt_itr_to_planet_itr(itr);
+ struct planet *p = tree_to_planet(node);
+ int direction = 0, i;
+ int up = 0, left = 0, right = 0, down = 0;
+
+ for (i = 0; i < 2; i++) {
+ if (it->limit[i].x < p->tree.pos.x)
+ left = 1;
+ else
+ right = 1;
+ if (it->limit[i].y < p->tree.pos.y)
+ up = 1;
+ else
+ down = 1;
+ }
+
+ if (left && up)
+ direction |= QUADTREE_UPLEFT;
+ if (right && up)
+ direction |= QUADTREE_UPRIGHT;
+ if (left && down)
+ direction |= QUADTREE_DOWNLEFT;
+ if (right && down)
+ direction |= QUADTREE_DOWNRIGHT;
+ if (direction == (QUADTREE_UPLEFT | QUADTREE_UPRIGHT |
+ QUADTREE_DOWNLEFT | QUADTREE_DOWNRIGHT))
+ direction |= QUADTREE_SELF;
+
+ return direction;
+}
+
+void planet_draw_iterator(struct quadtree *node, struct quadtree_iterator *it)
+{
+ struct planet *p = tree_to_planet(node);
+ struct planet_search_iterator *i = qt_itr_to_planet_itr(it);
+
+ draw_planet(i->screen, p, i->cam);
+}
+
+static void planet_recalculate_stats(struct quadtree *node)
+{
+ struct planet *p = tree_to_planet(node), *c;
+ struct vector vect;
+ double dist;
+ int i;
+
+ p->tree_area = 0;
+ p->tree_mass = p->mass;
+
+ for (i = 0; i < 4; i++) {
+ if (!node->child[i])
+ continue;
+
+ c = tree_to_planet(node->child[i]);
+ p->tree_mass += c->tree_mass;
+
+ vector_sub(&p->tree.pos, &c->tree.pos, &vect);
+ dist = vector_abs(&vect);
+ dist += c->tree_area;
+ p->tree_area = MAX(p->tree_area, dist);
+ }
}
+
+struct quadtree_ops planet_ops = {
+ .recalculate_stats = planet_recalculate_stats,
+};
+