Hex - GridManager

GridManager.cs

namespace Gameplay.World
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Runtime.CompilerServices;
    using Core.DataStructure;
    using Core.DataStructure.Adapters;
    using Core.Extension;
    using Core.Helper;
    using Core.World;
    using DxMessaging.Core;
    using DxMessaging.Unity;
    using Abilities.Components;
    using global::World;
    using global::World.Metadata;
    using global::World.ProceduralGeneration;
    using global::World.Tiles;
    using Health;
    using Spawning;
    using Towers;
    using Messages.Entity;
    using Messages.Towers;
    using Messages.World;
    using Networking;
    using Networking.Utils;
    using Portals;
    using Unity.Collections;
    using UnityEditor;
    using UnityEngine;
    using UnityEngine.Tilemaps;
    using Utils;
    using Component = UnityEngine.Component;
    using Object = UnityEngine.Object;

    // Used by game systems to query and modify the grid.
    [DisallowMultipleComponent]
    public sealed class GridManager : MessageAwareComponent, IGridManager 
    {
        private const string Tag = "GridManager";

        private static readonly List<TilemapType> TilemapTypes = Enum.GetValues(typeof(TilemapType)).OfType<TilemapType>().ToList();

        [field: SerializeField]
        public bool useFixedWorldSize { get; set; }
        
        [field: SerializeField]
        public Vector3Int worldSize { get; set; } = new(200, 200, 1);

        public int boundaryPadding = 20;

        public TilemapConfig TilemapConfig => TilemapConfig.Load();

        public IEnumerable<AbstractSpawner> Spawners => _spawners.Distinct();

        public ISet<FastVector3Int> SetPieceBoundaryLocations => _setPieceBoundaryLocations;

        public IReadOnlyCollection<int> IslandIds => _islands.Keys;

        public IReadOnlyCollection<BoundsInt> Islands => _islands.Values;

        public int TotalSize
        {
            get
            {
                if (_totalSize != null)
                {
                    return _totalSize.Value;
                }

                int totalSize = CalculateTotalArea();
                _totalSize = totalSize;
                return totalSize;
            }
        }

        public IEnumerable<FastVector3Int> AllFastPositionsWithinWorldIterator()
        {
            foreach (BoundsInt bounds in _islands.Values)
            {
                foreach (FastVector3Int cell in bounds.AllFastPositionsWithin())
                {
                    yield return cell;
                }
            }
        }

        public bool CollisionBaked => _collisionBaked;

        public List<Dictionary<TilemapType, Tilemap>> Tilemaps { get; private set; }

        public List<Dictionary<TilemapType, Dictionary<FastVector3Int, List<GameObject>>>> tilemapGameObjects { get; set; }

        public NativeParallelHashMap<FastVector3Int, int> GameObjectBlockedPositions => _gameObjectBlockedPositions;
        public NativeParallelHashSet<FastVector3Int> WorldBlockedPositionsCopy => _worldBlockedPositionsCopy;

        public IEnumerable<FastVector3Int> WalkablePositions => _walkablePositions[0].Values.SelectMany(quadTree => quadTree.elements);

        public bool WalkablePositionsBuilt { get; private set; }

        private readonly List<GameObject> _objectsAtPositionCache = new();
        private readonly List<AbstractSpawner> _spawners = new();
        private readonly HashSet<WarpPoint> _warpPoints = new();
        private readonly Dictionary<int, BoundsInt> _islands = new();
        
        private bool _collisionBaked;
        // For our internal use
        private readonly HashSet<FastVector3Int> _worldBlockedPositions = new();
        /*
            Even though it's declared [ReadOnly] in PathfindingJob, for some reason that marks it for write and we can't read from it from the main thread
            So this one's for jobs.
         */
        private NativeParallelHashSet<FastVector3Int> _worldBlockedPositionsCopy; 
        private NativeParallelHashMap<FastVector3Int, int> _gameObjectBlockedPositions;
        private readonly List<GameObject> _walkableObjectSource = new();
        private readonly Dictionary<int, Dictionary<int, QuadTree<FastVector3Int>>> _walkablePositions = new();
        private readonly Dictionary<GameObject, (HashSet<FastVector3Int>, List<MessageRegistrationHandle>)> _messagingHandlesByGameObject = new();
        private Grid _grid;
        // Cache all world positions so that WalkablePositions can be called from the Job system.
        private AllocatorManager.AllocatorHandle _handle = Allocator.Persistent;
        private NativeParallelHashMap<FastVector3Int, Vector3> _gridToWorld;
        private bool _gridToWorldInitialized;
        private readonly Dictionary<int, List<GameObject>> _setPieceGameObjects = new();
        private readonly HashSet<FastVector3Int> _setPieceBoundaryLocations = new();
        private Tile _placeholderTile;

        private int? _totalSize;
        private int? _adjustedTotalSize;

        protected override void Awake()
        {
            _placeholderTile = ScriptableObject.CreateInstance<Tile>();
            base.Awake();
            Initialize();
            if (transform.childCount == 0)
            {
                if (TryGetComponent(out GridCreation gridCreation))
                {
                    gridCreation.RecreateGrid();
                }
            }

            if (TryGetComponent(out SerializedGridManager serializedGridManager))
            {
                serializedGridManager.Deserialize();
            }

            UnityHelpers.SetInstance(Tag, this);
        }

        protected override void RegisterMessageHandlers()
        {
            _ = _messageRegistrationToken.RegisterUntargeted<WorldRegeneratedMessage>(HandleWorldRegeneratedMessage);
        }

        private void HandleWorldRegeneratedMessage(ref WorldRegeneratedMessage _)
        {
            this.Log("World regenerated with {0} islands, baking collision and elevation...", _islands.Count);
            _collisionBaked = false;
            BakeCollisionAndElevation();
        }

        protected override void OnDestroy()
        {
            base.OnDestroy();
            if (_gridToWorld.IsCreated)
            {
                _gridToWorld.Dispose();
            }

            if (_gameObjectBlockedPositions.IsCreated)
            {
                _gameObjectBlockedPositions.Dispose();
            }

            if (_worldBlockedPositionsCopy.IsCreated)
            {
                try
                {
                    _worldBlockedPositionsCopy.Dispose();
                }
                catch
                {
                    // Swallow, jobs might still be using it (and we don't care)
                }
            }

            _handle.Dispose();
            UnityHelpers.ClearInstance(Tag, this);
        }

        public bool TryGetIslandBounds(int islandId, out BoundsInt bounds)
        {
            return _islands.TryGetValue(islandId, out bounds);
        }

        public bool TryCreateIsland(BoundsInt bounds, out int islandId)
        {
            if (!TryGetNextIslandId(out islandId))
            {
                return false;
            }

            BoundsInt withPadding = bounds.WithPadding(boundaryPadding, boundaryPadding);
            if (0 < _islands.Count && _islands.Values.Any(island => island.FastIntersects2D(withPadding)))
            {
                return false;
            }

            _islands[islandId] = bounds;
            _totalSize = null;
            _adjustedTotalSize = null;
            return true;
        }

        public void ClearIslands()
        {
            _islands.Clear();
        }

        public void Initialize()
        {
            SetupMessageHandlers();
            ClearGameObjectsByPosition();
            _collisionBaked = false;
            _worldBlockedPositions.Clear();
            if (_worldBlockedPositionsCopy.IsCreated)
            {
                _worldBlockedPositionsCopy.Clear();
            }

            if (_gameObjectBlockedPositions.IsCreated)
            {
                _gameObjectBlockedPositions.Clear();
            }

            Tilemaps = new List<Dictionary<TilemapType, Tilemap>>(new Dictionary<TilemapType, Tilemap>[TilemapConfig.worldZ]);

            foreach (GameObject child in gameObject.IterateOverChildGameObjects())
            {
                if (!child.TryGetComponent(out Tilemap tilemap))
                {
                    continue;
                }

                TilemapMetadata tilemapMetadata = child.GetComponent<TilemapMetadata>();
                Dictionary<TilemapType, Tilemap> tilemapMapping;
                if (Tilemaps.Count <= tilemapMetadata.Elevation)
                {
                    tilemapMapping = new Dictionary<TilemapType, Tilemap>();
                    Tilemaps.Add(tilemapMapping);
                }
                else
                {
                    tilemapMapping = Tilemaps[tilemapMetadata.Elevation];
                    if (tilemapMapping == null)
                    {
                        tilemapMapping = new Dictionary<TilemapType, Tilemap>();
                        Tilemaps[tilemapMetadata.Elevation] = tilemapMapping;
                    }
                }

                if (!tilemapMapping.TryAdd(tilemapMetadata.TilemapType, tilemap))
                {
                    this.LogError(
                        "Existing tilemap for type {0} found at elevation {1} on object {2}. Current TileMappings: [{3}].",
                        tilemapMetadata.TilemapType, tilemapMetadata.Elevation, gameObject.name,
                        string.Join(",",
                            Tilemaps.SelectMany(existingTilemap => existingTilemap).Select(entry => (entry.Key, entry.Value.name))));
                }
            }

            tilemapGameObjects = new List<Dictionary<TilemapType, Dictionary<FastVector3Int, List<GameObject>>>>();
            
            for (int i = 0; i < TilemapConfig.worldZ; i++)
            {
                tilemapGameObjects.Add(new Dictionary<TilemapType, Dictionary<FastVector3Int, List<GameObject>>>());

                foreach (TilemapType type in TilemapTypes)
                {
                    tilemapGameObjects[i].Add(type, new Dictionary<FastVector3Int, List<GameObject>>());
                }
            }
        }

        public bool TryGetWalkablePositions(int islandId, out QuadTree<FastVector3Int> walkablePositions, int elevation = 0)
        {
            if (_walkablePositions.TryGetValue(elevation, out Dictionary<int, QuadTree<FastVector3Int>> islands))
            {
                return islands.TryGetValue(islandId, out walkablePositions);
            }

            walkablePositions = default;
            return false;
        }

        public bool TryGetIslandForPosition(Vector3 worldPosition, out int islandId, int elevation = 0)
        {
            return TryGetIslandAndBoundsForPosition(worldPosition, out islandId, out _, elevation);
        }
        public bool TryGetBoundsForPosition(Vector3 worldPosition, out BoundsInt bounds, int elevation = 0)
        {
            return TryGetIslandAndBoundsForPosition(worldPosition, out _, out bounds, elevation);
        }
        public bool TryGetIslandAndBoundsForPosition(Vector3 worldPosition, out int islandId, out BoundsInt bounds, int elevation = 0)
        {
            FastVector3Int gridPosition = WorldToGrid(worldPosition, elevation);
            return TryGetIslandAndBoundsForCell(gridPosition, out islandId, out bounds, elevation);
        }

        public bool TryGetIslandForCell(Vector3Int gridPosition, out int islandId, int elevation = 0)
        {
            return TryGetIslandAndBoundsForCell(gridPosition, out islandId, out _, elevation);
        }
        
        public bool TryGetBoundsForCell(Vector3Int gridPosition, out BoundsInt bounds, int elevation = 0)
        {
            return TryGetIslandAndBoundsForCell(gridPosition, out _, out bounds, elevation);
        }
        
        public bool TryGetIslandAndBoundsForCell(Vector3Int gridPosition, out int islandId, out BoundsInt bounds, int elevation = 0)
        {
            foreach (KeyValuePair<int, BoundsInt> islandBounds in _islands)
            {
                bounds = islandBounds.Value;
                if (bounds.FastContains2D(gridPosition))
                {
                    islandId = islandBounds.Key;
                    return true;
                }
            }

            islandId = default;
            bounds = default;
            return false;
        }

        private void ClearGameObjectsByPosition()
        {
            foreach ((_, List<MessageRegistrationHandle> handles) in _messagingHandlesByGameObject.Values)
            {
                foreach (MessageRegistrationHandle handle in handles)
                {
                    _messageRegistrationToken.RemoveRegistration(handle);
                }
            }
            _messagingHandlesByGameObject.Clear();
        }

        public static GridManager GetGridManager()
        {
            return UnityHelpers.Find<GridManager>(Tag);
        }

        public static GridManager Find() => GetGridManager();

        public Vector3 GridToWorld(FastVector3Int position)
        {
            if (_gridToWorldInitialized && _gridToWorld.IsCreated && _gridToWorld.TryGetValue(position, out Vector3 worldPosition))
            {
                return worldPosition;
            }

            return GetGrid().CellToWorld(position);
        }

        public Vector2 GridToWorld2D(FastVector3Int position)
        {
            return GridToWorld(position);
        }

        public FastVector3Int WorldToGrid(Vector3 position)
        {
            return WorldToGrid(position, 0);
        }

        public FastVector3Int WorldToGrid(Vector3 position, int elevation)
        {
            Vector3Int cellPosition = GetGrid().WorldToCell(position);
            cellPosition.z = elevation;
            return cellPosition;
        }

        public Vector3 SnapToClosestGridCell(Vector3 position, int elevation = 0)
        {
            Grid grid = GetGrid();
            Vector3Int cellPosition = grid.WorldToCell(position);
            cellPosition.z = elevation;
            return grid.CellToWorld(cellPosition);
        }

        /*
            Baking allows us to run async code against the GridManager.
         */
        public void BakeCollisionAndElevation()
        {
            if (_collisionBaked)
            {
                this.Log("Ignoring double-bake.");
                return;
            }

            BakeWorld();
            _worldBlockedPositions.Clear();
            _worldBlockedPositionsCopy.Clear();
            _gameObjectBlockedPositions.Clear();
            _spawners.Clear();
            _setPieceBoundaryLocations.Clear();
            foreach (FastVector3Int position in AllFastPositionsWithinWorldIterator())
            {
                if (IsPositionBlockedByWorld(position))
                {
                    _ = _worldBlockedPositions.Add(position);
                    _ = _worldBlockedPositionsCopy.Add(position);
                }

                if (IsPositionBlockedByGameObject(position, out List<GameObject> blockingGameObjectsCount))
                {
                    _ = _gameObjectBlockedPositions[position] = blockingGameObjectsCount.Count;
                }

                foreach (GameObject objectAtPosition in GetObjectsAtPosition(position))
                {
                    if (objectAtPosition.TryGetComponent(out AbstractSpawner spawner))
                    {
                        _spawners.Add(spawner);
                    }
                    else if (objectAtPosition.TryGetComponent(out WarpPoint wayPoint))
                    {
                        _ = _warpPoints.Add(wayPoint);
                    }
                }
            }

            _collisionBaked = true;
            BuildWalkablePositions();
            BuildSetPieceBoundaryLocations();
        }

        public void Clear()
        {
            _collisionBaked = false;
            if (_gameObjectBlockedPositions.IsCreated)
            {
                _gameObjectBlockedPositions.Clear();
            }

            _worldBlockedPositions.Clear();
            if (_worldBlockedPositionsCopy.IsCreated)
            {
                _worldBlockedPositionsCopy.Clear();
            }
            
            foreach (Tilemap tilemap in Tilemaps.SelectMany(tilemapEntry => tilemapEntry.Values))
            {
                tilemap.ClearAllTiles();
                tilemap.gameObject.DestroyAllChildrenGameObjects();
            }

            foreach (Dictionary<FastVector3Int, List<GameObject>> gameObjects in tilemapGameObjects.SelectMany(entry => entry.Values))
            {
                gameObjects.Clear();
            }

            foreach (GameObject child in gameObject.IterateOverChildGameObjects().Where(child => !child.HasComponent<Tilemap>()))
            {
                child.Destroy();
            }
        }

        // Are there any tiles that are blocking in this position? If not, return true.
        public bool IsPositionFree(FastVector3Int position)
        {
            return !IsPositionBlocked(position);
        }

        public bool IsPositionBlocked(FastVector3Int position)
        {
            if (!IsPositionInGrid(position))
            {
                return true;
            }

            return IsPositionBlockedIgnoreBoundsCheck(position);
        }

        private bool IsPositionBlockedIgnoreBoundsCheck(FastVector3Int position)
        {
            if (_collisionBaked)
            {
                if (_worldBlockedPositions.Contains(position))
                {
                    return true;
                }

                return _gameObjectBlockedPositions.TryGetValue(position, out int blockingGameObjectsCount) && 0 < blockingGameObjectsCount;
            }

            return IsPositionBlockedByWorld(position) || IsPositionBlockedByGameObject(position);
        }

        public IEnumerable<FastVector3Int> GetWalkableCellsInRange(FastVector3Int gridPosition, Vector3 worldPosition, float range, float minimumRange = 0f)
        {
            if (!WalkablePositionsBuilt)
            {
                this.LogError("WalkableCellsInRange called before WalkableCellsInRange built.");
                yield break;
            }

            if (!TryGetIslandAndBoundsForCell(gridPosition, out int islandId, out BoundsInt bounds))
            {
                this.LogError(
                    "Failed to find island for world position {0}. Current island count: {1}.", worldPosition,
                    _islands.Count);
                yield break;
            }

            // This is a cheaper "IsPositionInGrid" check (performance optimization)
            BoundsInt worldBounds = bounds;
            int xMin = worldBounds.xMin;
            int xMax = worldBounds.xMax;
            int yMin = worldBounds.yMin;
            int yMax = worldBounds.yMax;
            int zMin = worldBounds.zMin;
            int zMax = worldBounds.zMax;
            int elevation = (int)worldPosition.z;
            foreach (FastVector3Int walkablePosition in _walkablePositions[elevation][islandId].GetElementsInRange(worldPosition, range, minimumRange).Select(walkablePosition => new FastVector3Int(walkablePosition.x, walkablePosition.y, elevation)))
            {
                if (walkablePosition.x < xMin || xMax < walkablePosition.x || walkablePosition.y < yMin ||
                    yMax < walkablePosition.y || walkablePosition.z < zMin || zMax < walkablePosition.z)
                {
                    continue;
                }

                if (IsPositionBlockedIgnoreBoundsCheck(walkablePosition))
                {
                    continue;
                }

                yield return walkablePosition;
            }
        }

        public IEnumerable<Vector3> GetWalkablePositionsInRange(FastVector3Int gridPosition, Vector3 worldPosition, float range, float minimumRange = 0f)
        {
            foreach (Vector3Int walkableCell in GetWalkableCellsInRange(gridPosition, worldPosition, range, minimumRange))
            {
                yield return GridToWorld(walkableCell);
            }
        }

        public void RegisterSetPieceObjects(int setPieceId, List<GameObject> gameObjects)
        {
            _setPieceGameObjects[setPieceId] = gameObjects;
        }

        public bool TryGetSetPieceGameObjects(int setPieceId, out List<GameObject> gameObjects)
        {
            return _setPieceGameObjects.TryGetValue(setPieceId, out gameObjects);
        }

        private bool TryGetNextIslandId(out int nextIslandId)
        {
            for (nextIslandId = _islands.Count; nextIslandId < int.MaxValue; ++nextIslandId)
            {
                if (_islands.ContainsKey(nextIslandId))
                {
                    continue;
                }

                return true;
            }

            nextIslandId = int.MinValue;
            return false;
        }

        public void BakeWorld()
        {
            _gridToWorldInitialized = false;

            int GetAdjustedTotalSize() =>
                _islands.Values.Select(
                        bounds =>
                        {
                            Vector3Int size = AdjustedBounds(bounds).size;
                            return size.x * size.y;
                        })
                    .Sum();

            int adjustedTotalSize = GetAdjustedTotalSize();
            bool needsResize = _adjustedTotalSize != adjustedTotalSize;
            bool needsToCreateBaseIsland = _islands.Count <= 0 && useFixedWorldSize;

            if (needsResize || needsToCreateBaseIsland)
            {
                if (needsToCreateBaseIsland)
                {
                    BoundsInt? tilemapBounds = null;
                    if (0 < Tilemaps.Count)
                    {
                        foreach (Tilemap tilemap in Tilemaps[0].Values)
                        {
                            BoundsInt cellBounds = tilemap.cellBounds;
                            tilemapBounds = tilemapBounds?.ExpandBounds(cellBounds) ?? cellBounds;
                        }
                    }

                    BoundsInt defaultWorldSize = new(new Vector3Int(0 - (worldSize.x / 2), 0 - (worldSize.y / 2), 0), worldSize);
                    if (tilemapBounds != null)
                    {
                        Vector3Int size = tilemapBounds.Value.size;
                        if (size.x * size.y < worldSize.x * worldSize.y)
                        {
                            tilemapBounds = tilemapBounds.Value.ExpandBounds(defaultWorldSize);
                        }
                    }

                    BoundsInt bounds = tilemapBounds ?? defaultWorldSize;

                    _ = TryCreateIsland(bounds, out _);
                    adjustedTotalSize = GetAdjustedTotalSize();
                }

                if (_gameObjectBlockedPositions.IsCreated)
                {
                    _gameObjectBlockedPositions.Dispose();
                }

                if (_worldBlockedPositionsCopy.IsCreated)
                {
                    _worldBlockedPositionsCopy.Dispose();
                }

                if (_gridToWorld.IsCreated)
                {
                    _gridToWorld.Dispose();
                }
                else
                {
#if UNITY_EDITOR
                    AssemblyReloadEvents.beforeAssemblyReload += OnDestroy;
#endif
                }

                _gridToWorld = new NativeParallelHashMap<FastVector3Int, Vector3>(adjustedTotalSize, _handle);
                _gameObjectBlockedPositions = new NativeParallelHashMap<FastVector3Int, int>(adjustedTotalSize, _handle);
                _worldBlockedPositionsCopy = new NativeParallelHashSet<FastVector3Int>(adjustedTotalSize, _handle);
            }
            else
            {
                if (_gridToWorld.IsCreated)
                {
                    _gridToWorld.Clear();
                }

                if (_gameObjectBlockedPositions.IsCreated)
                {
                    _gameObjectBlockedPositions.Clear();
                }

                if (_worldBlockedPositionsCopy.IsCreated)
                {
                    _worldBlockedPositionsCopy.Clear();
                }
            }

            Grid grid = GetGrid();

            foreach (BoundsInt island in _islands.Values)
            {
                BoundsInt bounds = AdjustedBounds(island);
                foreach (FastVector3Int cell in bounds.AllFastPositionsWithin())
                {
                    _gridToWorld[cell] = grid.CellToWorld(cell);
                }
            }

            _gridToWorldInitialized = true;
            _totalSize = CalculateTotalArea();
            _adjustedTotalSize = adjustedTotalSize;
        }

        private int CalculateTotalArea()
        {
            return _islands.Values.Select(
                bounds =>
                {
                    Vector3Int size = bounds.size;
                    return size.x * size.y;
                }).Sum();
        }

        private void BuildWalkablePositions()
        {
            _walkablePositions.Clear();
            _walkableObjectSource.Clear();
            if (_warpPoints.Count <= 0)
            {
                _warpPoints.UnionWith(FindObjectsByType<WarpPoint>(FindObjectsSortMode.None));
                if (_warpPoints.Count <= 0)
                {
                    SceneTransitionManager sceneTransitionManager = SceneTransitionManager.Find(this);
                    if (sceneTransitionManager == null || sceneTransitionManager.IsLobby || sceneTransitionManager.IsGym)
                    {
                        _walkableObjectSource.AddRange(FindObjectsByType<PlayerRespawnPoint>(FindObjectsSortMode.None).Select(respawnPoint => respawnPoint.gameObject));
                        if (_walkableObjectSource.Count <= 0)
                        {
                            this.LogError("No PlayerRespawn found, WalkablePositions will be empty.");
                        }
                    }
                    else
                    {
                        this.LogError("No WarpPoints found, WalkablePositions will be empty.");
                    }

                    if (_walkableObjectSource.Count <= 0)
                    {
                        Dictionary<int, QuadTree<FastVector3Int>> quadTrees = new(_islands.Count);
                        foreach (int island in _islands.Keys)
                        {
                            quadTrees[island] = new QuadTree<FastVector3Int>(
                                Enumerable.Empty<FastVector3Int>(), GridToWorld2D, new Bounds());
                        }

                        _walkablePositions[0] = quadTrees;
                        return;
                    }
                }
                else
                {
                    _walkableObjectSource.AddRange(_warpPoints.Select(warpPoint => warpPoint.gameObject));
                }
            }
            else
            {
                _walkableObjectSource.AddRange(_warpPoints.Select(warpPoint => warpPoint.gameObject));
            }

            Grid grid = GetGrid();
            Dictionary<int, Vector3Int> walkableSourceByIslandId = new(_islands.Count);
            foreach (GameObject walkableSource in _walkableObjectSource)
            {
                Vector3 sourcePosition = walkableSource.transform.position;
                if (sourcePosition == default)
                {
                    this.LogError("Ignoring walkable source {0} with default source position.", walkableSource.name);
                    continue;
                }

                if (TryGetIslandForPosition(sourcePosition, out int islandId))
                {
                    walkableSourceByIslandId[islandId] = grid.WorldToCell(sourcePosition);
                }
            }

            Queue<FastVector3Int> cellsToExplore = new();
            HashSet<FastVector3Int> walkablePositions = new();
            _walkablePositions[0] = new Dictionary<int, QuadTree<FastVector3Int>>();
            foreach (KeyValuePair<int, Vector3Int> islandAndWalkableSource in walkableSourceByIslandId)
            {
                int islandId = islandAndWalkableSource.Key;
                if (!TryGetIslandBounds(islandId, out BoundsInt islandBounds))
                {
                    continue;
                }

                walkablePositions.Clear();
                Vector3Int seed = islandAndWalkableSource.Value;
                cellsToExplore.Clear();
                cellsToExplore.Enqueue(seed);
                bool TestContinuedSearchCandidate(FastVector3Int position)
                {
                    if (!islandBounds.FastContains2D(position))
                    {
                        return false;
                    }

                    if (IsPositionBlockedByWorld(position))
                    {
                        return false;
                    }

                    if (!walkablePositions.Add(position))
                    {
                        return false;
                    }

                    return true;
                }

                _ = TestContinuedSearchCandidate(seed);

                do
                {
                    FastVector3Int currentCell = cellsToExplore.Dequeue();
                    foreach (FastVector3Int neighbor in currentCell.GetNeighborsNoAlloc(Buffers.FastNeighbors))
                    {
                        if (TestContinuedSearchCandidate(neighbor))
                        {
                            cellsToExplore.Enqueue(neighbor);
                        }
                    }
                }
                while (0 < cellsToExplore.Count);

                Vector3 minimum = GridToWorld(islandBounds.min);
                Vector3Int worldSizeMax = islandBounds.max;
                worldSizeMax.x -= 1;
                worldSizeMax.y -= 1;
                worldSizeMax.z -= 1;
                Vector3 maximum = GridToWorld(worldSizeMax);

                float xMin = minimum.x;
                float xMax = maximum.x;
                float yMin = minimum.y;
                float yMax = maximum.y;
                Bounds worldBounds = new(
                    new Vector3((xMax + xMin) / 2f, (yMax + yMin) / 2f, 0f),
                    new Vector3(xMax - xMin, yMax - yMin, 0f));

                _walkablePositions[0][islandId] = new QuadTree<FastVector3Int>(
                    walkablePositions,
                    GridToWorld2D, worldBounds);
            }

            WalkablePositionsBuilt = true;
        }

        private void BuildSetPieceBoundaryLocations()
        {
            foreach (List<GameObject> setPieceObjects in _setPieceGameObjects.Values)
            {
                foreach (GameObject go in setPieceObjects)
                {
                    if (go != null && go.HasComponent<SetPieceBoundary>())
                    {
                        FastVector3Int position = WorldToGrid(go.transform.position);
                         _ = _setPieceBoundaryLocations.Add(position);
                    }
                }
            }
        }

        public bool IsPositionBlockedByWorld(FastVector3Int position)
        {
            if (_collisionBaked)
            {
                return _worldBlockedPositions.Contains(position);
            }
            
            TilemapConfig tilemapConfig = TilemapConfig;
            foreach (KeyValuePair<TilemapType, Tilemap> tilemapTypeAndTilemap in Tilemaps[position.z])
            {
                TilemapEntry entry = tilemapConfig.GetTilemapEntryForType(tilemapTypeAndTilemap.Key);
                if (!entry.HasCollision)
                {
                    continue;
                }

                if (entry.TileObjectType == TileObjectType.TileBase)
                {
                    Tilemap tilemap = tilemapTypeAndTilemap.Value;
                    if (tilemap != null && tilemap.HasTile(position))
                    {
                        return true;
                    }
                }
            }

            return false;
        }

        private bool IsPositionBlockedByGameObject(FastVector3Int position, out List<GameObject> blockingGameObjectsCount)
        {
            blockingGameObjectsCount = null;
            TilemapConfig tilemapConfig = TilemapConfig;
            int z = position.z;
            foreach (TilemapType tilemapType in Tilemaps[z].Keys)
            {
                TilemapEntry entry = tilemapConfig.GetTilemapEntryForType(tilemapType);
                if (!entry.HasCollision)
                {
                    continue;
                }

                if (entry.TileObjectType != TileObjectType.Prefab)
                {
                    continue;
                }

                Dictionary<TilemapType, Dictionary<FastVector3Int, List<GameObject>>> gameObjectsAtElevation = tilemapGameObjects[z];
                Dictionary<FastVector3Int, List<GameObject>> tilemapObjects = gameObjectsAtElevation[tilemapType];

                List<GameObject> gameObjects = null;
                bool? foundValue = tilemapObjects?.TryGetValue(position, out gameObjects);
                if (foundValue == true && gameObjects != null)
                {
                    _ = gameObjects.RemoveAll(go => go.IsDead());
                    blockingGameObjectsCount ??= new List<GameObject>();
                    blockingGameObjectsCount.AddRange(gameObjects);
                }
            }

            return blockingGameObjectsCount is { Count: > 0 };
        }

        private bool IsPositionBlockedByGameObject(FastVector3Int position)
        {
            TilemapConfig tilemapConfig = TilemapConfig;
            foreach (TilemapType tilemapType in Tilemaps[position.z].Keys)
            {
                TilemapEntry entry = tilemapConfig.GetTilemapEntryForType(tilemapType);
                if (!entry.HasCollision)
                {
                    continue;
                }

                if (entry.TileObjectType != TileObjectType.Prefab)
                {
                    continue;
                }

                Dictionary<TilemapType, Dictionary<FastVector3Int, List<GameObject>>> gameObjectsAtElevation = tilemapGameObjects[position.z];
                Dictionary<FastVector3Int, List<GameObject>> tilemapObjects = gameObjectsAtElevation[tilemapType];

                List<GameObject> gameObjects = null;
                bool? foundValue = tilemapObjects?.TryGetValue(position, out gameObjects);
                if (foundValue == true && gameObjects != null)
                {
                    _ = gameObjects.RemoveAll(go => go.IsDead());
                    if (0 < gameObjects.Count)
                    {
                        return true;
                    }
                }
            }

            return false;
        }

        public bool DoesTilemapHaveTileAtPosition(TilemapType type, Vector3Int position)
        {
            return Tilemaps[position.z][type].HasTile(position);
        }

        public List<GameObject> GetObjectsAtPosition(FastVector3Int position)
        {
            _objectsAtPositionCache.Clear();
            TilemapConfig tilemapConfig = TilemapConfig;
            int z = position.z;
            foreach (TilemapType tilemapType in Tilemaps[z].Keys)
            {
                TilemapEntry entry = tilemapConfig.GetTilemapEntryForType(tilemapType);
                if (entry.TileObjectType != TileObjectType.Prefab)
                {
                    continue;
                }

                Dictionary<TilemapType, Dictionary<FastVector3Int, List<GameObject>>> gameObjectsAtElevation = tilemapGameObjects[z];
                Dictionary<FastVector3Int, List<GameObject>> tilemapObjects = gameObjectsAtElevation[tilemapType];

                List<GameObject> gameObjects = null;
                bool? foundValue = tilemapObjects?.TryGetValue(position, out gameObjects);
                if (foundValue == true && gameObjects != null)
                {
                    _ = gameObjects.RemoveAll(go => go.IsDead());
                    if (gameObjects.Count <= 0)
                    {
                        _ = tilemapObjects.Remove(position);
                        continue;
                    }

                    foreach (GameObject go in gameObjects)
                    {
                        _objectsAtPositionCache.Add(go);
                    }
                }
            }

            return _objectsAtPositionCache;
        }

        public IEnumerable<KTile> GetTilesAtPosition(Vector3Int position)
        {
            TilemapConfig tilemapConfig = TilemapConfig;
            foreach (KeyValuePair<TilemapType, Tilemap> tilemapTypeAndTilemap in Tilemaps[position.z])
            {
                TilemapEntry entry = tilemapConfig.GetTilemapEntryForType(tilemapTypeAndTilemap.Key);
                if (entry.TileObjectType != TileObjectType.TileBase)
                {
                    continue;
                }

                KTile tile = tilemapTypeAndTilemap.Value.GetTile<KTile>(position);
                if (tile != null)
                {
                    yield return tile;
                }
            }
        }

        public bool TryPlaceTile(Object tile, FastVector3Int position)
        {
            if (!IsPositionInGrid(position))
            {
                return false;
            }

            switch (tile)
            {
                case ITilemapTile tilemapTile:
                {
                    PlaceTilemapTileIgnoreBoundsCheck(tilemapTile, position);
                    return true;
                }
                case GameObject gameObjectTile:
                {
                    return TryPlaceGameObject(gameObjectTile, position);
                }
                case Component component:
                {
                    return TryPlaceGameObject(component.gameObject, position);
                }
                default:
                    this.LogError($"Don't know how to place object {tile} in tilemap");
                    return false;
            }
        }

        public bool TryPlaceTileIgnoreBoundsCheck(ITilemapTile tile, Vector3Int position)
        {
            if (IsPositionBlockedIgnoreBoundsCheck(position))
            {
                return false;
            }

            PlaceTilemapTileIgnoreBoundsCheck(tile, position);
            return true;
        }

        private bool TryPlaceGameObject(GameObject gameObjectTile, Vector3Int position) => gameObjectTile.IsPrefab()
            ? TryPlacePrefab(gameObjectTile, position, out _)
            : TryPlaceGameObjectInstance(gameObjectTile, position);

        public bool TryPlaceTilemapTile(ITilemapTile tilemapTile, FastVector3Int position, bool force = false, bool ignoreBoundsCheck = false)
        {
            if (!force)
            {
                if (!ignoreBoundsCheck && !IsPositionInGrid(position))
                {
                    return false;
                }
                
                bool isPositionBlocked = TilemapConfig.DoesTilemapHaveCollision(tilemapTile.TilemapType) &&
                                         IsPositionBlocked(position);
                if (isPositionBlocked)
                {
                    return false;
                }
            }

            PlaceTilemapTileIgnoreBoundsCheck(tilemapTile, position);
            return true;
        }

        private void PlaceTilemapTileIgnoreBoundsCheck(ITilemapTile tilemapTile, FastVector3Int position)
        {
            TilemapType tilemapType = tilemapTile.TilemapType;
            TilemapEntry tilemapEntry = TilemapConfig.GetTilemapEntryForType(tilemapType);

            if (tilemapEntry.HasCollision)
            {
                _ = _worldBlockedPositions.Add(position);
                // Jobs will get mad if we write to the copy, so cheat and place it in the dynamic GameObjects list
                if (!_gameObjectBlockedPositions.TryGetValue(position, out int count))
                {
                    count = 0;
                }

                ++count;
                _gameObjectBlockedPositions[position] = count;
            }

            Tilemap tilemap = GetTilemapForTypeAndPosition(tilemapType, position);
            tilemap.SetTile(position, tilemapTile as TileBase);
        }

        public bool TryPlacePrefab(GameObject prefab, FastVector3Int position, out GameObject instance)
        {
            if (!IsPositionInGrid(position))
            {
                prefab.LogError("Position is not within grid - cannot place in grid at position {0}!", position);
                instance = default;
                return false;
            }

            if (!prefab.HasComponent<TilePrefab>())
            {
                prefab.LogError("Does not have TilePrefab - cannot place in grid at position {0}!", position);
                instance = default;
                return false;
            }

            Vector3 worldPosition = GridToWorld(position);
            instance = Instantiate(prefab, worldPosition, Quaternion.identity);
            SetNameByPosition(instance, position);

            if (Application.isPlaying)
            {
                if (NetUtils.IsHost())
                {
                    _ = instance.TryNetworkSpawn();
                }
            }
            else
            {
                /*
                    Manually force "spawn logic" on entities without spawning them.
                    In particular, this is a hack to make AbilityManager work with 
                    scene objects for ParallelSync to work with enemy scene objects.
                 */
                if (instance.TryGetComponent(out AbilityManager abilityManager))
                {
                    abilityManager.OnNetworkSpawn();
                }
            }

            return TryPlaceGameObjectInstance(instance, position);
        }

        public bool TryPlaceGameObjectInstance(GameObject gameObjectToPlace, FastVector3Int position)
        {
            if (!gameObjectToPlace.TryGetComponent(out TilePrefab tilePrefab))
            {
                gameObjectToPlace.LogError("Does not have TilePrefab - cannot place in grid at position {0}!", position);
                return false;
            }

            TilemapType tilemapType = tilePrefab.tilemapType;
            TilemapEntry tilemapEntry = TilemapConfig.GetTilemapEntryForType(tilemapType);

            Dictionary<TilemapType, Dictionary<FastVector3Int, List<GameObject>>> gameObjectsAtElevation = this.tilemapGameObjects[position.z];
            Dictionary<FastVector3Int, List<GameObject>> tilemapGameObjectsAtElevation = gameObjectsAtElevation[tilemapType];

            List<GameObject> gameObjects = tilemapGameObjectsAtElevation.GetOrAdd(position);
            if (gameObjects.Contains(gameObjectToPlace))
            {
                // We expect towers to be double placed as a belt-and-suspenders check
                if (!gameObjectToPlace.IsTower())
                {
                    gameObjectToPlace.LogError("Already exists - cannot place in grid at position {0}!", position);
                }

                return false;
            }

            if (tilemapEntry.HasCollision)
            {
                HashSet<FastVector3Int> existingPositions;
                if (!_messagingHandlesByGameObject.TryGetValue(gameObjectToPlace, out (HashSet<FastVector3Int> positions, List<MessageRegistrationHandle> handles) positionsAndHandle))
                {
                    MessageRegistrationHandle deathHandle = _messageRegistrationToken.RegisterGameObjectBroadcast<DeathMessage>(gameObjectToPlace, HandleEntityDeath);
                    MessageRegistrationHandle towerRefundedHandle = _messageRegistrationToken.RegisterGameObjectBroadcast(gameObjectToPlace, (ref TowerRefundedMessage _) => TryRemoveGameObject(gameObjectToPlace));
                    existingPositions = new HashSet<FastVector3Int>();
                    List<MessageRegistrationHandle> handles = new(2) { deathHandle, towerRefundedHandle };
                    _messagingHandlesByGameObject[gameObjectToPlace] = (existingPositions, handles);
                }
                else
                {
                    existingPositions = positionsAndHandle.positions;
                }

                if (!existingPositions.Contains(position))
                {
                    if (_gameObjectBlockedPositions.TryGetValue(position, out int count))
                    {
                        _gameObjectBlockedPositions[position] = count + 1;
                    }
                    else
                    {
                        _gameObjectBlockedPositions[position] = 1;
                    }
                    _ = existingPositions.Add(position);
                }
            }

            if (tilemapType == TilemapType.PlacementBounds && Tilemaps[position.z].TryGetValue(tilemapType, out Tilemap tilemap))
            {
                tilemap.SetTile(position, _placeholderTile ??= ScriptableObject.CreateInstance<Tile>());
            }

            if (gameObjectToPlace.TryGetComponent(out AbstractSpawner spawner))
            {
                _spawners.Add(spawner);
            }

            gameObjects.Add(gameObjectToPlace);
            return true;
        }

        public bool TryRemoveGameObject(GameObject gameObjectToRemove, FastVector3Int? maybePosition = null)
        {
            bool removed = false;

            if (gameObjectToRemove.TryGetComponent(out AbstractSpawner spawner))
            {
                int index = _spawners.IndexOf(spawner);
                if (0 <= index)
                {
                    _spawners.RemoveAtSwapBack(index);
                }
            }

            if (!gameObjectToRemove.TryGetComponent(out TilePrefab tilePrefab))
            {
                return false;
            }

            {
                int elevation = gameObjectToRemove.GetElevation();
                FastVector3Int position = maybePosition ?? WorldToGrid(gameObjectToRemove.transform.position, elevation);
                if (tilemapGameObjects[elevation].TryGetValue(tilePrefab.tilemapType, out Dictionary<FastVector3Int, List<GameObject>> gameObjectsByPosition))
                {
                    if (gameObjectsByPosition.TryGetValue(position, out List<GameObject> gameObjects))
                    {
                        removed = gameObjects.Remove(gameObjectToRemove);
                        if (gameObjects.Count <= 0)
                        {
                            if (Tilemaps[elevation].TryGetValue(tilePrefab.tilemapType, out Tilemap tilemap))
                            {
                                tilemap.SetTile(position, null);
                            }

                            _ = gameObjectsByPosition.Remove(position);
                        }
                    }
                }
            }

            // This is only populated for tiles with collision
            if (_messagingHandlesByGameObject.Remove(gameObjectToRemove, out (HashSet<FastVector3Int> positions, List<MessageRegistrationHandle> handles) positionAndHandle))
            {
                /*
                    When the application shuts down, we get removal calls from SetPieceBoundaries
                    where the messageRegistrationToken has already been set to null. When this
                    happens, we can just ignore it.
                */
                if (_messageRegistrationToken != null)
                {
                    foreach (MessageRegistrationHandle handle in positionAndHandle.handles)
                    {
                        _messageRegistrationToken.RemoveRegistration(handle);
                    }
                }

                HashSet<FastVector3Int> positions = positionAndHandle.positions;
                if (0 < positions.Count)
                {
                    foreach (FastVector3Int position in positions)
                    {
                        if (_gameObjectBlockedPositions.TryGetValue(position, out int count))
                        {
                            --count;
                            if (count <= 0)
                            {
                                _ = _gameObjectBlockedPositions.Remove(position);
                            }
                            else
                            {
                                _gameObjectBlockedPositions[position] = count;
                            }
                        }
                    }
                }

                removed = true;
            }

            return removed;
        }

        private void HandleEntityDeath(ref DeathMessage deathMessage)
        {
            GameObject entity = deathMessage.entity;
            // Ignore deaths for towers, they get respawned
            if (entity != null && entity.HasComponent<Tower>())
            {
                return;
            }
            _ = TryRemoveGameObject(entity);
        }

        private Tilemap GetTilemapForTypeAndPosition(TilemapType tilemapType, Vector3Int position)
        {
            Dictionary<TilemapType, Tilemap> tilemapsAtElevation = Tilemaps[position.z];
            return tilemapsAtElevation[tilemapType];
        }

        private static void SetNameByPosition(GameObject instance, Vector3Int position)
        {
            string instanceName = instance.name;
            int cloneIndex = instanceName.IndexOf("(Clone)", StringComparison.Ordinal);
            if (0 <= cloneIndex)
            {
                instanceName = instanceName.Substring(0, cloneIndex);
            }

            instance.name = $"{instanceName} [{position.x},{position.y},{position.z}]";
        }

        private static BoundsInt AdjustedBounds(BoundsInt bounds)
        {
            const int padding = 5;
            return bounds.WithPadding(padding, padding);
        }

        public bool IsPositionInGrid(FastVector3Int gridLocation)
        {
            return 0 < _islands.Count && _islands.Values.Any(island => island.FastContains2D(gridLocation));
        }

        public void SetNewTilemaps(List<Dictionary<TilemapType, Tilemap>> tilemaps)
        {
            _collisionBaked = false;
            Tilemaps = tilemaps;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public Grid GetGrid()
        {
            if (_grid != null)
            {
                return _grid;
            }

            return TryGetComponent(out _grid) ? _grid : null;
        }
    }
}