Изящный/Чистый (особый случай) Прямолинейный Алгоритм Обхода Сетки?

Я стираю старый мой проект. Одна из вещей, которые это должно было сделать, была - учитывая Декартову объединенную энергосистему и два квадрата на сетке, найдите список всех квадратов, через которые прошла бы строка, присоединяющаяся к центру тех двух квадратов.

Особый случай здесь - то, что все запускают, и конечные точки ограничены точным центром квадратов/ячеек.

Вот некоторые примеры - с парами демонстрационных начальных и конечных точек. Теневые квадраты - те, которые должны быть возвращены соответствующим вызовом функции

удаленная мертвая ссылка ImageShack - пример

Запуск и конечные точки упомянуты квадратами, в которых они находятся. В вышеупомянутом изображении, предполагая, что левая нижняя часть [1,1], строка на нижнем правом была бы определена как [6,2] кому: [9,5].

Таким образом, от (центр) квадрат на шестом столбце слева, на второй строке от нижней части до (центр) квадрат на девятом столбце слева, на пятой строке от нижней части

Который действительно не кажется сложным. Однако я так или иначе, казалось, нашел некоторый сложный алгоритм онлайн и реализовал его.

Я действительно вспоминаю, что это было очень, очень быстро. Как, optimized-for-a-hundreds-or-thousands-of-times-per-frames быстро.

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

Который является видом хорошо в понятии, но фактическая реализация оказалась симпатичным not-so-pretty, и я боюсь, что уровень оптимизации мог бы быть слишком высоким для того, в чем я практически нуждаюсь (я называю этот пересекающийся алгоритм, возможно, пять или шесть раз в минуту).

Существует ли простой, легкий для понимания, прозрачный прямолинейный алгоритм обхода сетки?

В программных терминах:

def traverse(start_point,end_point)
  # returns a list of all squares that this line would pass through
end

где данные координаты определяют сами квадраты.

Некоторые примеры:

traverse([0,0],[0,4])
# => [0,0], [0,1], [0,2], [0,3], [0,4]
traverse([0,0],[3,2])
# => [0,0], [0,1], [1,1], [2,1], [2,2], [3,2]
traverse([0,0],[3,3])
# => [0,0], [1,1], [2,2], [3,3]

Обратите внимание, что строки, которые перемещаются непосредственно через углы, не должны включать квадраты в "крыло" строки.

(Старый добрый Bresenham мог бы работать здесь, но это немного назад, от какого я хочу. Насколько я знаю для использования его, я должен был бы в основном применить его к строке и затем просканировать каждый квадрат на сетке для TRUE или FALSE. Неосуществимый - или по крайней мере неэлегантный - для больших сеток)

(Я повторно изучаю Bresenham и находящиеся в Bresenham алгоритмы, из-за моего недоразумения),

Для разъяснения одно возможное приложение этого было бы, если бы я хранил все свои объекты в игре в зонах (сетка), и я имею луч и хочу видеть, каких объектов луч касается. Используя этот алгоритм, я мог протестировать луч только к объектам, которые являются в данных зонах вместо каждого объекта на карте.

Фактическое использование этого в моем приложении состоит в том, что каждая мозаика имеет эффект, связанный с ним, и объект перемещает посредством данного линейного сегмента каждый поворот. На каждом шагу необходимо проверить для наблюдения, который придает объекту квадратную форму, пересек через, и поэтому, который эффекты относиться к объекту.

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

Что я ищу точно? Что-то концептуально/аккуратный и чистый. Кроме того, я понял, что из-за того, что я точно указываю, все запускают, и конечные точки всегда будут в центре квадратов/ячеек; таким образом, возможно, что-то, что использует в своих интересах, который был бы аккуратен также.