Оптимальное пересечение линий с квадратной сеткой

У меня есть алгоритм наведения лучей для поиска теней / света.

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

У меня есть код приведения луча, который направляет лучи вперед и помечает, когда луч находится внутри стены. Когда это происходит, луч обычно находится внутри клетки, а не на краю. В этот момент у меня есть стартовая пара x / y от источника света, угол, по которому прошел луч, и пара x / y внутри стены.

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

Если у меня есть фиксированные TILE_WIDTH и TILE_HEIGHT (и в этом случае они тоже равны); Есть ли какой-либо более оптимальный, конкретный метод для определения положения этого пересечения отрезка? То есть он использует преимущества отношений, и информация мне уже должна быть проще и / или быстрее, чем общий алгоритм.

1

Решение

Есть алгоритм Ву и Аманатид для Быстрое прохождение Voxel. Он рассчитывает точки пересечения луча с прямоугольными ребрами сетки.

2

Другие решения


По вопросам рекламы [email protected]