Quadtree | C# Online Compiler

Quadtree by FawkesWang

using System;
using System.Collections.Generic;
using System.Diagnostics;
					
public class Program
{
	public static void Main()
	{	
		// Quadtree
        Quadtree quadtree = new Quadtree(-32, -32, 64, 64);
		
		// 角色
        Character character1 = new Character(0, 0, quadtree);
		Character character2 = new Character(0, 1, quadtree);

        // 假設有100個隨機角色座標
        Random random = new Random();
        for (int i = 0; i < 100; i++)
        {
            float x = random.Next(-32000, 32001);
            float y = random.Next(-32000, 32001);
            Character character = new Character(x / 1000, y / 1000, quadtree);
        }
		
		// 創建 Stopwatch 實例
        Stopwatch stopwatch = new Stopwatch();

        // 開始計時
        stopwatch.Start();

        // 在(0, 0)附近查找20單位距離內的角色
        List<CharacterPosition> charactersNearby = quadtree.FindCharactersInArea(character1, 20);
		
		// 停止計時
        stopwatch.Stop();

        // 獲取經過的時間 (TimeSpan)
        TimeSpan elapsedTime = stopwatch.Elapsed;

        // 將時間轉換為毫秒 (Milliseconds)
        double milliseconds = elapsedTime.TotalMilliseconds;

        Console.WriteLine($"執行時間: {milliseconds} 毫秒");

        // 輸出結果
        Console.WriteLine("在20單位距離內的角色數量：" + charactersNearby.Count);
        foreach (var character in charactersNearby)
        {
            Console.WriteLine("X: " + character.x + ", Y: " + character.y);
        }
		
		 // 角色移動
        character1.Move(150, 150);
	}
}

class Character
{
    private CharacterPosition position;
    private Quadtree quadtree;

    public Character(float x, float y, Quadtree quadtree)
    {
        position = new CharacterPosition(x, y);
        this.quadtree = quadtree;
        quadtree.AddCharacter(position);
    }

    // 角色移動方法，同時更新Quadtree中的角色座標
    public void Move(float newX, float newY)
    {
        quadtree.RemoveCharacter(position);
        position.x = newX;
        position.y = newY;
        quadtree.AddCharacter(position);
    }

    public CharacterPosition GetPosition()
    {
        return position;
    }

    public Guid GetUID()
    {
        return position.uid;
    }
}

// 自定義結構表示角色座標
struct CharacterPosition
{
    public float x;
    public float y;
    public Guid uid; // 角色唯一識別符

    public CharacterPosition(float x, float y)
    {
        this.x = x;
        this.y = y;
        this.uid = Guid.NewGuid(); // 生成唯一識別符
    }
}

// Quadtree節點
class QuadTreeNode
{
    public float x;
    public float y;
    public float width;
    public float height;
    public List<CharacterPosition> characters;
    public QuadTreeNode[] children;

    public QuadTreeNode(float x, float y, float width, float height)
    {
        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;
        characters = new List<CharacterPosition>();
        children = null;
    }
}


/////

class Quadtree
{
    private QuadTreeNode root;
    private int maxCharactersPerNode = 4; // 每個節點最多容納的角色數量
	
	// 角色的UID字典
    private Dictionary<Guid, CharacterPosition> characterUIDMap = new Dictionary<Guid, CharacterPosition>();

    public Quadtree(float x, float y, float width, float height)
    {
        root = new QuadTreeNode(x, y, width, height);
    }

    // 添加角色到Quadtree
    public void AddCharacter(CharacterPosition character)
    {
        // 紀錄角色的UID
        characterUIDMap.Add(character.uid, character);
        AddCharacterRecursive(root, character);
    }

    private void AddCharacterRecursive(QuadTreeNode node, CharacterPosition character)
    {
        // 檢查節點是否有子節點，如果沒有，並且角色數量尚未達到上限，則直接將角色添加到該節點
        if (node.children == null && node.characters.Count < maxCharactersPerNode)
        {
            node.characters.Add(character);
        }
        else
        {
            // 否則，檢查角色所屬的象限，並遞歸地添加到相應的子節點中
            float subWidth = node.width / 2f;
            float subHeight = node.height / 2f;

            if (character.x < node.x + subWidth)
            {
                if (character.y < node.y + subHeight)
                {
                    if (node.children == null)
                        Subdivide(node);
                    AddCharacterRecursive(node.children[0], character);
                }
                else
                {
                    if (node.children == null)
                        Subdivide(node);
                    AddCharacterRecursive(node.children[1], character);
                }
            }
            else
            {
                if (character.y < node.y + subHeight)
                {
                    if (node.children == null)
                        Subdivide(node);
                    AddCharacterRecursive(node.children[2], character);
                }
                else
                {
                    if (node.children == null)
                        Subdivide(node);
                    AddCharacterRecursive(node.children[3], character);
                }
            }
        }
    }

