I''m writing a 2D scolling game to get a hang of things which can be best described as Zelda 2 during the side scrolling areas (you can walk left/right, jump etc.). As of now, I have a "block layer" which is built up by tiles. These tiles block any movement, so these will most likely be used to create walls, grounds and ceilings. Right now I have a player / character which can walk around, jump and duck in a room with a block layer like this. I have decided that each "game object" (including player) during one "tick" in the game engine should never really alter its absolute screen position but should instead controll its movement by changing its movement speed in the x and y axis. The game engine then changes the game object''s position according to these movement variables'' values. By doing this, it was simple to add things like gravity and jump, like in the later case I only needed to set the movement speed along the y axis to some number and the player will automatically go up and then fall back because of the gravity. Anyway, this part described above works fine (player moving along in a room with a block layer). I now obviously want to add other moveable objects, other "game objects". They should all be able to interact with each other. I have been thinking quite a lot on how to implement this both efficiently and easily. Bascially, my problem can be reduced to the following. Say I have a list with n game objects. During each tick in the game engine, I now want to update all these n objects'' speeds (and thereby positions) and also check if they collide with anything. One obvious solution would be to do something like: for all game objects update current game object''s speed check if game object intersects with any other game object This seems to be very ineffecient to me, O(n^2). One could speed things up a little by for instance only checking for collision with game objects *after* the current one in the list (since any collision with objects before in the list has already been checked), making the algorithm O(n^2/2), but still O(n^2). I figured that perhaps I could divide the "world" into smaller areas, keeping track of in which game area each object is (possibly several due to overlap) and then only check for collisions in the current area(s) every object is in. But this only helps the best case scenario, as it will still be O(n^2) in the worst case. Perhaps there is no other way. I can''t think of any anyway. To make collision detection simplier I have at least decided that all game objects will have a non-rotatable rectangual shape, so that all you have to do is to check whether two rectangual shapes interect or not. I just realized that this became a large post and I hope anyone bothers to read all this, but any help would be appreciated.

Maybe he has NPCs that crafts or practise disciplines...