Efficient logic culling: An easy and fast way of culling out logic based on distance.

Logic_Cull.blend (967 KB)

NEW:: Updated version
http://www.mediafire.com/?pteb4a02qbvv9ue


When one looks deep into the BGE’s python documentation, you notice a function related to activity culling that may have been implemented a long time ago, but what is it, does it even work, should I try it?

If you’re looking to see it being used in this example then you would be wrong, when I first saw that function, I figured an immediate disadvantage would be in the form of it deactivating the activity of objects that would need to be activated at all times no matter where they are in relation to the player (important for things like spawning objects). But luckily that weakness is not the end of the road for optimizing logic as we can always use the state system.

This implementation makes use of two near sensors, one for nearby objects and one for objects getting further away and out of range, their hitObjectList attributes are then used to activate and deactivate the logic of objects based on this principle. The reason why near sensors are used instead of iterating through the object list is that it would speed things up by only iterating through objects in a specific area instead of throughout the scene.

In this .blend file you will learn how to do the proper setup with the near sensors, you will also learn a quick way of deactivating all objects at the start to automate things if this is coming late in your project, and you will learn how you can disable the culling for various objects, even if they start or go out of range if they contain a certain property.

The script seen here is already being used with successful result in one of my own projects, with FPS rates going from as low as 10 due to hundreds of objects executing logic at once to a solid 60.

I hope that this can be useful for some of you out there with projects making heavy use of logic, enjoy. :slight_smile:

I was going to say that a script that loops through the object list and checks their distance would probably run faster, because I think the Near sensor takes into account the mesh of the object (i.e. if a polygon crosses the field, the sensor’s positive). Anyway, great to see a resource that shows how to deal with optimization.

I thought the near sensor used another way to determine this like the object bounds or the origin, though I’ve never read through the code to see the exact method.

Plus I’m not sure if you would have any distinct advantages looping through every object in the scene considering that one could have large scenes with thousands of objects, which would be quite a large number of objects to continuously loop through.

Yeah, maybe you’re right. I haven’t checked your method yet - when I do, I’ll give some more feedback.

EDIT: After seeing your method, it is indeed most likely faster than looping, as, like you said, you’re not looping through every object, but just the ones that cross the area around your player. Very elegant solution, and I like how you visualize the effect, too. You should make a game out of it, heh.

You’re always coming up with optimization methods - I remember you mentioned a method of triggering enemies when the player collided with them, or something to that effect, and now I think I’m using a similar method for my NPCs in Soldier Of. When the player wants to read a sign or something, it triggers the “active” property, which makes the NPC ‘wake up’ to communicate. After it’s finished, it ‘de-triggers’ the “active” property and goes back to sleep. I’m doing a similar thing for the water animation - because I’m using UV animation, all the water objects share meshes. Whichever activates first is the ‘active’ one - after that, all other water objects turn their ‘active’ properties to false, and thereby ‘shut-down’.

Thanks man. On a side note. I found your ‘game’ quite entertaining lol

testing two script ,with the same number of obj
one that use near sensorand another that loop all, and getDistanceTo()

whit sensor:
physic :0.6 ms
logic : 0.2 ms

tot: 0.8 ms

with getDistanceTo()
physic: 0.5 ms
logic: 0.7 ms

tot : 1.2 ms

effectively is more fast this solution with sensors :wink:

Yeah, I remember hearing(I think from a very knowledgeable BA member) that the near sensor checks every vertex of each object against the origin of the sensor’s owner. I’m concerned that this method could become slow for scenes with lots of vertices. But what do I know.

a strange and unoptimized loop start surely when there a collision with the sensor near, is easy to notice with mesh high poly as target.

the calculation can jump from 0.2(when is far) to 3/4 ms (when is near)

it seem which lack the optimization “normal” of bullet for triangle collision

