   Searching for collision
  Hey, first post here :)I'm a programmer with proffesional experience and I'm trying to get started with making games. I've looked at a few guides and comprehending the programming side of them is no big deal.Right now I'm practicing with a 2D game example I grabbed online. The collision detection this example provided was a simple brute force method that started to show its weakness after 40 sprites appeared on screen at once. I read some guides on collision detection, and while I understand the concept, there was some disconnect that I'm hoping I can ask about here.For 2D sprites using bounding boxes, the suggestion is to only check for collision on one axis. If one axis collides, then check for the other axis. The question is how do I effeciently iterate through all of my sprites to make this check?I had some ideas, but before laying down 15 hours of code I wanted to hear from people who have actually done this successfully.My initial idea was to sort the sprites based on one of the axis, and doing a simple binary search I'll only examine sprites close to the sprite in question. As sprites move I would have to continuously resort the axis. Am I on the right track here?   
  Sorting along one axis is definitely one possibility. What I usually do for my projects, though, is implement a quad tree. This is a data structure that partitions space much like a binary tree can partition a line. If you have a 100x100 world, for example, then the top node contains the entire world, and four children that are each 50x50. Those four children contain four more children each that are 25x25, and so on until you decide your children are small enough. At each level, you store all of the objects that can't fit any deeper (because they straddle an edge between two children).Quad trees are also useful if you have a scrolling map, since the same logic that works for "what objects intersect this object's bounding box" works for "what objects intersect the camera view". I have a Python quad tree implementation that you can read through as a reference here (open-source GPL).   ;  Thanks thats a huge help. Just so I'm understanding the concept... Even with the quadtree method, I still have the burden of updating the sprites around the tree as they move on screen, correct? Similar to the "sort" problem of my first idea?   ;  Yes. That's what the rebalanceTree function in my implementation is for. The correct data structure for your game will depend on what your game objects are doing. Quadtrees are good generic datastructures, but if your game only ever has, say, 20 moving objects at a time, they're overkill. They also don't gain you much if all of your objects are always very close together, for example.   