[游戏开发]用Unity实现KD树

思路

看他的文章:
https://blog.csdn.net/silangquan/article/details/41483689

KD树是二叉树, 写代码分为2步: 树的建立 和 最近搜索
乍一看, 光树的建立就要遍历好几遍, 效率还不如直接挨个点遍历一遍来的快, 那么, 什么情况下用KD树呢?
答: 在数据庞大且静态的时候
数据量小的时候, 直接遍历搜索就行了, 没必要用KD树
建立树的代价很高, 最好是一旦建立就不再变了. 如果是动态的数据, 点位要频繁更新的话, 也不适合用KD树

代码

代码写的贼乱, 懒得整理了, 主要是理解其中的思路

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

public enum SortType
{
    X,
    Y
}

[Serializable]
public class Branch
{
    public Vector2 pos;
    public SortType sortType;
    public Branch left;
    public Branch right;
}

public class HKDTree : MonoBehaviour
{
    public Transform canvas;
    Image tarImage;
    Image closerImage;
    List<Image> images = new List<Image>();
    List<Vector2> allPos = new List<Vector2>();
    List<Image> lines = new List<Image>();
    Image prefabH;
    Image prefabV;

    void Start()
    {
        Init();
    }

    void Init()
    {
        Image prefab = Resources.Load<Image>("Dot");
        Image targetPrefab = Resources.Load<Image>("Target");
        prefabH = Resources.Load<Image>("LineH");
        prefabV = Resources.Load<Image>("LineV");

        for (int i = 0; i < 5; i++)
        {
            Image tr = Instantiate(prefab, canvas);
            images.Add(tr);
        }

        tarImage = Instantiate(targetPrefab, canvas);

        closerImage = Instantiate(prefab, canvas);
        closerImage.color = Color.green;
    }

    void Update()
    {
        if (Input.GetKeyDown(KeyCode.Space))
        {
            DO();
        }
    }
    void DO()
    {
        allPos.Clear();
        for (int i = 0; i < images.Count; i++)
        {
            Vector2 pos = new Vector2(UnityEngine.Random.Range(-500, 500), UnityEngine.Random.Range(-500, 500));
            images[i].transform.localPosition = pos;
            allPos.Add(pos);
        }

        Vector2 tarPos = new Vector2(UnityEngine.Random.Range(-500, 500), UnityEngine.Random.Range(-500, 500));
        tarImage.transform.localPosition = tarPos;

        for (int i = 0; i < lines.Count; i++)
        {
           Destroy( lines[i].gameObject);
        }
        lines.Clear();
        Branch root = GetBranch(allPos);
        Search(root, tarPos);
        Branch closer = GetCloser(tarPos);

        closerImage.transform.localPosition = closer.pos;
    }

    Branch GetBranch(List<Vector2> poss)
    {
        if (poss.Count == 0)
        {
            return null;
        }
        SortType sortType = SortType.X;
        Vector2 mid = GetMid(poss, out sortType);
        poss.Remove(mid);
        List<Vector2> lefts = new List<Vector2>();
        List<Vector2> rights = new List<Vector2>();
        if (sortType == SortType.X)
        {
            Image line = Instantiate(prefabV, canvas);
            line.transform.localPosition = mid;
            lines.Add(line);
            for (int i = 0; i < poss.Count; i++)
            {
                if (poss[i].x < mid.x)
                {
                    lefts.Add(poss[i]);
                }
                else
                {
                    rights.Add(poss[i]);
                }
            }
        }
        else if (sortType == SortType.Y)
        {
            Image line = Instantiate(prefabH, canvas);
            line.transform.localPosition = mid;
            lines.Add(line);
            for (int i = 0; i < poss.Count; i++)
            {

                if (poss[i].y < mid.y)
                {
                    lefts.Add(poss[i]);
                }
                else
                {
                    rights.Add(poss[i]);
                }
            }
        }
        Branch branch = new Branch();
        branch.pos = mid;
        branch.sortType = sortType;
        branch.left = GetBranch(lefts);
        branch.right = GetBranch(rights);
        return branch;
    }

    Vector3 GetMid(List<Vector2> v, out SortType sortType)
    {
        float x = 0;
        float y = 0;
        float temp1 = 0;
        float temp2 = 0;
        int count = v.Count;
        for (int i = 0; i < count; i++)
        {
            temp1 += 1f / count * v[i].x * v[i].x;
            temp2 += 1f / count * v[i].x;
        }
        x = temp1 - temp2 * temp2;

        temp1 = 0;
        temp2 = 0;
        for (int i = 0; i < count; i++)
        {
            temp1 += 1f / count * v[i].y * v[i].y;
            temp2 += 1f / count * v[i].y;
        }
        y = temp1 - temp2 * temp2;

        //通过计算方差, 确定是用x还是y区分
        if (x > y)
        {
            sortType = SortType.X;
            v.Sort((a, b) => { return a.x.CompareTo(b.x); });
        }
        else
        {
            sortType = SortType.Y;
            v.Sort((a, b) => { return a.y.CompareTo(b.y); });
        }
        return v[count / 2];
    }

    Stack<Branch> branchStack = new Stack<Branch>();
    void Search(Branch branch, Vector2 pos)
    {
        if (branch == null)
        {
            return;
        }
        branchStack.Push(branch);
        if (branch.sortType == SortType.X)
        {
            if (pos.x < branch.pos.x)
            {
                Search(branch.left, pos);
            }
            else
            {
                Search(branch.right, pos);
            }
        }
        else if (branch.sortType == SortType.Y)
        {
            if (pos.y < branch.pos.y)
            {
                Search(branch.left, pos);
            }
            else
            {
                Search(branch.right, pos);
            }
        }
    }

    Branch  (Vector3 pos)
    {
        Branch closer = branchStack.Pop();
        float closerDis = Vector2.Distance(closer.pos, pos);
        while (branchStack.Count != 0)
        {
            Branch branch = branchStack.Pop();
            if (branch == null)
            {
                continue;
            }
            float dis = Vector2.Distance(branch.pos, pos);
            if (dis < closerDis)
            {
                closerDis = dis;
                closer = branch;
            }
            if (branch.sortType == SortType.X)
            {
                //圆与直线相交
                if (dis > Mathf.Abs(branch.pos.x - pos.x))
                {
                    if (pos.x < branch.pos.x)
                    {
                        branchStack.Push(branch.right);
                    }
                    else
                    {
                        branchStack.Push(branch.left);
                    }
                }
            }
            else if (branch.sortType == SortType.Y)
            {
                if (dis > Mathf.Abs(branch.pos.y - pos.y))
                {
                    if (pos.y < branch.pos.y)
                    {
                        branchStack.Push(branch.right);
                    }
                    else
                    {
                        branchStack.Push(branch.left);
                    }
                }
            }
        }
        return closer;
    }
}