{"action":"created","issue":{"url":"https://api.github.com/repos/haraldsegliens/shifter/issues/44","labels_url":"https://api.github.com/repos/haraldsegliens/shifter/issues/44/labels{/name}","comments_url":"https://api.github.com/repos/haraldsegliens/shifter/issues/44/comments","events_url":"https://api.github.com/repos/haraldsegliens/shifter/issues/44/events","html_url":"https://github.com/haraldsegliens/shifter/issues/44","id":64945877,"number":44,"title":"Optimization session","user":{"login":"haraldsegliens","id":9857685,"avatar_url":"https://avatars.githubusercontent.com/u/9857685?v=3","gravatar_id":"","url":"https://api.github.com/users/haraldsegliens","html_url":"https://github.com/haraldsegliens","followers_url":"https://api.github.com/users/haraldsegliens/followers","following_url":"https://api.github.com/users/haraldsegliens/following{/other_user}","gists_url":"https://api.github.com/users/haraldsegliens/gists{/gist_id}","starred_url":"https://api.github.com/users/haraldsegliens/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/haraldsegliens/subscriptions","organizations_url":"https://api.github.com/users/haraldsegliens/orgs","repos_url":"https://api.github.com/users/haraldsegliens/repos","events_url":"https://api.github.com/users/haraldsegliens/events{/privacy}","received_events_url":"https://api.github.com/users/haraldsegliens/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/haraldsegliens/shifter/labels/HIGH%20PRIORITY","name":"HIGH PRIORITY","color":"e11d21"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":10,"created_at":"2015-03-28T14:04:51Z","updated_at":"2015-04-04T20:52:35Z","closed_at":null,"body":"Need to optimize:\r\n1. GameplayController\r\n2. AI_Group\r\nThe result should be game over 60fps in the ai_quickTest scene with 3 groups in each side respawning  in 15 second interval.\r\n\r\nAdditionally, NPC weird rotations should be fixed. At the beginning of the battle NPC rotate in wrong direction, but not facing enemies. "},"comment":{"url":"https://api.github.com/repos/haraldsegliens/shifter/issues/comments/89663692","html_url":"https://github.com/haraldsegliens/shifter/issues/44#issuecomment-89663692","issue_url":"https://api.github.com/repos/haraldsegliens/shifter/issues/44","id":89663692,"user":{"login":"haraldsegliens","id":9857685,"avatar_url":"https://avatars.githubusercontent.com/u/9857685?v=3","gravatar_id":"","url":"https://api.github.com/users/haraldsegliens","html_url":"https://github.com/haraldsegliens","followers_url":"https://api.github.com/users/haraldsegliens/followers","following_url":"https://api.github.com/users/haraldsegliens/following{/other_user}","gists_url":"https://api.github.com/users/haraldsegliens/gists{/gist_id}","starred_url":"https://api.github.com/users/haraldsegliens/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/haraldsegliens/subscriptions","organizations_url":"https://api.github.com/users/haraldsegliens/orgs","repos_url":"https://api.github.com/users/haraldsegliens/repos","events_url":"https://api.github.com/users/haraldsegliens/events{/privacy}","received_events_url":"https://api.github.com/users/haraldsegliens/received_events","type":"User","site_admin":false},"created_at":"2015-04-04T20:52:35Z","updated_at":"2015-04-04T20:52:35Z","body":"I have done a little research.\r\n![capture](https://cloud.githubusercontent.com/assets/9857685/6994517/902dc6f8-db25-11e4-9152-0d93b3a2a52a.PNG)\r\nIt states that I must use VP tree.\r\nResearch code:\r\n```C#\r\nusing System;\r\nusing System.Collections.Generic;\r\nusing System.Linq;\r\nusing System.Text;\r\nusing System.Threading.Tasks;\r\nusing System.Diagnostics;\r\n\r\nnamespace ConsoleApplication2\r\n{\r\n    public struct Vector3\r\n    {\r\n        public int X;\r\n        public int Y;\r\n        public int Z;\r\n        public ulong sqrMagnitude(){return (ulong)(X*X+Y*Y+Z*Z);}\r\n        public static Vector3 operator -(Vector3 a,Vector3 b)\r\n        {\r\n            return new Vector3{ X = a.X-b.X, Y = a.Y-b.Y, Z = a.Z-b.Z};\r\n        }\r\n\r\n        public static Vector3 operator +(Vector3 a, Vector3 b)\r\n        {\r\n            return new Vector3 { X = a.X + b.X, Y = a.Y + b.Y, Z = a.Z + b.Z };\r\n        }\r\n    }\r\n\tpublic class Point\r\n\t{\r\n\t\tpublic Vector3 position;\r\n\t\tpublic int index;\r\n\t\tpublic uint id = 0;\r\n        public static uint reservedId = 1;\r\n\t}\r\n    public class KDNode\r\n    {\r\n    \tpublic int index;//from Point[]\r\n        public KDNode left;\r\n        public KDNode right;\r\n        public int axis;\r\n    }\r\n    public class VPNode\r\n    {\r\n    \tpublic int index;//from Point[]\r\n    \tpublic VPNode left;//inside\r\n    \tpublic VPNode right;//outside\r\n    \tpublic float threshold;\r\n    }\r\n    \r\n    public class Program\r\n    {\r\n        static Random random = new Random();\r\n    \t\r\n    \tstatic void Main(string[] args)\r\n        {\r\n            /*var points = new Point[] \r\n            { \r\n                new Point{ index = 0, position = new Vector3{ X = 4, Y = 0 } },\r\n                new Point{ index = 1, position = new Vector3{ X = 8, Y = 0 } },\r\n                new Point{ index = 2, position = new Vector3{ X = 12, Y = 0 } },\r\n                new Point{ index = 3, position = new Vector3{ X = 1, Y = 2 } },\r\n                new Point{ index = 4, position = new Vector3{ X = 3, Y = 3 } },\r\n                new Point{ index = 5, position = new Vector3{ X = 6, Y = 3 } },\r\n\t\t\t\tnew Point{ index = 6, position = new Vector3{ X = 10, Y = 3 } },\r\n                new Point{ index = 7, position = new Vector3{ X = 0, Y = 6 } },\r\n                new Point{ index = 8, position = new Vector3{ X = 2, Y = 6 } },\r\n                new Point{ index = 9, position = new Vector3{ X = 4, Y = 6 } },\r\n                new Point{ index = 10, position = new Vector3{ X = 6, Y = 6 } },\r\n                new Point{ index = 11, position = new Vector3{ X = 8, Y = 6 } },\r\n\t\t\t\tnew Point{ index = 12, position = new Vector3{ X = 12, Y = 6 } },\r\n                new Point{ index = 13, position = new Vector3{ X = 2, Y = 9 } },\r\n                new Point{ index = 14, position = new Vector3{ X = 6, Y = 9 } },\r\n                new Point{ index = 15, position = new Vector3{ X = 10, Y = 9 } },\r\n                new Point{ index = 16, position = new Vector3{ X = 1, Y = 10 } },\r\n                new Point{ index = 17, position = new Vector3{ X = 4, Y = 10 } },\r\n\t\t\t\tnew Point{ index = 18, position = new Vector3{ X = 8, Y = 10 } },\r\n                new Point{ index = 19, position = new Vector3{ X = 12, Y = 10 } }\r\n            };*/\r\n            var points = new Point[10000];\r\n            for(int i = 0;i < 10000;i++)\r\n            {\r\n            \tpoints[i] = new Point{index = i, position = new Vector3{ X = random.Next(1000),Y = random.Next(1000),Z = random.Next(1000)}};\r\n            }\r\n\t\t\tvar target = new Vector3 { X = 2, Y = 2, Z = 0 };\r\n\t\t\tvar st = new Stopwatch();\t\t\r\n\t\t\tst.Start();\r\n\t\t\tulong closestDist = int.MaxValue;\r\n\t\t\tint closest = -1;\r\n\t\t\tfor(int i = 0; i < points.Length;i++)\r\n\t\t\t{\r\n\t\t\t\tulong dist = (target-points[i].position).sqrMagnitude();\r\n\t\t\t\tif(dist < closestDist)\r\n\t\t\t\t{\r\n\t\t\t\t\tclosestDist = dist;\r\n\t\t\t\t\tclosest = i;\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t\tvar nnPoint = points[closest];\r\n\t\t\tst.Stop();\r\n\t\t\tConsole.WriteLine(\"Bruteforce: build time: 0 ticks\");\r\n\t\t\tConsole.WriteLine(\"Bruteforce: Query time \" + st.ElapsedTicks + \" ticks \" + nnPoint.index);\r\n\t\t\tst.Reset();\r\n\t\t\tst.Start();\r\n\t\t\tvar root = CreateKDTree(points);\r\n\t\t\tst.Stop();\r\n\t\t\tConsole.WriteLine();\r\n\t\t\tConsole.WriteLine(\"KDTREE Build time: \"  + st.ElapsedTicks + \" ticks\");\r\n            //KD_inorder(root);\r\n            st.Reset();\r\n\t\t\tst.Start();\r\n            nnPoint = KDNearestNeighbor(root, target,points);\r\n\t\t\tst.Stop();\r\n            Console.WriteLine(\"KDTREE: Query time \" + st.ElapsedTicks + \" ticks \" + nnPoint.index);\r\n\t\t\tst.Reset();\r\n\t\t\tst.Start();\r\n\t\t\troot = CreateBallTree(points);\r\n\t\t\tst.Stop();\r\n\t\t\tConsole.WriteLine();\r\n\t\t\tConsole.WriteLine(\"Ball tree: Build time: \"  + st.ElapsedTicks + \" ticks\");\r\n            //Console.WriteLine(\"Ball tree\");\r\n            //KD_inorder(root);\r\n            st.Reset();\r\n            st.Start();\r\n            nnPoint = KDNearestNeighbor(root, target,points);\r\n\t\t\tst.Stop();\r\n            Console.WriteLine(\"Ball tree: Query time: \" + st.ElapsedTicks + \" ticks \" + nnPoint.index);\r\n\t\t\tst.Reset();\r\n\t\t\tst.Start();\r\n\t\t\tvar root2 = CreateVPTree(points);\r\n\t\t\tst.Stop();\r\n\t\t\tConsole.WriteLine();\r\n\t\t\tConsole.WriteLine(\"VPTree: Build time: \"  + st.ElapsedTicks + \" ticks\");\r\n\t\t\t//Console.WriteLine(\"VP tree\");\r\n\t\t\t//VP_inorder(root2);\r\n\t\t\tst.Reset();\r\n\t\t\tst.Start();\r\n\t\t\tnnPoint = VPNearestNeighbor(root2,target,points);\r\n\t\t\tst.Stop();\r\n\t\t\tConsole.WriteLine(\"VPTree: Query time \" + st.ElapsedTicks + \" ticks \" + nnPoint.index);\r\n\t\t\tConsole.ReadKey();\r\n        }\r\n\r\n        static void KD_inorder(KDNode p, int indent=0)\r\n        {\r\n            if(p != null) {\r\n                if (p.left != null) KD_inorder(p.left, indent + 1);\r\n                if (indent > 0)\r\n                {\r\n                    for (int i = 0; i < indent; i++)\r\n                        Console.Write(\"---*\");\r\n                }\r\n                Console.WriteLine(\"\" + p.index);\r\n                if (p.right != null) KD_inorder(p.right, indent + 1);\r\n            }\r\n        }\r\n\r\n        public static KDNode CreateKDTree(Point[] points)\r\n        {\r\n            return CreateKDTree(0, points.OrderBy(x => x.position.X).Select(x => x.index).ToArray(),\r\n        \t                    points.OrderBy(x => x.position.Y).Select(x => x.index).ToArray(),points.OrderBy(x => x.position.Z).Select(x => x.index).ToArray(), points);\r\n        }\r\n        public static KDNode CreateKDTree(int depth, int[] sortedX, int[] sortedY, int[] sortedZ, Point[] points)\r\n        {\r\n            if (sortedX.Length == 0)\r\n                return null;\r\n\r\n            var a = new KDNode { axis = depth % 3 };\r\n            int pivotIndex = (int)((double)sortedX.Length / 2.0 - 0.5);\r\n            uint newId = Point.reservedId;\r\n            Point.reservedId++;\r\n            var leftX = new int[pivotIndex];\r\n            var leftY = new int[pivotIndex];\r\n            var leftZ = new int[pivotIndex];\r\n            var rightX = new int[sortedX.Length - pivotIndex - 1]; int x = 0;\r\n            var rightY = new int[sortedX.Length - pivotIndex - 1]; int y = 0;\r\n            var rightZ = new int[sortedX.Length - pivotIndex - 1];\r\n            if (a.axis == 0)\r\n            {\r\n                a.index = sortedX[pivotIndex];\r\n                for (int i = 0; i < pivotIndex; i++)\r\n                {\r\n                    points[sortedX[i]].id = newId;\r\n                    leftX[i] = sortedX[i];\r\n                }\r\n                int j = 0;\r\n                for (int i = pivotIndex + 1; i < sortedX.Length; i++,j++)\r\n                {\r\n                    rightX[j] = sortedX[i];\r\n                }\r\n                for (int i = 0; i < sortedY.Length; i++)\r\n                {\r\n                    int b = sortedY[i];\r\n                    if (b == a.index) continue;\r\n                    if (points[b].id == newId)\r\n                    {\r\n                        leftY[x] = b;\r\n                        x++;\r\n                    }\r\n                    else\r\n                    {\r\n                        rightY[y] = b;\r\n                        y++;\r\n                    }\r\n                }\r\n                x = 0;y = 0;\r\n                for (int i = 0; i < sortedZ.Length; i++)\r\n                {\r\n                    int b = sortedZ[i];\r\n                    if (b == a.index) continue;\r\n                    if (points[b].id == newId)\r\n                    {\r\n                        leftZ[x] = b;\r\n                        x++;\r\n                    }\r\n                    else\r\n                    {\r\n                        rightZ[y] = b;\r\n                        y++;\r\n                    }\r\n                }\r\n            }\r\n            else if(a.axis == 1)\r\n            {\r\n                a.index = sortedY[pivotIndex];\r\n                for (int i = 0; i < pivotIndex; i++)\r\n                {\r\n                    points[sortedY[i]].id = newId;\r\n                    leftY[i] = sortedY[i];\r\n                }\r\n                int j = 0;\r\n                for (int i = pivotIndex + 1; i < sortedY.Length; i++,j++)\r\n                {\r\n                    rightY[j] = sortedY[i];\r\n                }\r\n                for (int i = 0; i < sortedX.Length; i++)\r\n                {\r\n                    int z = sortedX[i];\r\n                    if (z == a.index) continue;\r\n                    if (points[z].id == newId)\r\n                    {\r\n                        leftX[x] = z;\r\n                        x++;\r\n                    }\r\n                    else\r\n                    {\r\n                        rightX[y] = z;\r\n                        y++;\r\n                    }\r\n                }\r\n                x = 0;\r\n                y = 0;\r\n                for (int i = 0; i < sortedZ.Length; i++)\r\n                {\r\n                    int z = sortedZ[i];\r\n                    if (z == a.index) continue;\r\n                    if (points[z].id == newId)\r\n                    {\r\n                        leftZ[x] = z;\r\n                        x++;\r\n                    }\r\n                    else\r\n                    {\r\n                        rightZ[y] = z;\r\n                        y++;\r\n                    }\r\n                }\r\n            }\r\n            else\r\n            {\r\n            \ta.index = sortedZ[pivotIndex];\r\n                for (int i = 0; i < pivotIndex; i++)\r\n                {\r\n                    points[sortedZ[i]].id = newId;\r\n                    leftZ[i] = sortedZ[i];\r\n                }\r\n                int j = 0;\r\n                for (int i = pivotIndex + 1; i < sortedZ.Length; i++,j++)\r\n                {\r\n                    rightZ[j] = sortedZ[i];\r\n                }\r\n                for (int i = 0; i < sortedX.Length; i++)\r\n                {\r\n                    int z = sortedX[i];\r\n                    if (z == a.index) continue;\r\n                    if (points[z].id == newId)\r\n                    {\r\n                        leftX[x] = z;\r\n                        x++;\r\n                    }\r\n                    else\r\n                    {\r\n                        rightX[y] = z;\r\n                        y++;\r\n                    }\r\n                }\r\n                x = 0;\r\n                y = 0;\r\n                for (int i = 0; i < sortedY.Length; i++)\r\n                {\r\n                    int z = sortedY[i];\r\n                    if (z == a.index) continue;\r\n                    if (points[z].id == newId)\r\n                    {\r\n                        leftY[x] = z;\r\n                        x++;\r\n                    }\r\n                    else\r\n                    {\r\n                        rightY[y] = z;\r\n                        y++;\r\n                    }\r\n                }\r\n            }\r\n            int v = depth + 1;\r\n            a.left = CreateKDTree(v, leftX, leftY,leftZ, points);\r\n            a.right = CreateKDTree(v, rightX, rightY,rightZ, points);\r\n            return a;\r\n        }\r\n\r\n        public static KDNode CreateBallTree(Point[] points)\r\n        {\r\n            return CreateBallTree(points.OrderBy(x => x.position.X).Select(x => x.index).ToArray(),\r\n        \t                    points.OrderBy(x => x.position.Y).Select(x => x.index).ToArray(),points.OrderBy(x => x.position.Z).Select(x => x.index).ToArray(), points);\r\n        }\r\n        public static KDNode CreateBallTree(int[] sortedX, int[] sortedY, int[] sortedZ, Point[] points)\r\n        {\r\n            if (sortedX.Length == 0)\r\n                return null;\r\n\r\n            var a = new KDNode();\r\n            int dx = sortedX[sortedX.Length-1]-sortedX[0];\r\n            int dy = sortedY[sortedY.Length-1]-sortedY[0];\r\n            int dz = sortedZ[sortedZ.Length-1]-sortedZ[0];\r\n            if(dx < dy && dz < dy)\r\n            \ta.axis = 1;\r\n            else if(dy < dz && dx < dz)\r\n            \ta.axis = 2;\r\n            int pivotIndex = (int)((double)sortedX.Length / 2.0 - 0.5);\r\n            uint newId = Point.reservedId;\r\n            Point.reservedId++;\r\n            var leftX = new int[pivotIndex];\r\n            var leftY = new int[pivotIndex];\r\n            var leftZ = new int[pivotIndex];\r\n            var rightX = new int[sortedX.Length - pivotIndex - 1]; int x = 0;\r\n            var rightY = new int[sortedX.Length - pivotIndex - 1]; int y = 0;\r\n            var rightZ = new int[sortedX.Length - pivotIndex - 1];\r\n            if (a.axis == 0)\r\n            {\r\n                a.index = sortedX[pivotIndex];\r\n                for (int i = 0; i < pivotIndex; i++)\r\n                {\r\n                    points[sortedX[i]].id = newId;\r\n                    leftX[i] = sortedX[i];\r\n                }\r\n                int j = 0;\r\n                for (int i = pivotIndex + 1; i < sortedX.Length; i++,j++)\r\n                {\r\n                    rightX[j] = sortedX[i];\r\n                }\r\n                for (int i = 0; i < sortedY.Length; i++)\r\n                {\r\n                    int b = sortedY[i];\r\n                    if (b == a.index) continue;\r\n                    if (points[b].id == newId)\r\n                    {\r\n                        leftY[x] = b;\r\n                        x++;\r\n                    }\r\n                    else\r\n                    {\r\n                        rightY[y] = b;\r\n                        y++;\r\n                    }\r\n                }\r\n                x = 0;y = 0;\r\n                for (int i = 0; i < sortedZ.Length; i++)\r\n                {\r\n                    int b = sortedZ[i];\r\n                    if (b == a.index) continue;\r\n                    if (points[b].id == newId)\r\n                    {\r\n                        leftZ[x] = b;\r\n                        x++;\r\n                    }\r\n                    else\r\n                    {\r\n                        rightZ[y] = b;\r\n                        y++;\r\n                    }\r\n                }\r\n            }\r\n            else if(a.axis == 1)\r\n            {\r\n                a.index = sortedY[pivotIndex];\r\n                for (int i = 0; i < pivotIndex; i++)\r\n                {\r\n                    points[sortedY[i]].id = newId;\r\n                    leftY[i] = sortedY[i];\r\n                }\r\n                int j = 0;\r\n                for (int i = pivotIndex + 1; i < sortedY.Length; i++,j++)\r\n                {\r\n                    rightY[j] = sortedY[i];\r\n                }\r\n                for (int i = 0; i < sortedX.Length; i++)\r\n                {\r\n                    int z = sortedX[i];\r\n                    if (z == a.index) continue;\r\n                    if (points[z].id == newId)\r\n                    {\r\n                        leftX[x] = z;\r\n                        x++;\r\n                    }\r\n                    else\r\n                    {\r\n                        rightX[y] = z;\r\n                        y++;\r\n                    }\r\n                }\r\n                x = 0;\r\n                y = 0;\r\n                for (int i = 0; i < sortedZ.Length; i++)\r\n                {\r\n                    int z = sortedZ[i];\r\n                    if (z == a.index) continue;\r\n                    if (points[z].id == newId)\r\n                    {\r\n                        leftZ[x] = z;\r\n                        x++;\r\n                    }\r\n                    else\r\n                    {\r\n                        rightZ[y] = z;\r\n                        y++;\r\n                    }\r\n                }\r\n            }\r\n            else\r\n            {\r\n            \ta.index = sortedZ[pivotIndex];\r\n                for (int i = 0; i < pivotIndex; i++)\r\n                {\r\n                    points[sortedZ[i]].id = newId;\r\n                    leftZ[i] = sortedZ[i];\r\n                }\r\n                int j = 0;\r\n                for (int i = pivotIndex + 1; i < sortedZ.Length; i++,j++)\r\n                {\r\n                    rightZ[j] = sortedZ[i];\r\n                }\r\n                for (int i = 0; i < sortedX.Length; i++)\r\n                {\r\n                    int z = sortedX[i];\r\n                    if (z == a.index) continue;\r\n                    if (points[z].id == newId)\r\n                    {\r\n                        leftX[x] = z;\r\n                        x++;\r\n                    }\r\n                    else\r\n                    {\r\n                        rightX[y] = z;\r\n                        y++;\r\n                    }\r\n                }\r\n                x = 0;\r\n                y = 0;\r\n                for (int i = 0; i < sortedY.Length; i++)\r\n                {\r\n                    int z = sortedY[i];\r\n                    if (z == a.index) continue;\r\n                    if (points[z].id == newId)\r\n                    {\r\n                        leftY[x] = z;\r\n                        x++;\r\n                    }\r\n                    else\r\n                    {\r\n                        rightY[y] = z;\r\n                        y++;\r\n                    }\r\n                }\r\n            }\r\n            a.left = CreateBallTree(leftX, leftY,leftZ, points);\r\n            a.right = CreateBallTree(rightX, rightY,rightZ, points);\r\n            return a;\r\n        }\r\n        \r\n        class KDNNArgs\r\n        {\r\n            public ulong minDistSQ = ulong.MaxValue;\r\n            public KDNode closest = null;\r\n        }\r\n        public static Point KDNearestNeighbor(KDNode node, Vector3 point,Point[] points)\r\n        {\r\n            var nn = new KDNNArgs();\r\n            KDNearestNeighbor(node, point, nn,points);\r\n            return points[nn.closest.index];\r\n        }\r\n        static void KDNearestNeighbor(KDNode node, Vector3 point, KDNNArgs args,Point[] points)\r\n        {\r\n        \tint p = node.axis == 0 ? point.X : (node.axis == 1 ? point.Y : point.Z);\r\n            int n = node.axis == 0 ? points[node.index].position.X : (node.axis == 1 ? points[node.index].position.Y : points[node.index].position.Z);\r\n            ulong sqDist = (points[node.index].position-point).sqrMagnitude();\r\n            if(sqDist < args.minDistSQ)\r\n            {\r\n                args.minDistSQ = sqDist;\r\n                args.closest = node;\r\n            }\r\n            if (p <= n)//left first\r\n            {\r\n                if(node.left != null)\r\n                    KDNearestNeighbor(node.left,point,args,points);\r\n                if (node.right != null)\r\n                {\r\n                \tulong a = (ulong)Math.Abs(p - n); a *= a;\r\n                    if (a < sqDist)\r\n                        KDNearestNeighbor(node.right, point, args,points);\r\n                }\r\n            }\r\n            else\r\n            {\r\n                if (node.right != null)\r\n                    KDNearestNeighbor(node.right, point, args,points);\r\n                if (node.left != null)\r\n                {\r\n                \tulong a = (ulong)Math.Abs(p - n); a *= a;\r\n                    if (a < sqDist)\r\n                        KDNearestNeighbor(node.left, point, args,points);\r\n                }\r\n            }\r\n        }\r\n        \r\n        //VP TREE  \r\n        public static VPNode CreateVPTree(Point[] points)\r\n        {\r\n        \tvar inp = new List<int>();\r\n        \tfor(int i = 0;i < points.Length;i++)\r\n        \t{\r\n        \t\tinp.Add(i);\r\n        \t}\r\n        \treturn CreateVPTree(inp,points);\r\n        }\r\n        static VPNode CreateVPTree(List<int> indices,Point[] points)\r\n        {\r\n        \tif(indices == null || indices.Count == 0) return null;\r\n        \tvar node = new VPNode{ index = indices[random.Next(indices.Count)] };\r\n        \tif(indices.Count > 1)\r\n        \t{\r\n        \t\tfloat d = 0;\r\n        \t\tforeach(var a in indices)\r\n        \t\t{\r\n        \t\t\tif(a == node.index) continue;\r\n        \t\t\td += (float)Math.Sqrt((points[a].position-points[node.index].position).sqrMagnitude());\r\n        \t\t}\r\n        \t\r\n        \t\tvar leftList = new List<int>();\r\n        \t\tvar rightList = new List<int>();\r\n        \t\tnode.threshold = d / (float)(indices.Count-1);\r\n        \t\tforeach(var index in indices)\r\n        \t\t{\r\n        \t\t\tif(index == node.index)\r\n        \t\t\t\tcontinue;\r\n        \t\t\tif(Math.Sqrt((points[index].position-points[node.index].position).sqrMagnitude()) <= node.threshold)\r\n        \t\t\t\tleftList.Add(index);\r\n        \t\t\telse\r\n        \t\t\t\trightList.Add(index);\r\n        \t\t}\r\n        \t\tnode.left = CreateVPTree(leftList,points);\r\n        \t\tnode.right = CreateVPTree(rightList,points);\r\n        \t}\r\n        \treturn node;\r\n        }\r\n        static void VP_inorder(VPNode p, int indent=0)\r\n        {\r\n            if(p != null) {\r\n                if (p.left != null) VP_inorder(p.left, indent + 1);\r\n                if (indent > 0)\r\n                {\r\n                    for (int i = 0; i < indent; i++)\r\n                        Console.Write(\"---*\");\r\n                }\r\n                Console.WriteLine(\"\" + p.index);\r\n                if (p.right != null) VP_inorder(p.right, indent + 1);\r\n            }\r\n        }\r\n        class VPNNArgs\r\n        {\r\n        \tpublic float minDist = float.MaxValue;\r\n            public VPNode closest = null;\r\n        }\r\n        public static Point VPNearestNeighbor(VPNode node, Vector3 point,Point[] points)\r\n        {\r\n            var nn = new VPNNArgs();\r\n            VPNearestNeighbor(node, point, nn,points);\r\n            return points[nn.closest.index];\r\n        }\r\n        static void VPNearestNeighbor(VPNode node, Vector3 point,VPNNArgs args,Point[] points)\r\n        {\r\n        \tif(node == null) return;\r\n        \tfloat dist = (float)Math.Sqrt((points[node.index].position - point).sqrMagnitude());\r\n        \tif(dist < args.minDist)\r\n        \t{\r\n        \t\targs.minDist = dist;\r\n        \t\targs.closest = node;\r\n        \t}\r\n        \tif(node.left == null && node.right == null)\r\n        \t\treturn;\r\n        \tif(dist <= node.threshold)\r\n        \t{\r\n        \t\tif(dist - args.minDist <= node.threshold)\r\n        \t\t\tVPNearestNeighbor(node.left,point,args,points);\r\n        \t\tif(dist + args.minDist >= node.threshold)\r\n        \t\t\tVPNearestNeighbor(node.right,point,args,points);\r\n        \t}\r\n        \telse\r\n        \t{\r\n        \t\tif(dist + args.minDist >= node.threshold)\r\n        \t\t\tVPNearestNeighbor(node.right,point,args,points);\r\n        \t\tif(dist - args.minDist <= node.threshold)\r\n        \t\t\tVPNearestNeighbor(node.left,point,args,points);\r\n        \t}\r\n        }\r\n    }\r\n}\r\n```"}}