git.mutantstargoat.com Git - ld42_outofspace/blob - src/gamescr.cc

   1 #include <assert.h>
   2 #include <vector>
   3 #include <gmath/gmath.h>
   4 #include "game.h"
   5 #include "screen.h"
   6 #include "opengl.h"
   7 #include "texture.h"
   8 #include "sdr.h"
   9 #include "mesh.h"
  10 #include "meshgen.h"
  11
  12 /* NOTES:
  13  * - whistle hhgg music
  14  * - colliding particles merge
  15  * - select objects and center camera on them
  16  * - tesselate only where necessary
  17  */
  18
  19 struct Particle {
  20         float radius;
  21         float mass;
  22         Vec2 pos;
  23         Vec2 vel;
  24
  25         float vis_height;
  26
  27         Particle *next, *prev;
  28 };
  29
  30 struct Emitter {
  31         Vec2 pos;
  32         float mass;
  33         float rate, chunk;
  34         float angle, spread;
  35
  36         float spawn_pending;
  37 };
  38
  39 struct Rect {
  40         int x, y;
  41         int width, height;
  42 };
  43
  44 struct QuadMesh {
  45         Vec3 *v;
  46         Vec2 *uv;
  47         uint16_t *idx;
  48
  49         int num_verts, num_idx, num_quads;
  50
  51         unsigned int vbo_v, vbo_uv, ibo;
  52 };
  53
  54 #define SIM_DT          0.016
  55
  56 #define GRID_SIZE       2048
  57 #define GRID_BITS       11
  58 #define GRID_X(idx)     (((idx) >> GRID_BITS) & (GRID_SIZE - 1))
  59 #define GRID_Y(idx)     ((idx) & (GRID_SIZE - 1))
  60 #define GRID_DELTA      ((float)FIELD_SIZE / (float)GRID_SIZE)
  61
  62 #define FIELD_SIZE      2048
  63 #define MIN_CAM_DIST    1.0f
  64 #define MAX_CAM_DIST    350.0f
  65
  66 #define MASS_TO_RADIUS(m)       log((m) + 1.0)
  67
  68 #define CONTRIB_THRES   0.005
  69 #define CONTRIB_RANGE(m) sqrt((m) / CONTRIB_THRES)
  70
  71 /* gravitational strength */
  72 #define GRAV_STR        16.0f
  73
  74 static int pos_to_grid(float x, float y);
  75 static Vec2 grid_to_pos(int gx, int gy);
  76
  77 static void calc_contrib_bounds(const Vec2 &pos, float mass, Rect *rect);
  78 static void add_influence(const Vec2 &pos, float mass, float radius, const Rect &cbox);
  79
  80 static Vec2 calc_field_grad(int gidx);
  81
  82 static void destroy_quadmesh(QuadMesh *m);
  83 static void draw_quadmesh(const QuadMesh *m, unsigned int prim = GL_QUADS);
  84 static void gen_quad_plane(QuadMesh *mesh, float width, float height, int usub, int vsub);
  85
  86 static void spawn_particle(const Vec2 &pos, const Vec2 &vel, float mass);
  87 static void add_particle(Particle *p);
  88 static void remove_particle(Particle *p);
  89 static Particle *alloc_particle();
  90 void free_particle(Particle *p);
  91
  92 static float grid[GRID_SIZE * GRID_SIZE];
  93 static Particle *grid_part[GRID_SIZE * GRID_SIZE];
  94 static Texture *grid_tex;
  95
  96 static Particle *plist;
  97
  98 static std::vector<Emitter*> emitters;
  99
 100 static Texture *gvis_tex;       // texture tile for visualizing a grid
 101 static unsigned int field_sdr;
 102 static int tess_level = 64;
 103 static float field_scale = 16.0f;
 104
 105 static QuadMesh field_mesh;
 106
 107 static Mesh *pmesh;
 108 static unsigned int particle_sdr;
 109
 110 static float cam_theta;
 111 static float cam_dist = 100.0f;
 112 static Vec2 *targ_pos;
 113 static Mat4 view_matrix, proj_matrix;
 114
 115 // emitter placement data (filled by event handlers, completed in update)
 116 static bool emit_place_pending;
 117 static Vec2 emit_place_pos;
 118
 119
 120 bool GameScreen::init()
 121 {
 122         grid_tex = new Texture;
 123         grid_tex->create(GRID_SIZE, GRID_SIZE, TEX_2D, GL_LUMINANCE32F_ARB);
 124         grid_tex->set_anisotropy(glcaps.max_aniso);
 125
 126         gvis_tex = new Texture;
 127         if(!gvis_tex->load("data/purple_grid.png")) {
 128                 return false;
 129         }
 130         gvis_tex->set_anisotropy(glcaps.max_aniso);
 131
 132         unsigned int vsdr, tcsdr, tesdr, psdr;
 133
 134         if(!(vsdr = load_vertex_shader("sdr/field.v.glsl")) ||
 135                         !(tcsdr = load_tessctl_shader("sdr/field.tc.glsl")) ||
 136                         !(tesdr = load_tesseval_shader("sdr/field.te.glsl")) ||
 137                         !(psdr = load_pixel_shader("sdr/field.p.glsl"))) {
 138                 return false;
 139         }
 140
 141         if(!(field_sdr = create_program_link(vsdr, tcsdr, tesdr, psdr, 0))) {
 142                 return false;
 143         }
 144         set_uniform_int(field_sdr, "gvis_tex", 0);
 145         set_uniform_int(field_sdr, "field_tex", 1);
 146         set_uniform_float(field_sdr, "gvis_scale", FIELD_SIZE / 32.0f);
 147         set_uniform_int(field_sdr, "tess_level", tess_level);
 148         set_uniform_float(field_sdr, "field_scale", field_scale);
 149
 150         gen_quad_plane(&field_mesh, FIELD_SIZE, FIELD_SIZE, 32, 32);
 151
 152         pmesh = new Mesh;
 153         gen_geosphere(pmesh, 1.0, 2);
 154
 155         if(!(particle_sdr = create_program_load("sdr/sph.v.glsl", "sdr/sph.p.glsl"))) {
 156                 return false;
 157         }
 158
 159         // XXX DBG
 160         emit_place_pos = Vec2(0, 0);
 161         emit_place_pending = true;
 162
 163         assert(glGetError() == GL_NO_ERROR);
 164         return true;
 165 }
 166
 167 void GameScreen::destroy()
 168 {
 169         free_program(field_sdr);
 170         delete gvis_tex;
 171         delete grid_tex;
 172         destroy_quadmesh(&field_mesh);
 173         delete pmesh;
 174 }
 175
 176 static void simstep()
 177 {
 178         // move existing particles
 179         Particle *p = plist;
 180         while(p) {
 181                 // calculate the field gradient at the particle position
 182                 int gidx = pos_to_grid(p->pos.x, p->pos.y);
 183                 Vec2 grad = calc_field_grad(gidx) * GRAV_STR;
 184
 185                 p->vel += grad * SIM_DT;
 186                 p->pos += p->vel * SIM_DT;
 187
 188                 // find the grid cell it's moving to
 189                 int gidx_next = pos_to_grid(p->pos.x, p->pos.y);
 190                 p->vis_height = 0.0f;//-grid[gidx_next] * field_scale;
 191
 192                 if(gidx_next == gidx) {
 193                         p = p->next;
 194                         continue;
 195                 }
 196
 197                 Particle *destp = grid_part[gidx_next];
 198                 if(destp) {
 199                         assert(destp != p);
 200                         // another particle at the destination, merge them
 201                         destp->vel += p->vel;
 202                         destp->mass += p->mass;
 203                         destp->radius = MASS_TO_RADIUS(destp->mass);
 204
 205                         // ... and remove it
 206                         grid_part[gidx] = 0;
 207                         Particle *next = p->next;
 208                         remove_particle(p);
 209                         free_particle(p);
 210                         p = next;
 211                 } else {
 212                         // destination is empty, go there
 213                         if(gidx != gidx_next) {
 214                                 grid_part[gidx] = 0;
 215                                 grid_part[gidx_next] = p;
 216                         }
 217
 218                         p = p->next;
 219                 }
 220         }
 221
 222         // TODO destroy particles which left the simulation field
 223
 224         // spawn particles
 225         int num_emitters = emitters.size();
 226         for(int i=0; i<num_emitters; i++) {
 227                 Emitter *em = emitters[i];
 228                 em->spawn_pending += em->rate * SIM_DT;
 229                 while(em->spawn_pending >= 1.0f && em->mass > 0.0f) {
 230                         Vec2 pvel;      // XXX calc eject velocity
 231
 232                         float angle = (float)rand() / (float)RAND_MAX * (M_PI * 2.0);
 233                         float emradius = MASS_TO_RADIUS(em->mass);
 234                         Vec2 ppos = em->pos + Vec2(cos(angle), sin(angle)) * emradius * 1.00001;
 235
 236                         float pmass = em->chunk > em->mass ? em->mass : em->chunk;
 237                         spawn_particle(ppos, pvel, pmass);
 238                         em->mass -= pmass;
 239
 240                         em->spawn_pending -= 1.0f;
 241                 }
 242         }
 243
 244         // remove dead emitters
 245         std::vector<Emitter*>::iterator it = emitters.begin();
 246         while(it != emitters.end()) {
 247                 Emitter *em = *it;
 248
 249                 if(em->mass <= 0.0f) {
 250                         printf("emitter depleted\n");
 251                         it = emitters.erase(it);
 252                         delete em;
 253                 } else {
 254                         it++;
 255                 }
 256         }
 257
 258         // calculate gravitational field - assume field within radius constant: m / r^2
 259         // first clear the field, and then add contributions
 260         memset(grid, 0, sizeof grid);
 261
 262         // contribution of emitters
 263         for(int i=0; i<num_emitters; i++) {
 264                 Emitter *em = emitters[i];
 265                 Rect cbox;
 266                 calc_contrib_bounds(em->pos, em->mass, &cbox);
 267                 float emradius = MASS_TO_RADIUS(em->mass);
 268
 269                 add_influence(em->pos, -em->mass, emradius, cbox);
 270         }
 271
 272         // contribution of particles
 273         p = plist;
 274         while(p) {
 275                 Rect cbox;
 276                 calc_contrib_bounds(p->pos, p->mass, &cbox);
 277                 add_influence(p->pos, p->mass, p->radius, cbox);
 278                 p = p->next;
 279         }
 280
 281         // update texture
 282         assert(glGetError() == GL_NO_ERROR);
 283         grid_tex->bind();
 284         glTexSubImage2D(GL_TEXTURE_2D, 0, 0, 0, GRID_SIZE, GRID_SIZE, GL_LUMINANCE,
 285                         GL_FLOAT, grid);
 286         assert(glGetError() == GL_NO_ERROR);
 287 }
 288
 289 static void update()
 290 {
 291         if(emit_place_pending) {
 292                 emit_place_pending = false;
 293                 Emitter *em = new Emitter;
 294                 em->pos = emit_place_pos;
 295                 em->mass = 100;
 296                 em->rate = 10;
 297                 em->chunk = 0.001 * em->mass;
 298                 em->angle = -1;
 299                 em->spread = 0;
 300                 em->spawn_pending = 0;
 301                 emitters.push_back(em);
 302
 303                 Rect cbox;
 304                 calc_contrib_bounds(em->pos, em->mass, &cbox);
 305                 printf("bounds: %d,%d %dx%d\n", cbox.x, cbox.y, cbox.width, cbox.height);
 306         }
 307
 308         // update simulation
 309         static float interval;
 310         interval += frame_dt;
 311         if(interval >= SIM_DT) {
 312                 interval -= SIM_DT;
 313                 simstep();
 314                 assert(glGetError() == GL_NO_ERROR);
 315         }
 316
 317         // update projection matrix
 318         proj_matrix.perspective(deg_to_rad(60.0f), win_aspect, 0.5, 5000.0);
 319
 320         // update view matrix
 321         Vec3 targ;
 322         if(targ_pos) {
 323                 targ.x = targ_pos->x;
 324                 targ.z = targ_pos->y;
 325         }
 326
 327         float theta = -deg_to_rad(cam_theta);
 328         Vec3 camdir = Vec3(sin(theta) * cam_dist, pow(cam_dist * 0.1, 2.0) + 0.5, cos(theta) * cam_dist);
 329         Vec3 campos = targ + camdir;
 330
 331         view_matrix.inv_lookat(campos, targ, Vec3(0, 1, 0));
 332 }
 333
 334 void GameScreen::draw()
 335 {
 336         update();
 337
 338         glClearColor(0.01, 0.01, 0.01, 1);
 339         glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
 340
 341         glMatrixMode(GL_PROJECTION);
 342         glLoadMatrixf(proj_matrix[0]);
 343         glMatrixMode(GL_MODELVIEW);
 344         glLoadMatrixf(view_matrix[0]);
 345
 346         glPushAttrib(GL_ENABLE_BIT);
 347         glDisable(GL_CULL_FACE);
 348
 349         // draw gravitational field
 350         glEnable(GL_TEXTURE_2D);
 351         bind_texture(gvis_tex, 0);
 352         bind_texture(grid_tex, 1);
 353
 354         glUseProgram(field_sdr);
 355         glPatchParameteri(GL_PATCH_VERTICES, 4);
 356         draw_quadmesh(&field_mesh, GL_PATCHES);
 357
 358         // draw particles
 359         glUseProgram(particle_sdr);
 360
 361         Particle *p = plist;
 362         while(p) {
 363                 int gidx = pos_to_grid(p->pos.x, p->pos.y);
 364
 365                 glPushMatrix();
 366                 glTranslatef(p->pos.x, p->vis_height, p->pos.y);
 367                 glScalef(p->radius, p->radius, p->radius);
 368
 369                 pmesh->draw();
 370
 371                 glPopMatrix();
 372                 p = p->next;
 373         }
 374
 375         glUseProgram(0);
 376
 377         glPopAttrib();
 378
 379         assert(glGetError() == GL_NO_ERROR);
 380 }
 381
 382 void GameScreen::reshape(int x, int y)
 383 {
 384 }
 385
 386
 387
 388 void GameScreen::keyboard(int key, bool pressed)
 389 {
 390         if(pressed) {
 391                 switch(key) {
 392                 case KEY_ESC:
 393                         pop_screen();
 394                         break;
 395
 396                 case ']':
 397                         if(tess_level < glcaps.max_tess_level) {
 398                                 tess_level++;
 399                                 printf("tessellation level: %d\n", tess_level);
 400                                 set_uniform_int(field_sdr, "tess_level", tess_level);
 401                                 glUseProgram(0);
 402                         }
 403                         break;
 404
 405                 case '[':
 406                         if(tess_level > 1) {
 407                                 tess_level--;
 408                                 printf("tessellation level: %d\n", tess_level);
 409                                 set_uniform_int(field_sdr, "tess_level", tess_level);
 410                                 glUseProgram(0);
 411                         }
 412                         break;
 413
 414                 case '=':
 415                         field_scale += 0.5;
 416                         printf("field scale: %f\n", field_scale);
 417                         set_uniform_float(field_sdr, "field_scale", field_scale);
 418                         break;
 419
 420                 case '-':
 421                         field_scale -= 0.5;
 422                         if(field_scale < 0.0f) {
 423                                 field_scale = 0.0f;
 424                         }
 425                         printf("field scale: %f\n", field_scale);
 426                         set_uniform_float(field_sdr, "field_scale", field_scale);
 427                         break;
 428
 429                 default:
 430                         break;
 431                 }
 432         }
 433 }
 434
 435 static int prev_x, prev_y;
 436
 437 void GameScreen::mbutton(int bn, bool pressed, int x, int y)
 438 {
 439         prev_x = x;
 440         prev_y = y;
 441 }
 442
 443 void GameScreen::mmotion(int x, int y)
 444 {
 445         int dx = x - prev_x;
 446         int dy = y - prev_y;
 447         prev_x = x;
 448         prev_y = y;
 449
 450         if(game_bnstate(2)) {
 451                 cam_theta += dx * 0.5;
 452         }
 453 }
 454
 455 void GameScreen::mwheel(int dir, int x, int y)
 456 {
 457         cam_dist -= dir * cam_dist * 0.05f;
 458         if(cam_dist <= MIN_CAM_DIST) cam_dist = MIN_CAM_DIST;
 459         if(cam_dist > MAX_CAM_DIST) cam_dist = MAX_CAM_DIST;
 460 }
 461
 462
 463 static int pos_to_grid(float x, float y)
 464 {
 465         int gx = ((x / (float)FIELD_SIZE) + 0.5f) * (float)GRID_SIZE;
 466         int gy = ((y / (float)FIELD_SIZE) + 0.5f) * (float)GRID_SIZE;
 467
 468         if(gx < 0) gx = 0;
 469         if(gx >= GRID_SIZE) gx = GRID_SIZE - 1;
 470         if(gy < 0) gy = 0;
 471         if(gy >= GRID_SIZE) gy = GRID_SIZE - 1;
 472
 473         return (gx << GRID_BITS) | gy;
 474 }
 475
 476 static Vec2 grid_to_pos(int gx, int gy)
 477 {
 478         float x = (((float)gx / (float)GRID_SIZE) - 0.5f) * (float)FIELD_SIZE;
 479         float y = (((float)gy / (float)GRID_SIZE) - 0.5f) * (float)FIELD_SIZE;
 480
 481         return Vec2(x, y);
 482 }
 483
 484 static void calc_contrib_bounds(const Vec2 &pos, float mass, Rect *rect)
 485 {
 486         int gidx = pos_to_grid(pos.x, pos.y);
 487         int gx = GRID_X(gidx);
 488         int gy = GRID_Y(gidx);
 489         int maxrange = (int)ceil(CONTRIB_RANGE(mass));
 490
 491         int sx = gx - maxrange;
 492         int sy = gy - maxrange;
 493         int ex = gx + maxrange;
 494         int ey = gy + maxrange;
 495
 496         if(ex > GRID_SIZE) ex = GRID_SIZE;
 497         if(ey > GRID_SIZE) ey = GRID_SIZE;
 498
 499         rect->x = sx < 0 ? 0 : sx;
 500         rect->y = sy < 0 ? 0 : sy;
 501         rect->width = ex - sx;
 502         rect->height = ey - sy;
 503 }
 504
 505 static void add_influence(const Vec2 &pos, float mass, float radius, const Rect &cbox)
 506 {
 507         float *gptr = grid + cbox.y * GRID_SIZE + cbox.x;
 508         Vec2 startpos = grid_to_pos(cbox.x, cbox.y);
 509
 510         for(int y=0; y<cbox.height; y++) {
 511                 for(int x=0; x<cbox.width; x++) {
 512                         Vec2 cellpos = Vec2(startpos.x + (float)x * GRID_DELTA, startpos.y);
 513
 514                         Vec2 dir = cellpos - pos;
 515                         float dsq = dot(dir, dir);
 516                         float radsq = radius * radius;
 517                         if(dsq < radsq) {
 518                                 dsq = radsq;
 519                         }
 520
 521                         gptr[x] += mass / dsq;
 522                 }
 523
 524                 startpos.y += GRID_DELTA;
 525                 gptr += GRID_SIZE;
 526         }
 527 }
 528
 529 static Vec2 calc_field_grad(int gidx)
 530 {
 531         int gx = GRID_X(gidx);
 532         int gy = GRID_Y(gidx);
 533
 534         int nidx = ((gx + 1 >= GRID_SIZE ? gx : gx + 1) << GRID_BITS) | gy;
 535         int pidx = ((gx > 0 ? gx - 1 : gx) << GRID_BITS) | gy;
 536         float dfdx = grid[nidx] - grid[pidx];
 537
 538         nidx = (gx << GRID_BITS) | (gy + 1 >= GRID_SIZE ? gy : gy + 1);
 539         pidx = (gx << GRID_BITS) | (gy > 0 ? gy - 1 : gy);
 540         float dfdy = grid[nidx] - grid[pidx];
 541
 542         return Vec2(dfdx, dfdy);
 543 }
 544
 545
 546 // ---- quad mesh operations ----
 547
 548 static void destroy_quadmesh(QuadMesh *m)
 549 {
 550         glDeleteBuffers(1, &m->vbo_v);
 551         glDeleteBuffers(1, &m->vbo_uv);
 552         glDeleteBuffers(1, &m->ibo);
 553
 554         delete [] m->v;
 555         delete [] m->uv;
 556         delete [] m->idx;
 557 }
 558
 559 static void draw_quadmesh(const QuadMesh *m, unsigned int prim)
 560 {
 561         glEnableClientState(GL_VERTEX_ARRAY);
 562         glEnableClientState(GL_TEXTURE_COORD_ARRAY);
 563
 564         glBindBuffer(GL_ARRAY_BUFFER, m->vbo_v);
 565         glVertexPointer(3, GL_FLOAT, 0, 0);
 566
 567         glBindBuffer(GL_ARRAY_BUFFER, m->vbo_uv);
 568         glTexCoordPointer(2, GL_FLOAT, 0, 0);
 569
 570         glBindBuffer(GL_ARRAY_BUFFER, 0);
 571
 572         glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, m->ibo);
 573         glDrawElements(prim, m->num_idx, GL_UNSIGNED_SHORT, 0);
 574         glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);
 575
 576         glDisableClientState(GL_VERTEX_ARRAY);
 577         glDisableClientState(GL_TEXTURE_COORD_ARRAY);
 578 }
 579
 580 static void gen_quad_plane(QuadMesh *m, float width, float height, int usub, int vsub)
 581 {
 582         Vec3 *vptr;
 583         Vec2 *uvptr;
 584         uint16_t *iptr;
 585
 586         if(usub < 1) usub = 1;
 587         if(vsub < 1) vsub = 1;
 588
 589         int uverts = usub + 1;
 590         int vverts = vsub + 1;
 591         m->num_verts = uverts * vverts;
 592         m->num_quads = usub * vsub;
 593         m->num_idx = m->num_quads * 4;
 594
 595         vptr = m->v = new Vec3[m->num_verts];
 596         uvptr = m->uv = new Vec2[m->num_verts];
 597         iptr = m->idx = new uint16_t[m->num_idx];
 598
 599         float du = 1.0f / (float)usub;
 600         float dv = 1.0f / (float)vsub;
 601
 602         float u = 0.0f;
 603         for(int i=0; i<uverts; i++) {
 604                 float x = (u - 0.5f) * width;
 605                 float v = 0.0f;
 606                 for(int j=0; j<vverts; j++) {
 607                         float y = (v - 0.5f) * height;
 608
 609                         *vptr++ = Vec3(x, 0, y);
 610                         *uvptr++ = Vec2(u, v);
 611
 612                         if(i < usub && j < vsub) {
 613                                 int idx = i * vverts + j;
 614
 615                                 *iptr++ = idx;
 616                                 *iptr++ = idx + vverts;
 617                                 *iptr++ = idx + vverts + 1;
 618                                 *iptr++ = idx + 1;
 619                         }
 620
 621                         v += dv;
 622                 }
 623                 u += du;
 624         }
 625
 626         glGenBuffers(1, &m->vbo_v);
 627         glBindBuffer(GL_ARRAY_BUFFER, m->vbo_v);
 628         glBufferData(GL_ARRAY_BUFFER, m->num_verts * 3 * sizeof(float), m->v, GL_STATIC_DRAW);
 629
 630         glGenBuffers(1, &m->vbo_uv);
 631         glBindBuffer(GL_ARRAY_BUFFER, m->vbo_uv);
 632         glBufferData(GL_ARRAY_BUFFER, m->num_verts * 2 * sizeof(float), m->uv, GL_STATIC_DRAW);
 633
 634         glGenBuffers(1, &m->ibo);
 635         glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, m->ibo);
 636         glBufferData(GL_ELEMENT_ARRAY_BUFFER, m->num_idx * sizeof(uint16_t), m->idx, GL_STATIC_DRAW);
 637
 638         glBindBuffer(GL_ARRAY_BUFFER, 0);
 639         glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);
 640 }
 641
 642 static void spawn_particle(const Vec2 &pos, const Vec2 &vel, float mass)
 643 {
 644         int gidx = pos_to_grid(pos.x, pos.y);
 645
 646         if(grid_part[gidx]) {
 647                 // merge with existing
 648                 Particle *p = grid_part[gidx];
 649                 p->vel += vel;
 650                 p->mass += mass;
 651                 p->radius = MASS_TO_RADIUS(p->mass);
 652
 653         } else {
 654                 Particle *p = alloc_particle();
 655                 p->pos = pos;
 656                 p->vel = vel;
 657                 p->mass = mass;
 658                 p->radius = MASS_TO_RADIUS(mass);
 659                 grid_part[gidx] = p;
 660
 661                 add_particle(p);
 662         }
 663 }
 664
 665 static void add_particle(Particle *p)
 666 {
 667         if(plist) plist->prev = p;
 668
 669         p->next = plist;
 670         p->prev = 0;
 671         plist = p;
 672 }
 673
 674 static void remove_particle(Particle *p)
 675 {
 676         assert(plist->prev == 0);
 677
 678         if(plist == p) {
 679                 assert(p->prev == 0);
 680                 plist = p->next;
 681         }
 682         if(p->prev) {
 683                 p->prev->next = p->next;
 684         }
 685         if(p->next) {
 686                 p->next->prev = p->prev;
 687         }
 688         p->prev = p->next = 0;
 689 }
 690
 691 // particle allocator
 692 #define MAX_PFREE_SIZE  256
 693 static Particle *pfree_list;
 694 static int pfree_size;
 695
 696 static Particle *alloc_particle()
 697 {
 698         if(pfree_list) {
 699                 Particle *p = pfree_list;
 700                 pfree_list = pfree_list->next;
 701                 pfree_size--;
 702                 return p;
 703         }
 704
 705         return new Particle;
 706 }
 707
 708 void free_particle(Particle *p)
 709 {
 710         if(pfree_size < MAX_PFREE_SIZE) {
 711                 p->next = pfree_list;
 712                 p->prev = 0;
 713                 pfree_list = p;
 714                 pfree_size++;
 715         } else {
 716                 delete p;
 717         }
 718 }