Running checks more efficiently

Hey everyone,

I was wondering if using a list of objects and doing a check on X# of them per frame would be more efficient than say, doing a check on them every frame.

Lets just make an example. In my game right now, I have the objects that are generated check every frame their x position against my camera's x position. If the value goes past a limit I reshuffle the object.

This got me thinking, wouldn't it be better to move all of the objects to a list, then every update do a loop that grabs objects off the top of the list, check them, then put them at the bottom of the list.

I could also adjust the number of checks it does based on the system resources available.

This also seems like a good way to check objects for LOD.

Does this sound worth it, or a waste of time?

 

If you are doing it a lot you can use a spatial partitioning technique like a quad tree or an oct tree. Or even a binary tree for something like an infinite runner.

 

Is it an issue? If not, your time may be better spent elsewhere.

If you go for it, watch out for memory allocation (and resulting garbage collection) if you're manipulating lists. This is something that should generate zero garbage, or it may make things worse than just updating everything every frame.

Distance-based LOD would be a good way to determine how frequently to run checks. Love/Hate, for example, does this. NPCs closer to the player update more frequently than distant NPCs. On a specified frequency, the LOD manager queues up all NPCs to recheck their distance from the player and update their LOD update frequency. (It wasn't worthwhile to add the overhead of spatial partitioning in this case.)

 

First thing's first: Profile it. Is that check causing a noticeable hit? If you haven't done this, don't optimize it. If you don't have a baseline to compare it to, you'll never know how much performance you saved, if any at all.

So AFTER you have profiled, and only if you've determined this is a problem:
Yes, this is pretty easy:

Code (csharp):

1. YourScript[] allScripts; //assign this in Start however you want
2. int currentIndex = 0;
3. int maxPerFrame = 10;
4. void Update() {
5. for (int x=0;x<maxPerFrame && x < allScripts.Length;x++) {
6. allScripts[currentIndex].PerformCheck();
7. currentIndex = (currentIndex + 1) % allScripts.Length;
8. }
9. }

 

Yeah, that's about the size of it. I should just have fired it up and tested it. Thanks for the advice everyone!

@BoredMormon - Any good reading material you can point me to about spatial partitioning? I'm guessing that involves doing things in chunks, correct? I just don't get what you mean by "quad tree".

 

I'm note sure (pun: as you are) about what you want to do.

But in case you want to do LODing, note that Unity has already it built-in: http://docs.unity3d.com/Manual/LevelOfDetail.html

 

For information on Quad Tree a good start would be wiki for a basic understanding and to see if it would fit your needs or not.
https://en.wikipedia.org/wiki/Quadtree

Quad trees are only really needed if you are breaking down complex tasks over a 2D area, Oct Tree for 3D area. For example In a project I worked on we were required to have huge areas visible at once with more than 1 million models. Obviously this wont render brute force but as detail only needs to be visible at a short range I used quad trees to pre-calculate at what distance each model should be loaded into memory and then displayed for the user. The result is like this image attached.

In your case if you literally are only checking X axis against something else then using any partitioning would be pointless as you need to calculate which partition you are in to begin with. If you are doing complex AI on objects close to the player then the technique becomes more useful after 'sorting' all entities you an then perform different calculations based on which partition they are in.

If your still struggling imagine, as I did to get my head around it, buckets, lots of them arranged in a grid over your 3D world. Each enemy moving around can only be in 1 bucket at a time. If you know where the player is in the world then you can get the closest buckets and only update enemies in them with the most complex AI (moving, looking, shooting, audio etc..). All other enemies in all other buckets only perform basic AI (moving) That is it at a basic level, you can subdivide buckets into more buckets but it is just repeating the process.

 

Cool, thanks!

I also found this great link:
http://gameprogrammingpatterns.com/spatial-partition.html

The guy who wrote Game Programming Patterns just put up the book for free online and there's an entire chapter on this.

I think I get what quad and oct trees are now. I was tripped up on the "tree" part. But more or less blocks or squares of space to organize objects to limit the amount of methods they run. So that it only check its self against other objects in that space and not all other objects.

Is that about right?

 

That's right. It's a space partitioning technique used to speed up space-related queries.
But do you really need to wrap up you own system. Unity already used that under the hood for physics and rendering.

What do you want to used that technique for?

 

Yep, nailed it! I think that is actually one of the articles I read when I wrote mine!

All the techniques are basically ways to organise your (tracked objects) consuming a small amount of processing time during the process in the hope that later on you will gain it back by processing less overall objects.

These systems completely fall over if your grid size is so large that all the tracked objects are in a single bucket as not only are you handling the organisation overhead your also performing all your processing for updating. So scale of your grid size is key but there isnt a single grid size that fits all.

In my case of handling terrain objects i just best guessed. I figure I dont need detail beyond 2km from the player so the grid size in most environments is 2km by 2km. (i have a 200km by 200km environment to put it into perspective). However in the case of handling AI enemies 2km by 2km would be probably too large unless your in space ships...

 

In a quadtree, buckets have a maximum size, so you keep subdividing quads until each bucket is the right size. You'll never have too many objects in a bucket. The only exception is if you impose a maximum number of buckets, for example by using a static array of buckets to eliminate heap allocation. But for an application like this, I think a reusable pool of buckets would be better. (One of my university professors was the guy who first applied quadtrees to spatial data. As they say, when all you have is a hammer, everything looks like a nail. I kind of got my fill of quadtrees, useful as they are.)