Читать книгу: «MINI DOOM Современный Python через игру Том 3 Третье измерение»

Вместо предисловия

Это третий том книги «MINI DOOM. Современный Python через игру». В первых двух томах ты освоил Python и открыл своё окно: холст 640 × 400 на numpy, игровой цикл с dt, управление через класс Input и шрифт 5×7 из битов. Стена между игрой и pygame из главы 12 держится до конца книги.

Теперь окно становится трёхмерным: бросаем лучи и поднимаем стены. Номера глав, листингов и рисунков в серии сквозные, поэтому ссылка «см. главу 12» ведёт туда же, куда и в однотомнике.

Серия целиком

— Том 1. Учимся держать оружие — главы 1–8: основы Python в консоли, от первой программы до ссылок и ресурсов.

— Том 2. Окно в ад — главы 9–13: окно pygame-ce, пиксели на numpy, игровой цикл, клавиатура и мышь, свой шрифт.

— Том 3. Третье измерение — главы 14–19: рейкастинг, стены, текстуры, пол и свет, профилировщик, двери.

— Том 4. Здесь кто-то есть — главы 20–25: спрайты, монстры, оружие, конечные автоматы, поиск пути, смерть.

— Том 5. Шум, свет и финальные титры — главы 26–29: звук, экраны, уровни в файлах, uv, ruff, mypy и pytest.

Все исходники серии — на GitHub: https://github.com/RushSex/MiniDoom-Python. Папка examples/chNN для каждой главы, готовая игра — папка minidoom. Там же README: uv sync, uv run main.py — и вперёд. Каждая глава начинается с проекта предыдущей, так что можно начать читать этот том, взяв готовый код последней главы прошлого тома.

Часть III. Третье измерение

Глава 14. Вид сверху

Вот и начинается то, ради чего ты купил эту книгу. В этой части из плоской карты вырастут стены, на стенах появятся кирпичи, под ногами — пол, над головой — потолок, а в темноте — двери. Но любой трёхмерный мир Doom на самом деле двумерный: это клетчатая карта, на которую мы смотрим особым образом. Поэтому начнём с того, что посмотрим на неё честно — сверху, как на шахматную доску. И разберёмся с математикой, без которой дальше никак: векторами.

Не пугайся. Нам понадобятся синус, косинус и теорема Пифагора — всё, что ты, возможно, пытался забыть после школы. Только теперь у них будет понятная работа: показывать, куда смотрит игрок, и не пускать его в стену.

Мир в клетку

Карта уровня — список строк, листинг 14.1. Каждый символ — клетка. Цифры — стены (разные цифры потом станут разными текстурами), точка — пол, P — место старта игрока. Так же хранили карты первые шутеры: Wolfenstein 3D 1992 года — прямо клетками 64 × 64.

Листинг 14.1 — Уровень — список строк

Важная договорённость: координаты игрока — в клетках, а не в пикселях. Игрок в точке (2.5, 1.5) стоит в центре клетки со столбцом 2 и строкой 1. Целая часть — номер клетки, дробная — где внутри неё. Пиксели появятся только при рисовании: вид сверху умножит клетки на 24, а вид из глаз в следующих главах — вообще по-своему. Мир не должен зависеть от размера экрана.

Класс карты — листинг 14.2. Строки превращаются в numpy-массив кодов символов, а из него одним сравнением получается булева сетка wall: True там, где стена.

Листинг 14.2 — Карта: сетка клеток

Строки 11–12 проверяют, что все строки карты одной длины: множество длин {len(r) for r in rows} должно состоять из одного элемента. Опечатка в карте — лишняя точка в строке — иначе обернётся странными стенами в неожиданных местах. Лучше сразу упасть с понятным сообщением. О том, как красиво сообщать об ошибках в файлах уровней, — в главе 28.

Строка 23 — метод is_wall считает стеной всё, что за краем карты. Это страховка: если по ошибке игрок или луч выйдет за пределы, он упрётся в невидимую стену, а не уронит программу с IndexError.

Векторы на пальцах

Вектор — это стрелка: у неё есть направление и длина. В программе стрелка — просто пара чисел (dx, dy): на сколько сдвинуться по x и на сколько по y. Шаг вправо на клетку — (1, 0), шаг вниз — (0, 1). Помни, что y на экране растёт вниз, поэтому «вниз» — плюс.

Нам нужны четыре операции, все они в листинге 14.3.

