Collision detection with many objects

[The_Mezentine]

So I'm still getting a handle on a lot of elements of SFML and I've got a few questions that I'm grappling with. I've been working with the Collision Detection methods laid out here: https://github.com/SFML/SFML/wiki/SourceSimpleCollisionDetection

Now this is great as long as I've got two objects to compare collision with, but if I'm working on say...a Breakout clone (I am) things get messier when I've got twenty objects on screen.
It would be easy to write a base SolidObject class, derive both the paddle and the bricks from that class, and make an array of SolidObjects containing one game's worth of paddle and bricks. From there I could scan through each element of that array, check for proximity to the Ball and if they're close enough pass them to one of the Collision methods. The problem is that that seems woefully inefficient, especially if I'm running it every frame. What about if I had fifty elements? Or a hundred?

I'm really looking for basic advice here, for anyone who has done major work with collision detection before. A direction to look in, an idea to try, any of that. Ideally what I'm looking to make is some kind of system that only looks at objects in close proximity to the Ball from the start, so that I'm not cycling through a huge array every time.

[Nexus]

The problem is that that seems woefully inefficient, especially if I'm running it every frame. What about if I had fifty elements? Or a hundred?

50 and 100 are still few objects. Colliding them is hardly a performance bottleneck. But of course it is wise to think about collision detection and response algorithms that scale better with the amount of objects. O(n^2) is bad scalability.

When your shapes involve complex collision that require a lot of time to compute, it might be worthwhile to perform a rough test if an object is even a candidate for collision (i.e. AABB). Only if this (fast) test is true, the exact collision detection algorithm runs. This doesn't reduce the amount of collisions totally performed, but it avoids unnecessary expensive operations.

We have recently had a similar discussion. But before you make your life overly complicated, there should be a need for the performance (and as I said, I don't think there is one in your case). Unless you are interested in the algorithms themselves and like to know how to deal with such issues in general.

It would be easy to write a base SolidObject class, derive both the paddle and the bricks from that class, and make an array of SolidObjects containing one game's worth of paddle and bricks.

That might be easy in the first term, but just out of interest: How would you find out which collision function to call, depending on the types to check; e.g. paddle <-> ball, brick <-> ball, ball <-> ball (in case of multiple balls)?

[OniLinkPlus]

For algorithms to greatly improve the performance of collision detection, I would first use a quadtree or something similar to drastically reduce the number of objects that you check for collisions. Then use an AABB collision check to rule out any impossible collisions within the regions of the quadtree that are being checked against. From there, use an exact algorithm to determine if there really are any collisions.

[The_Mezentine]

Thanks for the response. You're right, 50 and 100 are still fairly few objects, but if I were to expand this into something like a simple platformer there might be upwards of 2000-3000 blocks in a "level" and it seems downright wasteful to check if the player sprite is in collision with every single block in a stage every frame. Note that I'm not comparing every object to every object here, just a few "mobile" objects against immobile objects and other mobile objects.

That might be easy in the first term, but just out of interest: How would you find out which collision function to call, depending on the types to check; e.g. paddle <-> ball, brick <-> ball, ball <-> ball (in case of multiple balls)?

The plan in that situation would be for each object to have a type identifier member. The actual Collision methods I linked to above would just be for determining if a collision exists, and the specific implementation for each different type of object would handle the multiple types of collisions. Basically a three step process:
1.)Scan the object array looking at coordinates to determine proximity.
2.)Run collision on objects in close proximity.
3.)If collision returns true, access the type member of the colliding object and preform the appropriate action.

I'll check out the link you posted as well. You're right that this isn't a problem for the scope of my current project, but I am very interested in the theory behind a more robust algorithm, since that's what I'm going to need if I ever scale my projects up to something truly large.

EDIT: Looking at some articles on Quadtrees and Space Partitioning. I'm not seeing a solution to the problem of having to examine the co-ordinates of every object in existence every frame, even if Quadtrees and SP seem to help with the proximity issues. Am I missing something, or is that just how things have to work?

EDIT2:Okay, this is interesting:

The QuadTree is designed to be faster at querying the spatial domain than iteration, but the performance of the index depends on the distribution of objects in the domain. If items are clustered together, the tree tends to have many items in one branch which defeats the strategy of being able to cull large regions, and reduce the number of intersection tests.

Culling large amounts of space isn't a problem in my system, since things aren't organized spatially. I don't expend time looking for empty regions since I'm iterating over an array filled with solid objects. So I'm not sure if the QuadTree is going to be very helpful specifically. What does interest me though is finding a way focus the search over time, to hone in on objects in proximity to the test object, and not spend time checking the co-ordinates of other objects. To do that I'm pretty sure I need a tree structure so that I can ignore branches. Perhaps initiating a one-time organization system once all objects have been created...