Spatial Index using 3D Grid Registration

This is a simplified version of my 3D Grid Registration technique.
I think this is superior to Quadtrees / Octrees for many games.

GameObject.cs shows an example of an object that uses a GridObject to register itself into a Grid.

The idea is that that each GridObject maintains 1 or more registrations into the grid, depending on the size of the object.

The Grid is sparse and uses a Dictionary to store the populated cubes.

A pool of LinkedLists is used in order to avoid allocations.

The approach generates zero allocations / garbage during gameplay (if you size things correctly)

This index can be used for frustum culling, collision detection, ray casting and proximity detection.

Currently the implementation only supports Cuboid registrations and queries.
Frustum shaped support can be added by filtering the cubes by intersection testing with the frustum.
Support for strange shapes (like a long snake) can be implemented by breaking the shape down into a set of cuboids, maybe wrapped around spheres.

My full implementation is much more complex and includes support for separate linked lists for each object type and an internal event and queuing system that builds lists of jobs based on registration events – this ensures a very low opcount for large quantities of objects by avoiding repeated scanning etc.

Grid.cs

// - - - - - - - - - -
using System;
using System.Collections.Generic;
// - - - - - - - - - -
using Microsoft.Xna.Framework;
// - - - - - - - - - -
namespace GameSpace {
    // - - - - - - - - - -
    /// <summary>
    /// 3D Grid Registration Spatial Index
    /// </summary>
    public class Grid {
        // - - - - - - - - - -
        readonly StackOfLists stackOfLists;
        readonly DictKeyLL grid;
        // - - - - - - - - - -
        readonly Action<Key> actionKeyForQuery;
        // - - - - - - - - - -
        Action<Key, LL> actionKeyLL;
        // - - - - - - - - - -
        public Grid(int SizeOfStackOfLists, int CapacityOfDictKeyLL) {

            // Create pool of Linked Lists
            stackOfLists = new StackOfLists(SizeOfStackOfLists);

            // Create Dictionary<Key,LinkedList>
            grid = new DictKeyLL(CapacityOfDictKeyLL);

            // Delegate used to query the grid
            // invokes callback for every populated cube found
            actionKeyForQuery =
                (gridKey) => {
                    LL list;
                    if (grid.TryGetValue(gridKey, out list)) {
                        actionKeyLL(gridKey, list);
                    }//if
                };

        }//method
        // - - - - - - - - - -
        /// <summary>
        /// Scans all cubes in a cuboid defined by Min and Max coordinates
        /// </summary>
        public static void Scan(ref Key keyMin, ref Key keyMax, Action<Key> actionKey) {
            for (int x = keyMin.X; x <= keyMax.X; x++) {
                for (int y = keyMin.Y; y <= keyMax.Y; y++) {
                    for (int z = keyMin.Z; z <= keyMax.Z; z++) {
                        Key gridKey = new Key(x, y, z);
                        actionKey(gridKey);
                    }//for
                }//for
            }//for
        }//method
        // - - - - - - - - - -
        /// <summary>
        /// Scans cuboid and invokes callback for each populated cube found
        /// </summary>
        public void Query(ref Key keyMin, ref Key keyMax, Action<Key, LL> actionKeyLL) {
            this.actionKeyLL = actionKeyLL;
            Scan(ref keyMin, ref keyMax, actionKeyForQuery);
        }//method
        // - - - - - - - - - -
        /// <summary>
        /// Performs World Space to Grid Space mapping
        /// </summary>
        public static Key CreateKey(ref Vector3 P) {
            Key key =
                new Key(
                    (int)Math.Floor(P.X),
                    (int)Math.Floor(P.Y),
                    (int)Math.Floor(P.Z)
                );
            return key;
        }//method
        // - - - - - - - - - -
        /// <summary>
        /// Registers a node into the grid
        /// </summary>
        public void Register(ref Key gridKey, LinkedListNode<GridObject> node) {

            LL list;
            if (grid.TryGetValue(gridKey, out list)) {
                list.AddLast(node);
            } else {
                list = stackOfLists.Pop();
                list.AddFirst(node);
                grid.Add(gridKey, list);
            }//if

        }//method
        // - - - - - - - - - -
        /// <summary>
        /// Deregisters a node from the grid
        /// </summary>
        public void Deregister(ref Key gridKey, LinkedListNode<GridObject> node) {

            LL list;
#if DEBUG
            if (grid.TryGetValue(gridKey, out list)) {
                if (node.List != list) throw new ArgumentOutOfRangeException("node does not belong to gridKey");
            }//if
#endif
            // Remove Node from List
            list = (LL)node.List;
            list.Remove(node);

            // If list empty remove key from dict
            if (list.Count < 1) {
                stackOfLists.Push(list);
                grid.Remove(gridKey);
            }//if

        }//method
        // - - - - - - - - - -
        public class LL : LinkedList<GridObject> {
        }//class
        // - - - - - - - - - -
        public class DictKeyLL : Dictionary<Key, LL> {
            // - - - - - - - - - -
            public DictKeyLL(int Capacity)
                : base(Capacity) {
            }//method
            // - - - - - - - - - -
        }//class
        // - - - - - - - - - -
        public struct Key : IEquatable<Key> {
            // - - - - - - - - - -
            public int X;
            public int Y;
            public int Z;
            // - - - - - - - - - -
            public Key(int X, int Y, int Z) {
                this.X = X;
                this.Y = Y;
                this.Z = Z;
            }//method
            // - - - - - - - - - -
            public bool Equals(Key other) {
                return X == other.X && Y == other.Y && Z == other.Z;
            }//method
            // - - - - - - - - - -
            public override int GetHashCode() {
                return X + Z * 256 + Y * 65536;
            }//method
            // - - - - - - - - - -
            public override bool Equals(object obj) {
                throw new Exception("no no no");
            }//method
            // - - - - - - - - - -
        }//struct
        // - - - - - - - - - -
        class StackOfLists : Stack<LL> {
            // - - - - - - - - - -
            public StackOfLists(int MaxCount)
                : base(MaxCount) {

                // Create pool of Linked Lists
                for (int i = 0; i < MaxCount; i++) {
                    Push(new LL());
                }//for

            }//method
            // - - - - - - - - - -
        }//method
        // - - - - - - - - - -
    }//class
    // - - - - - - - - - -
}//namespace
// - - - - - - - - - -

