到目前为止，两个答案都指向***关于 .

还有一些其他方法，在 这个问题.

更新: 这是另一个参考一个>

I'm trying to implement a line-of-sight algorithm on a 2-dimensional grid. I know how it needs to work conceptually, but I can't think of how to implement it as an algorithm.

The basic idea is pretty simple. In pseudocode:

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

GetListOfSquaresOnLine would (conceptually) draw a straight line from the center of the grid square at point1 to the center of the grid square at point2, and return a list of all squares that this line passes through. But that's the part I have no idea how to implement. Anyone know how to do this? Delphi or C examples preferred, but not required.

Both of the answers so far point to a Wikipedia article on Bresenhams's algorithm. Here's the illustration the article gives, at full size. Notice that the line passes through grid squares that aren't highlighted, so Bresenham's algorithm only gives a subset of what you want.

Since you mention "line of sight", it sounds like you want an algorithm that enumerates all of the grid squares that the line goes through. This set is sometimes referred to as the super cover (of the line), and one algorithm is described here.

There are also some other approaches, given in the answers to this question.

Update: Here's another reference