LevelObjectManager.cs

#if CLIENT
using Barotrauma.Particles;
#endif
using Barotrauma.Networking;
using FarseerPhysics;
using Microsoft.Xna.Framework;
using System;
using System.Collections.Generic;
using System.Linq;
using Voronoi2;
using Barotrauma.Extensions;
 
namespace Barotrauma
{
    partial class LevelObjectManager : Entity, IServerSerializable
    {
        const int GridSize = 2000;
 
        private List<LevelObject> objects;
        private List<LevelObject> updateableObjects;
        private List<LevelObject>[,] objectGrid;
 
        const float ParallaxStrength = 0.0001f;
 
        public float GlobalForceDecreaseTimer
        {
            get;
            private set;
        }
 
        public LevelObjectManager() : base(null, Entity.NullEntityID)
        {
        }
 
        private readonly struct EventData : NetEntityEvent.IData
        {
            public readonly LevelObject LevelObject;
            
            public EventData(LevelObject levelObject)
            {
                LevelObject = levelObject;
            }
        }
        
        class SpawnPosition
        {
            public readonly GraphEdge GraphEdge;
            public readonly Vector2 Normal;
            public readonly List<LevelObjectPrefab.SpawnPosType> SpawnPosTypes = new List<LevelObjectPrefab.SpawnPosType>();
            public readonly Alignment Alignment;
            public readonly float Length;
 
            private readonly float noiseVal;
 
 
            public SpawnPosition(GraphEdge graphEdge, Vector2 normal, LevelObjectPrefab.SpawnPosType spawnPosType, Alignment alignment)
                : this(graphEdge, normal, spawnPosType.ToEnumerable(), alignment)
            { }
 
            public SpawnPosition(GraphEdge graphEdge, Vector2 normal, IEnumerable<LevelObjectPrefab.SpawnPosType> spawnPosTypes, Alignment alignment)
            {
                GraphEdge = graphEdge;
                Normal = normal.NearlyEquals(Vector2.Zero) ? Vector2.UnitY : Vector2.Normalize(normal);
                SpawnPosTypes.AddRange(spawnPosTypes);
 
                if (spawnPosTypes.Contains(LevelObjectPrefab.SpawnPosType.MainPath) || 
                    spawnPosTypes.Contains(LevelObjectPrefab.SpawnPosType.LevelStart) ||
                    spawnPosTypes.Contains(LevelObjectPrefab.SpawnPosType.LevelEnd))
                {
                    Length = 1000.0f;
                    Normal = Vector2.Zero;
                    Alignment = Alignment.Any;
                }
                else
                {
                    Alignment = alignment;                
                    Length = Vector2.Distance(graphEdge.Point1, graphEdge.Point2);
                }
 
                noiseVal =  
                    (float)(PerlinNoise.CalculatePerlin(GraphEdge.Point1.X / 10000.0f, GraphEdge.Point1.Y / 10000.0f, 0.5f) +
                            PerlinNoise.CalculatePerlin(GraphEdge.Point1.X / 20000.0f, GraphEdge.Point1.Y / 20000.0f, 0.5f));
            }
 
            public float GetSpawnProbability(LevelObjectPrefab prefab)
            {
                if (prefab.ClusteringAmount <= 0.0f) { return Length; }
                float noise = (noiseVal + PerlinNoise.GetPerlin(prefab.ClusteringGroup, prefab.ClusteringGroup * 0.3f)) % 1.0f;
                return Length * (float)Math.Pow(noise, prefab.ClusteringAmount);
            }
        }
 
