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