如何找到一條線上的所有網格？

Question

我正試圖在二維網格上實現視線算法。我知道它是如何在概念上工作的，但我想不出如何將它作爲一種算法來實現。

基本想法很簡單。在僞代碼：

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示例是首選，但不是必需的。

Answer 1

的答案都這麼遠點就Bresenhams的算法維基百科文章。以下是該文章給出的圖片，全尺寸。注意這條線穿過沒有突出顯示的網格，所以Bresenham的算法只給出你想要的一個子集。

既然你提到的「視線」，這聽起來像你想的是枚舉所有的線穿過方格的算法。這個集合有時被稱爲超級封面（行），並且one algorithm is described here。

還有一些其他的方法，在this question的答案給出。

更新：Here's another reference

Answer 2

是不是Bresenham's Algorithm你在找什麼？

Answer 3

見http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

Answer 4

這裏是an implementation I wrote in C。