Математика в сфере программирования

XXI Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке

Личный портфель

Математика в сфере программирования

Кислов Р.А. 1
1МОАУ "Лицей №6"
Кузнецова Л.А. 1
1МОАУ "Лицей №6"
Автор работы награжден дипломом победителя I степени
Диплом школьникаСвидетельство руководителя
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

ВВЕДЕНИЕ

Компьютеры и прочая программируемая техника – это неотъемлемая часть нашей жизни. Без них мы бы не смогли пользоваться всеми благами цивилизации. Однако за таким прекрасным результатом стоят годы работы различных мастеров своего дела. Одними из таких являются программисты. Они «говорят» компьютеру, что нужно делать, дают ему инструкции. Казалось бы, что программистам совсем не нужна математика, однако я хочу доказать обратное.

Актуальность исследования заключается в том, что сейчас очень много молодых людей хотят попасть в сферу информационных технологий (IT). Однако большинство из них сталкивается с проблемой: нужна ли им для этого математика? На этот вопрос я и хочу ответить.

Гипотеза исследования состоит в том, что хорошему программисту нужны хорошие знания математики.

Методы исследования:

  • Теоретические (поиск, изучение и анализ литературы, интернет ресурсов);

  • Практические (создание программы с использованием математики).

Объектом исследования является сфера информационных технологий.

Предмет исследования – процесс создания программы с использованием математических знаний.

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

Задачи для данного исследования выделены следующие:

  • Изучить историю возникновения программирования

  • Изучить значение математики в программировании

  • Разработать программу, применяя математические методы

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1 История возникновения программирования

Программирование появилось относительно недавно. Первым программистом в истории считается английский математик Чарльз Бэббидж. В 1833 году он предложил идею аналитической машины, которая могла бы выполнять различные вычисления по заданной программе. Хотя реализовать его аналитическую машину ему не удалось из-за финансовых и технических проблем, именно его работа легла в основу современного программирования. Бэббидж разработал принципы работы с программами, включая использование перфокарт и механических устройств для выполнения расчетов.

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

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

Ключевыми фигурами в истории развития программирования стали такие ученые, как Алан Тьюринг, Джон фон Нейман, Грейс Хоппер и другие. Эти люди разработали теоретические основы программирования, определили основные концепции и идеи, лежащие в основе современного программирования.

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

1.2 Значение математики в сфере программирования

Математика – это фундаментальная наука. В своей работе программист использует такие термины, как «типы данных», «классы», «методы», которые лишь косвенно относятся к математике. Однако программист не использует, например, те же квадратные уравнения или системы. Может показаться, что программисту математика вообще не нужна, но это далеко не так.

Математика является частью фундамента знаний хорошего программиста. Можно, конечно, написать пару программ и без её знания, однако дальше этого уйти не получится. Например, такие структуры данных, как массив, очередь, стек, список и т.д. основаны на математических концепциях. Без знания таких базовых структур данных, программист не сможет грамотно оптимизировать свой код и использовать все возможности языка, на котором пишет.

Однако не только структуры данных помогают программисту. В программировании используются также математические модели. Они позволяют предсказывать работу и дальнейший результат действий той или иной системы. Благодаря математической модели были созданы теория игр, концепция клеточных автоматов, квантовая логика и так далее. Без нее мы не смогли бы предсказывать погоду, а так как для этого используются огромные объемы данных, то эта работа напрямую относится к программистам, специалистам по Data Science.

Без математики мы бы не смогли оценить оптимизацию работы алгоритма. С этой задачей прекрасно справляется нотация Big O, в которой используются такие понятия, как «степень», «логарифм», «факториал». Такая оценка сложности называется асимптотическая.

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

Рисунок 1. График нотации BigO

2. СОЗДАНИЕ ПРОГРАММЫ

2.1 Основная теория рей-кастинга

Я долго думал, какая программа сможет точно показать силу математики в рамках программирования и остановился на рей-кастере. Рей-кастинг (не путать с рейтрейсингом) – это один из методов рендеринга компьютерной графики, который основывается на замерах лучей, «брошенных» из камеры. В качестве программы я решил сделать игру, графика в которой будет основываться на этом принципе. В сфере гейм-дева такие игры иногда называют 2.5D (2.5-мерными).

