一尘不染

如何找到一条线上的所有网格正方形?

algorithm

我正在尝试在二维网格上实现视线算法。我知道它在概念上需要如何工作,但我想不起来如何将其实现为算法。

基本思想很简单。用伪代码:

function LineOfSight(point1, point2): boolean
  squares = GetListOfSquaresOnLine(point1, point2)
  for each square in squares
    if square.IsOpaque then return false
  return true

GetListOfSquaresOnLine(在概念上)从点1的网格正方形的中心到点2的网格正方形的中心绘制一条直线,并返回此线穿过的所有正方形的列表。但这就是我不知道如何实现的部分。有人知道怎么做吗?最好使用Delphi或C示例,但不是必需的。


阅读 343

收藏
2020-07-28

共1个答案

一尘不染

到目前为止,这两个答案都指向Wikipedia上有关Bresenhams算法的文章。这是本文提供的全尺寸插图。注意,该线穿过未突出显示的网格正方形,因此Bresenham的算法仅给出所需内容的一个子集。

替代文字

因为您提到了“视线”,所以听起来您想要一种枚举该线穿过的所有网格正方形的算法。该集合有时被称为(该行的)超级封面,这里描述一种算法

更新: 这是另一个参考

2020-07-28