Back to General and Gameplay Programming

Efficiently Detecting if objects are out of screen?

Omar Shehata · 2013-01-14T19:19:39

I have a small optimization problem in my game. If I have 10,000 objects in-game, but only 10 objects on screen (or no objects on screen), the game will lag, because what I do is I check every single frame, for every object, if the object is inside the screen or not. So obviously as more objects are added, the slower things get. I thought about using some form of spatial indexing, so that if my camera is at (100,100), then instead of looping through 10k objects to know which are in-screen, I will simply ask my grid if there are any objects at 100,100, and do the same for neighbouring cells to get all objects inside the screen without ever having to loop, no matter if I have a thousand, or a million objects. The problem, however, was that this doesn't account for moving objects, because if an object moves, I would have to check every frame if it has entered another grid cell or exited its cell. So how do you detect which objects are inside the screen?

General and Gameplay Programming Programming

Started by OmarShehata January 07, 2013 11:11 AM

15 comments, last by CC Ricers 11 years, 3 months ago

OmarShehata

205

Author

January 09, 2013 02:07 PM

Thanks for all the replies so far!

To confirm, the game I'm working on is a 2D game.

So from what I understand there's really no one perfect solution that is going to fix everything, but combining all these different things to get the performance I need.

So I could implement quad trees, plus this "frustum culling" (which I'm guessing works just as well to 2D games as it does for 3D?)

I could also split my objects into "static" and "dynamic".

I could do as wintertime suggested, and have this sort of "probability" buckets, and not update some objects as much as others depending on how probable it is that they would be in the screen on the next update.

I'm using Lua with Love2D by the way.

21st Century Moose

13,459

January 10, 2013 01:45 AM

You then do some frustum culling by starting at the root node (the encompassing box) and recursively checking down through the children of each box. If you can't see a box in your frustum then you will not be able to see any of its children (and hence any objects within it) so it can be discarded. This way you can cull thousands of objects in one simple test.

Just adding to this: the opposite is also true - if a node is fully inside the frustum then all of it's child nodes are also guaranteed to be fully inside the frustum and you can skip testing for them too. Child nodes only need testing where their parent intersects the frustum.

Direct3D has need of instancing, but we do not. We have plenty of glVertexAttrib calls.

OmarShehata

205

Author

January 10, 2013 04:14 PM

The moving object problem isn't that bad. If you think for a while, you'll realize that you'll need to update only objects which move outside of the octree node. So, as long as the object stays inside a node, you don't need to change your spatial structure.

I wanted to ask about this. Even if the moving object is moving inside one cell, how do I know that? How do I know when it needs to be reassigned to a new node/cell if I'm not constantly checking if it's still within its node?

Strewya

2,802

January 11, 2013 08:15 AM

have the entity trigger the recalculation each time it moves. maybe even go as far as have a pointer to the node/cell it's in, so each time it moves it checks if it's still in the same node, and if not, do the recalculation.

devstropo.blogspot.com - Random stuff about my gamedev hobby

TheChubu

9,484

January 11, 2013 08:22 AM

I'd put something between the object and the data structure that holds the world together. Something that knows what to do with both, like a world manager or something like that. So the object has one object (or a list of 'em) to announce "Hey, I'm moving x units to this way!" And the manger says "Well, let's see what I can do about that buddy!" and they happily lived ever after.

"I AM ZE EMPRAH OPENGL 3.3 THE CORE, I DEMAND FROM THEE ZE SHADERZ AND MATRIXEZ"

My journals: dustArtemis ECS framework and Making a Terrain Generator

kauna

2,925

January 13, 2013 01:25 PM

[quote name='OmarShehata' timestamp='1357834485' post='5019896']
I wanted to ask about this. Even if the moving object is moving inside one cell, how do I know that? How do I know when it needs to be reassigned to a new node/cell if I'm not constantly checking if it's still within its node?
[/quote]

Each node should have 2 bounds, the strict bound (which comes from the octree subdivision) and the loose bound which is the strict bound + bounds of objects inside the node.

For placing an object inside the octree you should find the node which contains the center point of the objects bound and which isn't smaller than the objects bound.

You know that the object is inside the assigned node by checking the object bounds midpoint vs. nodes strict bound. If the mid point is outside of the bound then you'll need to reassign the object to a new node. Of course your objects needs to be aware in which node it resides.

Cheers!

CC Ricers

1,491

January 14, 2013 07:19 PM

[mods, please delete]

New game in progress: Project SeedWorld

My development blog: Electronic Meteor

Efficiently Detecting if objects are out of screen?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Efficiently Detecting if objects are out of screen?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines