Я пытаюсь реализовать алгоритм угла обзора на 2-мерной сетке. Я знаю, как это должно работать концептуально, но я не могу думать, как реализовать его как алгоритм.
Основная идея довольно проста. В псевдокоде:
function LineOfSight(point1, point2): boolean
squares = GetListOfSquaresOnLine(point1, point2)
for each square in squares
if square.IsOpaque then return false
return true
GetListOfSquaresOnLine
(концептуально) провел бы прямую линию от центра квадрата сетки в point1 к центру квадрата сетки в point2 и возвратил бы список всех квадратов, через которые проходит эта строка. Но это - первая часть, понятия не имеют, как реализовать. Кто-либо знает, как сделать это? Delphi или предпочтенные примеры C, но не требуемый.
Оба ответа пока указывают на статью в Википедии об алгоритме Брезенхамса . Вот иллюстрация в полном размере. Обратите внимание, что линия проходит через квадраты сетки, которые не выделены, поэтому алгоритм Брезенхема дает только часть того, что вы хотите.
Поскольку вы упомянули «линию прямой видимости», похоже, вам нужен алгоритм, который перечисляет все квадраты сетки, через которые проходит линия. Этот набор иногда называют суперпокрытием (линии), и здесь описан один алгоритм .
Есть и другие подходы, приведенные в ответах на этот вопрос .
Обновление: Вот еще одна ссылка