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