GridValue.cs

/*
This software is licensed under the Apache 2 license, quoted below.

Copyright 2014 Game Machine.
Copyright 2014 Chris Ochs <chris @ochsnet.com>

Licensed under the Apache License, Version 2.0 (the "License"); you may not
use this file except in compliance with the License. You may obtain a copy of
the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
License for the specific language governing permissions and limitations under
the License.
*/
using UnityEngine;

namespace LandRush {
    public class GridValue {
        public enum EntityType {
            None,
            Tree,
            Rock,
            Block
        }

        public string id;
        public Vector3 position;
        public EntityType entityType;
        public GameObject go;
        public bool active = false;
        public TreeInstance treeInstance;
        public int treeIndex;
    }
}

SpatialGrid.cs

/*
This software is licensed under the Apache 2 license, quoted below.

Copyright 2014 Game Machine.
Copyright 2014 Chris Ochs <chris @ochsnet.com>

Licensed under the Apache License, Version 2.0 (the "License"); you may not
use this file except in compliance with the License. You may obtain a copy of
the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
License for the specific language governing permissions and limitations under
the License.
*/
using System.Collections.Generic;
using System.Linq;

namespace LandRush {

    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) {
            this.max = max;
            this.cellSize = cellSize;
            this.convFactor = 1.0f / this.cellSize;
            this.width = (int)(this.max / this.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 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 * this.convFactor)) + (int)((z * this.convFactor)) * this.width;
        }
    }
}