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 int gravitations, optimizations;
   9
  10 static int draw_lines = 0;
  11 static int draw_tree_area = 0;
  12
  13 static void putpixel(struct SDL_Surface *screen, const int x, const int y,
  14                      const unsigned char r, const unsigned char g,
  15                      const unsigned char b)
  16 {
  17         int offset = y * screen->pitch + x * 4;
  18         unsigned char *buf = screen->pixels;
  19
  20         buf[offset++] = b;
  21         buf[offset++] = g;
  22         buf[offset]   = r;
  23 }
  24
  25 static void draw_line(SDL_Surface *screen, const struct vector *p1,
  26                       const struct vector *p2,
  27                       const unsigned char r, const unsigned char g,
  28                       const unsigned char b, const struct camera *cam)
  29 {
  30         struct vector dir, v;
  31         float len;
  32         int i;
  33
  34         vector_sub(p2, p1, &dir);
  35
  36         len = vector_abs(&dir);
  37         vector_scale(&dir, 1 / len, &dir);
  38         len *= cam->zoom;
  39
  40         vector_sub(p1, &cam->pos, &v);
  41         vector_scale(&v, cam->zoom, &v);
  42
  43         v.x += screen->w / 2;
  44         v.y += screen->h / 2;
  45
  46         for (i = 0; i < len ; i++) {
  47                 if (v.x >= 0 && v.x < screen->w &&
  48                     v.y >= 0 && v.y < screen->h)
  49                         putpixel(screen, v.x, v.y, r, g, b);
  50                 vector_add(&v, &dir, &v);
  51         }
  52 }
  53
  54 static void reshape_planet(struct planet *p)
  55 {
  56         p->radius = pow(p->mass / 100, 1 / 3.0);
  57 }
  58
  59 void init_planet(struct planet *p)
  60 {
  61         memset(p, 0, sizeof(*p));
  62         reshape_planet(p);
  63         p->r = get_random() % 256;
  64         p->g = get_random() % 256;
  65         p->b = get_random() % 256;
  66
  67         INIT_LIST_HEAD(&p->list);
  68         init_quadtree(&p->tree);
  69 }
  70
  71 /**
  72  * setup_planet - set the planet on a "solarsystem"
  73  * @p:          pointer to struct planet to set up
  74  * @mass:       mass of the planet to set up
  75  * @total_mass: total mass of the system
  76  * @radius:     maximum radius of the system
  77  */
  78
  79 static void setup_planet(struct planet *p, double mass, double total_mass,
  80                          double radius)
  81 {
  82         double angle = M_PI * 2 * get_random_double();
  83         double velocity;
  84         double distance;
  85
  86         distance = radius * pow(get_random_double(), 2);
  87         velocity = sqrt(total_mass / radius);
  88
  89         velocity *= pow(distance / radius, 0.2);
  90
  91         p->tree.pos.x = cos(angle) * distance;
  92         p->tree.pos.y = sin(angle) * distance;
  93
  94         p->speed.x = -sin(angle) * velocity;
  95         p->speed.y = cos(angle) * velocity;
  96
  97         p->mass = mass;
  98
  99         reshape_planet(p);
 100 }
 101
 102 void create_planets(struct planet *p, int num, double total_mass, double radius)
 103 {
 104         int i;
 105         double sum = 0;
 106         struct planet *new_planet;
 107
 108         setup_planet(p,
 109                      total_mass / num * 2 * get_random_double(),
 110                      total_mass,
 111                      radius);
 112
 113         for (i = 0; i < num; i++) {
 114                 new_planet = malloc(sizeof(*new_planet));
 115                 init_planet(new_planet);
 116
 117                 list_add(&new_planet->list, &p->list);
 118
 119                 setup_planet(new_planet,
 120                              total_mass / num * 2 * get_random_double(),
 121                              total_mass,
 122                              radius);
 123
 124                 quadtree_add(&p->tree, &new_planet->tree, &planet_ops);
 125
 126                 sum += new_planet->mass;
 127         }
 128 }
 129
 130 void draw_circle(SDL_Surface *screen, const struct vector *pos,
 131                  const double radius,
 132                  char r, char g, char b, int transparent)
 133 {
 134         int x, x_start, y, x_end;
 135         float r2 = radius * radius;
 136
 137         y = MAX(pos->y - radius, 0);
 138
 139         if (radius * 2 <= 1) {
 140                 if (pos->x >= 0 && pos->x < screen->w &&
 141                     pos->y >= 0 && pos->y < screen->h)
 142                         putpixel(screen, (int)pos->x, (int)pos->y,
 143                                  r, g, b);
 144                 return;
 145         }
 146
 147         for (; y < MIN(pos->y + radius, screen->h); y++) {
 148                 int offset;
 149                 unsigned char *buf = screen->pixels;
 150                 float y2 = (y - pos->y);
 151
 152                 y2 = sqrt(r2 - y2 * y2);
 153                 x_start = pos->x - y2;
 154                 x_end = pos->x + y2;
 155                 x_start = MAX(0, x_start);
 156                 x_end = MIN(x_end, screen->w);
 157
 158                 offset = y * screen->pitch + x_start * 4;
 159                 if (transparent) {
 160                         for (x = x_start; x < x_end; x++) {
 161                                 buf[offset++] += b;
 162                                 buf[offset++] += g;
 163                                 buf[offset++] += r;
 164                                 offset++;
 165                         }
 166                 } else {
 167                         for (x = x_start; x < x_end; x++) {
 168                                 buf[offset++] = b;
 169                                 buf[offset++] = g;
 170                                 buf[offset++] = r;
 171                                 offset++;
 172                         }
 173                 }
 174         }
 175 }
 176
 177 void draw_planet(SDL_Surface *screen, const struct planet *p,
 178                  const struct camera *cam)
 179 {
 180         struct vector pos;
 181         float radius = p->radius * cam->zoom;
 182         int i;
 183
 184         vector_sub(&p->tree.pos, &cam->pos, &pos);
 185         vector_scale(&pos, cam->zoom, &pos);
 186         pos.x += screen->w / 2;
 187         pos.y += screen->h / 2;
 188
 189         if (draw_tree_area)
 190                 draw_circle(screen, &pos, p->tree_area * cam->zoom,
 191                             p->r / 8, p->g / 8, p->b / 8, 1);
 192
 193         if (draw_lines) {
 194                 for (i = 0; i < 4; i++) {
 195                         if (!p->tree.child[i])
 196                                 continue;
 197
 198                         struct planet *q = tree_to_planet(p->tree.child[i]);
 199
 200                         draw_line(screen, &p->tree.pos, &q->tree.pos,
 201                                   p->r, p->g, p->b, cam);
 202                 }
 203         }
 204
 205         draw_circle(screen, &pos, radius, p->r, p->g, p->b, 0);
 206 }
 207
 208 int gravitize_planet_with_planet(struct planet *a, struct planet *b,
 209                                  const double time)
 210 {
 211         struct vector distance, sum;
 212         double dist, f, acc;
 213
 214         if (a->to_be_deleted || b->to_be_deleted)
 215                 return 0;
 216
 217         gravitations++;
 218
 219         vector_sub(&a->tree.pos, &b->tree.pos, &distance);
 220
 221         dist = vector_abs(&distance);
 222
 223         if (dist < (a->radius + b->radius)) {
 224                 merge_planets(a, b);
 225                 return 1;
 226         }
 227
 228         vector_div(&distance, dist, &distance);
 229
 230         f = a->mass * b->mass / (dist * dist) * time;
 231
 232         acc = f / b->mass;
 233         vector_scale(&distance, acc, &sum);
 234         vector_add(&b->speed, &sum, &b->speed);
 235
 236         acc = f / a->mass;
 237         vector_scale(&distance, acc, &sum);
 238         vector_sub(&a->speed, &sum, &a->speed);
 239
 240         return 0;
 241 }
 242
 243 int gravitize_planet_with_tree(struct planet *a, struct planet *b,
 244                                const double time)
 245 {
 246         struct vector distance, sum;
 247         double dist, f, acc;
 248
 249         if (a->to_be_deleted || b->to_be_deleted)
 250                 return 0;
 251
 252         gravitations++;
 253
 254         vector_sub(&a->tree.pos, &b->tree.pos, &distance);
 255
 256         dist = vector_abs(&distance);
 257
 258         vector_div(&distance, dist, &distance);
 259
 260         f = a->mass * b->tree_mass / (dist * dist) * time;
 261
 262         acc = f / a->mass;
 263         vector_scale(&distance, acc, &sum);
 264         vector_sub(&a->speed, &sum, &a->speed);
 265
 266         acc = f / b->tree_mass;
 267         vector_scale(&distance, acc, &sum);
 268         vector_add(&b->tree_speed, &sum, &b->tree_speed);
 269
 270         return 0;
 271 }
 272
 273 /*
 274  * Merge planets a and b together
 275  *
 276  * The smaller planet will be deleted, matter will be transferred to
 277  * the bigger planet.
 278  */
 279 static struct planet *_merge_planets(struct planet *a, struct planet *b)
 280 {
 281         struct quadtree *parent = &a->tree;
 282         struct vector pa, pb, p;
 283         float mass;
 284
 285         vector_scale(&a->speed, a->mass, &pa);
 286         vector_scale(&b->speed, b->mass, &pb);
 287         vector_add(&pa, &pb, &p);
 288         mass = a->mass + b->mass;
 289
 290         if (a->mass < b->mass)
 291                 parent = quadtree_move(&a->tree, b->tree.pos, &planet_ops);
 292
 293         nr->mass = mass;
 294         reshape_planet(nr);
 295         vector_div(&p, nr->mass, &nr->speed);
 296
 297         a->mass = mass;
 298         reshape_planet(a);
 299         vector_div(&p, a->mass, &a->speed);
 300
 301         return tree_to_planet(quadtree_find_parent(parent));
 302 }
 303
 304 /*
 305  * Merge planets a and b into a the new planet, which pointer is
 306  * returned to the caller. The other planet is removed from the linked
 307  * list and it's memory is freed. The merged planet will be kept in
 308  * the list.
 309  */
 310 struct planet *merge_planets(struct planet *a, struct planet *b)
 311 {
 312         struct quadtree *p;
 313         _merge_planets(a, b);
 314
 315         list_del(&b->list);
 316         p = quadtree_del(&b->tree, &planet_ops);
 317
 318         free(b);
 319         return tree_to_planet(p);
 320 }
 321
 322 static void gravitize_planet(struct planet *p, struct planet *pt, double time)
 323 {
 324         struct vector vect;
 325         float dist;
 326         int i;
 327
 328         vector_sub(&p->tree.pos, &pt->tree.pos, &vect);
 329         dist = vector_abs(&vect);
 330
 331         if (p != pt)
 332                 gravitize_planet_with_planet(p, pt, time);
 333
 334         if (dist > pt->tree_area * 8) {
 335                 /*
 336                  * OK, the node is far enough. We can approximate the
 337                  * entire tree as a single entity.
 338                  */
 339                 optimizations += pt->tree.children;
 340                 gravitize_planet_with_tree(p, pt, time);
 341                 return;
 342         }
 343
 344         /* Otherwise, gravitize with each of the child */
 345         for (i = 0; i < 4; i++) {
 346                 if (!pt->tree.child[i])
 347                         continue;
 348
 349                 gravitize_planet(p, tree_to_planet(pt->tree.child[i]),
 350                                  time);
 351         }
 352 }
 353
 354 void gravitize_planet_tree(struct planet *p, double time)
 355 {
 356         int i;
 357
 358         for (i = 0; i < 4; i++) {
 359                 if (!p->tree.child[i])
 360                         continue;
 361
 362                 gravitize_planet_tree(tree_to_planet(p->tree.child[i]),
 363                                       time);
 364         }
 365
 366         gravitize_planet(p,
 367                          tree_to_planet(quadtree_find_parent(&p->tree)),
 368                          time);
 369 }
 370
 371 struct planet *move_planet(struct planet *p, const double time)
 372 {
 373         struct vector tmp, new_pos;
 374
 375         vector_scale(&p->speed, time, &tmp);
 376         vector_add(&p->tree.pos, &tmp, &new_pos);
 377
 378         return tree_to_planet(quadtree_move(&p->tree, new_pos, &planet_ops));
 379 }
 380
 381 int propagate_tree_movement(struct planet *p)
 382 {
 383         int i, count = 1;
 384
 385         for (i = 0; i < 4; i++) {
 386                 if (!p->tree.child[i])
 387                         continue;
 388
 389                 vector_add(&tree_to_planet(p->tree.child[i])->speed,
 390                         &p->tree_speed,
 391                         &tree_to_planet(p->tree.child[i])->speed);
 392
 393                 count += propagate_tree_movement(
 394                         tree_to_planet(p->tree.child[i]));
 395         }
 396
 397         vector_add(&p->tree_speed, &p->speed, &p->speed);
 398
 399         p->tree_speed.x = 0;
 400         p->tree_speed.y = 0;
 401
 402         return count;
 403 }
 404
 405 struct planet *prune_planet_tree(struct planet *p)
 406 {
 407         struct quadtree *tree_parent = &p->tree;
 408         int i;
 409 /*
 410         while (head != start) {
 411                 p = list_to_planet(head);
 412                 if (p->to_be_deleted) {
 413                         if (head == start)
 414                                 start = head->next;
 415                         list_del(&p->list);
 416                         tree_parent = quadtree_del(&p->tree, &planet_ops);
 417                         head = head->next;
 418                         free(p);
 419                         continue;
 420                 }
 421
 422                 head = head->next;
 423         }
 424
 425         return tree_to_planet(tree_parent);
 426 */
 427         for (i = 0; i < 4; i++) {
 428                 if (!p->tree.child[i])
 429                         continue;
 430
 431                 prune_planet_tree(tree_to_planet(p->tree.child[i]));
 432         }
 433
 434         if (p->to_be_deleted) {
 435                 list_del(&p->list);
 436                 tree_parent = quadtree_del(&p->tree, &planet_ops);
 437                 free(p);
 438                 return tree_to_planet(tree_parent);
 439         }
 440
 441         planet_ops.recalculate_stats(&p->tree);
 442
 443         return tree_to_planet(quadtree_find_parent(&p->tree));
 444 }
 445
 446 void print_planet(const struct planet *p)
 447 {
 448         printf("pos: (%f,%f), speed: (%f,%f), mass: %f, radius %f\n",
 449                p->tree.pos.x, p->tree.pos.y, p->speed.x, p->speed.y, p->mass, p->radius);
 450 }
 451
 452 int planet_search_rectangular(struct quadtree *node,
 453                               struct quadtree_iterator *itr)
 454 {
 455         struct planet_search_iterator *it = qt_itr_to_planet_itr(itr);
 456         struct planet *p = tree_to_planet(node);
 457         int direction = 0, i;
 458         int up = 0, left = 0, right = 0, down = 0;
 459
 460         for (i = 0; i < 2; i++) {
 461                 if (it->limit[i].x < p->tree.pos.x)
 462                         left = 1;
 463                 else
 464                         right = 1;
 465                 if (it->limit[i].y < p->tree.pos.y)
 466                         up = 1;
 467                 else
 468                         down = 1;
 469         }
 470
 471         if (left && up)
 472                 direction |= QUADTREE_UPLEFT;
 473         if (right && up)
 474                 direction |= QUADTREE_UPRIGHT;
 475         if (left && down)
 476                 direction |= QUADTREE_DOWNLEFT;
 477         if (right && down)
 478                 direction |= QUADTREE_DOWNRIGHT;
 479         if (direction == (QUADTREE_UPLEFT | QUADTREE_UPRIGHT |
 480                           QUADTREE_DOWNLEFT | QUADTREE_DOWNRIGHT))
 481                 direction |= QUADTREE_SELF;
 482
 483         return direction;
 484 }
 485
 486 void planet_draw_iterator(struct quadtree *node, struct quadtree_iterator *it)
 487 {
 488         struct planet *p = tree_to_planet(node);
 489         struct planet_search_iterator *i = qt_itr_to_planet_itr(it);
 490
 491         draw_planet(i->screen, p, i->cam);
 492 }
 493
 494 static void planet_recalculate_stats(struct quadtree *node)
 495 {
 496         struct planet *p = tree_to_planet(node), *c;
 497         struct vector vect;
 498         double dist;
 499         int i;
 500
 501         p->tree_area = 0;
 502         p->tree_mass = p->mass;
 503
 504         for (i = 0; i < 4; i++) {
 505                 if (!node->child[i])
 506                         continue;
 507
 508                 c = tree_to_planet(node->child[i]);
 509                 p->tree_mass += c->tree_mass;
 510
 511                 vector_sub(&p->tree.pos, &c->tree.pos, &vect);
 512                 dist = vector_abs(&vect);
 513                 dist += c->tree_area;
 514                 p->tree_area = MAX(p->tree_area, dist);
 515         }
 516 }
 517
 518 struct quadtree_ops planet_ops = {
 519         .recalculate_stats = planet_recalculate_stats,
 520 };
 521