current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 2 down vote favorite
2

This question already has an answer here:

I am developing a 2D game with very large levels in which two teams(around 200 objects per team) fight against each other in planes, tanks, turrets,...etc. With every entity shooting bullets at their enemy it is expected that there would be a numerous amount of objects at one instant. What collision detection algorithm could I use to support collision for a massive number of entities at once? The objects are simple figures(rectangles and circles). Would a brute force approach suffice or break up the level into a grid?

share|improve this question

marked as duplicate by Josh Petrie♦ Jan 25 at 2:09

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
    
I would recommend a uniform grid if your levels are bounded. They are very simple to conceptualise, implement and fast to access. However, if your levels are too big, you should use a hash table to fill buckets. gamedev.net/page/resources/_/technical/game-programming/… –  DaleyPaley Jun 5 '13 at 5:53
    
@DaleyPaley You should add that as an answer, even though there's already an accepted one. People can still upvote it and the one asking might change their mind and pick it as the better one as well. There's no need to hide in the comments. :) –  Mario Jun 5 '13 at 8:54

3 Answers 3

up vote 1 down vote

If you have a bounded domain, then you can use a uniform subdivision. It is the simplest of all spatial subdivision systems.

However, if you have an enormous world, very sparsely populated then I would recommend spatial hashing. You simply use a hash map to fill buckets. It is fairly simply to implement, but you need a good hash function.

share|improve this answer
up vote 0 down vote

Other answers are surely worth a thought, but with just the tiny amount of 400 objects to test against, I would recommend you do profiling afterwards.

A simple brute force might turn out faster depending on your language and environment. Some runtime environments (like e.g. Java or Lua) might have blazingly fast array loops compared to very slow generic container like hashtables.

Of course, this is heavily dependend on how fast your collision tests with the actual objects are. Is some simple axis aligned bounding box checking or some sphere intersection enough? Or do you actually need to trace a 3D-ray against a mesh? (2D doesn't always means you don't have a third dimension where a bullet could go over some object..) *)

*) Edit: oh, I am sorry. You already mentioned that the objects are "simple figures", making my suggestion about a simple brute force even more interesting to try out.

share|improve this answer

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