В игровой индустрии первым использовать технологию рей-кастинга придумал Джон Кармак в игре «Wolfenstein 3D». Тогда это было невероятным новшеством, потому что ограничения мощностей компьютеров не позволяли отрисовывать 3D-графику, да еще и в реальном времени. Кармак использовал этот алгоритм повторно в прорывной игре «Doom» 1993 года. Там он дополнил его структурой данных BSP (Binary Space Partitioning), чтобы ускорить производительность игры.

Для создания своего рей-каст движка, я использовал язык C# с фреймворком .NET, а также биндинг на библиотеку SFML. В первую очередь необходимо разобраться как работает такой движок. Все изображение строится по 2D карте. Изначально нам дана позиция игрока на этой карте, его поворот и его угол обзора. Мы выпускаем луч в начале угла обзора игрока. Немного его увеличиваем и проверяем, не ударился ли он об стену. Если нет, повторяем процедуру до тех пор, пока луч не ударится о стену. Затем делаем точно также для оставшегося угла обзора и, переведя длину луча в вертикальную полоску на экране, получаем «трехмерное» изображение карты. Рисунок ниже наглядно показывает все вышеперечисленное.

Рисунок 2. Визуализация работы рей-кастинга

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

Рисунок 3. 2D этап разработки игры

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

Рисунок 4. Луч с большим шагом проходит сквозь стену

Поэтому для тайловых карт (которые можно поделить на равные квадраты) существует специальный алгоритм под названием DDA (Digital Differential Analyzer). Суть его не очень проста, но довольно понятна.

Сначала мы определяем, смотрит ли игрок вниз или вверх (на двухмерной карте). На основе этого рассчитываем расстояние до столкновения луча с первой горизонтальной линией (верхней или нижней зависит от поворота игрока, как указано выше). Получим координату Y точки столкновения и прямоугольный треугольник. Через тангенс угла поворота игрока находим координату X точки столкновения по формуле [ ] , где α – угол поворота игрока. Затем по теореме Пифагора находим расстояние от игрока до точки столкновения луча с горизонтальной линией.

Проверяем, есть ли там стена. Если нет, то нам необходимо найти оффсет движения луча (насколько необходимо увеличить луч, чтобы он столкнулся со следующей горизонтальной линией). Находится он просто: по Y мы просто прибавляем размер тайла (квадрата), а X находим также через тангенс (см. предыдущую формулу). По теореме Пифагора находим оффсет луча. Прибавляем этот оффсет до тех пор, пока луч не столкнется со стеной. Находим длину луча и записываем.

Далее делаем всё тоже самое с вертикальными линиями. У нас получилось две длины – столкновение по горизонтали и столкновение по вертикали. Сравниваем их и находим меньшую. Это и будет являться расстоянием от игрока до ближайшей стены в направлении этого луча. Схема ниже поясняет, что мы только что сделали.

Рисунок 5. Схема расчета длины луча (sideDistX/Y – расстояние до ближаейшей вертикальной/горизонтальной линии, deltaDistX/Y – оффсет луча)

Затем нам остается только сконвертировать длину луча в длину полосы на экране. Делается это по формуле [ ] , где a – это длина тайла, s – ширина экрана, а d – длина луча. Теперь выводим эту линию на экран в соответствии с ее положением, повторяем алгоритм для всего угла обзора и получаем результат ниже (красными являются лучи, которые попали в горизонтальную стену, а синими – в вертикальную).

Рисунок 6. 2D и 3D варианты рей-кастинга

Однако если мы приблизимся к какой-либо стене, то произойдет следующее.

Рисунок 7. Искажение прямой стены (эффект «рыбьего глаза»)

На самом деле линии делают точно так, как мы им сказали. Лучи по бокам действительно длиннее лучей в центре, значит они дальше и рисовать их нужно меньшего размера. Чтобы избежать такого эффекта, нам нужно лишь умножить длину луча на косинус разницы углов игрока и луча, превращая евклидову длину в перпендикулярную: [ ] , где – перпендикулярная длина, – евклидова длина, а α – разница угла игрока и угла луча. Рисунок ниже для пояснения (красная линия – евклидово расстояние, синяя – перпендикулярное).