GridObject.cs

// - - - - - - - - - -
using System;
using System.Collections.Generic;
// - - - - - - - - - -
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
// - - - - - - - - - -
namespace GameSpace {
    // - - - - - - - - - -
    /// <summary>
    /// Registers a single game object into multiple grid cubes
    /// </summary>
    public class GridObject {
        // - - - - - - - - - -
        readonly GameObject gob;
        // - - - - - - - - - -
        readonly int maxNodeCount;
        // - - - - - - - - - -
        readonly Grid grid;
        // - - - - - - - - - -
        readonly KeyLLN[] gridNodes;
        // - - - - - - - - - -
        readonly Action<Grid.Key> actionRegister; // Persistent delegate to stop lambda garbage
        // - - - - - - - - - -
        bool flagRegistered = false;
        // - - - - - - - - - -
        int keyCount = 0;
        // - - - - - - - - - -
        /// <param name="gob">GameObject to register</param>
        /// <param name="grid">Grid in which to register GameObject</param>
        /// <param name="maxNodeCount">Maximum number of Grid cubes required to register this GameObject</param>
        public GridObject(GameObject gob, Grid grid, int maxNodeCount) {

            this.gob = gob;

            this.maxNodeCount = maxNodeCount;

            gridNodes = new KeyLLN[maxNodeCount];

            // Persist Grid Reference
            this.grid = grid;

            // Construct Grid Keys
            for (int i = 0; i < maxNodeCount; i++) {
                gridNodes[i] = new KeyLLN(this);
            }//for

            // Persist delegate to avoid allocations
            actionRegister =
                (gridKey) => {
                    gridNodes[keyCount].gridKey = gridKey;
                    grid.Register(ref gridKey, gridNodes[keyCount].node);
                    keyCount++;
                };

        }//method
        // - - - - - - - - - -
        /// <summary>
        /// True if this GridObject is registered
        /// </summary>
        public bool Registered {
            get {
                return flagRegistered;
            }//get
        }//method
        // - - - - - - - - - -
        /// <summary>
        /// Register this GridObject into the Grid
        /// </summary>
        public void GridRegister(ref Vector3 Pmin, ref Vector3 Pmax) {

			if (flagRegistered || keyCount != 0) throw new Exception("no no no");

            // Calculate bounding Cuboid in Grid Space
            Grid.Key keyMin = Grid.CreateKey(ref Pmin);
            Grid.Key keyMax = Grid.CreateKey(ref Pmax);

            // Scan Cuboid and call register delegate
            Grid.Scan(ref keyMin, ref keyMax, actionRegister);

            // Mark GameObject as registered
            flagRegistered = true;

        }//method
        // - - - - - - - - - -
        /// <summary>
        /// Deregister this GridObject from the Grid
        /// </summary>
        public void GridDeregister() {

            // Scan active grid keys
            for (int ki = 0; ki < keyCount; ki++) {

                // Deregister from Grid
                Grid.Key gridKey = gridNodes[ki].gridKey;
                grid.Deregister(ref gridKey, gridNodes[ki].node);

            }//for

            // Reset keyCount
            keyCount = 0;

            // Mark GameObject as unregistered
            flagRegistered = false;

        }//method
        // - - - - - - - - - -
        public struct KeyLLN {
            // - - - - - - - - - -
            public Grid.Key gridKey;
            public readonly LinkedListNode<GridObject> node;
            // - - - - - - - - - -
            public KeyLLN(GridObject gob) {
                this.gridKey = new Grid.Key();
                this.node = new LinkedListNode<GridObject>(gob);
            }//method
            // - - - - - - - - - -
        }//struct
        // - - - - - - - - - -
    }//class
    // - - - - - - - - - -
}//namespace
// - - - - - - - - - -

