algorithm - 在基于平铺地图的游戏中访问圆形平铺的快速算法

Question

我需要一个非常快速的算法来访问磁盘中的图块。最后，我不需要完美的光盘，但我确实需要一个非常快速的算法。

我知道我可以使用边界方块，并遍历该方块中的所有图块，然后计算x²+y²<R²以确定图块是否在圆盘中。在我的情况下，这将非常慢，因为我必须每秒测试数千个圆圈，这意味着数百万个图块，而x²+y²<R²对数百万个图块的测试很慢。

我需要一些快速的东西，即使它不是很准确（=即使它不是一个完美的光盘，变形）

如果速度足够快，即使是八边形（填充）也可以。

Answer 1

x² + y² < R²→x² < R² − y²所以x ∈ ( −√(R²−y²); +√(R²−y²))

我认为计算每条线的范围已经足够快了。如果没有，请使用 Bresenham 的算法使其更快。

Answer 2

与其遍历所有图块并测试它们是否位于圆形区域中，不如直接进入实际上位于圆中的图块并根据需要添加标志和进程...

使用八边形可能会便宜得多，但是当标题/区域的宽度发生变化时，您会遇到必须计算八边形宽度高度和适当角度的问题。的优点x^2 + y^2是一致性。

最后，我建议研究极坐标。x = rcos(theta)和y = r*sin(theta)。如果将cos(theta)和的所有值sin(theta)放入一个数组中，程序将跳过必要的三角计算并跳转到直接测试数据。快速谷歌搜索将提供所有必要的极坐标关系。