Листинг 19.1. Новая программа отсечения лучей

void Ray Caster(long x,long у,long view_angle)

{

// Эта функция является сердцем системы. Она основана на программе

// RAY.С. Обратите особое внимание на оптимизацию по скорости

// работы. Это достигается, в основном, за счет использования таблиц

// поиска и применения математики с фиксированной запятой.

int cell_x, // Текущие координаты луча

сеll_у,

ray, // Обрабатываемый луч

casting=2, // Указывает, обработаны ли обе координаты

х_hit_type, // Указывают на тип объекта, пересеченного

у_hit_type, // лучом. Используется при выборе текстуры

х_bound, // Следующая точка пересечения луча

y_bound,

next_y_cell, // Используется при отрисовке ячейки, в

next_x_cell, // которой находится луч

xray=0, // Счетчик проверенных точек пересечения

// с вертикалями плана

yray=0, // Счетчик проверенных точек пересечения

// с горизонталями плана

х_delta, // Смещение, которое необходимо добавить

у_delta, // для перехода к следующей ячейке

xb_save,

yb_save,

xi_save, // Используется для сохранения координат

yi_save, // точек пересечения

scale;

long cast=0,

dist_x, // Расстояние;от точки пересечения

dist_у; // до позиции игрока

float xi, // Используются при расчетах

yi; // пересечений

// СЕКЦИЯ 1 ////////////////////////////////////////////

// ИНИЦИАЛИЗАЦИЯ

// Рассчитываем начальный угол по отношению к направлению

// взгляда игрока. Угол зрения - 60 градусов. Обрабатываем

//поочередно обе половины угла

if ((view_angle-=ANGLE_30) < 0 }

{

view_angle=ANGLE_360 + view angle;

}

// цикл по всем 320 лучам

for(ray=319;ray>=0; ray--)

{

// СЕКЦИЯ 2 //////////////////////////////

// Вычислить первое пересечение по Х

// Нам необходимо узнать, какая именно половина плана,

// по отношению к оси Y, обрабатывается

if (view_angle >= ANGLE_0 && view_angle < ANGLE_180)

{

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

// На плане она должна быть выше игрока.

y_bound = (CELL_Y_SIZE + (у & 0xFFC0));

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

y_delta =- CELL_Y_SIZE;

// На основании первой возможной линии горизонтального

// пересечения рассчитываем отсечение по горизонтали

xi -= inv_tan_table[view_angle] * (y_bound - у) + х;

// Устанавливаем смещение ячейки

next_у_cell = 0;

} // Конец обработки else

{

// Рассчитываем первую горизонталь, которую может пересечь луч.

// На плане она должна быть ниже игрока

y_bound = (int)(у & 0xFFC0);

// Рассчитываем смещение для перехода к следующей горизонтали

y_delta = -CELL_Y_SIZE;

// На основании первой возможной линии горизонтального

// пересечения рассчитываем отсечение по горизонтали

xi = inv_tan_table[view_angle] * (y_bound - у) + х;

// Устанавливаем смещение ячейки

next_у_cell = -1;

} // Конец обработки // СЕКЦИЯ 3 ////////////////////////////

// вычислить первое пересечение по Y

// Нам надо знать, которая именно половина плана,

// по отношению к оси X, обрабатывается

if (view_angle < ANGLE_90 || view_angle >= ANGLE_270)

{

// Рассчитываем первое отсечение по оси Y

// Определяем первую вертикаль, которую может пересечь луч.

//На плане она должна быть справа от игрока

x_bound = (int)(CELL_X_SIZE + (х & 0xFFC0));

// Определяем смещение для перехода к следующей ячейке

x_delta = CELL_X_SIZE;

// На основании первой возможной линии вертикального

// пересечения вычисляем первое отсечение по оси Y

yi = tan_table[view_angle] * (х_bound - х) + у;

// Устанавливаем смещение ячейки

next_x_cell = 0;

}

else

{

// Определяем первую вертикаль, которую может пересечь луч.

// На плане она должна быть левее игрока

x_bound = (int)(х & 0xFFC0);

// Определяем смещение для перехода к следующей ячейке

x_delta = -CELL_X_SIZE;

// На основании первой линии вертикального пересечения

// рассчитываем первое отсечение по оси Y

yi = tan_table[view_angle] * (x_bound - х) + у;

// Устанавливаем смещение ячейки

next_x_cell = -1;

} // Конец обработки

//начать отсечение

casting = 2; // Одновременно обрабатываем 2 луча

хrау=уrау=0; // Сбрасываем флаги пересечения

// СЕКЦИЯ 4 /////////////////////////////

// Продолжаем расчет для обоих лучей

while(casting)

{

if (xray!=INTERSECTION_FOUND)

{ // Рассчитываем текущую позицию для проверки

сеll_х = ((x_bound+next_x_cell) >> CELL_X_SIZE_FP);

cell_y = (int)yi;

cell_y>>=CELL_Y_SIZE__FP;

// Проверяем, не находится ли в проверяемой области блок

if ((x_hit_type = world[cell_y](cell_x])!=0)

{ // Рассчитываем расстояние

dist_x = (long)((yi - у) * inv_sin_table[view_angle]);

yi_save = (int)yi;

xb_save = x_bound;

// Конец расчета по оси X

xray = INTERSECTION_FOUND;

casting--;

} // Конец обработки наличия блока

else

// Рассчитываем следующее пересечение по Y

{

yi += y_step[view_angle];

// Ищем следующую возможную Х-координату пересечения

x_bound += x_delta;

} // Конец else

}

// СЕКЦИЯ 5 //////////////////////////

if (уray!=INTERSECTION_FOUND)

{ // Рассчитываем текущую позицию для проверки

cell x = xi;

cell_x>>=CELL_X_SIZE_FP;

cell_y = ((y_bound + next_y_cell) >> CELL_Y_SIZE_FP);

// Проверяем, не находится ли в текущей позиции блок

if ((y_hit_type = world[cell_y][cell_x])!=0)

// Вычисляем расстояние

dist_y = (long)((xi - x) * inv_cos_table [view angle]);

xi_save = (int)xi;

yb_save = у_bound;

у_ray = INTERSECTION_FOUND;

casting--;

} // Конец обработки наличия блока else

{ // Прекращаем расчет по оси Y

xi += x_step[view angle];

// Вычисляем следующую возможную линию пересечения

у_bound += у_delta;

} // Конец else

}

} // Конец while

// СЕКЦИЯ 6 /////////////////////////////////

// На этом этапе мы вычислили точки пересечения с

// горизонтальными и вертикальными стенами. Теперь

// определяем, которая из них ближе

if (dist_x < dist_y)

{

// Вертикальная стена ближе

// Рассчитать масштаб и умножить его на поправочный

// коэффициент для устранения сферических искажений

scale = (int)(cos_table[ray]/dist_x);

// Отсечь фрагмент текстуры

if (scale>(MAX_SCALE-1)) scale=(MAX_SCALE-1);

scale_row = scale_table[scale-1];

if (scale>(WINDOW_HEIGHT-1))

{

sliver_clip = (scale-(WINDOW_HEIGHT-1)) >> 1;

scale=(WINDOW_HEIGHT-l);

}

else

sliver_clip =0;

sliver_scale = scale-1;

// Установить параметры для ассемблерной процедуры

sliver_texture = object.frames[x_hit_type];

sliver_column = (yi_save & 0х00ЗF);

sliver_top = WINDOW_MIDDLE - (scale >> 1);.

sliver_ray = ray;

// Отобразить фрагмент текстуры

Render_Sliver_32();

} // Конец if else

// горизонтальная стена ближе

{

//Рассчитать масштаб и умножить его на поправочный

//коэффициент для устранения сферических искажений

scale = (int)(cos_table[ray]/dist_y);

if (scale>(MAX_SCALE-l)) scale=(MAX_SCALE-1);

// Выполняем отсечение

scale_row = scale_table{scale-l];

if (scale>(WINDOW_HEIGHT-1)) {

sliver_clip = (scale-(WINDOW_HEIGHT-1)) >> 1;

scale=(WINDOW_HEIGHT-l);

}

else

sliver_clip = 0;

sliver_scale = scale-1;

// Устанавливаем параметры для ассемблерной процедуры

sliver_texture= object.frames[y_hit_type+l];

sliver_column = (xi_save & 0x003F);

sliver_top = WINDOW_MIDDLE - (scale >> 1);

sliver_ray = ray;

// Отображаем текстуру

Render_Sliver_32();

} // Конец else

// секция 7 ///////////////////////////////////

// Переходим к следующему лучу

// Проверяем, не превысил ли угол 360 градусов

if (++view_angle>=ANGLE_360)

{

view_angle=0;

} // Конец if

} // Конец for

} // Конец функции

