I have created a linked list (Not using STL) to manage my sprites. At the moment I am using simple console output to get the hang of this, but would like to know how to manage collision etc. I am creating a small Space Invaders style game, and might have about 50 enemies on the screen at once. I am also going to use my list for the bullets the player character uses. How do I efficiently manage collision? * Do I read through my bullets list, and for each bullet check the enemies list with the coordinates of the bullet? If I have more than 10 bullets does this become inefficient? Someone mentioned trees, but as I have only just started to understand how a linked list works I think that that is a little beyond me (I took a small look at the tutorials section on this site) I haven't programmed a game before, and hopefully can make something of this program. Also, how do I draw the sprites to the screen? Do I return a type that holds the sprite information for my drawing routines to render, or do I contain my render function within the list class itself? I know render isn't the correct term considering I am using text output.. but eventually I will be drawing stuff Any help is much apprectiated, thank-you. =*= If things seem bad, think that they can get a whole load worse, and they don't seem so bad anymore =*= [edited by - hammerstein_02 on June 3, 2002 12:02:18 PM]

This is how I would suggest implementing your game. Have a BulletOnScreen list and an EnemyOnScreen list. Every frame, loop though the bullet list, and check if that bullet has intersected an enemy on the screen (just use bounding box collision to begin with). If so, kill the enemy and bullter (ie, remove them from the list). Do not worry about this with respect with speed. You won''t notice a difference from having 10 enemies or having 10,000 enemies.

Your speed concerns should be with drawing the graphics. To draw, just loop through both lists drawing everything that is on the screen.

computers are so fast now that you can''t possibly notice the difference with 50 eneimes and 10 bullets between using brute force and a more sophisticated algorithm. rule one is always profile before you optimize, or you are wasting your time.

to answer your question though, assuming a very large number of collisions, you could use some form of spatial partioning (quadtree, radix sort along one axis, etc) to divide the space up into little pieces. each piece of space keeps a list of enemies in it. now the bullets need only be checked with other objects in the same piece of space.