   Particle Collision detection
  Hey all! [smile]I recently started working on a new project. In it, the whole ground is made up of 2x2 pixel particles, which act as a grain of dirt. At this point, they are affected by gravity, and will stop when they touch the bottom of the screen. However, I don't want them to just stop if there Y position is bigger than 550 pixels - rather, I want them to detect collision with each other, and when hitting an other dirt particle, they will stop on top of the dirt particle below it. And this brings me to the point: What are the most efficient solutions for detecting collision with a few 1000 particles? Right now the best I can think of is having the particles in a few vectors, with each of these vectors representing a vertical slice of the screen. Then we check only on those vectors if it is touching another particle.What would you guys do? Thanks in advance, Pseudobot.   
  Is this for sand game?I never really looked into it, but if I had to guess I'd say those use cellular automata, similar to game of life.On each iteration, go through entire board. Check the neighbors of each cell, and act upon it. For gravity, you'd simply check if there is anything in cell directly beneath, then either move the particle, or keep it in current position.   ;  Yes, the mechanics for the ground are pretty similar to the sand games.However, with your method, how exactly will I know which particle is directly below the current one?   ;Quote:However, with your method, how exactly will I know which particle is directly below the current one?Entire world is a 2D array, where each cell represents the type of particle. To simulate next time step, iterate over all cells, and choose what to do for each one. You'll note that falling sand games run at constant FPS, not depending on number of particles.For gravity, the immediate problem is that if you have two particles falling down right one on top of another, they cannot be simulated in single pass. The one on top would see that there is something beneath, and wouldn't move.A way to solve it that comes to mind is to use multi pass algorithm. On first, determine which cells are subject to gravity (empty cells for example aren't). On second pass, do bottom to top pass to determine which particles will or won't move. On third, actually move the particles.Since you're working from bottom up, if some particle hits the ground (force is 0, determined in first pass), the gravity array will be 0. The scanline above would see that particle beneath is not an empty cell, but that force is 0 and it can't move. So you set the cell to 0 as well.This then propagates, setting the force of entire gravity array to 0 for particles that cannot move since they collided.On third pass, just apply the forces from gravity array.There might be more optimal ways to code this, check the wiki entry and the Falling Sand Game forums for discussions on implementation details. There's various source code available as well, but I haven't checked it.The physics are very simple for these, they aren't really physics, just something that simulates the expected behavior.   ;  Sweet, splitting the entire world into cells works like a charm.:)   