Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

What would be the best way to implement gravity if I have a list of different "surfaces" which if the player is on top of acceleration will stop? Would there be a better way than to loop through all of the surfaces on the map and see if the player is colliding with it?

BTW, I'm using XNA Game studios, but pseudo code is fine.

share|improve this question

marked as duplicate by John McDonald, ClassicThunder, Anko, bummzack, Sean Middleditch May 30 '13 at 0:26

This question was marked as an exact duplicate of an existing question.

What you're looking for is Spatial Hashing, and although you're (probably) asking about 2D, 3D stuff works the same way:… – John McDonald May 19 '13 at 5:49

Would there be a better way than to loop through all of the surfaces on the map and see if the player is colliding with it?

This is essentially the basic concept and pretty much the only way to do it overall. But besides this, there is space for optimization, what John simply called "Spatial Hashing".

The idea behind this is reducing the amount of calculations required to get to your goal, by not having to look at each and every element (essentially narrowing down the selection; which usually happens based on location/size).

So, we've got the "spatial" portion, but what about hashing? Hashing is essentially transforming some complex collection of data (like different rectangles or coordinates) into some shorter/more simple representation allowing faster comparison (e.g. rather than compare 4 values only compare 1).

Just some random assumptions to make this more clear, why it is important (this is intentionally naive):

  • Let's assume there are 1000 objects in our level. These could be blocks, platforms, power-ups, enemies, etc.
  • When the player moves, there are four positions being checked (feet, head, left, and right).
  • So every time the player moves (essentially once per logic iteration) you'll have to go through all 1000 objects and determine whether they overlap with one of the four collision points.
  • That means you've got 4000 checks per iteration. Now imagine you have to do this for more objects, not just the player, and this is getting out of hands pretty fast.

So how to optimize this? Lower the number of checks first:

  • You could determine whether some objects overlap at all, e.g. does the player even get close to that object? The most common principle for this is bounding box collision (collide boxes including the objects).
  • Now you still iterate over all 1000 objects, but before checking 4 points you just see whether the objects nearly touch/overlap. You're now down to 1000 comparisons! That's reducing overall processing time, unless the objects overlap all the time (which is very unlikely).

The next logical step would be creating categories for your objects (not always feasible). For example, you don't check an object for collisions unless it is explicitly defined as being some "collideable":

  • This check could happen before checking overlapping, but it could as well happen by defining different collections (so you don't have to iterate over non-collideables in the first place).
  • Depending on the amount of non-collideables, this might reduce the number of iterations by quite some margin.

But what happens if you've indeed got lots of collideables? For example, your whole map could be made of collision shapes, or maybe even some shown textures that require pixel perfect collision. Introduce some organisational grouping to allow smaller sub groups of elements:

  • There are different approaches available for this. If you've ever heard of "Balanced Trees", "BSP Trees", etc. this is where this is going. I won't go into detail and just explain a rather simple Approach.
  • Split your game world into multiple small parts. For example, split the map into different "Screens".
  • The world can still be continuous, this is just for organisational behind-the-scenes stuff.
  • To do this, add some additional array where each element can contain a number of objects (e.g. List<GameObject>).
  • Add the objects to this list based on their location in the game world. For example, objects in the leftmost part of the world would go into objectsByScreen[0]. Objects one screen further to the right would go into objectsByScreen[1], etc.
  • Now, to check collisions, you only look into these sub groups based on the player's current screen rather than iterating over all objects in your world/level.
  • Based on your design, complexity, etc. this might reduce the initial iteration over 1000 objects down to maybe 10. This is quite a lot!

However, there is one downside to this: Moving elements will give you quite some trouble, because you'll have to update the lists they're in, if they move around. To solve this there are different approaches: - Create another set for dynamic content that is updated/recreated once every frame (might be too ineffective based on the number of elements moving). - Store the "parents" for every object and only remove/add them just-in-time when required (e.g. moving over a boundary).

As for the actual implementation, that's really up to you, because it might as well depend on whether your game world is 2D or 3D.

share|improve this answer
Thank you, this is what I was looking for. – Josh May 25 '13 at 1:07

Not the answer you're looking for? Browse other questions tagged or ask your own question.