Программирование игр для Windows. Советы профессионала

Вычисление точки первого пересечения


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

формула 6.2. Вычисление первой Y-координаты пересечения.

(Yi – Yp)

-------------  =  M

(Xi – Xp)



 

Yi = M * (Xi – Xp) + Yp

 

где (Xi,Yi) - точки пересечения линии и (Xp,Yp) — позиция игрока. После некоторых алгебраических преобразований получаем:

Формула 6.3. Вычисление первой Х-координаты пересечения.

Xi = M-1 * (Yi – Yp) + Xp

 

Для нахождения первого пересечения текущего луча нам надо выполнить только два умножения и сложение. Не так плохо. Мы обязательно это оптимизируем, но сделаем это позже. Переменная М — это величина наклона, которую мы уже вычислили и занесли в таблицу наклонов.

Единственное, что может нас расстроить в этих преобразованиях, это их рекурсивность: каждое преобразование требует предварительного вычисления Другого. Это несколько затруднительно. Но вы можете заметить, что Xi в первом равенстве на самом деле означает «первая граничная вертикальная линия», a Yi во втором выражении означает «первая граничная горизонтальная линия». В этом и заключена изюминка метода отсечения лучей для квадратных матриц. Далее, мы знаем, что луч пересекается с каждой из ячеек в вертикальном и горизонтальном столбце. Рисунок 6.24 поясняет это, Если мы однажды вычислим первое пересечение, то сможем найти и все остальные пересечения с лучом, а также конец его траектории.

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

Некоторые, программисты любят это делать за два прохода: в первом вычисляются все возможные горизонтальные пересечения, а во втором — все вертикальные пересечения. Рисунок 6.25 демонстрирует эту идею.

Это нормально, но я предпочитаю делать это одновременно. Время выполнения обоих методов одинаково, а остальное - дело вкуса. Есть еще одна деталь в работе с пересечениями, для каждого из них (включая самое первое) мы проверяем наличие непрозрачного объекта. Мы должны посмотреть во все стороны от пересечения и попробовать его заметить. Направление просмотра зависит or нашего положения. Если мы находим объект, то останавливаемся и вычисляем дистанцию до пересечения (мы научимся это делать позже). Если мы не обнаруживаем пересечений, то просто продолжаем вычисления до тех пор, пока луч не упрется в какой-либо объект или не выйдет за границы нашего игрового мира.



Содержание раздела