Листинг 14.3 — Векторы: направление, перпендикуляр, длина, угол

— Направление из угла. Игрок смотрит под углом angle, значит, единичная стрелка «вперёд» — (cos angle, sin angle). Единичная — длиной ровно 1: так устроены синус и косинус.

— Перпендикуляр. Повернуть стрелку на 90° по часовой (у нас y вниз, так что это «вправо») — (−dy, dx). Без синусов, просто переставить и поменять знак.

— Длина. Теорема Пифагора: math.hypot(x, y) = √(x² + y²). Расстояние до импа в точке (4, 3) — ровно 5, египетский треугольник.

— Скалярное произведение. dx · ux + dy · uy для двух единичных векторов — косинус угла между ними. Больше нуля — цель впереди, меньше — за спиной, около единицы — прямо по курсу. Это самая полезная формула в игровой математике: «видит ли монстр игрока», «попала ли пуля в конус» — всё через неё.

Схема — на рисунке 14.1.

Рисунок 14.1 — Вектор «вперёд», перпендикуляр «вправо» и направление на цель

Угол из вектора добывает math.atan2(y, x) — «арктангенс с двумя аргументами». Обычный atan(y / x) не отличает «вправо-вниз» от «влево-вверх» (у них одинаковое отношение) и падает при x = 0. atan2 смотрит на знаки обоих чисел и всегда возвращает правильный угол от −180° до 180°.

В какой я клетке

Чтобы спросить карту «здесь стена?», нужно перевести дробные координаты в номер клетки — отбросить дробную часть. Кажется, это int(x). Листинг 14.4 показывает, почему нет.

Листинг 14.4 — int и floor на отрицательных числах

int отбрасывает дробную часть к нулю: int(−0.4) = 0. А math.floor округляет вниз: floor(−0.4) = −1. Для положительных чисел разницы нет, для отрицательных — целая клетка. Точка −0.4 лежит левее клетки 0, за краем карты, и правильный ответ — «клетка −1», то есть стена. С int игрок может высунуть плечо за край карты, и никто этого не заметит.

Скольжение вдоль стен

Движение у нас уже есть с главы 12. Осталось не пускать игрока в стены. Первая мысль: посчитать новую точку и, если она в стене, никуда не двигаться. Сравним это со вторым способом в листинге 14.5: игрок бежит по диагонали в стену справа от него.

Листинг 14.5 — Стоп или скольжение: два способа столкновений

Наивный способ упёрся в стену и встал как вкопанный: каждая следующая точка по диагонали — в стене, значит, стоим. А в любом шутере, прижавшись к стене под углом, ты скользишь вдоль неё. Хитрость — проверять оси по очереди: сначала пробуем сдвинуться по x; не вышло — ладно. Потом отдельно по y — а вдоль стены сдвиг свободен. Именно так двигались герои Wolfenstein и Doom.

Остаётся решить, что значит «точка в стене». Игрок — не точка, у него есть ширина. Если проверять только центр, он залезет в стену наполовину, и стена в виде из глаз окажется прямо перед носом. Сделаем тело квадратиком со стороной 2R и проверим все клетки, которые он задевает. Всё вместе — в листинге 14.6.

Листинг 14.6 — Игрок с телом и скольжением вдоль стен

Листинг 14.6 (продолжение) — Игрок с телом и скольжением вдоль стен

Строки 37–40. Квадратик от (x − R, y − R) до (x + R, y + R) может задеть одну, две или четыре клетки — смотря где стоит. Перебираем все клетки от floor(y − R) до floor(y + R) по вертикали и так же по горизонтали. При R = 0.25 это не больше четырёх проверок.

Строки 43–49 — скольжение: сначала шаг по x, потом по y от уже сдвинутой точки.

Скорость теперь — в клетках в секунду: 3 шагом и 5,5 бегом. Остальное в update тебе знакомо по главе 12, только движение идёт через try_move.

Рисуем сверху

Вид сверху — листинг 14.7: клетки прямоугольниками, игрок — треугольником, плюс линия взгляда. Над картой — координаты игрока и угол в градусах.

Листинг 14.7 — Вид сверху

