Как найти все квадраты сетки на линии?

Я пытаюсь реализовать алгоритм прямой видимости на двумерной сетке. Я знаю, как это должно работать концептуально, но я не могу придумать, как реализовать его как алгоритм.

Основная идея довольно проста. В псевдокоде:

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 предпочтительны, но не требуются.

Ответы

Ответ 1

Оба ответа до сих пор указывают на статью Википедии об алгоритме Bresenhams. Вот иллюстрация, которую дает статья, при полном размере. Обратите внимание, что линия проходит через квадраты сетки, которые не выделены, поэтому алгоритм Брешенема дает только подмножество того, что вы хотите.

alt text

Поскольку вы упоминаете "линию визирования", это звучит так, будто вам нужен алгоритм, который перечисляет все квадраты сетки, через которые проходит линия. Этот набор иногда называют супер-обложкой (строки), а здесь описывается один алгоритм.

Существуют и другие подходы, приведенные в ответах на этот вопрос.

Обновление: Здесь другая ссылка