        public void PlaceObjects(Level level, int amount)
        {
            objectGrid = new List<LevelObject>[
                level.Size.X / GridSize,
                (level.Size.Y - level.BottomPos) / GridSize];
 
            List<SpawnPosition> availableSpawnPositions = new List<SpawnPosition>();
            var levelCells = level.GetAllCells();
            availableSpawnPositions.AddRange(GetAvailableSpawnPositions(levelCells, LevelObjectPrefab.SpawnPosType.Wall));
            availableSpawnPositions.AddRange(GetAvailableSpawnPositions(level.SeaFloor.Cells, LevelObjectPrefab.SpawnPosType.SeaFloor));
 
            foreach (Structure structure in Structure.WallList)
            {
                if (!structure.HasBody || structure.IsHidden) { continue; }
 
                LevelObjectPrefab.SpawnPosType spawnPosType = LevelObjectPrefab.SpawnPosType.None;
                if (level.Ruins.Any(r => r.Submarine == structure.Submarine))
                {
                    spawnPosType = LevelObjectPrefab.SpawnPosType.RuinWall;
                }
                else if (structure.Submarine?.Info?.Type == SubmarineType.Outpost)
                {
                    spawnPosType = LevelObjectPrefab.SpawnPosType.OutpostWall;
                }
                else
                {
                    continue;
                }
 
                if (structure.IsHorizontal)
                {
                    bool topHull = Hull.FindHull(structure.WorldPosition + Vector2.UnitY * 64) != null;
                    bool bottomHull = Hull.FindHull(structure.WorldPosition - Vector2.UnitY * 64) != null;
                    if (topHull && bottomHull) { continue; }
 
                    availableSpawnPositions.Add(new SpawnPosition(
                        new GraphEdge(new Vector2(structure.WorldRect.X, structure.WorldPosition.Y), new Vector2(structure.WorldRect.Right, structure.WorldPosition.Y)),
                        bottomHull ? Vector2.UnitY : -Vector2.UnitY,
                        spawnPosType,
                        bottomHull ? Alignment.Bottom : Alignment.Top));
                }
                else
                {
                    bool rightHull = Hull.FindHull(structure.WorldPosition + Vector2.UnitX * 64) != null;
                    bool leftHull = Hull.FindHull(structure.WorldPosition - Vector2.UnitX * 64) != null;
                    if (rightHull && leftHull) { continue; }
 
                    availableSpawnPositions.Add(new SpawnPosition(
                        new GraphEdge(new Vector2(structure.WorldPosition.X, structure.WorldRect.Y), new Vector2(structure.WorldPosition.X, structure.WorldRect.Y - structure.WorldRect.Height)),
                        leftHull ? Vector2.UnitX : -Vector2.UnitX,
                        spawnPosType,
                        leftHull ? Alignment.Left : Alignment.Right));
                }
            }
 
            foreach (var posOfInterest in level.PositionsOfInterest)
            {
                if (posOfInterest.PositionType != Level.PositionType.MainPath && posOfInterest.PositionType != Level.PositionType.SidePath) { continue; }
 
                availableSpawnPositions.Add(new SpawnPosition(
                    new GraphEdge(posOfInterest.Position.ToVector2(), posOfInterest.Position.ToVector2() + Vector2.UnitX), 
                    Vector2.UnitY, 
                    LevelObjectPrefab.SpawnPosType.MainPath, 
                    Alignment.Top));
            }
 
            availableSpawnPositions.Add(new SpawnPosition(
                new GraphEdge(level.StartPosition - Vector2.UnitX, level.StartPosition + Vector2.UnitX),
                -Vector2.UnitY, LevelObjectPrefab.SpawnPosType.LevelStart, Alignment.Top));
            availableSpawnPositions.Add(new SpawnPosition(
                new GraphEdge(level.EndPosition - Vector2.UnitX, level.EndPosition + Vector2.UnitX),
                -Vector2.UnitY, LevelObjectPrefab.SpawnPosType.LevelEnd, Alignment.Top));
 
            var availablePrefabs =LevelObjectPrefab.Prefabs.OrderBy(p => p.UintIdentifier).ToList();
            objects = new List<LevelObject>();
            updateableObjects = new List<LevelObject>();
 
            Dictionary<LevelObjectPrefab, List<SpawnPosition>> suitableSpawnPositions = new Dictionary<LevelObjectPrefab, List<SpawnPosition>>();
            Dictionary<LevelObjectPrefab, List<float>> spawnPositionWeights = new Dictionary<LevelObjectPrefab, List<float>>();
            for (int i = 0; i < amount; i++)
            {
                //get a random prefab and find a place to spawn it
                LevelObjectPrefab prefab = GetRandomPrefab(level, availablePrefabs);
                if (prefab == null) { continue; }
                if (!suitableSpawnPositions.ContainsKey(prefab))
                {
                    float minDistance = level.Size.X * 0.2f;
 
                    bool allowAtStart = prefab.AllowAtStart;
                    bool allowAtEnd = prefab.AllowAtEnd;
                    if (GameMain.GameSession?.GameMode is PvPMode)
                    {
                        //in PvP mode, the object must be allowed at both the start and end to be placed at either end
                        //since the 2nd team starts at the end of the level, it'd be unfair to allow e.g. ballast flora to spawn at the end of the level but not the start
                        allowAtEnd = allowAtStart = allowAtEnd && allowAtStart;
                    }
 
                    suitableSpawnPositions.Add(prefab, 
                        availableSpawnPositions.Where(sp =>
                            sp.SpawnPosTypes.Any(type => prefab.SpawnPos.HasFlag(type)) && 
                            sp.Length >= prefab.MinSurfaceWidth &&
                            (allowAtStart || !level.IsCloseToStart(sp.GraphEdge.Center, minDistance)) &&
                            (allowAtEnd || !level.IsCloseToEnd(sp.GraphEdge.Center, minDistance)) &&
                            (sp.Alignment == Alignment.Any || prefab.Alignment.HasFlag(sp.Alignment))).ToList());
 
                    spawnPositionWeights.Add(prefab,
                        suitableSpawnPositions[prefab].Select(sp => sp.GetSpawnProbability(prefab)).ToList());
                }
 
                SpawnPosition spawnPosition = ToolBox.SelectWeightedRandom(suitableSpawnPositions[prefab], spawnPositionWeights[prefab], Rand.RandSync.ServerAndClient);
                if (spawnPosition == null && prefab.SpawnPos != LevelObjectPrefab.SpawnPosType.None) { continue; }
                PlaceObject(prefab, spawnPosition, level);
                if (prefab.MaxCount < amount)
                {
                    if (objects.Count(o => o.Prefab == prefab) >= prefab.MaxCount)
                    {
                        availablePrefabs.Remove(prefab);
                    }
                }
            }
 
            foreach (Level.Cave cave in level.Caves)
            {
                availablePrefabs = LevelObjectPrefab.Prefabs.Where(p => p.SpawnPos.HasFlag(LevelObjectPrefab.SpawnPosType.CaveWall))
                    .OrderBy(p => p.UintIdentifier).ToList();
                availableSpawnPositions.Clear();
                suitableSpawnPositions.Clear(); 
                spawnPositionWeights.Clear();
 
                var caveCells = cave.Tunnels.SelectMany(t => t.Cells);
                List<VoronoiCell> caveWallCells = new List<VoronoiCell>();
                foreach (var edge in caveCells.SelectMany(c => c.Edges))
                {
                    if (!edge.NextToCave) { continue; }
                    if (edge.Cell1?.CellType == CellType.Solid) { caveWallCells.Add(edge.Cell1); }
                    if (edge.Cell2?.CellType == CellType.Solid) { caveWallCells.Add(edge.Cell2); }
                }
                availableSpawnPositions.AddRange(GetAvailableSpawnPositions(caveWallCells.Distinct(), LevelObjectPrefab.SpawnPosType.CaveWall));
 
                for (int i = 0; i < cave.CaveGenerationParams.LevelObjectAmount; i++)
                {
                    //get a random prefab and find a place to spawn it
                    LevelObjectPrefab prefab = GetRandomPrefab(cave.CaveGenerationParams, availablePrefabs, requireCaveSpecificOverride: true);
                    if (prefab == null) { continue; }
                    if (!suitableSpawnPositions.ContainsKey(prefab))
                    {
                        suitableSpawnPositions.Add(prefab,
                            availableSpawnPositions.Where(sp =>
                                sp.Length >= prefab.MinSurfaceWidth &&
                                (sp.Alignment == Alignment.Any || prefab.Alignment.HasFlag(sp.Alignment))).ToList());
                        spawnPositionWeights.Add(prefab,
                            suitableSpawnPositions[prefab].Select(sp => sp.GetSpawnProbability(prefab)).ToList());
                    }
                    SpawnPosition spawnPosition = ToolBox.SelectWeightedRandom(suitableSpawnPositions[prefab], spawnPositionWeights[prefab], Rand.RandSync.ServerAndClient);
                    if (spawnPosition == null && prefab.SpawnPos != LevelObjectPrefab.SpawnPosType.None) { continue; }
                    PlaceObject(prefab, spawnPosition, level, cave);
                    if (amount > prefab.MaxCount && objects.Count > prefab.MaxCount)
                    {
                        int objectCount = 0;
                        for (int j = 0; j < objects.Count; j++)
                        {
                            if (objects[j].Prefab == prefab && objects[j].ParentCave == cave)
                            {
                                objectCount++;
                                if (objectCount >= prefab.MaxCount)
                                {
                                    break;
                                }
                            }
                        }
                        if (objectCount >= prefab.MaxCount)
                        {
                            availablePrefabs.Remove(prefab);
                        }
                    }
                }             
            }
        }
 
