Thanks, guys. Very informative, especially since I checked and compression will not be covered in my remaining coursework, nor have my professors always been very helpful on saying where an application of the material will be practical anyway (but I did check the documents section; that is literally the first place I checked... nothin doin )
In the spirit of sharing, I’m going to talk about something that’s more related to game development than to hacking: a little data structure called the quadtree
. A quadtree is a kind of tree where the branch nodes have four children (leaves, as usual, have none). As the helpful image from Wikipedia shows, you would generally subdivide a 2D space into four quadrants, then subdivide as necessary until all the nodes have as much detail as you want. Basically, the octree’s hot 2D cousin.
This is not strictly an algorithm in itself, no, but it lends itself to tasks like spatial indexing. It works well when it wouldn’t do to not index and a simple 2D grid would not be sufficient.
The peril of not indexing: A simple distance calculation between objects is not too expensive. For circles, you don’t even need the strict distance; you can just compare the squared differences in coordinates with adjustments for radii. But it is more expensive if you go beyond representing everything as a circle, and when you have a lot of things to test... well, if you were to test every object against every other object, you would have to perform (n2
)/2 tests (it’s the handshake problem). That said, if you know that’s not going to be a problem, you probably don’t want to add the complexity.
Why a grid might not work: A grid is good and well if you know the objects are going to be spaced reasonably uniformly. You can optimize out more expensive tests by first using the “manhattan distance” (bad name, everyone who’s ever gotten a good look at a map of the island knows the blocks are longer one way; other names for it are incredibly awkward, though). The problem is that in video games, that’s hardly a guarantee. What you tend to have is some empty spaces over here, and some crowded spaces over there. That said, if you know that’s
not going to be a problem either, then you probably don’t want to add the complexity.
When you have items placed in a quadtree properly, however (and that is not trivial and is left as an exercise to the reader, but in collision detection what isn’t?), you can simply use the spatial properties of the tree to partition out your collision detection. Objects only need to be tested against other objects related to their tree’s node (all descendants, but only direct
Barring any subtleties that may arise (this is mostly helpful with static frames, for instance; it doesn’t take motion into account, so it won’t help with the “bullet through paper” problem or anything), the main tradeoff is that this is definitely overhead (I’ve seen recommendations to rebuild the tree per frame; not sure that’s strictly necessary, but haven’t gotten to test that hypothesis yet). In a good number of games, this simply won’t be a necessary optimization. Still, there’s other neat stuff you can do with this data structure, not all of it relevant to games.