Использованный алгоритм фактически является модификацией метода построчного сканирования, однако если традиционный алгоритм осуществляет построение изображения по строкам, то в данном случае более эффективным является подход, основанный на построении изображения по столбцам. Это связано с тем, что при пересечении лабиринта плоскостью, соответствующей горизонтальной строке пикселов, возникает большое количество различных отрезков, подавляющая часть которых игроку не видна. Но если вместо строк использовать столбцы, то ситуация намного упрощается (рис. 13.3) - не только заметно сокращается количество пересечений, но существенным является только ближайшее из них (ясно, что пересечение с полом и с потолком на самом деле можно не рассматривать), так как оно закроет собой все остальные пересечения. Так как высота пола постоянна, для правильной отрисовки столбца достаточно знать лишь расстояние до ближайшей вдоль плоскости стены (вопрос о текстуре будет рассмотрен позже).
Посмотрим на сцену сверху: стенам соответствуют вертикальные и горизонтальные отрезки, а каждой секущей плоскости - луч, выходящий из положения наблюдателя. Тем самым задачу определения ближайшей стены для каждого столбца можно решать не в пространстве, а на плоскости Оху.
Фактически мы приходим к двумерной трассировке лучей (ray casting) - из точки, соответствующей положению игрока на карте, выпускается пучок лучей и для каждого из них находится ближайшее пересечение со стенами лабиринта (рис. 13.4).
Самый простой подход к задаче о нахождении ближайшего пересечения луча со стенами лабиринта (проверить все стены на пересечение с лучом и выбрать среди точек пересечения ближайшую) является слишком медленным и неэффективным. Удобнее воспользоваться тем, что стены являются сегментами линий сетки. Для этого пересекаемые Компьютерная графика. Полигональные модели лучом клетки отслеживаются в порядке распространения луча из начальной клетки, содержащей игрока, до тех пор, пока не будет встречена непустая клетка.
Наиболее простой реализацией подобного подхода является следующая: сначала на пересечение с лучом проверяются вертикальные стены (параллельные оси Ох), затем проверяются горизонтальные (параллельные оси Оу) стены и выбирается ближайшее пересечение.