        public void PlaceNestObjects(Level level, Level.Cave cave, Vector2 nestPosition, float nestRadius, int objectAmount)
        {
            Rand.SetSyncedSeed(ToolBox.StringToInt(level.Seed));
 
            var availablePrefabs = LevelObjectPrefab.Prefabs.Where(p => p.SpawnPos.HasFlag(LevelObjectPrefab.SpawnPosType.NestWall))
                .OrderBy(p => p.UintIdentifier).ToList();
            Dictionary<LevelObjectPrefab, List<SpawnPosition>> suitableSpawnPositions = new Dictionary<LevelObjectPrefab, List<SpawnPosition>>();
            Dictionary<LevelObjectPrefab, List<float>> spawnPositionWeights = new Dictionary<LevelObjectPrefab, List<float>>();
 
            List<SpawnPosition> availableSpawnPositions = new List<SpawnPosition>();
            var caveCells = cave.Tunnels.SelectMany(t => t.Cells);
            List<VoronoiCell> caveWallCells = new List<VoronoiCell>();
            foreach (var edge in caveCells.SelectMany(c => c.Edges))
            {
                if (!edge.NextToCave) { continue; }
                if (MathUtils.LineSegmentToPointDistanceSquared(edge.Point1.ToPoint(), edge.Point2.ToPoint(), nestPosition.ToPoint()) > nestRadius * nestRadius) { continue; }
                if (edge.Cell1?.CellType == CellType.Solid) { caveWallCells.Add(edge.Cell1); }
                if (edge.Cell2?.CellType == CellType.Solid) { caveWallCells.Add(edge.Cell2); }
            }
            availableSpawnPositions.AddRange(GetAvailableSpawnPositions(caveWallCells.Distinct(), LevelObjectPrefab.SpawnPosType.CaveWall));
 
            for (int i = 0; i < objectAmount; i++)
            {
                //get a random prefab and find a place to spawn it
                LevelObjectPrefab prefab = GetRandomPrefab(cave.CaveGenerationParams, availablePrefabs, requireCaveSpecificOverride: false);
                if (prefab == null) { continue; }
                if (!suitableSpawnPositions.ContainsKey(prefab))
                {
                    suitableSpawnPositions.Add(prefab,
                        availableSpawnPositions.Where(sp =>
                            sp.Length >= prefab.MinSurfaceWidth &&
                            (sp.Alignment == Alignment.Any || prefab.Alignment.HasFlag(sp.Alignment))).ToList());
                    spawnPositionWeights.Add(prefab,
                        suitableSpawnPositions[prefab].Select(sp => sp.GetSpawnProbability(prefab)).ToList());
                }
                SpawnPosition spawnPosition = ToolBox.SelectWeightedRandom(suitableSpawnPositions[prefab], spawnPositionWeights[prefab], Rand.RandSync.ServerAndClient);
                if (spawnPosition == null && prefab.SpawnPos != LevelObjectPrefab.SpawnPosType.None) { continue; }
                PlaceObject(prefab, spawnPosition, level);
                if (objects.Count(o => o.Prefab == prefab) >= prefab.MaxCount)
                {
                    availablePrefabs.Remove(prefab);
                }                    
            }            
        }
 