Новый отсекатель лучей сродни первому (файл RAY.С из шестой главы) и имеет то же самое строение. Оптимизация была проведена, скорее, на микроскопическом, нежели на макроскопическом уровне. Это означает, что я

оптимизировал программу строку за строкой вместо изменения базовой техники, Такой подход дал прекрасный результат и я получил увеличение скорости примерно на порядок. Я использовал множество вычислений с фиксированной запятой, целые, логические операции, несколько больше справочных таблиц для увеличения скорости вычислений до приемлемого уровня. Наконец, я прибегнул к ассемблированию, чтобы получить последние несколько процентов прироста. Хотя, вообще-то, и версия чисто на Си успешно работала на 486-й машине, но на 386-й она выполнялась исключительно медленно (по крайней мере, по словам моего друга Эшвина, а я думаю, мы можем поверить ему).

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

Секция 1

Здесь мы не изменяли ничего.

Секция 2

Обратите внимание, как теперь вычисляется Y-пересечение: для этого используются целочисленные и логические операции. Основная идея заключена в том, что любое число, деленное нацело по модулю N, равно тому же самому числу, логически объединенному с М-1 по принципу AND. Другими словами,

Х % 64 == Х AND 63

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

Секция 3

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

Секция 4

Это то место, где проверяются начала дальнейших пересечений. Я оказал этой и следуюхцей секции наибольшее внимание с точки зрения оптимизации, потому что данная часть является внутренним циклом отсекателя лучей. В любой программе в первую очередь нужно оптимизировать самый внутренний цикл, азатем уже переходить к внешним. Я внимательно рассмотрел вычисления cell_x и cell_у и оптимизировал их, использовав для деления сдвиг. Наконец, все расчеты были преобразованы к формату с фиксированной запятой за исключением вычисления расстояния, в котором по-прежнему участвуют значения типа FLOAT.