Строки 8–9. topview нужен класс Game для аннотации, а game нужен topview для рисования. Если оба модуля импортируют друг друга, получится циклический импорт: Python начнёт загружать game, оттуда пойдёт в topview, а тот попросит Game из ещё не загруженного game — ImportError. Выход: импортировать Game только для проверки типов. Константа TYPE_CHECKING равна False, когда программа работает, и True, когда код читает mypy. Аннотации в Python 3.14 и новее ленивые — вычисляются, только если их кто-то попросит, — поэтому g: Game в строке 14 спокойно работает без настоящего импорта.

Строки 24–27 — вложенная функция at: точка на расстоянии r от игрока под углом angle + turn, переведённая в пиксели холста. Из трёх таких точек получается треугольник: нос впереди, два угла сзади — под углами ±2,5 радиана, это примерно ±143°.

Запустим под роботом: он отходит назад к стене, идёт боком, поворачивает мышью и бежит вперёд, рисунок 14.2.

Листинг 14.8 — Прогон вида сверху под роботом

Рисунок 14.2 — Вид сверху: игрок прижался к стене и скользит вдоль неё

Игрок упёрся в стену снизу и уткнулся в выступ — но не залез в него ни на пиксель: правый бок квадратика остановился ровно у границы клетки. Попробуй сам: беги наискосок в любую стену, и тебя поведёт вдоль неё.

Итоги главы

— Мир — сетка клеток; координаты игрока — дробные, в клетках; пиксели — только при рисовании.

— Вектор «вперёд» — (cos a, sin a), «вправо» — (−dy, dx), длина — math.hypot.

— Скалярное произведение единичных векторов — косинус угла: впереди или сзади.

— atan2 — угол из вектора без потери знаков; углы храним в радианах.

— Клетку получаем через math.floor, не int.

— Столкновения: тело-квадратик и проверка осей по очереди — скольжение вдоль стен.

— Циклический импорт лечится TYPE_CHECKING и ленивыми аннотациями.

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

Упражнения

Упражнение 14.1. Что выведет? Листинг 14.9. Отдельно подумай о странном «−0.0».

Листинг 14.9 — Упражнение 14.1

Упражнение 14.2. Найди баг. В листинге 14.10 игрок идёт вправо к стене, но в итоге влезает в неё на 0,22 клетки. Почему?

Листинг 14.10 — Упражнение 14.2

Упражнение 14.3. Напиши сам. Функция facing(px, py, angle, tx, ty) должна возвращать True, если точка (tx, ty) находится в конусе ±30° от взгляда игрока. Используй скалярное произведение, без atan2.

Упражнение 14.4. Подумай. Почему при R = 0.5 игрок не сможет пройти в проход шириной в одну клетку, а при R = 0.25 — пройдёт?

Задачи

Задача 14.1. Зум карты. Сделай так, чтобы колёсико мыши меняло размер клетки CELL от 8 до 40 пикселей. Подумай, где хранить текущий масштаб и как передать событие колёсика через стену из главы 12.

Задача 14.2. Карта, которая едет за игроком. Если карта больше экрана, нарисуй её так, чтобы игрок всегда был в центре холста, а карта двигалась под ним.

Задача 14.3. Радар. Добавь на карту точку-цель и выведи над картой надпись LEFT, RIGHT или AHEAD — в какую сторону игроку поворачивать, чтобы смотреть на цель.

Глава 15. Бросаем лучи

Вот главный секрет Wolfenstein 3D и всех его потомков. Чтобы нарисовать стену в столбце экрана, нужно знать одно: как далеко до стены в этом направлении. Близко — стена высокая, далеко — низкая. Значит, для каждого из 640 столбцов экрана бросаем из глаз игрока луч и ищем, где он упрётся в стену. Это и есть рейкастинг (raycasting) — «бросание лучей».

В этой главе мы научимся бросать луч честно и быстро — по клеткам, а не по крошечным шагам. Сначала напишем один луч обычным циклом, потом все 640 разом на numpy, измерим, кто быстрее, и нарисуем веер лучей на карте.

Как не надо: шагать по чуть-чуть

Первая идея, которая приходит в голову: двигаться вдоль луча маленькими шажками, скажем, по 0,01 клетки, и на каждом шаге проверять, не в стене ли мы. Работает, но плохо. Стена в 10 клетках — это тысяча проверок на один луч, 640 тысяч на кадр. И при этом шаг может перепрыгнуть через угол стены: луч пройдёт по диагонали между двумя клетками-стенами, задев их только краешками. На экране появятся дырки.

