Welcome to Our Community

Welcome to our support forums. We hope you find the information you are looking for. Please note that some areas of these forums are not visible to guests, and require a forum account. Registration is free and easy, and we won't spam you or share your email address with anyone.

Sign Up
  1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Octree for Unity 2015-01-17

A basic Octree implementation for Unity

  1. StagPoint
    I'm honestly surprised that Unity does not have an Octree class built in (or at least it doesn't have one exposed to scripts). It's such a fundamental and useful structure for game development that almost everyone needs to use an Octree at some point or another.

    Since there wasn't one already available in Unity, and even if there was it would probably allocate memory like crazy like many of Unity's built-in classes, I decided to write my own.

    I've been using the one presented here in my Combat A.I. sandbox, and it's been pretty solid and fairly performant for me, so I thought I'd share it with anyone who was interested.

    [​IMG]
    You can find basic API documentation here - http://stagpoint.com/docs/octree/annotated.html

    ADDING AN ITEM TO THE OCTREE

    When you add an item to an Octree, you will get an ISpatialToken reference in return. This token must be retained if the item to be added is not static and permanent, since the token is used to update the item's position as well as to remove it when done.
    Code (C#):
    void OnEnable()
    {
       // Add this GameObject to the Octree and retain the ISpatialToken
       // instance so that the position can be updated later
       this.trackingInfo = SpatialDatabase.AddItem( this, this.collider.bounds );
    }

    UPDATING AN ITEM'S POSITION IN THE OCTREE


    As mentioned above, you will use the ISpatialToken reference to update the item's position in the Octree:
    Code (C#):
    void Update()
    {
       if( this.trackingInfo != null )
       {
         // Update the item's position in the Octree
         this.trackingInfo.Update( collider.bounds );
       }
    }

    REMOVING AN ITEM FROM THE OCTREE


    Similarly, you use the ISpatialToken reference to remove the item from the Octree:
    Code (C#):
    void OnDisable()
    {
       if( this.trackingInfo != null )
       {
         this.trackingInfo.Remove();
         this.trackingInfo = null;
       }
    }

    EXECUTING A QUERY

    Code (C#):
    // Execute an octree query looking for objects of type [Agent] that
    // are within [radius] meters of [position].
    using( var query = octree.ExecuteQuery<Agent>( position, radius ) )
    {

       // NOTE: See the section below on MEMORY USAGE
       processResults( query.Results );

    }
    The Octree class also provides overloads for ExecuteQuery that allow for testing against an axis-aligned bounding box, a line segment, or an array of planes (like a camera frustum).


    MEMORY USAGE


    This Octree class uses object pooling internally so that it does not result in ongoing memory allocations, which will prevent the performance-killing garbage collection cycles that would result otherwise.

    Because of this, you will want to either allocate your own SpatialDatabaseQuery instances and pass those to Octree.ExecuteQuery(), or use the pattern shown in the Executing a Query section, which automatically returns the query to the object pool ready for re-use.

    This also means that you must not keep a reference to the query's Results list, since that list will also be recycled. If a persistent list is needed, you should copy the Results list to your own local list.

    PERFORMANCE

    This is certainly not the most optimized Octree class you could create, but in my current tests it is performant enough. Performing a query against an Octree with nearly 24,000 items in it, for each AI agent in the scene, only takes roughly 1ms per frame. This is of course highly dependent on what's being stored (24,000 is way more than typical), how densely packed or localized the items are, and many other factors. It's probably safe to say that even the most basic Octree structure can improve performance of proximity/visibility testing by several orders of magnitude over not using any broad-phase testing at all.