I’m creating group behaviours and I am detecting neighbours with a Trigger Sphere Collider.
So basically, each time there is OnTriggerEnter, I check the collider’s gameobject tag, if its the tag I want, I check in my dictionary if the gameobject’s id is there. If its not, I insert it in the dictionary.
And I do the other way around when there is a OnTriggerExit.
Now my question comes because I’d like to know if anyone has done it in a more efficient way. I’m keeping each neighbour in a Dictionary<(int)GameObjectID, GameObject>. I’m only doing so, so I can compare the gameobjects by their ID, since I quite don’t know if comparing them directly would work. Otherwise I would keep them in a Simple List. Ideally I could keep them on a SortedList by distance, but then again, I need to know if I can compare gameobject with gameobject directly.
Sounds fine. The only other way I can think of is if you cast a ray. But that could be sloppy if objects are not always aligned on a grid. Also, you would have to cast a ray in 4 directions. The ray cast, may have to run all the time… Yah, I think triggers, storing in a list, or dictionary would be fine.
Maintaining simple lists is very inefficient. You’re constantly resorting that list based on distance which will allocate like crazy. You should use a quad tree or simplify it and just use a grid based system. Each grid cell is a fixed size and has a list of the objects that are inside of it. It also has top, bottom, left and right properties which are references to the neighbor cells. When an object moves from one grid cell to the other you unregister it from the old grid cell and register it with the new one. Now, your player can calculate what cell it is in just by coordinates. When you want to check objects of a certain distance, you just go through the objects registered in the player cell and depending on cell size and desired distance, traverse the neighbors as well. This has the advantage of allowing you to do your checks in very few queries. You may have thousands of objects but you never have to sort them all and you only query cells and then check the objects in the neighbors and player cell meaning you automatically filter out all objects you don’t care about very efficiently.
Space partitioning was considered, but I’m working in 3 dimensions, so it would be a little more complex. I’ve never used ( I know how the theory behind ) Quad-Trees or N-Trees before Do you know any good tutorial explaining their benefits/usage?
As a last resort for optimization I’ll make a view frustrum to eliminate gameobjects behind the object and use that as a trigger collider, this will hopefully make it run twice as fast ( assuming I have less than half the trigger volume of a sphere ).
Right now I’m using an old Macbook Pro with no dedicated graphics card and it works fine (fps wise) up to 50 objects. When going to 100 its slows down to non playable framerates… So I have my basis line there, although I’m using placeholder cubes instead of polished models. In any case, that will be the GPU’s problem then. I’ll be upgrading to a new computer with a nVidia graphics card and hopefully the PhysX system will have my back then.
Well my blog has a good series on building XNA Terrain with LOD and culling. The XNA bit is irrelevant but it’s all implemented using a QuadTree. I’d suggest taking a quick read and understanding how the QuadTree structure works first:
Since you’re working in 3D Space, what you’ll want to look at is an Octree. It’s almost identical to a QuadTree except instead of squares it uses cubes and divides in the Y direction as well. Rather than bounding squares, you have bounding volumes (cubes) that you’re dividing into 8 bounding cubes. Understanding a QuadTree first will help an Octree implementation really quick.
Even though it’s more complex, using the Octree approach will still be more efficient than your View Frustrum approach. You may be checking all objects within distance which would leave you checking several extra objects, but you could use the difference between the directional vector and your forward vector to determine whether an object is behind you. The problem with the View Frustrum approach is that it’s very expensive to do intersect tests with volumes. If you could project them to 2D shapes as I did in my XNA Terrain Tutorial then you could use the Separating Axis Theorem to do the intersect tests which is very fast, but that only works with convex shapes and wouldn’t work with a sphere.
It should return true if the object is the same.