Hello. I'm making a sort of simulation that will eventually become a game, but it involves large numbers of small particles, and more importantly, I need to know roughly when they hit each other (I'm considering the particles squares for my purposes, and it works fine). Currently I have a system set up with around 2000 particles, but its getting really slow. Can I reasonably expect to increase the amount of particles to at least 5000 without much lag? Here's my current setup, please tell me how I can improve.. nested 'for' loop, can't really explain.. like this. for (int x=0;x<numParticles;x++){ for (int y=x;y<numParticles;y++){ //notice the y=x if (certain condition){ if ((d[y].x>d[z].x-5)&&(d[y].x<d[z].x+5)&&(d[y].y>d[z].y-5)&&(d[y].y<d[z].y+5)){ //is there a faster way to see if the dots are touching? do collision stuff here } } } } I would really like it if I could get this to go a bit faster, thanks for your help! ~Adam~ P.S. I got a second idea, let me know what you think! I could have a 2d array set up, around 300x300. The array could hold 0 for no particle, 1 for 1 type, and 2 for the other. Then, I would just have to check the surrounding 'slots' of the array for particles. Would that speed it up at all, do you think?

Well it would probably be faster to consider the particles spheres. That way you can do a single comparison instead of four. All you need to do is pick a radius for your particles, and check if the distance between the centre point of any two particles is less than the radius. If so, they are touching or intersecting.

Also you can use the distance squared to avoid having to take a square root:

if (DistanceSquared < RadiusSquared*4){   // collision}

The above assumes that each particle has the same radius.

The simplest thing to do would be to compare every particle to every other particle. To speed it up you might consider dividing your world up into chunks: spheres, cubes, whatever. When you move your particles, put them into an appropriate chunk (should be a quick operation: just use the particle coordinates to pick the chunk -- it's sort of like hashing, in a way). That way you only have to compare particles which are near each other.

cheers
sam

[Edited by - izzo on June 20, 2005 12:24:15 AM]

It looks like you're using a rectangular boundary for your sprites, right? For when you're doing the collision detection?

It would probably be faster if you converted to a spherical boundary. Then all you need to do is subtract the two particle xyz position vectors and find the magnitutde of that difference. If the magnitude is less than the sum of the particle's radii, then they've colided.


.. I think... someone correct me if I'm wrong.

Algorithmically, what would really speed things up is a dynamic OcTree. (Or something similar)

Basically, this would reduce the calculation time from
"NumParticles * (NumParticles / 2) * Comparison Time" (Algorithmically O(N^2))
To
"NumParticles * ln(NumParticles) * Constant" (Algorithmically (approx) O(N ln(N)))

Basically, if you use an algorithm like this you shouldn't be surprised at improvements on the order of 100s of times faster with enough particles. ln(base 2)1024 = approximately 10.



An OcTree is basically a tree of cubes, where every cube can contain up to 8 cubes , one for every combination of top/bottom, left/right and front/back. Each cube is 1/8 the size of the parent cube, hence the name OcT.

One way to use OcTrees that works well in situations like yours is to specify a maximum number of points that can occupy a cube (eg 10). Once more than 10 objects are placed into a cube, it is split into it's 8 constituent sub-cubes, and the points sorted into the correct sub-cube.

When you want to check any point you just consider the cube it resides in and the neighbouring cubes that are near enough to have points that may effect the point you are currently checking.

An OcTree will require quite a bit of high-quality techical code. There are probably OcTree implementations you can download, and there'll be good tutorials somewhere on the world-wide google.

A Dynamic OcTree (One which doesn't have to be rebuilt every frame) is even trickier, but yet faster still.

------------------------------------------------------------------------
If an OcTree is too bulky, you might consider a simple 3-dimensional array of cubes. Then when checking a point you only have to consider the cube it occupies and, at most, all the neighbouring cubes (3x3x3 = 27 cubes).
Each cube will require something like a linked-list to store all the points that it holds. A linked-list is probably the best method.


Hope it helps

Hey, thanks. Actually, this is in 2d, so it won't be quite as complicated :)

I think that I'll try a grid of squares, each with a linked list. I've actually made a linked list VERY recently, so that sounds great to me. Thanks very much for your help! Rating++

If it's 2D, you might want to look into a Quadtree. Which is like an OcTree, but 2D.

You split your surface up into a 4 sections, and each of those sections contains another 4.. it's exactly the same concept as the OcTree Krylloan mentioned, just in 2D.