        private void PlaceObject(LevelObjectPrefab prefab, SpawnPosition spawnPosition, Level level, Level.Cave parentCave = null)
        {
            float rotation = 0.0f;
            if (prefab.AlignWithSurface && spawnPosition != null && spawnPosition.Normal.LengthSquared() > 0.001f)
            {
                rotation = MathUtils.VectorToAngle(new Vector2(spawnPosition.Normal.Y, spawnPosition.Normal.X));
            }
            rotation += Rand.Range(prefab.RandomRotationRad.X, prefab.RandomRotationRad.Y, Rand.RandSync.ServerAndClient);
 
            Vector2 position = Vector2.Zero;
            Vector2 edgeDir = Vector2.UnitX;
            if (spawnPosition == null)
            {
                position = new Vector2(
                    Rand.Range(0.0f, level.Size.X, Rand.RandSync.ServerAndClient),
                    Rand.Range(0.0f, level.Size.Y, Rand.RandSync.ServerAndClient));
            }
            else
            {
                edgeDir = (spawnPosition.GraphEdge.Point1 - spawnPosition.GraphEdge.Point2) / spawnPosition.Length;
                position = spawnPosition.GraphEdge.Point2 + edgeDir * Rand.Range(prefab.MinSurfaceWidth / 2.0f, spawnPosition.Length - prefab.MinSurfaceWidth / 2.0f, Rand.RandSync.ServerAndClient);
            }
 
            if (!MathUtils.NearlyEqual(prefab.RandomOffset.X, 0.0f) || !MathUtils.NearlyEqual(prefab.RandomOffset.Y, 0.0f))
            {
                Vector2 offsetDir = spawnPosition.Normal.LengthSquared() > 0.001f ? spawnPosition.Normal : Rand.Vector(1.0f, Rand.RandSync.ServerAndClient);
                position += offsetDir * Rand.Range(prefab.RandomOffset.X, prefab.RandomOffset.Y, Rand.RandSync.ServerAndClient);
            }
 
            var newObject = new LevelObject(prefab,
                new Vector3(position, Rand.Range(prefab.DepthRange.X, prefab.DepthRange.Y, Rand.RandSync.ServerAndClient)), Rand.Range(prefab.MinSize, prefab.MaxSize, Rand.RandSync.ServerAndClient), rotation);
            AddObject(newObject, level);
            newObject.ParentCave = parentCave;
 
            foreach (LevelObjectPrefab.ChildObject child in prefab.ChildObjects)
            {
                int childCount = Rand.Range(child.MinCount, child.MaxCount + 1, Rand.RandSync.ServerAndClient);
                for (int j = 0; j < childCount; j++)
                {
                    var matchingPrefabs = LevelObjectPrefab.Prefabs.Where(p => child.AllowedNames.Contains(p.Name));
                    int prefabCount = matchingPrefabs.Count();
                    var childPrefab = prefabCount == 0 ? null : matchingPrefabs.ElementAt(Rand.Range(0, prefabCount, Rand.RandSync.ServerAndClient));
                    if (childPrefab == null) { continue; }
 
                    Vector2 childPos = position + edgeDir * Rand.Range(-0.5f, 0.5f, Rand.RandSync.ServerAndClient) * prefab.MinSurfaceWidth;
 
                    var childObject = new LevelObject(childPrefab,
                        new Vector3(childPos, Rand.Range(childPrefab.DepthRange.X, childPrefab.DepthRange.Y, Rand.RandSync.ServerAndClient)),
                        Rand.Range(childPrefab.MinSize, childPrefab.MaxSize, Rand.RandSync.ServerAndClient),
                        rotation + Rand.Range(childPrefab.RandomRotationRad.X, childPrefab.RandomRotationRad.Y, Rand.RandSync.ServerAndClient));
 
                    AddObject(childObject, level);
                    childObject.ParentCave = parentCave;
                }
            }
        }
 
