Sorting objects in 2d space

[{MSX}]

Hi! i've some object in a 2d space. I want to make collision detection, so in teory i have to test each one with all other objects.
Obviously this is too expensive.. i was wondering how can one optimize the control.
Are there solutions to this?

I've had this idea, but i don't know if it's the best (probably not :P ):
I could keep all objects sorted by one coordinate (for example X), and then check each object only with some neighbours.. For example i could check in each "direction" until i find an object that is far enought in the X coordinate to be surely not colliding.

[Almindor]

I am working on a 2d arcade "shootem up" game and I have had no problems with speed in my department. Since I do software rendering(SDL) all CPU power which get's used is the refresh part. In any case I use 2 things.

Layers: if you can, layer objects which can hit themselves into lists(use arrays if you require superspeed)

Constant Y sorting: I do this, but not because of collision per se, but to see which get's blitted when. (I can "hide" behind objects with player). I use a typical bubblesort for this with "cancel" and "backtrack" effect.
Typical requirement is O(n + # of exchanged positions)
So if nothing changes it's a O(n) pass. I tested it and it was MUCH better than with original quicksort. But it depends on situation.

However as I sayed, unless you really do stuff ALL the time(no pause, or max. framerate) your game will take almost 0CPU without refreshing the screen and blitting(just try it for fun :) )

[Almindor]

One last thing which comes to mind.

If you're a real performance freak and need that sorting, you can do a linked-list.

You give every object on the scene a "previous" and "next" in terms of for example Y. Then if it moves, it will check recursivly in the "previous" or "next" direction until it finds bigger or lesser Y and then shifts.

[cairnswm]

The way I do collision detection in my games is to create an array that covers my internal map. This array is usually not the same size as the actual map but broken into a number of smaller squares.

For example my RunAWar map consists of 30x30 tiles but the internal collision array is 60x60 (probably should have been 90x90).

Each object registers itself in the collision array. (So an Orc standing at pixel point 400,400 tells the collision array point 20,20 he is at that square). Each object when it moves checks the collision square it wants to move to to check if there is something there (So elf at 390,380 moves SE and checks the new block it wants to move to (which is 20,20) and finds the orc there).

If the space an object wants to move to is empty then he deregisters himself from the current collision array location and reregisters himself in the new collision array location.

Objects also do not need to be allocated to only a single collision array location. The ruins and buildings in RunAWar all take up 15 collision locations.

This way the number of objects in the 2D space have no impact on the performance of your collision checking. In addition by adding a 'Movable' tag to my objects, immovable objects have no impact on the game performance (except rendering) at all.

Typically my collision array consists of two values, a passable value and the object that is in that position. This could easily be expanded to a movement cost value or even an area of influence.

The collision array is also very useful for doing pathfinding as all passable/blocked locations are already available to you.

[lief]

Split the screen or area into a large grid, and check to see if they are in same grid square, if they are then check to see if bounding boxes overlap, if they do then do per-pixel checking if you like. I just use a get distance function for most things though, if its under a certain distance then do more accurate check if needed.
if you want you can also have a moved flag set for objects, if an object hasn't moved, don't run checks. lastly, maybe a variable frequency limiter - if the object is moving slower then it doesn't need to check as often.
you will find that unless you have thousands (or many hundreds at least) of objects it will not slow your game down much with the speeds of computers these days.
you will find better areas you can optimize your code to gain more speed.

[cairnswm]

Any method that requires multiple checking per movement will slow the system down at some point. My method (which will work in any 2D space) has a lower impact.