    // 將節點劃分為四個子節點
    private void Subdivide(QuadTreeNode node)
    {
        float subWidth = node.width / 2f;
        float subHeight = node.height / 2f;
        float x = node.x;
        float y = node.y;

        node.children = new QuadTreeNode[4];
        node.children[0] = new QuadTreeNode(x, y, subWidth, subHeight);
        node.children[1] = new QuadTreeNode(x, y + subHeight, subWidth, subHeight);
        node.children[2] = new QuadTreeNode(x + subWidth, y, subWidth, subHeight);
        node.children[3] = new QuadTreeNode(x + subWidth, y + subHeight, subWidth, subHeight);

        // 將原節點中的角色重新分配到子節點中
        foreach (var character in node.characters)
        {
            AddCharacterRecursive(node.children[GetCharacterQuadrant(node, character)], character);
        }

        node.characters.Clear();
    }

    // 獲取角色所屬的象限
    private int GetCharacterQuadrant(QuadTreeNode node, CharacterPosition character)
    {
        float subWidth = node.width / 2f;
        float subHeight = node.height / 2f;

        if (character.x < node.x + subWidth)
        {
            if (character.y < node.y + subHeight)
                return 0;
            else
                return 1;
        }
        else
        {
            if (character.y < node.y + subHeight)
                return 2;
            else
                return 3;
        }
    }

    // 移除角色從Quadtree
    public void RemoveCharacter(CharacterPosition character)
    {
        // 移除角色的UID
        characterUIDMap.Remove(character.uid);
        RemoveCharacterRecursive(root, character);
    }

    private bool RemoveCharacterRecursive(QuadTreeNode node, CharacterPosition character)
    {
        if (node == null)
            return false;

        // 如果角色在節點中，則移除並返回true
        if (node.characters.Remove(character))
            return true;

        // 否則，遞歸檢查子節點
        if (node.children != null)
        {
            foreach (var child in node.children)
            {
                if (RemoveCharacterRecursive(child, character))
                    return true;
            }
        }

        return false;
    }
	
    // 在區域中找到角色，使用角色物件作為搜索中心
    public List<CharacterPosition> FindCharactersInArea(Character character, float radius)
    {
        CharacterPosition position = character.GetPosition();
        List<CharacterPosition> charactersInArea = new List<CharacterPosition>();
        FindCharactersInAreaRecursive(root, position.x, position.y, radius, charactersInArea, character.GetUID());
        return charactersInArea;
    }

    private void FindCharactersInAreaRecursive(QuadTreeNode node, float centerX, float centerY, float radius, List<CharacterPosition> charactersInArea, Guid uidToExclude)
    {
        if (node == null)
            return;

        // 檢查圓形與節點的區域是否相交，如果不相交則跳過
        float closestX = Math.Max(node.x, Math.Min(centerX, node.x + node.width));
        float closestY = Math.Max(node.y, Math.Min(centerY, node.y + node.height));
        float distanceX = centerX - closestX;
        float distanceY = centerY - closestY;
        float distanceSquared = (distanceX * distanceX) + (distanceY * distanceY);

        if (distanceSquared > radius * radius)
            return;

        // 檢查節點中的角色是否在圓形區域內，如果是且不是要排除的角色，則添加到結果列表
        foreach (var character in node.characters)
        {
            if (character.uid == uidToExclude)
                continue;

            float dx = character.x - centerX;
            float dy = character.y - centerY;
            if ((dx * dx) + (dy * dy) <= radius * radius)
            {
                charactersInArea.Add(character);
            }
        }

        // 遞歸處理子節點
        if (node.children != null)
        {
            foreach (var child in node.children)
            {
                FindCharactersInAreaRecursive(child, centerX, centerY, radius, charactersInArea, uidToExclude);
            }
        }
    }
	
	// 清除所有資訊，但保留大小
    public void Clear()
    {
        ClearRecursive(root);
    }

    private void ClearRecursive(QuadTreeNode node)
    {
        node.characters.Clear();
        node.children = null;

        if (node.children != null)
        {
            foreach (var child in node.children)
            {
                ClearRecursive(child);
            }
        }
    }
}

​x
 
using System;
using System.Collections.Generic;
using System.Diagnostics;
                    
