Как устроен морской бой? часть 2
Бодрое снарядное попадалово
Точно не скажешь, но давненько когда-то в одной компьютерной игре про корабли…
Ну вот, хотел вам про схему бронирования и бронепробиваемость разными снарядами рассказать, а гейм-дизайнеры, оказывается, такую статью уже написали. Знаете, с этими снарядами что запрограммируешь, то и случается: то, вроде, пробивают, а то не пробивают… А расскажу я вам тогда лучше про зайца да про то, чем можно померяться с другими пассажирами в лифте. Женщин научу, как уличить мужа в неверности, а мужчин — как правильно пройти в библиотеку. Временами буду сбиваться с мысли — возможно, расскажу немножко о задачах, с которыми сталкивается программист при расчёте попадания снаряда в броню. Но вы меня останавливайте, чтобы я сильно не отвлекался от зайцев и лифтов на всякую ерунду.
Снаряд, он ведь как? Вначале летит до цели. Это баллистика, и про неё я уже рассказывал в своей предыдущей статье. Потом ударяет в броню, пробивает её, влетает внутрь корабля, отскакивает от шпангоута, проламывает шкаф и стенку в каюте старпома, нокаутирует кока, залетает в машинное отделение, после чего, наконец, происходит срабатывание взрывателя и большой бум. Или не пробивает броню — зря, что ли, её поставили? Всё это — терминальная баллистика.
Как вы думаете, с точки зрения программиста — что общего у терминальной баллистики с обычной баллистикой? Совершенно верно! В первую очередь то, что терминальная баллистика тоже сама себя не запрограммирует.
Представьте себе, что вас взяли на место впавшего в истерику героя комикса и вам предстоит программировать терминальную баллистику. Первое, с чем вы столкнётесь, — это необходимость определить факт попадания снаряда в броню и подсчитать, в какую именно точку он попал. Только после этого можно будет начинать рассуждать о том, пробил он броню или не пробил, и какой вред нанёс. А то, может, он вообще мимо просвистел. Поэтому садимся и программируем.
Всякий программист знает, что, прежде чем начать сотрясать клавиатуру мощными ударами мозолистых пальцев, желательно продумать три главных момента:
— Достаточно ли у нас кофе для написания подобной программы?
— Какие данные будет использовать наша программа (или кусочек программы, в данном случае — расчёт попадания снаряда в броню)?
— Какие алгоритмы для обработки этих данных мы применим?
Пункт 1. Кофе
Раскрою инсайдерскую информацию: кофе в Lesta Studio предостаточно, поэтому перейдём сразу ко второму пункту.
Пункт 2. Входные данные
Если мы собираемся рассчитывать попадание снаряда в броню, то, разумеется, нам необходимо иметь полную информацию о том, как именно эта броня располагается в пространстве и какой формой обладает. Как же нам описать форму брони, чтобы программа могла с ней работать? Забудем пока про материал, массу и другие характеристики, сосредоточимся только на форме. Представьте, что вы разговариваете по телефону с роботом и должны точно описать ему какую-то сложную геометрическую форму так, чтобы ваш телефон не оказался испорченным.
Если бы мы работали со сферическими кораблями в вакууме, это сразу бы облегчило задачу. Ведь у сферического корабля и броня сферическая. А чтобы описать сферу, всё, что потребовалось бы, — это указать её радиус.
Или вот если бы корабли проектировались под влиянием произведений классиков супрематизма и состояли исключительно из прямоугольных параллелепипедов, это тоже решило бы проблему: параллелепипед можно задать длиной, шириной и высотой.
Но что делать, если наша броня не соответствует ни одной из простейших геометрических фигур? Если она может быть вообще какая угодно: изгибаться, изламываться, иметь дырки, выпуклости, впадины… да хотя бы иметь форму зайца или кофейника? Нет, водить по воздуху руками со словами: «она такая… такая… а вот тут на ощупь — просто обалдеть…», — не разрешается — ведь вы говорите с роботом по телефону. И зайцев он никогда в жизни не видел, даже не надейтесь.
Попробуем разбить произвольную поверхность на что-то более простое. Например, разобьём её на многоугольники. Чем больше многоугольников мы зададим и чем мельче их размер, тем точнее они будут повторять форму поверхности. Вершины мы можем задать их трёхмерными координатами, а каждый многоугольник — перечислением номеров вершин, из которых он состоит. То, что мы получим, называется «меш», он же сетка (mesh, англ. — сетка). Это основной способ описания формы произвольных трёхмерных тел.
Кстати, если при слове «многоугольник» вы представили себе девяти-, семнадцати- или даже двухсотугольник, то давайте на минутку отвлечёмся и прокатимся вместе с нашими героями на лифте в сторону восьмого этажа:
Надеюсь, вы вынесли из этой поездки главное — понимание того, что приставка «много-» вполне может означать «три», «два»… (иногда даже «один», хотя это уже редкость). Так вот, если вы уже представили себе девяти-, семнадцати- или двухсотугольник, умерьте свой аппетит: речь идёт всего лишь о треугольниках. Максимум — о четырёхугольниках. Максимум! Но для солидности их называют многоугольниками, хотя, на мой взгляд, больше чем на «несколькоугольники» они не тянут.
Пункт 3. Алгоритмы.
Для того чтобы понять, как нам работать с «мешем», вспомним основы векторной алгебры. Кто ещё помнит основы векторной алгебры, может сразу перескочить абзацев на пять вперед.
Вектор в трёхмерном пространстве можно рассматривать как набор из трёх чисел, а можно как стрелочку определённой длины и направления. Стрелочку можно рисовать откуда угодно. Но если рисовать её из начала координат, то она приведёт нас в точку, координаты которой как раз окажутся равны тем самым трём числам. Основные же операции с векторами, без которых никак не получится обойтись, — это скалярное и векторное произведение. Формулы их примерно такие:
Два вектора:
V1 = (X1, Y1, Z1)
V2 = (X2, Y2, Z2)
Их скалярное произведение:
V1 * V2 = X1*X2 +Y1*Y2 + Z1*Z2
Их векторное произведение:
V1 х V2 = (Y1*Z2 – Z1*Y2, Z1*X2 – X1*Z2, X1*Y2 – Y1*X2)
Однако куда интереснее не просто голые формулы, а особенности, которыми они обладают. Скалярное произведение двух векторов обладает важнейшим свойством: для векторов, направленных примерно в одну сторону, оно положительно, а для векторов, направленных в противоположные стороны, — отрицательно. Как это свойство можно использовать? Очень просто. Хотя бы так:
В этом комиксе для простоты использовались двумерные векторы, поэтому для каждой проверки жене пришлось сделать два умножения и одно сложение (либо вычитание). Для трехмерных векторов ей пришлось бы сделать на одно умножение и одно сложение больше.
Векторное произведение двух векторов — это третий вектор. Он перпендикулярен первым двум векторам: например, если вы начертили два вектора на земле, то их векторное произведение будет направлено строго вверх либо вниз. А если один вектор направлен вверх, а другой — вперёд от вас, то их произведение будет направлено вправо. Или влево. Чтобы сообразить, куда именно, представьте, что вы открываете бутылку вина, вращая штопор от первого вектора ко второму, подобно тому, как часовая стрелка вращается от полудня к трём часам дня. Направление, в котором станет ввинчиваться ваш штопор, и будет соответствовать векторному произведению.
Как мы можем использовать это свойство на практике (кроме как для открывания бутылок)? К примеру, вам понадобилось пройти в библиотеку…
Всего двенадцать умножений и три сложения/вычитания — и дело в шляпе! Этот трюк не раз спасал меня в моменты моих ночных гуляний по библиотекам.
Ну а теперь, после того как мы вспомнили основы векторной алгебры, давайте попробуем применить всю эту магию к снаряду и броне. Пусть снаряд за очередное мгновение своей жизни пролетел отрезок, показанный на рисунке красным цветом. Нам нужно узнать, попал ли он в броню (которая совершенно случайно оказалась в форме зайца — это просто совпадение, не обращайте внимания), и если попал — то в какую её точку. Для этого мы сделаем следующее:
1. Выберем какой-нибудь треугольник брони. Проведём плоскость через три его вершины.
2. Найдём точку пересечения траектории снаряда с этой плоскостью.
3. Проверим, лежит ли эта точка внутри треугольника.
— Если нет — значит, снаряд не попал в данный треугольник. Надо проверить остальные треугольники.
— Если да — значит, снаряд попал в данный треугольник. Но всё равно надо проверить остальные треугольники — ведь пересечений может быть несколько.
4. Повторим предыдущие действия для всех-всех треугольников «меша».
Оставив первый и второй пункт в качестве домашнего задания, разберём лишь третий: как нам проверить, лежит ли полученная нами точка внутри треугольника?
Сделать это очень просто. Встанем на плоскость треугольника и обойдём его стороны, двигаясь по часовой стрелке. Если точка внутри треугольника, то она всегда будет оставаться справа от нас. Или всегда слева — если мы обходим треугольник в обратном направлении. Если же точка снаружи треугольника — в процессе обхода она будет оказываться иногда справа, а иногда слева от нас.
Как проверить, что точка справа от нас? Легко! Вначале определить, в какой стороне у нас «право», а потом проверить, что точка примерно в той же стороне. Я знаю одну семейную пару, которая отлично справляется с такой задачей.
В итоге, чтобы определить, что точка внутри треугольника, им понадобится сделать всего-навсего сорок пять умножений и пятнадцать сложений. Это ещё не считая пересечения отрезка с плоскостью, которое было оставлено вам в качестве домашнего задания: сколькими математическими операциями вы сумели обойтись?
Должен признаться, что алгоритм, который мы рассмотрели, — не самый быстрый. Он приведён просто для примера, чтобы продемонстрировать, какого рода вычисления могут встретиться. Можно придумать алгоритмы и более шустрые, но всё равно для каждого треугольника придётся произвести хотя бы несколько арифметических операций. А теперь умножьте всё это на количество треугольников в «меше», на количество находящихся в игре кораблей и на количество одновременно летящих снарядов, и вы поймете, что вычисление попадания может оказаться весьма и весьма трудоёмкой задачей для процессора. Однако есть хитрости, которые позволяют значительно сократить количество вычислений…
Ну вот, снаряд ещё даже внутрь корабля не влетел, а я уже устал. Пожалуй, о том, как нам оптимизировать производительность, а также о том, как снаряд, пробив броню, разносит всё внутри вдребезги напополам, расскажу в следующих статьях. А пока пойду поужинаю: у меня как раз подоспело рагу из зайца, нарезанного на аккуратные треугольные кусочки. Ну ладно, ладно, не из зайца — из кролика. Откуда у меня заяц возьмётся? Просто похвастаться хотел, преувеличил немножко.