        private void AddObject(LevelObject newObject, Level level)
        {
            if (newObject.Triggers != null)
            {
                foreach (LevelTrigger trigger in newObject.Triggers)
                {
                    trigger.OnTriggered += (levelTrigger, obj) =>
                    {
                        OnObjectTriggered(newObject, levelTrigger, obj);
                    };
                }
            }
 
            var spriteCorners = new List<Vector2>
            {
                Vector2.Zero, Vector2.Zero, Vector2.Zero, Vector2.Zero
            };
 
            Sprite sprite = newObject.Sprite ?? newObject.Prefab.DeformableSprite?.Sprite;
 
            //calculate the positions of the corners of the rotated sprite
            if (sprite != null)
            {
                Vector2 halfSize = sprite.size * newObject.Scale / 2;
                spriteCorners[0] = -halfSize;
                spriteCorners[1] = new Vector2(-halfSize.X, halfSize.Y);
                spriteCorners[2] = halfSize;
                spriteCorners[3] = new Vector2(halfSize.X, -halfSize.Y);
 
                Vector2 pivotOffset = sprite.Origin * newObject.Scale - halfSize;
                pivotOffset.X = -pivotOffset.X;
                pivotOffset = new Vector2(
                    (float)(pivotOffset.X * Math.Cos(-newObject.Rotation) - pivotOffset.Y * Math.Sin(-newObject.Rotation)),
                    (float)(pivotOffset.X * Math.Sin(-newObject.Rotation) + pivotOffset.Y * Math.Cos(-newObject.Rotation)));
 
                for (int j = 0; j < 4; j++)
                {
                    spriteCorners[j] = new Vector2(
                        (float)(spriteCorners[j].X * Math.Cos(-newObject.Rotation) - spriteCorners[j].Y * Math.Sin(-newObject.Rotation)),
                        (float)(spriteCorners[j].X * Math.Sin(-newObject.Rotation) + spriteCorners[j].Y * Math.Cos(-newObject.Rotation)));
 
                    spriteCorners[j] += new Vector2(newObject.Position.X, newObject.Position.Y) + pivotOffset;
                }
            }
 
            float minX = spriteCorners.Min(c => c.X) - newObject.Position.Z * ParallaxStrength;
            float maxX = spriteCorners.Max(c => c.X) + newObject.Position.Z * ParallaxStrength;
 
            float minY = spriteCorners.Min(c => c.Y) - newObject.Position.Z * ParallaxStrength - level.BottomPos;
            float maxY = spriteCorners.Max(c => c.Y) + newObject.Position.Z * ParallaxStrength - level.BottomPos;
 
            if (newObject.Triggers != null)
            {
                foreach (LevelTrigger trigger in newObject.Triggers)
                {
                    if (trigger.PhysicsBody == null) { continue; }
                    for (int i = 0; i < trigger.PhysicsBody.FarseerBody.FixtureList.Count; i++)
                    {
                        trigger.PhysicsBody.FarseerBody.GetTransform(out FarseerPhysics.Common.Transform transform);
                        trigger.PhysicsBody.FarseerBody.FixtureList[i].Shape.ComputeAABB(out FarseerPhysics.Collision.AABB aabb, ref transform, i);
 
                        minX = Math.Min(minX, ConvertUnits.ToDisplayUnits(aabb.LowerBound.X));
                        maxX = Math.Max(maxX, ConvertUnits.ToDisplayUnits(aabb.UpperBound.X));
                        minY = Math.Min(minY, ConvertUnits.ToDisplayUnits(aabb.LowerBound.Y) - level.BottomPos);
                        maxY = Math.Max(maxY, ConvertUnits.ToDisplayUnits(aabb.UpperBound.Y) - level.BottomPos);
                    }
                }
            }
 
#if CLIENT
            if (newObject.ParticleEmitters != null)
            {
                foreach (ParticleEmitter emitter in newObject.ParticleEmitters)
                {
                    Rectangle particleBounds = emitter.CalculateParticleBounds(new Vector2(newObject.Position.X, newObject.Position.Y));
                    minX = Math.Min(minX, particleBounds.X);
                    maxX = Math.Max(maxX, particleBounds.Right);
                    minY = Math.Min(minY, particleBounds.Y - level.BottomPos);
                    maxY = Math.Max(maxY, particleBounds.Bottom - level.BottomPos);
                }
            }
#endif
            objects.Add(newObject);
            if (newObject.NeedsUpdate) { updateableObjects.Add(newObject); }
            newObject.Position.Z += (minX + minY) % 100.0f * 0.00001f;
 
            int xStart = (int)Math.Floor(minX / GridSize);
            int xEnd = (int)Math.Floor(maxX / GridSize);
            if (xEnd < 0 || xStart >= objectGrid.GetLength(0)) { return; }
 
            int yStart = (int)Math.Floor(minY / GridSize);
            int yEnd = (int)Math.Floor(maxY / GridSize);
            if (yEnd < 0 || yStart >= objectGrid.GetLength(1)) { return; }
 
            xStart = Math.Max(xStart, 0);
            xEnd = Math.Min(xEnd, objectGrid.GetLength(0) - 1);
            yStart = Math.Max(yStart, 0);
            yEnd = Math.Min(yEnd, objectGrid.GetLength(1) - 1);
 
            for (int x = xStart; x <= xEnd; x++)
            {
                for (int y = yStart; y <= yEnd; y++)
                {
                    var list = objectGrid[x, y];
                    if (list == null) { objectGrid[x, y] = list = new List<LevelObject>(); }
 
                    //insertion sort in ascending order (= prefer rendering objects in front)
                    int drawOrderIndex = 0;
                    while (drawOrderIndex < list.Count && list[drawOrderIndex].Position.Z < newObject.Position.Z)
                    {
                        drawOrderIndex++;
                    }
                    list.Insert(drawOrderIndex, newObject);
                }
            }            
        }
 
