java - 在游戏中检测触摸物体的有效方法？

Question

想象一下，一款类似模拟人生的 2D 游戏，适用于基于触摸的手机，用户可以在其中与场景中的几乎任何对象进行交互。

我如何有效地检测玩家正在触摸哪个对象？

根据我的短暂经验，循环遍历场景中的所有可见对象并检查它们是否被触摸到目前为止已经完成了工作，但是当屏幕中可能有很多移动的对象时听起来有点低效'是吗？保留可见的移动对象列表本身会消耗时间，因为可能必须在每一帧中循环遍历所有对象。

我想到的其他解决方案是:

• 空间散列。将屏幕划分为一个网格，将可见的对象放入相应的桶中。对点击对象的检测速度很快，但每帧将对象放入正确的桶中会产生额外的开销。

• 维护四叉树。移动对象必须一直重新排列，以前的解决方案看起来更好。

在这种情况下通常会做什么？

非常感谢。

Answer 1

要考虑的第一个可能性是加速方法是否真的对您的情况有所帮助。例如，如果您每帧只有一个查询，则您当前的方法需要检查每个对象一次。但是，如果您的所有对象都在移动，几乎所有加速结构都需要更新每个对象一次——那么，在那种情况下，何必呢？

如果您确定确实需要加速结构，那么您的两种解决方案似乎都是合理的:

• 对于触摸界面，您知道查询的大小。因此，如果您所有的对象都是触摸大小或更小，空间哈希应该是一个很好的解决方案。
• 如果您的对象可能很大，请注意空间散列可能需要将大对象添加到许多散列桶中。在这种情况下，四叉树可能是更好的主意。

另一种解决方案是维护边界框树。有多种算法使用它；特别是 R-tree .