7 struct quadtree_ops planet_ops;
9 static void putpixel(struct SDL_Surface *screen, const int x, const int y,
10 const unsigned char r, const unsigned char g,
11 const unsigned char b)
13 int offset = y * screen->pitch + x * 4;
14 unsigned char *buf = screen->pixels;
21 static void reshape_planet(struct planet *p)
23 p->radius = pow(p->mass / 100, 1 / 3.0);
26 void init_planet(struct planet *p)
28 memset(p, 0, sizeof(*p));
30 p->r = get_random() % 256;
31 p->g = get_random() % 256;
32 p->b = get_random() % 256;
34 INIT_LIST_HEAD(&p->list);
35 init_quadtree(&p->tree);
39 * setup_planet - set the planet on a "solarsystem"
40 * @p: pointer to struct planet to set up
41 * @mass: mass of the planet to set up
42 * @total_mass: total mass of the system
43 * @radius: maximum radius of the system
46 static void setup_planet(struct planet *p, double mass, double total_mass,
49 double angle = M_PI * 2 * get_random_double();
53 distance = radius * pow(get_random_double(), 2);
54 velocity = sqrt(total_mass / radius);
56 velocity *= pow(distance / radius, 0.2);
58 p->pos.x = cos(angle) * distance;
59 p->pos.y = sin(angle) * distance;
61 p->speed.x = -sin(angle) * velocity;
62 p->speed.y = cos(angle) * velocity;
69 void create_planets(struct planet *p, int num, double total_mass, double radius)
73 struct planet *new_planet;
76 total_mass / num * 2 * get_random_double(),
80 for (i = 0; i < num; i++) {
81 new_planet = malloc(sizeof(*new_planet));
82 init_planet(new_planet);
84 list_add(&new_planet->list, &p->list);
86 setup_planet(new_planet,
87 total_mass / num * 2 * get_random_double(),
91 quadtree_add(&p->tree, &new_planet->tree, &planet_ops);
93 sum += new_planet->mass;
97 void draw_planet(SDL_Surface *screen, struct planet *p,
98 const struct camera *cam)
101 float radius = p->radius * cam->zoom;
102 float r2 = radius * radius;
103 int x, x_start, y, x_end;
105 vector_sub(&p->pos, &cam->pos, &pos);
106 vector_scale(&pos, cam->zoom, &pos);
107 pos.x += screen->w / 2;
108 pos.y += screen->h / 2;
110 y = MAX(pos.y - radius, 0);
112 if (radius * 2 <= 1) {
113 if (pos.x >= 0 && pos.x < screen->w &&
114 pos.y >= 0 && pos.y < screen->h)
115 putpixel(screen, (int)pos.x, (int)pos.y,
120 for (; y < MIN(pos.y + radius, screen->h); y++) {
122 unsigned char *buf = screen->pixels;
123 float y2 = (y - pos.y);
125 y2 = sqrt(r2 - y2 * y2);
126 x_start = pos.x - y2;
128 x_start = MAX(0, x_start);
129 x_end = MIN(x_end, screen->w);
131 offset = y * screen->pitch + x_start * 4;
132 for (x = x_start; x < x_end; x++) {
133 buf[offset++] = p->b;
134 buf[offset++] = p->g;
135 buf[offset++] = p->r;
141 int gravitize_planets(struct planet *a, struct planet *b, const double time)
143 struct vector distance, sum;
146 vector_sub(&a->pos, &b->pos, &distance);
148 dist = vector_abs(&distance);
150 /* Return true in case of a collision */
151 if (dist < (a->radius + b->radius))
154 vector_div(&distance, dist, &distance);
156 f = a->mass * b->mass / (dist * dist) * time;
159 vector_scale(&distance, acc, &sum);
160 vector_add(&b->speed, &sum, &b->speed);
163 vector_scale(&distance, acc, &sum);
164 vector_sub(&a->speed, &sum, &a->speed);
170 * Merge planets a and b into planet a
172 * It is left for the caller to deal with the scrap planet b
174 static void _merge_planets(struct planet *a, struct planet *b)
176 struct vector pa, pb, p;
178 vector_scale(&a->speed, a->mass, &pa);
179 vector_scale(&b->speed, b->mass, &pb);
180 vector_add(&pa, &pb, &p);
182 if (a->mass < b->mass)
187 vector_div(&p, a->mass, &a->speed);
191 * Merge planets a and b into a the new planet a, which pointer is
192 * returned to the caller. Planet b is removed from the linked list
193 * and it's memory is freed. The merged planet will retain in the
196 struct planet *merge_planets(struct planet *a, struct planet *b)
198 _merge_planets(a, b);
201 quadtree_del(&b->tree, &planet_ops);
207 static int planet_search_when_moving(struct quadtree *node,
208 struct quadtree_iterator *itr)
210 struct planet *p = tree_to_planet(node);
211 struct planet_search_iterator *it = qt_itr_to_planet_itr(itr);
212 int direction = 0, i;
213 int up = 0, left = 0, right = 0, down = 0;
215 for (i = 0; i < 2; i++) {
216 if (it->limit[i].x < p->pos.x)
220 if (it->limit[i].y < p->pos.y)
227 direction |= QUADTREE_UPLEFT;
229 direction |= QUADTREE_UPRIGHT;
231 direction |= QUADTREE_DOWNLEFT;
233 direction |= QUADTREE_DOWNRIGHT;
234 if ((left && right) || (up && down))
235 direction |= QUADTREE_SELF;
240 void planet_move_iterator(struct quadtree *node, struct quadtree_iterator *it)
242 struct quadtree *parent;
244 parent = quadtree_del(node, &planet_ops);
245 quadtree_add(parent, node, &planet_ops);
248 struct planet *move_planet(struct planet *p, const double time)
250 struct vector tmp, new_pos;
251 struct quadtree *parent, *tree_parent;
253 struct planet_search_iterator it;
257 vector_scale(&p->speed, time, &tmp);
258 vector_add(&p->pos, &tmp, &new_pos);
260 /* Check if we have crossed any of the parents */
261 parent = p->tree.parent;
263 pa = tree_to_planet(parent);
264 if (p->pos.x < pa->pos.x && new_pos.x > pa->pos.x)
266 if (p->pos.x > pa->pos.x && new_pos.x < pa->pos.x)
268 if (p->pos.y < pa->pos.y && new_pos.y > pa->pos.y)
270 if (p->pos.y > pa->pos.y && new_pos.y < pa->pos.y)
274 parent = parent->parent;
278 tree_parent = quadtree_del(&p->tree, &planet_ops);
280 quadtree_add(tree_parent, &p->tree, &planet_ops);
281 return tree_to_planet(tree_parent);
285 * Now, search the subtree for any crossed children and move
286 * them into correct place within the tree.
288 it.qt_iterator.head = &p->tree;
289 it.limit[0] = p->pos;
290 it.limit[1] = new_pos;
291 it.qt_iterator.direction = planet_search_when_moving;
292 it.qt_iterator.callback = planet_move_iterator;
293 walk_quadtree(&it.qt_iterator);
297 return tree_to_planet(quadtree_find_parent(&p->tree));
300 void print_planet(const struct planet *p)
302 printf("pos: (%f,%f), speed: (%f,%f), mass: %f, radius %f\n",
303 p->pos.x, p->pos.y, p->speed.x, p->speed.y, p->mass, p->radius);
306 int planet_spatial_compare(struct quadtree *ta, struct quadtree *tb)
308 struct planet *a, *b;
310 a = tree_to_planet(ta);
311 b = tree_to_planet(tb);
313 up = b->pos.y < a->pos.y;
314 left = b->pos.x < a->pos.x;
325 int planet_search_rectangular(struct quadtree *node,
326 struct quadtree_iterator *itr)
328 struct planet_search_iterator *it = qt_itr_to_planet_itr(itr);
329 struct planet *p = tree_to_planet(node);
330 int direction = 0, i;
331 int up = 0, left = 0, right = 0, down = 0;
333 for (i = 0; i < 2; i++) {
334 if (it->limit[i].x < p->pos.x)
338 if (it->limit[i].y < p->pos.y)
345 direction |= QUADTREE_UPLEFT;
347 direction |= QUADTREE_UPRIGHT;
349 direction |= QUADTREE_DOWNLEFT;
351 direction |= QUADTREE_DOWNRIGHT;
352 if (direction == (QUADTREE_UPLEFT | QUADTREE_UPRIGHT |
353 QUADTREE_DOWNLEFT | QUADTREE_DOWNRIGHT))
354 direction |= QUADTREE_SELF;
359 void planet_draw_iterator(struct quadtree *node, struct quadtree_iterator *it)
361 struct planet *p = tree_to_planet(node);
362 struct planet_search_iterator *i = qt_itr_to_planet_itr(it);
364 draw_planet(i->screen, p, i->cam);
367 static void planet_recalculate_stats(struct quadtree *node)
369 struct planet *p = tree_to_planet(node), *c;
375 p->tree_mass = p->mass;
377 for (i = 0; i < 4; i++) {
381 c = tree_to_planet(node->child[i]);
382 p->tree_mass += c->tree_mass;
384 vector_sub(&p->pos, &c->pos, &vect);
385 dist = vector_abs(&vect);
386 dist += c->tree_area;
387 p->tree_area = MAX(p->tree_area, dist);
391 struct quadtree_ops planet_ops = {
392 .compare = planet_spatial_compare,
393 .recalculate_stats = planet_recalculate_stats,