        public static Point GetGridIndices(Vector2 worldPosition)        
        {
            return new Point(
                (int)Math.Floor(worldPosition.X / GridSize),
                (int)Math.Floor((worldPosition.Y - Level.Loaded.BottomPos) / GridSize));
        }
 
        public IEnumerable<LevelObject> GetAllObjects()
        {
            return objects;
        }
 
        private readonly static HashSet<LevelObject> objectsInRange = new HashSet<LevelObject>();
        public IEnumerable<LevelObject> GetAllObjects(Vector2 worldPosition, float radius)
        {
            var minIndices = GetGridIndices(worldPosition - Vector2.One * radius);
            if (minIndices.X >= objectGrid.GetLength(0) || minIndices.Y >= objectGrid.GetLength(1)) { return Enumerable.Empty<LevelObject>(); }
 
            var maxIndices = GetGridIndices(worldPosition + Vector2.One * radius);
            if (maxIndices.X < 0 || maxIndices.Y < 0) { return Enumerable.Empty<LevelObject>(); }
 
            minIndices.X = Math.Max(0, minIndices.X);
            minIndices.Y = Math.Max(0, minIndices.Y);
            maxIndices.X = Math.Min(objectGrid.GetLength(0) - 1, maxIndices.X);
            maxIndices.Y = Math.Min(objectGrid.GetLength(1) - 1, maxIndices.Y);
 
            objectsInRange.Clear();
            for (int x = minIndices.X; x <= maxIndices.X; x++)
            {
                for (int y = minIndices.Y; y <= maxIndices.Y; y++)
                {
                    if (objectGrid[x, y] == null) { continue; }
                    foreach (LevelObject obj in objectGrid[x, y])
                    {
                        if (obj.Prefab.HideWhenBroken && obj.Health <= 0.0f) { continue; }
                        objectsInRange.Add(obj);
                    }
                }
            }
 
            return objectsInRange;
        }
 
