Unity_LargeScaleSearchTarget

大规模目标时，常规遍历搜索、KDTree搜索、格子搜索以及八叉树搜索的性能对比。

多大规模算大规模？

常规搜索方式下耗时很久的就算。假如只搜索一次的话，PC上5000数量起，手机上100数量起。

通常的搜索目标要求

• 范围内最近的1个目标
• 范围内最近的n个目标（n>1)
• 范围内的随机n个目标（n>1)

实验的四种搜索方式

• Normal，常规搜索，直接遍历所有目标。
• KDTreeNearest和KDTreeNearestRange，由于KDTree搜索最近的一个和搜索范围内的目标过程不一样，所以要分别进行测试。KDTRee构建是需要花费时间的，所以将搜索目标的请需求集中起来，构建好后，一次性完成所有搜索需求。
• Grid，网格搜索。从最近的格子开始一圈一圈向外围搜索。可以在O(1)的时间内更新怪物所在的格子，维护格子的性能消耗可以忽略。
• Octree，八叉树搜索。同样是将搜索请求集中起来，八叉树构建好，一次性完成所有搜索请求。实际应用过程中应该动态更新树，除非大量节点都更换了格子，否则更新的效率更高。

结论

• 通常Grid是最快的。当大量怪物扎堆挤入同一个格子时才会降低格子的效果。如果格子过大还可以缩小格子尺寸来解决这种情况。可以说只要内存足够，就不是问题。假如是平面1024*1024个格子，每个格子4字节（需要一个列表记录怪物），就需要4M。
• KDTreeNearest所有规模下都有稳定的表现。但是只是搜索最近的1个。搜索最近的n个目标可以用一个最大堆存储搜索到的目标，离英雄最远的在顶上，每次发现比堆顶目标更近的，就把堆顶替换掉。KDTree的优势就在于不论分布范围多大，都能处理；缺点就是节点移动后更新效率不高。
• KDTreeNearestRange搜索范围内的所有目标。搜索范围越大，遍历的节点越多就越慢。搜索范围内随机N个目标就得用这个方式。除非范围覆盖全图，否则不会比常规搜索慢。
• Octree搜索在范围较大时速度明显慢，应该是比较的次数更多（xyz三维比较）。构建比较费时间，当搜索范围很小时速度非常快。当移动改变格子的对象很少时，维护tree的时间就很少，Octree就非常适合，总体上会比kdtree快。所以Octree虽然慢了点，但是节点更新效率高，节点移动的情况下比KDtree好。
• Normal，数量比较少时，用这个方也没问题。测试机器，200个敌人，10个英雄同时搜索1次目标，耗时是5ms左右。如果分帧每帧完成2个搜索需求，就是1ms了。CPU不忙的场景完全可以接受。

测试条件

• 测试渣渣手机 海思麒麟710 CPU频率 4×Cortex A73 2.2 GHz + 4×Cortex A53 1.7 GHz
• 英雄搜索方式：所有英雄同时搜索n次目标。
• 地图50x50

一些测试数据

搜索模式	怪物数量	攻击距离	英雄数量	搜索次数	格子大小	耗时（ms）
Normal	100	20	10	1	-	2.642
Normal	100	20	10	10	-	22.330
Normal	200	20	10	1	-	5.194
Normal	200	20	10	10	-	35.148
Normal	1000	20	10	1	-	14.294
Normal	1000	20	10	10	-	104.638
Normal	3000	20	10	1	-	41.387
Normal	3000	20	10	10	-	460.581
KDTreeNearestR.	100	10	10	1	-	1.281
KDTreeNearestR.	100	10	10	10	-	4.290
KDTreeNearestR.	100	20	10	10	-	10.310
KDTreeNearestR.	200	10	10	1	-	2.572
KDTreeNearestR.	200	10	10	10	-	8.197
KDTreeNearestR.	200	20	10	10	-	20.390
KDTreeNearestR.	1000	10	10	1	-	6.230
KDTreeNearestR.	1000	10	10	10	-	20.939
KDTreeNearestR.	1000	20	10	10	-	57.858
KDTreeNearestR.	3000	10	10	1	-	23.012
KDTreeNearestR.	3000	10	10	10	-	69.803
KDTreeNearestR.	3000	20	10	10	-	240.204
KDTreeNearestR.	3000	3	10	10	-	20.978
KDTreeNearest	100	10	10	1	-	1.693
KDTreeNearest	100	10	10	10	-	8.776
KDTreeNearest	100	20	10	10	-	8.862
KDTreeNearest	200	10	10	1	-	3.160
KDTreeNearest	200	10	10	10	-	13.833
KDTreeNearest	200	20	10	10	-	13.828
KDTreeNearest	1000	10	10	1	-	8.049
KDTreeNearest	1000	10	10	10	-	18.813
KDTreeNearest	1000	20	10	10	-	-
KDTreeNearest	3000	10	10	1	-	18.144
KDTreeNearest	3000	10	10	10	-	23.922
KDTreeNearest	3000	20	10	10	-	-
KDTreeNearest	3000	3	10	10	-	24.854
Grid	100	10	10	1	2	0.490
Grid	100	10	10	10	2	2.630
Grid	100	20	10	10	2	2.623
Grid	100	20	10	10	5	3.066
Grid	200	10	10	1	2	0.464
Grid	200	10	10	10	2	2.540
Grid	200	20	10	10	2	2.519
Grid	200	20	10	10	5	4.156
Grid	1000	10	10	1	2	0.487
Grid	1000	10	10	10	2	2.387
Grid	1000	20	10	10	2	2.392
Grid	1000	20	10	10	5	7.434
Grid	3000	10	10	1	2	0.381
Grid	3000	10	10	10	2	3.294
Grid	3000	20	10	10	2	2.252
Grid	3000	20	10	10	5	22.944
Grid	3000	3	10	10	2	1.381
		3
以下数据在PC上测得		3
Normal	3000	10	10	1	-	20.000
KDTreeNearestR.	3000	10	10	1	-	16.000
KDTreeNearest	3000	10	10	1	-	14.000
Grid	3000	10	10	1	2	0.500
Normal	3000	3	10	1	-	22.000
KDTreeNearestR.	3000	3	10	1	-	8.000
KDTreeNearestR.	3000	3	10	10	-	12.551
KDTreeNearest	3000	3	10	1	-	8.000
KDTreeNearest	3000	3	10	10		12.151
Grid	3000	3	10	1	2	0.500
Octree	100	10	10	1	-	1.500
Octree	100	10	10	10	-	6.000
Octree	100	20	10	10	-	10.000
Octree	200	10	10	1	-	3.000
Octree	200	10	10	10	-	5.000
Octree	200	20	10	10	-	16.000
Octree	1000	10	10	1	-	17.000
Octree	1000	10	10	10	-	35.000
Octree	1000	20	10	10	-	90.000
Octree	3000	10	10	1	-	46.000
Octree	3000	10	10	10	-	110.000
Octree	3000	20	10	10	-	340.000
Octree	3000	3	10	10	-	35.454
Octree	3000	3	10	10	均匀分布	40.000
Octree	3000	3	10	1	-	33.004