Проверка соприкосновений линии с ячейками массива

[Руслантус]

Имеется карта, состоящая из тайлов размером 32x32. Имеются две точки. Мне нужно пройтись по тайлам между этими двумя точками. Пример:


Мой вариант: постепенно идти от одной точки к другой, передвигаясь по 1 единице и при каждом передвижение обращаться к тайлу по получившимся координатам, и делать проверку. Но этот вариант накладный, так как будет частое обращение к массиву, причём к одним и тем же ячейкам. Мне нужно делать это быстро.

Может есть какой-то другой вариант?

[Kostia]

Можно проверять пересечение с сеткой и если пересекаются 2 стороны одной ячейки, то ту ячейку и нужно брать. И отдельно обыграть ситуацию 3

[ViktorR]

Я вот о чем подумал.
Зная координаты двух точек, можно вычислять координаты центров тайлов.
Номер тайла по Х или по У может быть вычислен из координат точек целочисленным делением. Определяем расстояние от центра тайла до прямой и таким образом определяем принадлежат ли точки прямой тайлу. Затем можно определить выше или ниже центра тайла проходит прямая и следующую точку для тестирования брать в центре соответствующего тайла со сдвигом вниз -> вправо или ...
Задача некоторым образом смахивает на алгоритм Брезенхема для прямой - координаты (номера) тайлов - точки такой прямой, но тут ещё надо покумекать ...

Как-то так ...

[Zer0]

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

[ViktorR]

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


Не до конца осмыслил свое предложение ...

[Руслантус]

Я сделал так, как написал в 1 посте. Ещё добавил сохранение прошлой позиции тайла, дабы не обращаться к одному и тому же тайлу несколько раз. Мне эта реализация вполне подошла.