Алгоритм 6.1. Алгоритм отсечения лучей

// Пусть игрок находится в позиции (хр,ур) и его взгляд

// Направлен под углом view_angle

// Инициализируем переменные

// Начальный угол -30 градусов относительно направления взгляда

стартовый угол = угол просмотра - 30;

// необходимо отсечь 320 лучей, по одному на каждый экранный столбец

for (ray=0; rау<320; rау++)

{

вычислить наклон текущего луча

while (луч не отсечен)

{

// проверить на вертикальное пересечение

if (не пересекается с вертикальной стеной)

if (луч отсек блок по вертикали)

{

вычислить дистанцию от (хр,ур) до точки пересечения

сохранить дистанцию

} //конец проверки на вертикальное пересечение

if (не было пересечения с горизонтальной стеной)

if (луч отсек блок по горизонтали)

{

вычислить дистанцию от (хр,ур) до точки пересечения

сохранить дистанцию

} // конец проверки по горизонтали

} // конец цикла while

if (горизонтальное пересечение ближе вертикального)

{

вычислить масштаб по горизонтали

нарисовать полосу изображения

}

// конец оператора if

else // вертикальное пересечение ближе горизонтального

{

вычислить масштаб по вертикали нарисовать полосу изображения

} // конец оператора else

} // конец

Конечно, мы опустили множество деталей, но при этом четко формализовали основную идею алгоритма.

Единственный вопрос, который может смутить: «А почему это всегда работает?». Просто мы смоделировали процесс прорисовки образа частицами света. Правда, проделали мы это в обратную сторону, но главное — такой метод работает. Он удаляет невидимые поверхности, создает перспективу и содержит всю необходимую информацию для создания теней, освещения и текстур. Именно поэтому алгоритм отсечения лучей является очень мощным средством для программиста. Мы можем создавать в играх окружение, которое было бы невозможно получить, используя стандартную технику работы с многоугольниками.

Вы можете сказать, что мир, построенный из одинаковых блоков, выглядит весьма скучно. Да, это так, но если вы добавите тени и разукрасите стены всевозможной фактурой, все сказочно преобразится. Вы сможете создать восхитительное окружение для ваших игр. Впоследствии вы сможете уменьшить размер блоков для создания более сложных сцен. Кроме того, вы научитесь изображать поверхности с углом наклона в 45°. Все в ваших руках.

Вас может остановить только быстродействие, поэтому надо постоянно искать пути для сокращения времени выполнения на всех этапах обработки, изображений. Тем более, что DOOM уже доказал: для ПК нет ничего невозможного.

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

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

Математические основы отсечения лучей

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

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

§ рисование лучей;

§ вычисление координат первого пересечения;

§ вычисление координат следующего пересечения;

§ вычисление.расстояния;

§ масштабирование;

§ уменьшение проекционного искажения;

§ рисование полос.

Рисование лучей

Очевидно, что лучи, которые мы отсекаем, на самом деле представляют собой линии. Они начинаются в точке зрения игрока, совпадающей с его позицией на двухмерной карте. Мы решили иметь поле просмотра равным 60°. Таким образом, нам нужно составить таблицу соответствия для всех возможных лучей, которые можно отсечь с любого угла просмотра. Эта таблица должна содержать значения наклонов всех возможных лучей по отношению к плану просмотра. Исходя из значения наклона, мы сможем произвести отсечение луча из точки наблюдения игрока.