7
\$\begingroup\$

I am building a MMO game server for a 2D game and am currently implementing the collision detection, and I am would like to know what I should do.

Lets say I have 1000 players playing and 10,000 objects, should I just iterate over them all to determine if colliding? This seems a bit pricey.

I could separating the world into chunks and iterating every object for each player in it's chunk.

I would like to know some other ideas or what is standard. What's the best way for a MMO server to handle collision detection with static objects?

Improve this question
\$\endgroup\$
1

1 Answer 1

Reset to default
14
\$\begingroup\$

  1. The world being separated into chunks is indeed the first step you should take, with each chunk being handled separatedly.

  2. Static objects? Purely static in the sense that they never move, and never disappear? Then you could simply incorporate these objects into whatever data structure you're using for player navigation in the world (such as a grid, navigation mesh or visibility graph). No need for doing any individual collision detection. This could be done manually by the designers, or automatically by the engine as a preprocessing step of the content pipeline.

  3. If on the other hand you'd like to actually perform collision detection between dynamic entities inside each chunk, depending on the expected amount of simultanous entities you might benefit from using a spatial partitioning data structure (such as a quadtree or a grid) to reduce the amount of entities that need to be iterated. In general, research the broader topic of broad-phase collision detection (no pun intended) which includes the aforementioned spatial division techniques as well as other approaches such as sweep and prune.

Improve this answer
\$\endgroup\$
8
  • 3
    \$\begingroup\$ Side note: a subset of all physics engines is utility for detecting collision, even if you don't use physics to move you can still use the collision detection if you don't want to write your own. \$\endgroup\$
    – Patrick Hughes
    Jan 3, 2012 at 3:02
  • 1
    \$\begingroup\$ @PatrickHughes True. A couple years ago I spent hours trying to get OBB-OBB intersections working correctly using the separating axis theorem. Then in 5 minutes I dropped Box2D in and solved the problem. \$\endgroup\$
    – David Gouveia
    Jan 3, 2012 at 3:06
  • \$\begingroup\$ Not to mention they already implement broadphase for you. \$\endgroup\$
    – David Gouveia
    Jan 3, 2012 at 3:43
  • 1
    \$\begingroup\$ Is it practical to 'turn off' all the other calculations in a physics engine to facilitate this? Often you don't want to try and perform proper physics on an MMO server because objects regularly move in a discontinuous manner. \$\endgroup\$
    – Kylotan
    Jan 3, 2012 at 14:30
  • 1
    \$\begingroup\$ I said nothing about twitching or 'weird', but MMO objects often need to move discontinuously because you need to snap them to certain positions, eg. for teleporting/zoning, or for correcting bad predictions and speed hacks, etc. I haven't used physics packages in years but back then it was typically quite difficult to handle arbitrary movements like that, hence my question. \$\endgroup\$
    – Kylotan
    Jan 4, 2012 at 11:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .