git.itanic.dy.fi Git - sdl-planets/blob - planet.c

   1 #include <math.h>
   2
   3 #include "random.h"
   4 #include "planet.h"
   5 #include "utils.h"
   6
   7 struct quadtree_ops planet_ops;
   8
   9 static int draw_lines = 0;
  10
  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)
  14 {
  15         int offset = y * screen->pitch + x * 4;
  16         unsigned char *buf = screen->pixels;
  17
  18         buf[offset++] = b;
  19         buf[offset++] = g;
  20         buf[offset]   = r;
  21 }
  22
  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)
  27 {
  28         struct vector dir, v;
  29         float len;
  30         int i;
  31
  32         vector_sub(p2, p1, &dir);
  33
  34         len = vector_abs(&dir);
  35         vector_scale(&dir, 1 / len, &dir);
  36         len *= cam->zoom;
  37
  38         vector_sub(p1, &cam->pos, &v);
  39         vector_scale(&v, cam->zoom, &v);
  40
  41         v.x += screen->w / 2;
  42         v.y += screen->h / 2;
  43
  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);
  49         }
  50 }
  51
  52 static void reshape_planet(struct planet *p)
  53 {
  54         p->radius = pow(p->mass / 100, 1 / 3.0);
  55 }
  56
  57 void init_planet(struct planet *p)
  58 {
  59         memset(p, 0, sizeof(*p));
  60         reshape_planet(p);
  61         p->r = get_random() % 256;
  62         p->g = get_random() % 256;
  63         p->b = get_random() % 256;
  64
  65         INIT_LIST_HEAD(&p->list);
  66         init_quadtree(&p->tree);
  67 }
  68
  69 /**
  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
  75  */
  76
  77 static void setup_planet(struct planet *p, double mass, double total_mass,
  78                          double radius)
  79 {
  80         double angle = M_PI * 2 * get_random_double();
  81         double velocity;
  82         double distance;
  83
  84         distance = radius * pow(get_random_double(), 2);
  85         velocity = sqrt(total_mass / radius);
  86
  87         velocity *= pow(distance / radius, 0.2);
  88
  89         p->pos.x = cos(angle) * distance;
  90         p->pos.y = sin(angle) * distance;
  91
  92         p->speed.x = -sin(angle) * velocity;
  93         p->speed.y = cos(angle) * velocity;
  94
  95         p->mass = mass;
  96
  97         reshape_planet(p);
  98 }
  99
 100 void create_planets(struct planet *p, int num, double total_mass, double radius)
 101 {
 102         int i;
 103         double sum = 0;
 104         struct planet *new_planet;
 105
 106         setup_planet(p,
 107                      total_mass / num * 2 * get_random_double(),
 108                      total_mass,
 109                      radius);
 110
 111         for (i = 0; i < num; i++) {
 112                 new_planet = malloc(sizeof(*new_planet));
 113                 init_planet(new_planet);
 114
 115                 list_add(&new_planet->list, &p->list);
 116
 117                 setup_planet(new_planet,
 118                              total_mass / num * 2 * get_random_double(),
 119                              total_mass,
 120                              radius);
 121
 122                 quadtree_add(&p->tree, &new_planet->tree, &planet_ops);
 123
 124                 sum += new_planet->mass;
 125         }
 126 }
 127
 128 void draw_circle(SDL_Surface *screen, const struct vector *pos,
 129                  const double radius,
 130                  char r, char g, char b, int transparent)
 131 {
 132         int x, x_start, y, x_end;
 133         float r2 = radius * radius;
 134
 135         y = MAX(pos->y - radius, 0);
 136
 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,
 141                                  r, g, b);
 142                 return;
 143         }
 144
 145         for (; y < MIN(pos->y + radius, screen->h); y++) {
 146                 int offset;
 147                 unsigned char *buf = screen->pixels;
 148                 float y2 = (y - pos->y);
 149
 150                 y2 = sqrt(r2 - y2 * y2);
 151                 x_start = pos->x - y2;
 152                 x_end = pos->x + y2;
 153                 x_start = MAX(0, x_start);
 154                 x_end = MIN(x_end, screen->w);
 155
 156                 offset = y * screen->pitch + x_start * 4;
 157                 if (transparent) {
 158                         for (x = x_start; x < x_end; x++) {
 159                                 buf[offset++] += b;
 160                                 buf[offset++] += g;
 161                                 buf[offset++] += r;
 162                                 offset++;
 163                         }
 164                 } else {
 165                         for (x = x_start; x < x_end; x++) {
 166                                 buf[offset++] = b;
 167                                 buf[offset++] = g;
 168                                 buf[offset++] = r;
 169                                 offset++;
 170                         }
 171                 }
 172         }
 173 }
 174
 175 void draw_planet(SDL_Surface *screen, struct planet *p,
 176                  const struct camera *cam)
 177 {
 178         struct vector pos;
 179         float radius = p->radius * cam->zoom;
 180         int i;
 181
 182         vector_sub(&p->pos, &cam->pos, &pos);
 183         vector_scale(&pos, cam->zoom, &pos);
 184         pos.x += screen->w / 2;
 185         pos.y += screen->h / 2;
 186
 187         if (draw_lines) {
 188                 for (i = 0; i < 4; i++) {
 189                         if (!p->tree.child[i])
 190                                 continue;
 191
 192                         struct planet *q = tree_to_planet(p->tree.child[i]);
 193
 194                         draw_line(screen, &p->pos, &q->pos,
 195                                   p->r, p->g, p->b, cam);
 196                 }
 197         }
 198
 199         draw_circle(screen, &pos, radius, p->r, p->g, p->b, 0);
 200 }
 201
 202 int gravitize_planets(struct planet *a, struct planet *b, const double time)
 203 {
 204         struct vector distance, sum;
 205         double dist, f, acc;
 206
 207         vector_sub(&a->pos, &b->pos, &distance);
 208
 209         dist = vector_abs(&distance);
 210
 211         /* Return true in case of a collision */
 212         if (dist < (a->radius + b->radius))
 213                 return 1;
 214
 215         vector_div(&distance, dist, &distance);
 216
 217         f = a->mass * b->mass / (dist * dist) * time;
 218
 219         acc = f / b->mass;
 220         vector_scale(&distance, acc, &sum);
 221         vector_add(&b->speed, &sum, &b->speed);
 222
 223         acc = f / a->mass;
 224         vector_scale(&distance, acc, &sum);
 225         vector_sub(&a->speed, &sum, &a->speed);
 226
 227         return 0;
 228 }
 229
 230 /*
 231  * Merge planets a and b into planet a
 232  *
 233  * It is left for the caller to deal with the scrap planet b
 234  */
 235 static void _merge_planets(struct planet *a, struct planet *b)
 236 {
 237         struct vector pa, pb, p;
 238
 239         vector_scale(&a->speed, a->mass, &pa);
 240         vector_scale(&b->speed, b->mass, &pb);
 241         vector_add(&pa, &pb, &p);
 242
 243         if (a->mass < b->mass)
 244                 a->pos = b->pos;
 245
 246         a->mass += b->mass;
 247         reshape_planet(a);
 248         vector_div(&p, a->mass, &a->speed);
 249 }
 250
 251 /*
 252  * Merge planets a and b into a the new planet a, which pointer is
 253  * returned to the caller. Planet b is removed from the linked list
 254  * and it's memory is freed. The merged planet will retain in the
 255  * list.
 256  */
 257 struct planet *merge_planets(struct planet *a, struct planet *b)
 258 {
 259         _merge_planets(a, b);
 260
 261         list_del(&b->list);
 262         quadtree_del(&b->tree, &planet_ops);
 263
 264         free(b);
 265         return a;
 266 }
 267
 268 static int planet_search_when_moving(struct quadtree *node,
 269                                      struct quadtree_iterator *itr)
 270 {
 271         struct planet *p = tree_to_planet(node);
 272         struct planet_search_iterator *it = qt_itr_to_planet_itr(itr);
 273         int direction = 0, i;
 274         int up = 0, left = 0, right = 0, down = 0;
 275
 276         for (i = 0; i < 2; i++) {
 277                 if (it->limit[i].x < p->pos.x)
 278                         left = 1;
 279                 else
 280                         right = 1;
 281                 if (it->limit[i].y < p->pos.y)
 282                         up = 1;
 283                 else
 284                         down = 1;
 285         }
 286
 287         if (left || up)
 288                 direction |= QUADTREE_UPLEFT;
 289         if (right || up)
 290                 direction |= QUADTREE_UPRIGHT;
 291         if (left || down)
 292                 direction |= QUADTREE_DOWNLEFT;
 293         if (right || down)
 294                 direction |= QUADTREE_DOWNRIGHT;
 295         if ((left && right) || (up && down))
 296                 direction |= QUADTREE_SELF;
 297
 298         return direction;
 299 }
 300
 301 void planet_move_iterator(struct quadtree *node, struct quadtree_iterator *it)
 302 {
 303         struct quadtree *parent;
 304
 305         if (node == it->head)
 306                 return;
 307
 308         parent = quadtree_del(node, &planet_ops);
 309         quadtree_add(parent, node, &planet_ops);
 310 }
 311
 312 struct planet *move_planet(struct planet *p, const double time)
 313 {
 314         struct vector tmp, new_pos;
 315         struct quadtree *parent, *tree_parent;
 316         struct planet *pa;
 317         struct planet_search_iterator it;
 318
 319         int modify = 0;
 320
 321         vector_scale(&p->speed, time, &tmp);
 322         vector_add(&p->pos, &tmp, &new_pos);
 323
 324         /* Check if we have crossed any of the parents */
 325         parent = p->tree.parent;
 326         while (parent) {
 327                 pa = tree_to_planet(parent);
 328                 if (p->pos.x < pa->pos.x && new_pos.x > pa->pos.x)
 329                         modify = 1;
 330                 if (p->pos.x > pa->pos.x && new_pos.x < pa->pos.x)
 331                         modify = 1;
 332                 if (p->pos.y < pa->pos.y && new_pos.y > pa->pos.y)
 333                         modify = 1;
 334                 if (p->pos.y > pa->pos.y && new_pos.y < pa->pos.y)
 335                         modify = 1;
 336
 337                 if (!modify) {
 338                         parent = parent->parent;
 339                         continue;
 340                 }
 341
 342                 tree_parent = quadtree_del(&p->tree, &planet_ops);
 343                 p->pos = new_pos;
 344                 quadtree_add(tree_parent, &p->tree, &planet_ops);
 345                 return tree_to_planet(tree_parent);
 346         }
 347
 348         if(p->tree.children) {
 349                 /*
 350                  * Now, search the subtree for any crossed children and move
 351                  * them into correct place within the tree.
 352                  */
 353                 it.qt_iterator.head = &p->tree;
 354                 it.limit[0] = p->pos;
 355                 it.limit[1] = new_pos;
 356                 it.qt_iterator.direction = planet_search_when_moving;
 357                 it.qt_iterator.callback = planet_move_iterator;
 358                 walk_quadtree(&it.qt_iterator);
 359         }
 360         p->pos = new_pos;
 361
 362         return tree_to_planet(quadtree_find_parent(&p->tree));
 363 }
 364
 365 void print_planet(const struct planet *p)
 366 {
 367         printf("pos: (%f,%f), speed: (%f,%f), mass: %f, radius %f\n",
 368                p->pos.x, p->pos.y, p->speed.x, p->speed.y, p->mass, p->radius);
 369 }
 370
 371 int planet_spatial_compare(struct quadtree *ta, struct quadtree *tb)
 372 {
 373         struct planet *a, *b;
 374         int up, left;
 375         a = tree_to_planet(ta);
 376         b = tree_to_planet(tb);
 377
 378         up = b->pos.y < a->pos.y;
 379         left = b->pos.x < a->pos.x;
 380
 381         if (up && left)
 382                 return 0;
 383         if (up && !left)
 384                 return 1;
 385         if (left)
 386                 return 2;
 387         return 3;
 388 }
 389
 390 int planet_search_rectangular(struct quadtree *node,
 391                               struct quadtree_iterator *itr)
 392 {
 393         struct planet_search_iterator *it = qt_itr_to_planet_itr(itr);
 394         struct planet *p = tree_to_planet(node);
 395         int direction = 0, i;
 396         int up = 0, left = 0, right = 0, down = 0;
 397
 398         for (i = 0; i < 2; i++) {
 399                 if (it->limit[i].x < p->pos.x)
 400                         left = 1;
 401                 else
 402                         right = 1;
 403                 if (it->limit[i].y < p->pos.y)
 404                         up = 1;
 405                 else
 406                         down = 1;
 407         }
 408
 409         if (left && up)
 410                 direction |= QUADTREE_UPLEFT;
 411         if (right && up)
 412                 direction |= QUADTREE_UPRIGHT;
 413         if (left && down)
 414                 direction |= QUADTREE_DOWNLEFT;
 415         if (right && down)
 416                 direction |= QUADTREE_DOWNRIGHT;
 417         if (direction == (QUADTREE_UPLEFT | QUADTREE_UPRIGHT |
 418                           QUADTREE_DOWNLEFT | QUADTREE_DOWNRIGHT))
 419                 direction |= QUADTREE_SELF;
 420
 421         return direction;
 422 }
 423
 424 void planet_draw_iterator(struct quadtree *node, struct quadtree_iterator *it)
 425 {
 426         struct planet *p = tree_to_planet(node);
 427         struct planet_search_iterator *i = qt_itr_to_planet_itr(it);
 428
 429         draw_planet(i->screen, p, i->cam);
 430 }
 431
 432 static void planet_recalculate_stats(struct quadtree *node)
 433 {
 434         struct planet *p = tree_to_planet(node), *c;
 435         struct vector vect;
 436         double dist;
 437         int i;
 438
 439         p->tree_area = 0;
 440         p->tree_mass = p->mass;
 441
 442         for (i = 0; i < 4; i++) {
 443                 if (!node->child[i])
 444                         continue;
 445
 446                 c = tree_to_planet(node->child[i]);
 447                 p->tree_mass += c->tree_mass;
 448
 449                 vector_sub(&p->pos, &c->pos, &vect);
 450                 dist = vector_abs(&vect);
 451                 dist += c->tree_area;
 452                 p->tree_area = MAX(p->tree_area, dist);
 453         }
 454 }
 455
 456 struct quadtree_ops planet_ops = {
 457         .compare = planet_spatial_compare,
 458         .recalculate_stats = planet_recalculate_stats,
 459 };
 460