GameObject.cs

// - - - - - - - - - -
using System;
// - - - - - - - - - -
using Microsoft.Xna.Framework;
// - - - - - - - - - -
namespace GameSpace {
    // - - - - - - - - - -
    public class GameObject {
        // - - - - - - - - - -
        static readonly Random rnd = new Random();
        // - - - - - - - - - -
        Vector3 HalfLen = new Vector3(0.5f, 0.5f, 0.5f);
        // - - - - - - - - - -
        const int MaxKeyCount = 8;
        // - - - - - - - - - -
        Vector3 Pcenter;
        // - - - - - - - - - -
        readonly GridObject gridObject;
        // - - - - - - - - - -
        public GameObject(Grid grid) {
            gridObject = new GridObject(this, grid, MaxKeyCount);
            SetPos();
        }//method
        // - - - - - - - - - -
        public void GridRegister() {

            Vector3 Pmin;
            Vector3.Subtract(ref Pcenter, ref HalfLen, out Pmin);

            Vector3 Pmax;
            Vector3.Add(ref Pcenter, ref HalfLen, out Pmax);

            gridObject.GridRegister(ref Pmin, ref Pmax);

        }//method
        // - - - - - - - - - -
        public void GridDeregister() {
            gridObject.GridDeregister();
        }//method
        // - - - - - - - - - -
        /// <summary>
        /// Move to random location (used for testing)
        /// </summary>
        public void SetPos() {

            const float Size = 100.0f;

            Pcenter.X = (float)rnd.NextDouble() * Size * 2.0f - Size;
            Pcenter.Y = (float)rnd.NextDouble() * Size * 2.0f - Size;
            Pcenter.Z = (float)rnd.NextDouble() * Size * 2.0f - Size;

        }//method
        // - - - - - - - - - -
    }//class
    // - - - - - - - - - -
}//namespace
// - - - - - - - - - -
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: