7 struct quadtree_ops planet_ops;
9 static int draw_lines = 0;
11 static void putpixel(struct SDL_Surface *screen, const int x, const int y,
12 const unsigned char r, const unsigned char g,
13 const unsigned char b)
15 int offset = y * screen->pitch + x * 4;
16 unsigned char *buf = screen->pixels;
23 static void draw_line(SDL_Surface *screen, const struct vector *p1,
24 const struct vector *p2,
25 const unsigned char r, const unsigned char g,
26 const unsigned char b, const struct camera *cam)
32 vector_sub(p2, p1, &dir);
34 len = vector_abs(&dir);
35 vector_scale(&dir, 1 / len, &dir);
38 vector_sub(p1, &cam->pos, &v);
39 vector_scale(&v, cam->zoom, &v);
44 for (i = 0; i < len ; i++) {
45 if (v.x >= 0 && v.x < screen->w &&
46 v.y >= 0 && v.y < screen->h)
47 putpixel(screen, v.x, v.y, r, g, b);
48 vector_add(&v, &dir, &v);
52 static void reshape_planet(struct planet *p)
54 p->radius = pow(p->mass / 100, 1 / 3.0);
57 void init_planet(struct planet *p)
59 memset(p, 0, sizeof(*p));
61 p->r = get_random() % 256;
62 p->g = get_random() % 256;
63 p->b = get_random() % 256;
65 INIT_LIST_HEAD(&p->list);
66 init_quadtree(&p->tree);
70 * setup_planet - set the planet on a "solarsystem"
71 * @p: pointer to struct planet to set up
72 * @mass: mass of the planet to set up
73 * @total_mass: total mass of the system
74 * @radius: maximum radius of the system
77 static void setup_planet(struct planet *p, double mass, double total_mass,
80 double angle = M_PI * 2 * get_random_double();
84 distance = radius * pow(get_random_double(), 2);
85 velocity = sqrt(total_mass / radius);
87 velocity *= pow(distance / radius, 0.2);
89 p->tree.pos.x = cos(angle) * distance;
90 p->tree.pos.y = sin(angle) * distance;
92 p->speed.x = -sin(angle) * velocity;
93 p->speed.y = cos(angle) * velocity;
100 void create_planets(struct planet *p, int num, double total_mass, double radius)
104 struct planet *new_planet;
107 total_mass / num * 2 * get_random_double(),
111 for (i = 0; i < num; i++) {
112 new_planet = malloc(sizeof(*new_planet));
113 init_planet(new_planet);
115 list_add(&new_planet->list, &p->list);
117 setup_planet(new_planet,
118 total_mass / num * 2 * get_random_double(),
122 quadtree_add(&p->tree, &new_planet->tree, &planet_ops);
124 sum += new_planet->mass;
128 void draw_circle(SDL_Surface *screen, const struct vector *pos,
130 char r, char g, char b, int transparent)
132 int x, x_start, y, x_end;
133 float r2 = radius * radius;
135 y = MAX(pos->y - radius, 0);
137 if (radius * 2 <= 1) {
138 if (pos->x >= 0 && pos->x < screen->w &&
139 pos->y >= 0 && pos->y < screen->h)
140 putpixel(screen, (int)pos->x, (int)pos->y,
145 for (; y < MIN(pos->y + radius, screen->h); y++) {
147 unsigned char *buf = screen->pixels;
148 float y2 = (y - pos->y);
150 y2 = sqrt(r2 - y2 * y2);
151 x_start = pos->x - y2;
153 x_start = MAX(0, x_start);
154 x_end = MIN(x_end, screen->w);
156 offset = y * screen->pitch + x_start * 4;
158 for (x = x_start; x < x_end; x++) {
165 for (x = x_start; x < x_end; x++) {
175 void draw_planet(SDL_Surface *screen, struct planet *p,
176 const struct camera *cam)
179 float radius = p->radius * cam->zoom;
182 vector_sub(&p->tree.pos, &cam->pos, &pos);
183 vector_scale(&pos, cam->zoom, &pos);
184 pos.x += screen->w / 2;
185 pos.y += screen->h / 2;
188 for (i = 0; i < 4; i++) {
189 if (!p->tree.child[i])
192 struct planet *q = tree_to_planet(p->tree.child[i]);
194 draw_line(screen, &p->tree.pos, &q->tree.pos,
195 p->r, p->g, p->b, cam);
199 draw_circle(screen, &pos, radius, p->r, p->g, p->b, 0);
202 int gravitize_planets(struct planet *a, struct planet *b, const double time)
204 struct vector distance, sum;
207 vector_sub(&a->tree.pos, &b->tree.pos, &distance);
209 dist = vector_abs(&distance);
211 /* Return true in case of a collision */
212 if (dist < (a->radius + b->radius))
215 vector_div(&distance, dist, &distance);
217 f = a->mass * b->mass / (dist * dist) * time;
220 vector_scale(&distance, acc, &sum);
221 vector_add(&b->speed, &sum, &b->speed);
224 vector_scale(&distance, acc, &sum);
225 vector_sub(&a->speed, &sum, &a->speed);
231 * Merge planets a and b into planet a
233 * It is left for the caller to deal with the scrap planet b
235 static struct planet *_merge_planets(struct planet *a, struct planet *b)
237 struct quadtree *parent = &a->tree;
238 struct vector pa, pb, p;
241 vector_scale(&a->speed, a->mass, &pa);
242 vector_scale(&b->speed, b->mass, &pb);
243 vector_add(&pa, &pb, &p);
244 mass = a->mass + b->mass;
246 if (a->mass < b->mass)
247 parent = quadtree_move(&a->tree, b->tree.pos, &planet_ops);
249 a->r = (a->r * a->mass + b->r * b->mass) / mass;
250 a->g = (a->g * a->mass + b->g * b->mass) / mass;
251 a->b = (a->b * a->mass + b->b * b->mass) / mass;
255 vector_div(&p, a->mass, &a->speed);
257 return tree_to_planet(quadtree_find_parent(parent));
261 * Merge planets a and b into a the new planet a, which pointer is
262 * returned to the caller. Planet b is removed from the linked list
263 * and it's memory is freed. The merged planet will retain in the
266 struct planet *merge_planets(struct planet *a, struct planet *b)
269 _merge_planets(a, b);
272 p = quadtree_del(&b->tree, &planet_ops);
275 return tree_to_planet(p);
278 struct planet *move_planet(struct planet *p, const double time)
280 struct vector tmp, new_pos;
282 vector_scale(&p->speed, time, &tmp);
283 vector_add(&p->tree.pos, &tmp, &new_pos);
285 return tree_to_planet(quadtree_move(&p->tree, new_pos, &planet_ops));
288 void print_planet(const struct planet *p)
290 printf("pos: (%f,%f), speed: (%f,%f), mass: %f, radius %f\n",
291 p->tree.pos.x, p->tree.pos.y, p->speed.x, p->speed.y, p->mass, p->radius);
294 int planet_search_rectangular(struct quadtree *node,
295 struct quadtree_iterator *itr)
297 struct planet_search_iterator *it = qt_itr_to_planet_itr(itr);
298 struct planet *p = tree_to_planet(node);
299 int direction = 0, i;
300 int up = 0, left = 0, right = 0, down = 0;
302 for (i = 0; i < 2; i++) {
303 if (it->limit[i].x < p->tree.pos.x)
307 if (it->limit[i].y < p->tree.pos.y)
314 direction |= QUADTREE_UPLEFT;
316 direction |= QUADTREE_UPRIGHT;
318 direction |= QUADTREE_DOWNLEFT;
320 direction |= QUADTREE_DOWNRIGHT;
321 if (direction == (QUADTREE_UPLEFT | QUADTREE_UPRIGHT |
322 QUADTREE_DOWNLEFT | QUADTREE_DOWNRIGHT))
323 direction |= QUADTREE_SELF;
328 void planet_draw_iterator(struct quadtree *node, struct quadtree_iterator *it)
330 struct planet *p = tree_to_planet(node);
331 struct planet_search_iterator *i = qt_itr_to_planet_itr(it);
333 draw_planet(i->screen, p, i->cam);
336 static void planet_recalculate_stats(struct quadtree *node)
338 struct planet *p = tree_to_planet(node), *c;
344 p->tree_mass = p->mass;
346 for (i = 0; i < 4; i++) {
350 c = tree_to_planet(node->child[i]);
351 p->tree_mass += c->tree_mass;
353 vector_sub(&p->tree.pos, &c->tree.pos, &vect);
354 dist = vector_abs(&vect);
355 dist += c->tree_area;
356 p->tree_area = MAX(p->tree_area, dist);
360 struct quadtree_ops planet_ops = {
361 .recalculate_stats = planet_recalculate_stats,