Правильный способ придумали ещё в 1987 году для трассировки лучей по сетке: DDA (digital differential analyzer). Идея простая: стена может начаться только на линии сетки. Значит, нам интересны лишь точки, где луч пересекает линии, — и мы прыгаем от одной такой точки к следующей. На луч — столько шагов, сколько клеток он пересёк. Десять клеток — десять-пятнадцать проверок.

DDA: от линии к линии

Посмотри на рисунок 15.1. Луч пересекает два семейства линий: вертикальные (x = 1, 2, 3…) и горизонтальные (y = 1, 2, 3…). Между соседними вертикальными линиями расстояние по лучу всегда одно и то же — назовём его step_x. Между горизонтальными — step_y. Если луч идёт почти горизонтально, вертикальные линии он пересекает часто (step_x маленький), а горизонтальные — редко.

Рисунок 15.1 — DDA: луч прыгает с линии на линию; числа — расстояние по лучу

Откуда взять step_x? Направление луча — единичный вектор (dx, dy). Пройдя по нему расстояние t, мы сдвинемся по x на t · dx. Чтобы сдвинуться ровно на одну клетку, нужно t = 1 / |dx|. Так же step_y = 1 / |dy|. При dx = 0 (луч строго вертикальный) step_x — бесконечность: вертикальных линий он никогда не пересечёт.

Алгоритм держит два счётчика: next_x — расстояние по лучу до ближайшей ещё не пройденной вертикальной линии, next_y — до горизонтальной. На каждом шаге берём меньший: если ближе вертикальная линия, переходим в соседнюю клетку по x и прибавляем к next_x ещё step_x. Иначе — то же по y. Пришли в клетку — проверили, стена ли. Листинг 15.1 печатает каждый шаг для луча с рисунка 15.1.

Листинг 15.1 — Один луч по DDA: каждый шаг на печать

Шесть шагов — и стена найдена. Сравни с рисунком: синие и оранжевые точки идут по возрастанию расстояния, и клетки меняются то по x, то по y. Последняя клетка (5, 3) — стена в нижней комнате, луч упёрся в неё сверху.

Первая точка требует отдельного расчёта: игрок стоит не на линии, а внутри клетки. Если луч идёт вправо, до первой вертикальной линии по x остаётся cx + 1 − ox, а влево — ox − cx. Умножаем на step_x — получаем расстояние по лучу. Это строки 20–21.

640 лучей разом

Один луч мы бросили. На экран нужно 640 — по лучу на столбец. Можно вызвать цикл 640 раз. А можно сделать то же самое, что мы делали с пикселями в главе 10, — переложить работу на numpy. Только тут есть загвоздка: лучи летят разное число шагов. Один упрётся в стену через две клетки, другой через двадцать.

Решение — держать список живых лучей. На каждом шаге numpy сдвигает все живые лучи на клетку, проверяет, кто упёрся, записывает их результат и выкидывает из списка. Цикл крутится, пока живые есть. Листинг 15.2.

Листинг 15.2 — Все лучи разом на numpy

Листинг 15.2 (продолжение) — Все лучи разом на numpy

Строки 17–22 — результат в датаклассе Hits: не один луч, а массивы по лучу на элемент. side — какую грань клетки пересёк луч: 0 — вертикальную линию (луч пришёл слева или справа), 1 — горизонтальную. Пригодится в следующей главе, чтобы раскрасить грани по-разному.

