Skip to main content
Game Development

Return to Answer

Commonmark migration
Source Link
Community Bot
Community Bot
  • 1

Preface: I'm not familiar with Box2D, but these structures can be found in Boost Geometry (R-trees) if you are really interested, as well as other libraries:

#Premature Optimization (Don't Do it)

Premature Optimization (Don't Do it)

Premature optimization leads to longer development times with no benefit, but many people consider micro optimizations to be the only cause of premature optimization when in reality it applies to more than that. Even higher level optimization can be time consuming and equally fruitless.

Do the easiest thing you can implement first, if it actually ends up being a bottleneck then optimize. For your test numbers, I doubt even the slowest solution you've suggested will matter in the slightest.

That being said, if you do actually find performance issues with any naive solution you've chosen...

#Spatial datastructures

Spatial datastructures

Instead of iterating for all entities for each player, use spatial hashing or other spatial data-structures that should already be used for broad phased collision detection.

This can be:

plus any extras I've missed.

With these methods, you should be able to retrieve the list of enemies mostly in range of sight (use final check to make sure that they are actually in range before sending) in times between O(log(N)*N) to O(N), much faster than your O(N^2) suggestions. The issue will be updating these structures upon both players and entities moving. You will have to figure out for yourself which of these structures will be better for your use case (you could probably also come back here and ask as well). Some will work better with static entities some will work better for moving, and you may be able to utilize box2d's broad phase collider.

You are essentially colliding a bounding volume (box or circle) of the players vision with the bounding volumes of the other entities, if it intersects then you send that information to that client.

Preface: I'm not familiar with Box2D, but these structures can be found in Boost Geometry (R-trees) if you are really interested, as well as other libraries:

#Premature Optimization (Don't Do it)

Premature optimization leads to longer development times with no benefit, but many people consider micro optimizations to be the only cause of premature optimization when in reality it applies to more than that. Even higher level optimization can be time consuming and equally fruitless.

Do the easiest thing you can implement first, if it actually ends up being a bottleneck then optimize. For your test numbers, I doubt even the slowest solution you've suggested will matter in the slightest.

That being said, if you do actually find performance issues with any naive solution you've chosen...

#Spatial datastructures

Instead of iterating for all entities for each player, use spatial hashing or other spatial data-structures that should already be used for broad phased collision detection.

This can be:

plus any extras I've missed.

With these methods, you should be able to retrieve the list of enemies mostly in range of sight (use final check to make sure that they are actually in range before sending) in times between O(log(N)*N) to O(N), much faster than your O(N^2) suggestions. The issue will be updating these structures upon both players and entities moving. You will have to figure out for yourself which of these structures will be better for your use case (you could probably also come back here and ask as well). Some will work better with static entities some will work better for moving, and you may be able to utilize box2d's broad phase collider.

You are essentially colliding a bounding volume (box or circle) of the players vision with the bounding volumes of the other entities, if it intersects then you send that information to that client.

Preface: I'm not familiar with Box2D, but these structures can be found in Boost Geometry (R-trees) if you are really interested, as well as other libraries:

Premature Optimization (Don't Do it)

Premature optimization leads to longer development times with no benefit, but many people consider micro optimizations to be the only cause of premature optimization when in reality it applies to more than that. Even higher level optimization can be time consuming and equally fruitless.

Do the easiest thing you can implement first, if it actually ends up being a bottleneck then optimize. For your test numbers, I doubt even the slowest solution you've suggested will matter in the slightest.

That being said, if you do actually find performance issues with any naive solution you've chosen...

Spatial datastructures

Instead of iterating for all entities for each player, use spatial hashing or other spatial data-structures that should already be used for broad phased collision detection.

This can be:

plus any extras I've missed.

With these methods, you should be able to retrieve the list of enemies mostly in range of sight (use final check to make sure that they are actually in range before sending) in times between O(log(N)*N) to O(N), much faster than your O(N^2) suggestions. The issue will be updating these structures upon both players and entities moving. You will have to figure out for yourself which of these structures will be better for your use case (you could probably also come back here and ask as well). Some will work better with static entities some will work better for moving, and you may be able to utilize box2d's broad phase collider.

You are essentially colliding a bounding volume (box or circle) of the players vision with the bounding volumes of the other entities, if it intersects then you send that information to that client.

Source Link
Krupip
Krupip
  • 1.8k
  • 13
  • 24

Preface: I'm not familiar with Box2D, but these structures can be found in Boost Geometry (R-trees) if you are really interested, as well as other libraries:

#Premature Optimization (Don't Do it)

Premature optimization leads to longer development times with no benefit, but many people consider micro optimizations to be the only cause of premature optimization when in reality it applies to more than that. Even higher level optimization can be time consuming and equally fruitless.

Do the easiest thing you can implement first, if it actually ends up being a bottleneck then optimize. For your test numbers, I doubt even the slowest solution you've suggested will matter in the slightest.

That being said, if you do actually find performance issues with any naive solution you've chosen...

#Spatial datastructures

Instead of iterating for all entities for each player, use spatial hashing or other spatial data-structures that should already be used for broad phased collision detection.

This can be:

plus any extras I've missed.

With these methods, you should be able to retrieve the list of enemies mostly in range of sight (use final check to make sure that they are actually in range before sending) in times between O(log(N)*N) to O(N), much faster than your O(N^2) suggestions. The issue will be updating these structures upon both players and entities moving. You will have to figure out for yourself which of these structures will be better for your use case (you could probably also come back here and ask as well). Some will work better with static entities some will work better for moving, and you may be able to utilize box2d's broad phase collider.

You are essentially colliding a bounding volume (box or circle) of the players vision with the bounding volumes of the other entities, if it intersects then you send that information to that client.