 |
Author |
Topic: Optimizing particle collision system algorithms (Read 956 times) |
|
moving_ninja
|
Optimizing particle collision system algorithms
« on: Jan 19th, 2005, 7:06am » |
|
Ez,
got a question regarding simple particle collision systems that scale really well. At the moment im working on some code the generates a bunch of particles, places them all over the place and sends them flying around into each other. To detect a collision though, each time a particle moves.. it checks its position against every other one and changes its direction accordingly. This method works ok for a small number of particles(~2000) but when increase to say 20000 it just lags completely.
Just wondering if anyone had any ideas as to how to optimize the algorithms in these systems as im sure from some of the work ive seen that its possible to have more than 2000 particles interacting with each other.
The method im using to detect a collision right now is this:
void collision(Particle replicant)
{
int rep_id = replicant.pid;
for(int i=0;i<cells;i++)
{
Particle temp = swarm[i];
//check it is not the same particle
if(temp.pid != rep_id)
{
//this just compares xy values
if(replicant.condition(temp))
{
//change direction
swarm[i].dirX*=-1;
swarm[i].dirY*=-1;
this.dirX*=-1;
this.dirY*=-1;
}
}
}
}
I'd be really interested to hear whatever ideas people had on this.. checking a collision seemed like the simplest way for particles to interact and im hoping this system can be modified later to create emergent/swarm systems which at the moment seems computationally infeasible using my current design..
all the best,
mn
|
http://www.movingninja.com
|
|
|
toxi
|
Re: Optimizing particle collision system algorithm
« Reply #1 on: Jan 19th, 2005, 11:37am » |
|
if these are only 2D particles, i'd recommend using a so called quadtree to divide the entire space recursively. every particle will be assigned to a node in the quadtree, based on its position. then when moving a particle, you only need to check all the other nodes in its neighbourhood (i.e. particles assigned to the same tree node) and then update the references/positions in the tree. i've got a generic lingo (director) implementation on my website, it's only a few dozens of lines of code and shouldn't be hard to convert it to processing. here's the script:
http://toxi.co.uk/zips/quadtree.zip
alternatively, if the particles are in 3D space, you'd use an octtree instead.
|
http://toxi.co.uk/
|
|
|
moving_ninja
|
Re: Optimizing particle collision system algorithm
« Reply #2 on: Jan 20th, 2005, 12:39am » |
|
Cheers for the info and the code.. I knew there was something wierd about trying to do the whole thing using a normal array.
|
http://www.movingninja.com
|
|
|
|