Секция 5

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

Секция 6

Эта секция изменена совсем чуть-чуть:

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

§ Во-вторых, я перекомпоновал текстурные элементы и уменьшил их размер;

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

Отображение текстур - это ассемблерная процедура, получающая входные данные через глобальные переменные программы. Это было сделано, для скорости. Текстурирование - чрезвычайно простая процедура. Когда обнаружено пересечение, точка вместе с соответствующим ей блоком 64х64 пикселя вычисляется и передается текстуре. Эта позиция (0-63) используется как индекс памяти текстуры для получения требуемого фрагмента.

Секция 7

Ничего интересного тут нет.

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

Изображение текстуры

Мы обсуждали эту тему на протяжении седьмой главы "Усовершенствованная битовая графика и специальные эффекты", так что я не собираюсь снова вдаваться в технические подробности. Но поскольку в Warlock вывод текстур применяется очень активно, стоит снова вернуться к этому вопросу. Текстуры для рисования вертикальных полосок извлекаются из битовой карты изображения, заранее подготовленной и находящейся где-то в памяти. Посмотрите па рисунок 19.3. На нем показаны текстуры, которые я нарисовал для Warlock.

Эти текстуры размером 64х64 пикселя были созданы с помощью редактора DPaint. Как мы узнали ранее, изображение текстуры в игре с отсечением лучей. составляется из множества вертикальных полосок. Текстура масштабируется путем преобразования исходного количества пикселей изображения к окончательному размеру. Основная задача состоит в том, чтобы выполнить эту операцию быстро. Для этого, я предложил написать программу отрисовки фрагмента на ассемблере. Это функция, рисующая отмасштабированные и текстурированные вертикальные полоски. Она работает по тому же самому алгоритму, что мы обсуждали ранее. Только сейчас я предварительно вычислил индексы масштабирования- В сущности, я заранее рассчитал все возможные масштабы для размеров стен от 1 до 220 пикселей и, подсчитав индексы масштабирования, свел их в массивную таблицу (примерно на 40К). Следовательно, если размер изображения должен составлять 100 пикселей, вы обращаетесь к сотой строке справочной таблицы. Каждая точка берется из исходной матрицы изображения, используя массив данных сотой строки и n-го столбца, где n — рисуемый пиксель. Вероятно, я объясняю так, что кажется, будто это очень трудно сделать. Жаль. Скорее всего, программа окажется более легкой для понимания! Листинг 19.2 содержит Сн-версию программы рисования фрагмента, а Листинг 19.3 содержит ее ассемблерную версию. Си-версия нуждается в добавлении механизма отсечения по границам игрового окна, но не беспокойтесь об этом. Только взгляните на внутренний цикл Си-версии и сравните его с ассемблерной версией.