Well I just did a test where I subdivided and smoothed the cubes a bit (without modifiers), then did another test where I extruded all the faces first before subdividing and smoothing. Looking at the profiler, I was not able to see a discernible difference in the amount of time used up by the logic despite the sharp increase in poly count. The only thing I noticed was a slight increase in the time needed to calculate the physics. (in which something like that is generally expected when you have more polygons, even with no logic running)

Perhaps you increased the time by using the modifier stack (as there have been tests showing it can slow things down somewhat)?

you should see a difference even in your demo, but you need to selecting collision triangle for all cube (not box)
the “potential” slow of near sensor is clearly visible in this blend(is very over a normal collision calculation)

however,
is not a error of sensor Near (as I thought)
but is instead a weak point of Bullet

the same big slow can also be caused by a dynamic object ghost
when crossing a high poly mesh

:wink:

Attachments

near.blend (286 KB)

awsome!

i was wondering though could you do somewhat of kinda the same thing if you had a object when near player it switches to state 2 that has all the logic then when its away from the player it switches back to the first state with little logic?

Testing it by adding a high poly object to my test scene set to triangle mesh bounds, I can confirm that the additional overhead in physics more than offsets the gain created by minimizing the total amount of objects being iterated through.

I Just uploaded a new version which solves that, the objects are now split into two main groups, the cubes have a property named ‘LowPoly’ and there’s two new highpoly objects with triangle meshes containing the property ‘HighPoly’.

With this, the near sensors have been tweaked to only check for objects containing the ‘LowPoly’ property, for objects with the HighPoly property, the script now does a second round of initialization that iterates through the objList once more and shunts the highpoly objects into a new list providing they aren’t already there, the loop then terminating when the iteration is complete.

This is where things get a lot faster, the script in general now uses a hybrid method where, for the highpoly objects, the getDistanceTo() method is used instead of the near sensor method. Despite the slight amount of additional work that is needed in terms of setting the properties, it does look from tests that this method will be able to keep the speed to a maximum while maintaining a minimal amount of objects being looped through at once. The only thing this test doesn’t show right now is how to check if the highpoly object no longer exists in the scene which would result in it being deleted from the list, but those who are well versed in the usage of lists and ‘for’ statements could probably figure that out.

Also, while this change may keep the speed to a very high rate in almost any type of scene that has both lowpoly and highpoly objects, all bets are off if you switch these highpoly objects to rigidbody (in which I don’t think there’s any type of logic that would be able to help you there)


i was wondering though could you do somewhat of kinda the same thing if you had a object when near player it switches to state 2 that has all the logic then when its away from the player it switches back to the first state with little logic?

Pretty much all you would have to do in that is move all the logic in the cubes from state 1 to state 2. And even if you don’t do that, everything concerning the state switching is in one script so it shouldn’t be difficult to reverse it.

First off, you should always try to avoid high poly physics objects (use separate graphics and physics meshes if you have to). Second, getDistanceTo() involves a square root, which could be slow if used per object per frame. Instead, try using the distance squared. So, if you had this:


if ob1.getDistanceTo(ob2) > 5

try this:


if (ob2.worldPosition - ob1.worldPosition).length_squared > 25

Everyone hates math even computers :stuck_out_tongue:
Thanks Moguri, you give me the idea :slight_smile:

Just pointing out that you should not use " object " word in the for loop, because object is a python built-in i think (aka new style class thingy).

Furthermore, there are faster ways of doing the same thing. Using a KDTree with range search can quickly determine near neighbours around a point.

Code Sample Agoose77 ?

EDIT:
I mean been studying the Moedrn kdtree but for some reason its seems too… i dont know… large?
Just curious about personal implementations :slight_smile:


from kdtree import KDTree
# http://code.google.com/p/python-kdtree/
tree = KDTree.construct_from_data([(1,2,3),(4,0,1),(5,3,1),(10,5,4),(9,8,9),(4,2,4)])
nearest = tree.query(query_point=(5,4,3), t=3)

:slight_smile: