Login | Register

Nerd Paradise

For the last time, it's called "soda". Not "pop".

Coding Interview 10: Efficient and Scalable Sprite collision

Post by: Blake
Posted on: 11 Vigeo 10:0 - 1.23.50
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(n2) 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(n2) 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.

cs_interview_sprites.png
1_1 : { A }
4_1 : { B }
2_2 : { C }
3_2 : { C }
4_2 : { B }
2_3 : { C, F }
3_3 : { C }
4_3 : { D, E }


In this particular example, there are only two buckets where there are multiple sprites. All other buckets can be ignored because they will not produce collisions. This means there are only two comparisons between pairs of sprites. If they were all compared against each other, that would be 15 comparisons. Of course there's quite a bit of overhead you need to do to get this benefit, but it scales in a mostly linear fashion.

The complexity goes up when they all form a mosh pit, but not worse than the common solution of comparing each sprite with each other sprite.
facebook twitter Stumbleupon Reddit del.icio.us Digg
User Comments: 0
No comments yet. You could be the first!
You must be logged in to add a comment
Current Date: 14 Vigeo 0:0Current Time: 13.65.57Join us in IRC...
Server: irc.esper.net
Channel: #nerdparadise
Your IP: 54.82.211.237Browser: UnknownBrowser Version: 0