        private static List<SpawnPosition> GetAvailableSpawnPositions(IEnumerable<VoronoiCell> cells, LevelObjectPrefab.SpawnPosType spawnPosType)
        {
            List<LevelObjectPrefab.SpawnPosType> spawnPosTypes = new List<LevelObjectPrefab.SpawnPosType>(4);
            List<SpawnPosition> availableSpawnPositions = new List<SpawnPosition>();
            bool requireCaveSpawnPos = spawnPosType == LevelObjectPrefab.SpawnPosType.CaveWall;
            foreach (var cell in cells)
            {
                foreach (var edge in cell.Edges)
                {
                    if (!edge.IsSolid || edge.OutsideLevel) { continue; }
                    if (requireCaveSpawnPos != edge.NextToCave) { continue; } 
                    Vector2 normal = edge.GetNormal(cell);
 
                    Alignment edgeAlignment = 0;
                    if (normal.Y < -0.5f)
                        edgeAlignment |= Alignment.Bottom;
                    else if (normal.Y > 0.5f)
                        edgeAlignment |= Alignment.Top;
                    else if (normal.X < -0.5f)
                        edgeAlignment |= Alignment.Left;
                    else if(normal.X > 0.5f)
                        edgeAlignment |= Alignment.Right;
 
                    spawnPosTypes.Clear();
                    spawnPosTypes.Add(spawnPosType);
                    if (spawnPosType.HasFlag(LevelObjectPrefab.SpawnPosType.MainPathWall) && edge.NextToMainPath) { spawnPosTypes.Add(LevelObjectPrefab.SpawnPosType.MainPathWall); }
                    if (spawnPosType.HasFlag(LevelObjectPrefab.SpawnPosType.SidePathWall) && edge.NextToSidePath) { spawnPosTypes.Add(LevelObjectPrefab.SpawnPosType.SidePathWall); }
                    if (spawnPosType.HasFlag(LevelObjectPrefab.SpawnPosType.CaveWall) && edge.NextToCave) { spawnPosTypes.Add(LevelObjectPrefab.SpawnPosType.CaveWall); }                   
 
                    availableSpawnPositions.Add(new SpawnPosition(edge, normal, spawnPosTypes, edgeAlignment));
                }
            }
            return availableSpawnPositions;
        }
 
