java - 更快的距离测量

Question

我目前正在开发一款游戏，我需要从服务器向客户端发送数据包以在客户端上产生特定的粒子效果，但是，客户端只能在半径为 64 的范围内渲染此粒子游戏中的立方单位。

为了避免向所有客户端发送数据包，我将测量客户端与粒子起源点之间的距离，但将为每个客户端计算该距离，并且运行时间应少于游戏刻度(50 毫秒) ).

粒子会随着玩家的移动而播放，并会发送给距离内的所有客户端，所以性能有点关键(考虑到玩家数量多)。

游戏 API 为两个位置之间的距离提供了这个公式(没有平方根):

正方形(x1 - x2) + 正方形(y1 - y2) + 正方形(z1 - z2);

我的想法是以粒子为中心点在每个轴上创建一个长度为 128 的“盒子”，这样做的缺点是角落的客户端不会渲染粒子但会获取数据包，浪费了一点带宽。

问题是，使用欧几里德距离测量距离会比简单地在粒子周围创建一个“盒子”并比较客户端是否在其中更快？有没有其他方法可以更快地测量距离？

Answer 1

一种非常有效的方法是使用八叉树(三维四叉树)作为数据结构，尤其是对于大量点。

参见 Wikipedia article进行介绍。

这是一个 3 维空间索引，可以让您快速检索某个三维(矩形)范围内的点。

如果你想进一步减少点数，你可以使用你的距离公式进一步过滤你找到的点；但是使用 Oct-tree 空间索引应该已经显着减少了点数，这不会降低性能。