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