算法优化建议和讨论(一)

ljh · 发表于 2020-6-20 13:47:05

大家好，我是小雨微梁。大家如果喜欢这个帖子可以支持一下哈
敌人索敌，技能范围判定以及很多情况时，都需要找到最近的目标。默认脚本的算法是遍历所有敌人，找到最近的距离。然而这样有n个敌人，每一帧就至少要算n次了。我想了一个算法，想和大家讨论，看下可不可行。
如图，先把所有敌人分别按x和y坐标排序，如果相同就拿另一个轴的排，得到两个数组，这是可以重复使用的，每帧只用算一次。

然后对于每个需要找到最近敌人的时候，用以下算法就可以了
如图。比如要找ID为8的敌人的最近敌人。
1.分别找到在x轴和y轴上最近的目标。可以看到在x轴上的是7，y轴上的是5。如果在x轴和y轴上最近的是同一个敌人，就可以直接结束了。
2.比较7和5分别与8的y轴距离和x轴距离，取最小的那个。在这里是5
3.离8最近的敌人就在5和14之间，也就是5/6/9/7/10/14，遍历在这个区间的敌人就好。注意看我的图才能理解这一步。
原理的话很简单，比如纸上有ABC三个点，如果离A点最近是C点，它的横坐标离A点横坐标的距离和纵坐标离A点纵坐标的距离总不可能比B点横坐标到A点横坐标的距离和B点纵坐标A点纵坐标的距离都要大吧
不过这只是我的突发奇想，没有经过验证，所以拿出来讨论和参考。