public class Program
{
    public static void Main()
    {   
        // Quadtree
        Quadtree quadtree = new Quadtree(-32, -32, 64, 64);
        
        // 角色
        Character character1 = new Character(0, 0, quadtree);
        Character character2 = new Character(0, 1, quadtree);
​
        // 假設有100個隨機角色座標
        Random random = new Random();
        for (int i = 0; i < 100; i++)
        {
            float x = random.Next(-32000, 32001);
            float y = random.Next(-32000, 32001);
            Character character = new Character(x / 1000, y / 1000, quadtree);
        }
        
        // 創建 Stopwatch 實例
        Stopwatch stopwatch = new Stopwatch();
​
        // 開始計時
        stopwatch.Start();
​
        // 在(0, 0)附近查找20單位距離內的角色
        List<CharacterPosition> charactersNearby = quadtree.FindCharactersInArea(character1, 20);
        
        // 停止計時
        stopwatch.Stop();
​
        // 獲取經過的時間 (TimeSpan)
        TimeSpan elapsedTime = stopwatch.Elapsed;
​
        // 將時間轉換為毫秒 (Milliseconds)
        double milliseconds = elapsedTime.TotalMilliseconds;
​
        Console.WriteLine($"執行時間: {milliseconds} 毫秒");
​
        // 輸出結果
        Console.WriteLine("在20單位距離內的角色數量：" + charactersNearby.Count);
        foreach (var character in charactersNearby)
        {
            Console.WriteLine("X: " + character.x + ", Y: " + character.y);
        }
        
         // 角色移動
        character1.Move(150, 150);
    }
}
​
class Character
{
    private CharacterPosition position;
    private Quadtree quadtree;
​
    public Character(float x, float y, Quadtree quadtree)
    {
        position = new CharacterPosition(x, y);
        this.quadtree = quadtree;
        quadtree.AddCharacter(position);
    }
​
    // 角色移動方法，同時更新Quadtree中的角色座標
    public void Move(float newX, float newY)
    {
        quadtree.RemoveCharacter(position);
        position.x = newX;
        position.y = newY;
        quadtree.AddCharacter(position);
    }
​
    public CharacterPosition GetPosition()
    {
        return position;
    }
​
    public Guid GetUID()
    {
        return position.uid;
    }
}
​
// 自定義結構表示角色座標
struct CharacterPosition
{
    public float x;
    public float y;
    public Guid uid; // 角色唯一識別符
​
    public CharacterPosition(float x, float y)
    {
        this.x = x;
        this.y = y;
        this.uid = Guid.NewGuid(); // 生成唯一識別符
    }
}
​
// Quadtree節點
class QuadTreeNode
{
    public float x;
    public float y;
    public float width;
    public float height;
    public List<CharacterPosition> characters;
    public QuadTreeNode[] children;
​
    public QuadTreeNode(float x, float y, float width, float height)
    {
        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;
        characters = new List<CharacterPosition>();
        children = null;
    }
}
​
​
/////
​
class Quadtree
{
    private QuadTreeNode root;
    private int maxCharactersPerNode = 4; // 每個節點最多容納的角色數量
    
