SpatialHash.cs

using System.Collections.Generic;
using System.Linq;

namespace GameCommon
{
    public class SpatialGrid
    {
        public static Dictionary<string, SpatialGrid> Grids = new Dictionary<string, SpatialGrid>();
        private Dictionary<int, Dictionary<string, GridValue>> Cells = new Dictionary<int, Dictionary<string, GridValue>>();
        private Dictionary<string, GridValue> ObjectIndex = new Dictionary<string, GridValue>();
        private Dictionary<string, int> CellsIndex = new Dictionary<string, int>();


        private int Max;
        private int CellSize = 0;
        private float ConvFactor;
        private int Width;
        private float Goffset = 50000f;

        public SpatialGrid(int max, int cellSize)
        {
            Max = max;
            CellSize = cellSize;
            ConvFactor = 1.0f / CellSize;
            Width = (int)(Max / CellSize);
        }

        public int Count()
        {
            return ObjectIndex.Count;
        }

        public static SpatialGrid FindOrCreate(string id, int max, int cellSize)
        {
            if (!Grids.ContainsKey(id))
            {
                Grids[id] = new SpatialGrid(max, cellSize);
            }
            return Grids[id];
        }

        public HashSet<int> CellsWithinBounds(float x, float z)
        {
            HashSet<int> mcells = new HashSet<int>();

            int offset = this.CellSize;

            int startX = (int)(x - offset);
            int startZ = (int)(z - offset);

            int endX = (int)(x + offset);
            int endZ = (int)(z + offset);

            for (int rowNum = startX; rowNum <= endX; rowNum += offset)
            {
                for (int colNum = startZ; colNum <= endZ; colNum += offset)
                {
                    if (rowNum >= 0 && colNum >= 0)
                    {
                        mcells.Add(Hash(rowNum, colNum));
                    }
                }
            }
            return mcells;
        }

        public List<GridValue> Neighbors(float x, float z, GridValue.EntityType entityType)
        {
            List<GridValue> result = new List<GridValue>();

            ICollection<GridValue> gridValues;
            HashSet<int> cells = CellsWithinBounds(x + Goffset, z + Goffset);
            foreach (int cell in cells)
            {
                gridValues = GridValuesInCell(cell);
                if (gridValues == null)
                {
                    continue;
                }
                foreach (GridValue gridValue in gridValues)
                {
                    if (gridValue != null)
                    {
                        if (entityType == GridValue.EntityType.None)
                        {
                            result.Add(gridValue);
                        }
                        else if (gridValue.entityType == entityType)
                        {
                            result.Add(gridValue);
                        }
                    }
                }
            }
            return result;
        }

        public ICollection<GridValue> GridValuesInCell(int cell)
        {
            if (Cells.ContainsKey(cell))
            {
                return Cells[cell].Values;
            }
            else
            {
                return null;
            }
        }

        public List<GridValue> Values()
        {
            return ObjectIndex.Values.ToList();
        }

        public List<string> Keys()
        {
            return ObjectIndex.Keys.ToList();
        }

        public bool Contains(string id)
        {
            return ObjectIndex.ContainsKey(id);
        }

        public GridValue Get(string id)
        {
            return ObjectIndex[id];
        }

        public void Remove(string id)
        {
            if (ObjectIndex.ContainsKey(id))
            {
                ObjectIndex.Remove(id);
                int cell = CellsIndex[id];
                CellsIndex.Remove(id);
                Dictionary<string, GridValue> cellGridValues = Cells[cell];
                cellGridValues.Remove(id);
            }
        }

        public void Set(GridValue gridValue)
        {
            bool hasExisting = false;
            int oldCellValue = -1;
            string id = gridValue.id;

            if (ObjectIndex.ContainsKey(id))
            {
                hasExisting = true;
                oldCellValue = CellsIndex[id];
            }

            int cell = Hash(gridValue.position.X + Goffset, gridValue.position.Z + Goffset);

            Dictionary<string, GridValue> cellGridValues;

            if (hasExisting && oldCellValue != cell)
            {
                if (Cells.ContainsKey(oldCellValue))
                {
                    cellGridValues = Cells[oldCellValue];
                    if (cellGridValues.ContainsKey(id))
                    {
                        cellGridValues.Remove(id);
                    }
                    if (cellGridValues.Count == 0)
                    {
                        Cells.Remove(oldCellValue);
                    }
                }
            }
            CellsIndex[id] = cell;
            ObjectIndex[id] = gridValue;



            if (Cells.ContainsKey(cell))
            {
                cellGridValues = Cells[cell];
                cellGridValues[id] = gridValue;
            }
            else
            {
                cellGridValues = new Dictionary<string, GridValue>();
                cellGridValues[id] = gridValue;
                Cells[cell] = cellGridValues;
            }
        }

        public int Hash(float x, float z)
        {
            return (int)((x * ConvFactor)) + (int)((z * ConvFactor)) * Width;
        }
    }
}