Строки 29–31 — шаги для всех лучей. np.where(условие, а, б) — это векторный тернарный оператор: поклеточно берёт а, где условие истинно, и б, где ложно. Но учти: numpy вычисляет оба варианта для всех элементов, а потом выбирает. Поэтому 1.0 / dx посчитается и там, где dx = 0, и numpy выдаст предупреждение о делении на ноль. Блок with np.errstate(divide="ignore») временно его отключает — мы и так подменяем эти элементы на FAR.

Строки 38 и 43–58 — живые лучи. alive — массив номеров, и все операции идут через a = alive: next_x[a] — только значения живых лучей. Маска hit говорит, кто из них упёрся в стену; a[hit] — их номера в общих массивах, туда пишем результат. a[~hit] — оставшиеся, они летят дальше. Тильда ~ — это «не» для булевых массивов.

Строка 39 — хитрость с рамкой. np.pad добавляет вокруг карты слой стен толщиной в одну клетку. Теперь даже луч, который как-то вылетел за край, найдёт стену, а индексы мы сдвигаем на единицу (строки 50–51) и зажимаем clip, чтобы не уехать за массив. Проверка «внутри ли карты» исчезла, и в цикле не осталось ни одного if по элементам.

Строка 40 — страховка MAX_STEPS. Если в карте ошибка и где-то есть дыра в стене, луч мог бы лететь вечно. 128 шагов хватит для любой нашей карты, а вечный цикл исключён.

Кто быстрее

Пора измерить. Листинг 15.3 бросает 640 лучей обычным циклом Python и функцией cast_rays — на нашем уровне и на пустом поле 64 × 64, где лучи летят далеко. Каждый замер повторяется 20 раз, берём лучший результат: так меньше влияют посторонние процессы.

Листинг 15.3 — Цикл Python против numpy

Листинг 15.3 (продолжение) — Цикл Python против numpy

Вот это поворот. numpy быстрее, но вовсе не в 148 раз, как было с пикселями в главе 10, — всего в два-три раза, а на большом поле и того меньше. Почему? Каждый проход цикла в cast_rays — это десяток операций numpy, и у каждой есть постоянная цена: проверить типы, выделить память под результат, запустить цикл на C. Пока в массиве тысячи и миллионы элементов, эта цена незаметна. А у нас всего 640 лучей, и к концу живых остаются единицы. На поле 64 × 64 цикл делает около 60 проходов, и на последних из них numpy гоняет всю свою машинерию ради пары лучей.

Вывод, который стоит запомнить на всю жизнь: numpy выигрывает на больших массивах и проигрывает на маленьких. Векторизовать стоит там, где работы много. А где она, мы узнаем в следующей главе: 640 лучей — это всего 640 чисел, а пикселей стен на экране — до 256 000. Вот там цикл Python и numpy разойдутся на порядки.

Лучшее из 20 запусков, а не среднее — тоже сознательный выбор. Помехи — другие программы, сборщик мусора, частота процессора — могут только замедлить код, но не ускорить. Поэтому самый быстрый прогон ближе всего к чистой скорости кода.

Веер на карте

Покажем лучи на карте. Добавим в вид сверху 32 луча в поле зрения игрока и подсветим клетки, в которые они упёрлись, листинг 15.4. Уровень заодно переехал из main.py в отдельный модуль level.py: он понадобился и программе замера, а импортировать main ради списка строк — значит тащить за ним pygame и всё окно.

Листинг 15.4 — Вид сверху с веером лучей

Строка 29: углы лучей — угол взгляда плюс равномерная сетка от −FOV/2 до +FOV/2. np.linspace(−0,675, 0,675, 32) — 32 числа с равным шагом, включая оба конца. Поле зрения 1,35 радиана — около 77°, как в нашей будущей игре.

Строки 32–34: точка попадания — начало луча плюс направление, умноженное на расстояние. Рисуем отрезок от игрока до неё.

Строки 35–37: клетки, в которые упёрлись лучи, — синие: светлее, если луч пришёл сбоку (side = 0), темнее — если сверху или снизу. Робот отходит вниз, к длинному коридору, и чуть поворачивает мышью, рисунок 15.2.

Листинг 15.5 — Прогон с веером лучей

Рисунок 15.2 — Веер лучей: каждый луч останавливается на первой стене

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

Итоги главы

— Рейкастинг: для каждого столбца экрана — луч и расстояние до первой стены.

— DDA прыгает между пересечениями с линиями сетки: step_x = 1/|dx|, step_y = 1/|dy|.

— Много лучей разом: массив живых лучей, маска попаданий, a[hit] и a[~hit].

— np.where вычисляет обе ветки; np.errstate гасит предупреждения о делении на ноль.

— np.pad добавляет рамку стен и убирает проверки границ.

— numpy выигрывает на больших массивах; на 640 элементах выигрыш скромный. Сначала измеряй.

Контрольная точка: мы знаем расстояние до стены в каждом направлении. Осталось превратить расстояния в картинку — и мир встанет на ноги.

Упражнения

Упражнение 15.1. Что выведет? Листинг 15.6.

Листинг 15.6 — Упражнение 15.1

Упражнение 15.2. Найди баг. В листинге 15.7 луч летит строго вниз, а программа падает. Найди причину.

Листинг 15.7 — Упражнение 15.2

Упражнение 15.3. Напиши сам. Добавь в Hits поле steps — сколько шагов сделал каждый луч — и выведи среднее и максимум для веера на нашем уровне.