Skip to content

Spatial Hash

The Spatial Hash algorithm is a performant non-physics based query system that returns a list of objects contained in a position and a certain radius.

Performance

This algorithm scales with the amount of objects tracked. Its performance shines the most when there are multiple queries launched in a single frame. For more information about how this algorithm works check this Twitter post:

https://twitter.com/catsoftstudios/status/1201520331724333058

Creating a Domain

The first thing needed is to create a world domain from where to track all objects and organize the space partitioning. We recommend setting up a static class that will handle registering all the changes that happen in the scene. For example:

public static class MySpatialHash
{
    public static SpatialHash Value { get; private set; } = new SpatialHash();

    [RuntimeInitializeOnLoadMethod(RuntimeInitializeLoadType.SubsystemRegistration)]
    private static void OnSubsystemsInit()
    {
        Value = new SpatialHash();
    }
}

The previous code snippet initializes the Value field with the default SpatialHash constructor. the OnSubsystemInit() is a method that gets called at the very beginning of starting the game, before any scene is loaded, thanks to its attribute.

Tracking Changes

Each object instance is responsible for updating the domain value when it changes. To do so, the object must implement the ISpatialHash interface, as well as call the Insert(), Remove() and Update() methods to start, stop and update the spatial hash's domain. For example:

public class MyComponent : MonoBehaviour, ISpatialHash
{
    void OnEnable() 
    {
        // Start tracking this object
        MySpatialHash.Value.Insert(this);
    }

    void OnDisable() 
    {
        // Stop tracking this object
        MySpatialHash.Value.Remove(this);
    }

    void Update()
    {
        // Update tracking position
        MySpatialHash.Value.Update(this);
    }

    // ISpatialHash interface. Position in space:
    Vector3 ISpatialHash.Position => this.transform.position;

    // ISpatialHash interface. Identifies this class:
    int ISpatialHash.UniqueCode => this.gameObject.GetInstanceID();
}

Boost Performance

This code is meant for demonstration purposes and might not be optimal on every case. If you want to squeeze every drop of performance, you may want to cache the last tracked position and only call the Update(this) method when its position has changed.

Requesting Collections

To request all the objects around a point and within a specific radius, use the Query(Vector3 point, float radius) method, which returns a list of game objects contained in the specified region.

// Define a point and radius in the 3D space:
Vector3 point = new Vector3(0,0,0);
float radius = 10f;

// request for all tracked game object within:
List<ISpatialHash> list = MySpatialHash.Value.Query(point, radius);

The list contains all components that implement the ISpatialHash interface tracked in this domain that are within the spherical region defined.

Back to top