    // 角色的UID字典
    private Dictionary<Guid, CharacterPosition> characterUIDMap = new Dictionary<Guid, CharacterPosition>();
​
    public Quadtree(float x, float y, float width, float height)
    {
        root = new QuadTreeNode(x, y, width, height);
    }
​
    // 添加角色到Quadtree
    public void AddCharacter(CharacterPosition character)
    {
        // 紀錄角色的UID
        characterUIDMap.Add(character.uid, character);
        AddCharacterRecursive(root, character);
    }
​
    private void AddCharacterRecursive(QuadTreeNode node, CharacterPosition character)
    {
        // 檢查節點是否有子節點，如果沒有，並且角色數量尚未達到上限，則直接將角色添加到該節點
        if (node.children == null && node.characters.Count < maxCharactersPerNode)
        {
            node.characters.Add(character);
        }
        else
        {
            // 否則，檢查角色所屬的象限，並遞歸地添加到相應的子節點中
            float subWidth = node.width / 2f;
            float subHeight = node.height / 2f;
​
            if (character.x < node.x + subWidth)
            {
                if (character.y < node.y + subHeight)
                {
                    if (node.children == null)
                        Subdivide(node);
                    AddCharacterRecursive(node.children[0], character);
                }
                else
                {
                    if (node.children == null)
                        Subdivide(node);
                    AddCharacterRecursive(node.children[1], character);
                }
            }
            else
            {
                if (character.y < node.y + subHeight)
                {
                    if (node.children == null)
                        Subdivide(node);
                    AddCharacterRecursive(node.children[2], character);
                }
                else
                {
                    if (node.children == null)
                        Subdivide(node);
                    AddCharacterRecursive(node.children[3], character);
                }
            }
        }
    }
​
    // 將節點劃分為四個子節點
    private void Subdivide(QuadTreeNode node)
    {
        float subWidth = node.width / 2f;
        float subHeight = node.height / 2f;
        float x = node.x;
        float y = node.y;
​
        node.children = new QuadTreeNode[4];
        node.children[0] = new QuadTreeNode(x, y, subWidth, subHeight);
        node.children[1] = new QuadTreeNode(x, y + subHeight, subWidth, subHeight);
        node.children[2] = new QuadTreeNode(x + subWidth, y, subWidth, subHeight);
        node.children[3] = new QuadTreeNode(x + subWidth, y + subHeight, subWidth, subHeight);
​
        // 將原節點中的角色重新分配到子節點中
        foreach (var character in node.characters)
        {
            AddCharacterRecursive(node.children[GetCharacterQuadrant(node, character)], character);
        }
​
        node.characters.Clear();
    }
​
    // 獲取角色所屬的象限
    private int GetCharacterQuadrant(QuadTreeNode node, CharacterPosition character)
    {
        float subWidth = node.width / 2f;
        float subHeight = node.height / 2f;
​
        if (character.x < node.x + subWidth)
        {
            if (character.y < node.y + subHeight)
                return 0;
            else
                return 1;
        }
        else
        {
            if (character.y < node.y + subHeight)
                return 2;
            else
                return 3;
        }
    }
​
    // 移除角色從Quadtree
    public void RemoveCharacter(CharacterPosition character)
    {
        // 移除角色的UID
        characterUIDMap.Remove(character.uid);
        RemoveCharacterRecursive(root, character);
    }
​
    private bool RemoveCharacterRecursive(QuadTreeNode node, CharacterPosition character)
    {
        if (node == null)
            return false;
​
        // 如果角色在節點中，則移除並返回true
        if (node.characters.Remove(character))
            return true;
​
        // 否則，遞歸檢查子節點
        if (node.children != null)
        {
            foreach (var child in node.children)
            {
                if (RemoveCharacterRecursive(child, character))
                    return true;
            }
        }
​
        return false;
    }
    
    // 在區域中找到角色，使用角色物件作為搜索中心
    public List<CharacterPosition> FindCharactersInArea(Character character, float radius)
    {
        CharacterPosition position = character.GetPosition();
        List<CharacterPosition> charactersInArea = new List<CharacterPosition>();
        FindCharactersInAreaRecursive(root, position.x, position.y, radius, charactersInArea, character.GetUID());
        return charactersInArea;
    }
​
    private void FindCharactersInAreaRecursive(QuadTreeNode node, float centerX, float centerY, float radius, List<CharacterPosition> charactersInArea, Guid uidToExclude)
    {
        if (node == null)
            return;
​
        // 檢查圓形與節點的區域是否相交，如果不相交則跳過
        float closestX = Math.Max(node.x, Math.Min(centerX, node.x + node.width));
        float closestY = Math.Max(node.y, Math.Min(centerY, node.y + node.height));
        float distanceX = centerX - closestX;
        float distanceY = centerY - closestY;
        float distanceSquared = (distanceX * distanceX) + (distanceY * distanceY);
​
        if (distanceSquared > radius * radius)
            return;
​
        // 檢查節點中的角色是否在圓形區域內，如果是且不是要排除的角色，則添加到結果列表
        foreach (var character in node.characters)
        {
            if (character.uid == uidToExclude)
                continue;
​
            float dx = character.x - centerX;
            float dy = character.y - centerY;
            if ((dx * dx) + (dy * dy) <= radius * radius)
            {
                charactersInArea.Add(character);
            }
        }
​
        // 遞歸處理子節點
        if (node.children != null)
        {
            foreach (var child in node.children)
            {
                FindCharactersInAreaRecursive(child, centerX, centerY, radius, charactersInArea, uidToExclude);
            }
        }
    }
    
    // 清除所有資訊，但保留大小
    public void Clear()
    {
        ClearRecursive(root);
    }
​
    private void ClearRecursive(QuadTreeNode node)
    {
        node.characters.Clear();
        node.children = null;
​
        if (node.children != null)
        {
            foreach (var child in node.children)
            {
                ClearRecursive(child);
            }
        }
    }
}
​
​
​
​
​
​

[Subject]
  CN=t1

[Issuer]
  CN=t1

[Serial Number]
  656299D125614D0BA954D36896FABA7F

[Not Before]
  9/4/2019 10:57:46 AM

[Not After]
  9/4/2020 11:07:46 AM

[Thumbprint]
  35E8525AB9CBEA0D3A6024E7244CC25EE7A8CC0E

Last Run:	9:27:22 am
Compile:	0.252s
Execute:	0.016s
Memory:	32kb
CPU:	0.031s

View IL Code