Tile based space partitioning

I needed a way to split the world into tiles so that an entity can quickly find other entities nearby.

The tile node contains the entities in categories and a list of waypoint ids.

public class TileNode 
{    
    /// Contains a list of entities in this tile node    
    public List  [] EntitiesInNode;    

    /// Contains a list of waypoint ids in this quad tree node    
    public List  WaypointsInNode = new List  ();    
    
    public TileNode (int entityGroupCount)     
    {        
        EntitiesInNode = new List  [entityGroupCount];        
        
        for (int i = 0; i < entityGroupCount; ++i)        
        {            
            // reserve 20 entities             
            EntitiesInNode [i] = new List  (20);        
        }    
    }
}

The system holds the tiles and splits the world into grids. Notice that the members are static because there is supposed to be only one instance of this system anyway.

public class TilePartitioningSystem : MonoBehaviour 
{
    /// Size of a single tile
    public static float TileSize { get; private set; }

    /// Total size of the world
    public static float WorldSize { get; private set; }

    /// How many squares on the side
    public static int TileRowCount { get; private set; }

    /// Nodes in the quad tree
    public static TileNode [] Tiles;

    public static void InitializeTilePartitioningSystem (int tileRowCount, float worldSize, int entityGroupCount)
    {
        Debug.Assert (1 < tileRowCount, "Invalid tileRowCount");
        Debug.Assert (0 < worldSize, "Invalid worldSize");

        TileRowCount = tileRowCount;

        TileSize = worldSize / tileRowCount;

        WorldSize = worldSize;

        Tiles = new TileNode [TileRowCount * TileRowCount];

        for (int i = 0; i < Tiles.Length; ++i)
        {
            Tiles [i] = new TileNode (entityGroupCount);
        }

        // Store waypoints in respective tiles
        for (int i = 0; i < WaypointSystem.Waypoints.Length; ++i )
        {
            WaypointBehaviour waypoint = WaypointSystem.Waypoints [i];

            int tileIndex = TilePartitioningSystem.GetTileIndex (waypoint.gameObject.transform.position);

            Tiles [tileIndex].WaypointsInNode.Add (i);
        }
    } 

    public static int GetTileIndex (Vector3 position)
    {
        return (int) (position.x / TileSize) + ((int) (position.z / TileSize) * TileRowCount);
    }

    public static int GetTileIndex (float x, float z)
    {
        return (int) (x / TileSize) + ((int) (z / TileSize) * TileRowCount);
    }

We need ways to add and remove a moving entity from the tiles.

/// Add an entity to the tile.
public static void AddEntityToTile (int tileIndex, int entityGroup, GameObject entity)
{
    Debug.Assert (0 <= tileIndex && tileIndex < Tiles.Length, "Out of range:" + tileIndex);
    Debug.Assert (0 <= entityGroup && entityGroup < Tiles [tileIndex].EntitiesInNode.Length, "Invalid entityGroup:" + entityGroup);
    Debug.Assert (null != entity, "AddEntityToTile:null entity");
  
    Tiles [tileIndex].EntitiesInNode [entityGroup].Add (entity);
}

public static void RemoveEntityFromTile (int tileIndex, int entityGroup, GameObject entity)
{
    Tiles [tileIndex].EntitiesInNode [entityGroup].Remove (entity);
}

We need a way to get a list of the nearby tiles. Tiles in the corners or on the last/first rows will have fewer neighbors.

public static void GetNearbyTiles (ref List  nearbyTiles, int tileIndex)
{
    // Add start tile
    nearbyTiles.Add (tileIndex);
  
    // Determine edges of tile
    bool notFirstRow = tileIndex >= TileRowCount,
     notLastRow = tileIndex < (Tiles.Length - TileRowCount),
            notFirstColumn = 0 != (tileIndex % TileRowCount),
     notLastColumn = (TileRowCount - 1) != (tileIndex % TileRowCount);
  
    // Add surrounding tiles
    // Add tile below
    if (notFirstRow)
    {   
        nearbyTiles.Add (tileIndex - TileRowCount);
    }
    // Add tile above
    if (notLastRow)
    {
        nearbyTiles.Add (tileIndex + TileRowCount);
    }
    // Add tile on the left
    if (notFirstColumn)
    {
        nearbyTiles.Add (tileIndex - 1);
    }
    // Add tile on the right
    if (notLastColumn)
    {
        nearbyTiles.Add (tileIndex + 1);
    }
    // Add tile on the bottom right
    if (notFirstRow && notLastColumn)
    {
        nearbyTiles.Add (tileIndex - TileRowCount + 1);
    }
    // Add tile on the bottom left
    if (notFirstRow && notFirstColumn)
    {
        nearbyTiles.Add (tileIndex - TileRowCount - 1);
    }
    // Add tile on the upper left
    if (notLastRow && notFirstColumn)
    {
        nearbyTiles.Add (tileIndex + TileRowCount - 1);
    }
    // Add tile on the upper right
    if (notLastRow && notLastColumn)
    {
        nearbyTiles.Add (tileIndex + TileRowCount + 1);
    }
}

Finally, the entity updates itself in the TilePartitioningSystem when it moves.

int newTileIndex = TilePartitioningSystem.GetTileIndex (gameObject.transform.position);

// Update tile index
if (newTileIndex != entityData_.QuadTreeIndex)
{
    TilePartitioningSystem.RemoveEntityFromTile (entityData_.QuadTreeIndex, (int) entityData_.EntityGroup, gameObject);

    entityData_.QuadTreeIndex = newTileIndex;

    TilePartitioningSystem.AddEntityToTile (entityData_.QuadTreeIndex, (int) entityData_.EntityGroup, gameObject);
}

So if an entity wants to find the other entities of a certain category nearby they just check the TilePartitioningSystem like this:

TileNode tile = TilePartitioningSystem.Tiles [entityData.QuadTreeIndex];