ActionTowerDefense/ActionTowerDefense/Assets/Scripts/PolliwogManager.cs

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class PolliwogManager : MonoBehaviour
{
    private static PolliwogManager instance;

    public List<Polliwog> list = new List<Polliwog>();

    private QuadTree quadTree;
    private float quadTreeUpdateInterval = 0.1f;
    private float lastQuadTreeUpdateTime;
    private Rect quadTreeBounds;

    public const int maxNum = 100;

    public static PolliwogManager GetInstance()
    {
        if( instance == null )
        {
            GameObject obj = new GameObject();
            obj.name = typeof(PolliwogManager).ToString();
            DontDestroyOnLoad(obj);
            instance = obj.AddComponent<PolliwogManager>();
        }
        return instance;
    }

    private void Start()
    {
        quadTreeBounds = new Rect(-20, -20, 200, 200);
        quadTree = new QuadTree(0, quadTreeBounds);
    }

    private void UpdateQuadTree()
    {
        if (Time.time - lastQuadTreeUpdateTime < quadTreeUpdateInterval) return;
        lastQuadTreeUpdateTime = Time.time;

        quadTree.Clear();
        foreach (Polliwog fish in list)
        {
            if(fish.isInGroup) quadTree.Insert(fish);
        }
    }

    public List<Polliwog> GetNearbyFish(Vector2 position, float radius)
    {
        UpdateQuadTree();
        return quadTree.Retrieve(position, radius);
    }

    public void AddPolliwog(Polliwog polliwog)
    {
        if(list.Count >= maxNum) return;
        if(!list.Contains(polliwog)) list.Add(polliwog);
    }

    public void RemovePolliwog(Polliwog polliwog)
    {
        if (list.Contains(polliwog)) list.Remove(polliwog);
    }

    public bool IsFull()
    {
        return list.Count >= maxNum;
    }

    public void Refresh()
    {
        list.Clear();
        quadTree.Clear();
    }
}

public class QuadTree
{
    private const int MAX_OBJECTS = 20;
    private const int MAX_LEVELS = 5;

    private int level;
    private List<Polliwog> objects;
    private Rect bounds;
    private QuadTree[] nodes;

    public QuadTree(int level, Rect bounds)
    {
        this.level = level;
        this.bounds = bounds;
        objects = new List<Polliwog>();
        nodes = new QuadTree[4];
    }

    public void Clear()
    {
        objects.Clear();

        for (int i = 0; i < nodes.Length; i++)
        {
            if (nodes[i] != null)
            {
                nodes[i].Clear();
                nodes[i] = null;
            }
        }
    }

    private void Split()
    {
        float subWidth = bounds.width / 2f;
        float subHeight = bounds.height / 2f;
        float x = bounds.x;
        float y = bounds.y;

        nodes[0] = new QuadTree(level + 1, new Rect(x + subWidth, y, subWidth, subHeight));
        nodes[1] = new QuadTree(level + 1, new Rect(x, y, subWidth, subHeight));
        nodes[2] = new QuadTree(level + 1, new Rect(x, y + subHeight, subWidth, subHeight));
        nodes[3] = new QuadTree(level + 1, new Rect(x + subWidth, y + subHeight, subWidth, subHeight));
    }

    private int GetIndex(Vector2 position)
    {
        int index = -1;
        float verticalMidpoint = bounds.x + (bounds.width / 2);
        float horizontalMidpoint = bounds.y + (bounds.height / 2);

        bool topQuadrant = position.y > horizontalMidpoint;
        bool bottomQuadrant = position.y < horizontalMidpoint;

        if (position.x < verticalMidpoint)
        {
            if (topQuadrant) index = 2;
            else if (bottomQuadrant) index = 1;
        }
        else if (position.x > verticalMidpoint)
        {
            if (topQuadrant) index = 3;
            else if (bottomQuadrant) index = 0;
        }

        return index;
    }

    public void Insert(Polliwog obj)
    {
        if (nodes[0] != null)
        {
            int index = GetIndex(obj.transform.position);

            if (index != -1)
            {
                nodes[index].Insert(obj);
                return;
            }
        }

        objects.Add(obj);

        if (objects.Count > MAX_OBJECTS && level < MAX_LEVELS)
        {
            if (nodes[0] == null)
            {
                Split();
            }

            int i = 0;
            while (i < objects.Count)
            {
                int index = GetIndex(objects[i].transform.position);
                if (index != -1)
                {
                    nodes[index].Insert(objects[i]);
                    objects.RemoveAt(i);
                }
                else
                {
                    i++;
                }
            }
        }
    }

    public List<Polliwog> Retrieve(Vector2 position, float radius)
    {
        List<Polliwog> returnObjects = new List<Polliwog>();
        returnObjects.AddRange(objects);

        if (nodes[0] != null)
        {
            int index = GetIndex(position);
            if (index != -1)
            {
                returnObjects.AddRange(nodes[index].Retrieve(position, radius));
            }
            else
            {
                // 检查所有子节点是否与搜索区域相交
                for (int i = 0; i < nodes.Length; i++)
                {
                    if (RectOverlapCircle(nodes[i].bounds, position, radius))
                    {
                        returnObjects.AddRange(nodes[i].Retrieve(position, radius));
                    }
                }
            }
        }

        return returnObjects;
    }

    private bool RectOverlapCircle(Rect rect, Vector2 circleCenter, float radius)
    {
        float closestX = Mathf.Clamp(circleCenter.x, rect.x, rect.x + rect.width);
        float closestY = Mathf.Clamp(circleCenter.y, rect.y, rect.y + rect.height);

        float distanceX = circleCenter.x - closestX;
        float distanceY = circleCenter.y - closestY;

        return (distanceX * distanceX + distanceY * distanceY) < (radius * radius);
    }
}