        public void Update(float deltaTime)
        {
            GlobalForceDecreaseTimer += deltaTime;
            if (GlobalForceDecreaseTimer > 1000000.0f)
            {
                GlobalForceDecreaseTimer = 0.0f;
            }
 
            if (updateableObjects is not null)
            {
                foreach (LevelObject obj in updateableObjects)
                {
                    if (GameMain.NetworkMember is { IsServer: true })
                    {
                        obj.NetworkUpdateTimer -= deltaTime;
                        if (obj.NeedsNetworkSyncing && obj.NetworkUpdateTimer <= 0.0f)
                        {
                            GameMain.NetworkMember.CreateEntityEvent(this, new EventData(obj));
                            obj.NeedsNetworkSyncing = false;
                            obj.NetworkUpdateTimer = NetConfig.LevelObjectUpdateInterval;
                        }
                    }
                    if (obj.Prefab.HideWhenBroken && obj.Health <= 0.0f) { continue; }
 
                    if (obj.Triggers != null)
                    {
                        obj.ActivePrefab = obj.Prefab;
                        for (int i = 0; i < obj.Triggers.Count; i++)
                        {
                            obj.Triggers[i].Update(deltaTime);
                            if (obj.Triggers[i].IsTriggered && obj.Prefab.OverrideProperties[i] != null)
                            {
                                obj.ActivePrefab = obj.Prefab.OverrideProperties[i];
                            }
                        }
                    }
 
                    if (obj.PhysicsBody != null)
                    {
                        if (obj.Prefab.PhysicsBodyTriggerIndex > -1) { obj.PhysicsBody.Enabled = obj.Triggers[obj.Prefab.PhysicsBodyTriggerIndex].IsTriggered; }
                        /*obj.Position = new Vector3(obj.PhysicsBody.Position, obj.Position.Z);
                        obj.Rotation = -obj.PhysicsBody.Rotation;*/
                    }
                }
            }
 
            UpdateProjSpecific(deltaTime);            
        }
 
        partial void UpdateProjSpecific(float deltaTime);
 
        private void OnObjectTriggered(LevelObject triggeredObject, LevelTrigger trigger, Entity triggerer)
        {
            if (trigger.TriggerOthersDistance <= 0.0f) { return; }
            foreach (LevelObject obj in objects)
            {
                if (obj == triggeredObject || obj.Triggers == null) { continue; }
                foreach (LevelTrigger otherTrigger in obj.Triggers)
                {
                    otherTrigger.OtherTriggered(trigger, triggerer);
                }
            }
        }
 
        private static LevelObjectPrefab GetRandomPrefab(Level level, IList<LevelObjectPrefab> availablePrefabs)
        {
            if (availablePrefabs.Sum(p => p.GetCommonness(level.LevelData)) <= 0.0f) { return null; }
            return ToolBox.SelectWeightedRandom(
                availablePrefabs,
                availablePrefabs.Select(p => p.GetCommonness(level.LevelData)).ToList(), Rand.RandSync.ServerAndClient);
        }
 
        private static LevelObjectPrefab GetRandomPrefab(CaveGenerationParams caveParams, IList<LevelObjectPrefab> availablePrefabs, bool requireCaveSpecificOverride)
        {
            if (availablePrefabs.Sum(p => p.GetCommonness(caveParams, requireCaveSpecificOverride)) <= 0.0f) { return null; }
            return ToolBox.SelectWeightedRandom(
                availablePrefabs,
                availablePrefabs.Select(p => p.GetCommonness(caveParams, requireCaveSpecificOverride)).ToList(), Rand.RandSync.ServerAndClient);
        }
 
        public override void Remove()
        {
            objectsInRange.Clear();
            if (objects != null)
            {
                foreach (LevelObject obj in objects)
                {
                    obj.Remove();
                }
                objects.Clear();
                updateableObjects.Clear();
            }
            RemoveProjSpecific();
 
            base.Remove();
        }
 
        partial void RemoveProjSpecific();
 
        public void ServerEventWrite(IWriteMessage msg, Client c, NetEntityEvent.IData extraData = null)
        {
            if (extraData is not EventData eventData) { throw new Exception($"Malformed LevelObjectManager event: expected {nameof(LevelObjectManager)}.{nameof(EventData)}"); }
            LevelObject obj = eventData.LevelObject;
            msg.WriteRangedInteger(objects.IndexOf(obj), 0, objects.Count);
            obj.ServerWrite(msg, c);
        }
    }
}