Nerd Paradise : Coding Interview 10: Efficient and Scalable Sprite collision

Nerd Paradise : Coding Interview 10: Efficient and Scalable Sprite collision

Consider a list of sprites. Suppose these sprites are in a game on a GIANT map. It's not a particularly crowded map, but because the map is SO huge there are thousands of sprites. Write a collision detection algorithm.

Yes, I really was asked this question once in an interview for a non game development position. It's a great basic-understand-of-data-structures question.

The common solution

For simple games with dozens of sprites on a screen, it's not a horrible approach to simply check each sprite with every other sprite and see if there are any collisions. That is a O(n²) algorithm and that's pretty acceptable when your data set can be described as "dozens".

For large data sets

Once you get to the point where you've got hundreds upon hundreds of sprites, O(n²) is no longer good enough. You need something that's, at most, O(n). For this, we use virtualized buckets.

First, create a function that converts a sprite's location into a list of coordinate keys. Each key represents a small-ish region of the game map that you have gridded off. If it's a 2D game with sprites that are generally 50 pixels wide and tall imagine a grid partitioning the world every 250 pixels. If there's a sprite whose X,Y coordinates are (625, 375), then that sprite would be in the middle of the sector in the 3rd column, 2nd row. Its coordinate key may look like "3_2". If he partially overlapping the edge of a grid sector or even standing on the intersection two grid lines, then this function would return 2 or 4 keys, accordingly.

Now that you can quickly describe where on the map a sprite is, create a lookup hashtable/dictionary. This lookup table has string for keys and lists of sprites as values. Go through your list of sprites and figure out which coordinate keys they create. If the lookup table doesn't have an entry for that key, create a new list of sprites and add the sprite to the list. Otherwise just add the sprite to the existing list. And remember, sometimes sprites can be added to multiple buckets.

Now that you've looped through the list once, you have a dictionary of keys with lists of sprites. Remember how I said the game world isn't crowded? That means these lists typically have 1 sprite or sometimes 2. Occasionally you'll have more. But the point is there aren't many. If you loop through these buckets, you only need to check the sprites against other sprites in the same bucket. With no more than a few sprites in each bucket, this makes the complexity linear.

Read full article from Nerd Paradise : Coding Interview 10: Efficient and Scalable Sprite collision