2
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ 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/… \$\endgroup\$ – DaleyPaley Jun 5 '13 at 5:53
  • \$\begingroup\$ @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. :) \$\endgroup\$ – Mario Jun 5 '13 at 8:54
5
\$\begingroup\$

Since your game is 2D, I would recommend using QuadTrees.

Here's a good tutorial to get you started: http://www.kyleschouviller.com/wsuxna/quadtree-source-included/

Another good one: http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

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