Рисунок 8. Евклидово и перпендикулярное расстояние до точки на плоскости

2.2 Дополнительные возможности рей-кастера

Основная механика нашей игры сделана, а это значит, что можно теперь ее немного приукрасить, добавив текстуры. Я решил использовать текстуры 32x32 пикселя, потому что на них будет проще объяснить.

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

Рисунок 9. Выбор вертикальной полосы текстуры

Следом, перед тем, как мы будем отрисовывать стены, мы нарисуем два прямоугольника – небо и землю, на верхнюю и нижнюю половины экрана. Благодаря такой технике у нас получится следующее изображение.

Рисунок 10. Текстурированный рей-кастер

Но это еще не все возможности рей-кастера. Помимо текстур мы можем добавить также спрайты. Спрайты – это 2D изображения на плоскости, но в нашем случае мы будем отображать их в «3D» мире. Для примера возьмем текстуру краба. Для начала мы находим угол между игроком и крабом. Сделать это можно функцией Atan2, которая принимает в качестве параметра два катета и выдает угол. Затем из полученного угла вычтем угол поворота игрока. Теперь найдем высоту спрайта по такой же формуле, как и высоту линий, только вместо длины луча подставим расстояние между игроком и спрайтом. Позицию по координате X найти чуть сложнее. Нужно воспользоваться формулой [ ] , где α – это угол между игроком и крабом, – это ширина экрана, а – это ширина спрайта.

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

Рисунок 11. Спрайты в 3D пространстве

Способов улучшения данной программы огромное множество. Можно оптимизировать используемые алгоритмы: использовать многопоточность (т.к. бо́льшая часть кода нагружает именно процессор, а не видеокарту), избавиться от лишних циклов и т.д. Можно добавить что-то новое: реализовать GUI и превратить это в полноценную игру. В качестве примера, я немного доработал игру и выложил её исходный код на GitHub: https://github.com/coppershortsword137/Raycaster-Game.

ЗАКЛЮЧЕНИЕ

Таким образом, мы выполнили все поставленные задачи, а именно:

  • Изучить историю возникновения программирования

  • Изучить значение математики в программировании

  • Создать программу с использованием математики

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

СПИСОК ИНФОРМАЦИОННЫХ ИСТОЧНИКОВ

  1. Васильев А.Н. Программирование на C# для начинающих. Основные сведения.

  2. Марк Дж. Прайс. C# 7 и .NET Core. Кросс-платформенная разработка для профессионалов.

  3. Бонд Д. Г. Unity и C#. Геймдев от идеи до реализации.

Ссылки на электронные ресурсы

  1. https://www.sfml-dev.org/documentation/2.6.1/(дата обращения: 29.11.2023)

  2. https://habr.com/ru/companies/macloud/articles/560712/ (дата обращения: 01.12.2023)

  3. https://youtu.be/BAReJ0QtkZA?si=uC8lLQCw5DcYOzJ1 (дата обращения: 01.12.2023)

  4. https://ru.wikipedia.org/wiki/Ray_casting (дата обращения: 01.12.2023)

  5. https://youtu.be/g2o22C3CRfU?si=NwSi9AJs59ktA568 (дата обращения: 02.12.2023)

  6. https://tochmah.ru/matematika-v-programmirovanii-osnovy-i-primenenie/ (дата обращения: 14.12.2023)

  7. https://siobr.ru/istoriya-vozniknoveniya-programmirovaniya/ (дата обращения: 15.12.2023)

  8. https://www.youtube.com/@3DSage (дата обращения: 03.12.2023)

  9. https://youtu.be/LUYxLjic0Bc?si=SCGVEQ27ikffCCKl (дата обращения: 20.12.2023)

  10. https://youtu.be/OpIS1zoz6fU?si=FxohcNSJdt7vPx2D (дата обращения: 22.12.2023)

  11. https://learn.microsoft.com/en-us/dotnet/ (дата обращения: 25.11.2023)

  12. https://youtu.be/yTRzfKh4Tg0?si=VJ41Rq_BEcRWAMPI (дата обращения: 27.12.2023)

  13. https://lodev.org/cgtutor/raycasting.html (дата обращения: 29.11.2023)

Просмотров работы: 42