Курсовая работа студента 341 группы Осипова Никиты Алексеевича Научный



Дата13.05.2013
Размер57.1 Kb.
ТипКурсовая
Санкт-Петербургский Государственный Университет

Математико-механический факультет

Кафедра системного программирования

Разработка 3D пиксельного физического движка

Курсовая работа студента 341 группы

Осипова Никиты Алексеевича

Научный руководитель

директор академических программ Exigen Services, выпускник кафедры системного программирования 1985 г., Оносовский В.В

Санкт-Петербург – 2012

Содержание

Содержание ………………………………………………………………………………… 2

Введение ……………………………………………………………………………………. 3

Модель и постановка задачи ……………………………………………………………….4

Описание алгоритма ………………………………………………………………………..5

Заключение ………………………………………………………………………………….8

Введение

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

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

Модель и постановка задачи

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

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

Саму задачу можно разделить на 3 подзадачи:

  • Реализация 2D физики

  • Реализация 2D пиксельной физики

  • Реализация 3D пиксельной физики

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

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


Реализация 2D пиксельной физики подразумевает обработку двумерной картинки, в которой значения сетки в нашем двумерном массиве принимают значения 0 и 1, т.е. закрашен данный пиксель, или нет.
И, наконец, реализация 3D пиксельной физики позволяет обрабатывать движение шарика в полноценном 3D пиксельном игровом поле.

Описание алгоритма

  • Реализация 2D физики

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

Очевидно, что проблему составляет момент, когда мячик ударяется об стенку.

Для поиска положения мячика после соударения может быть два способа. Первый – стандартная тригонометрия и равенство угла отражения и угла преломления. Второй – через вектора и скалярное произведение. Как показал опыт, второй метод немного выигрывает в производительности, а так же является более наглядным, что повышает читаемость кода. Его и опишем подробнее.

Из известной нас скорости движения мячика легко получить вектор его движения. Назовём его l. Искомый вектор отражения назовём r. Прямая, от которой мы отражаемся, задана двумя точками (x1,y1) и (x2,y2). Вектор нормали n (ненормированый) определяется как разность соответствующих координат, поменянная местами. И теперь, из простых геометрических соображений (см. рис. 1), мы получаем формулу 1.


(рис. 1) (формула 1)
Итак, мы получили результирующий вектор отражения. Теперь, найдя точку пересечения прямой, содержащей вектор движения, с отрезком стены, мы можем вычислить расстояние, которое шарику осталось пролететь после столкновения. Зная это и вектор отражения, найдём точку положения шарика после отражения.

  • Реализация 2D пиксельной физики

В случае пиксельной физики отличие в том, что у нас отсутствуют заданные аналитически поверхности. В 2D мы лишь можем проверить есть в данной точке стена, или нет.
Для решения этой задачи существует три подхода. Первый – свести задачу к предыдущей. То есть перед началом игры аппроксимировать всё поле отрезками с достаточной точностью, а затем, аналогично первому пункту, искать пересечение вектора движения со всеми отрезками, из которых состоит игровое поле. Очевидно, что даже если оптимизировать работу, и искать пересечение не со всеми отрезками на поле, а лишь с небольшим их количеством, работать быстро такая программа не будет. А главное, в связи с особенностями игры, поля могут подгружаться достаточно быстро – а в этом случае ожидание на аппроксимацию карты выйдет очень большим. Второй подход – это искать все точки пересечения с шариком, в области, которую он пройдёт на следующем шаге. Затем аппроксимировать эти точки кривой, считать точку пересечения с полученной кривой, восстанавливать нормаль и искать угол отражения. Этот метод даст наибольшую точность. Однако, он очень медленный. А главное, что подобная точность в игре и не нужна - важнее скорость. И третий метод. Мы так же ищем точки пересечения, но не аппроксимируем, а ищем среднюю точку этой области, соединяем её с центром шарика и считаем, что получили нормаль. Точность подобного метода ниже чем во втором варианте, зато он гораздо быстрее.
При реализации третьего метода важная часть - это длинна шага, который будет делать шарик прежде чем мы в очередной раз будем проверять его на столкновение. Необходимо, чтобы длинна шага не позволяла шарику пересечь слишком большую область – от этого сильно упадёт точность и возможны ситуации, когда вектор отражения и вовсе будет абсурдным. Проще всего выбрать длину шага в один пиксель – тогда мы не сможем пересечь сразу слишком много пикселей разных стенок. Можно требовать, чтобы скорость шарика была невелика.

  • Реализация 3D пиксельной физики

При реализации 3D пиксельной физики используются результаты предыдущих пунктов. Т.е. обоснование, почему не реализовывать через аппроксимацию поверхностей остаётся тем же – это слишком медленно.

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

Заключение

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


Похожие:

Курсовая работа студента 341 группы Осипова Никиты Алексеевича Научный iconКурсовая работа студента I курса дневного отделения группы Научный руководитель
Своего рода неосознанным отражением нового состояния страны стали и изменения в русской речи, и в частности активизация целого ряда...
Курсовая работа студента 341 группы Осипова Никиты Алексеевича Научный iconКурсовая работа студента 345 группы

Курсовая работа студента 341 группы Осипова Никиты Алексеевича Научный iconКурсовая работа студента группы кн-302 Смажилюка Игоря Павловича

Курсовая работа студента 341 группы Осипова Никиты Алексеевича Научный iconКурсовая работа студента 445 группы
Создать для существующей платформы DocsVision автогенератор классов-моделей. Требования к генератору
Курсовая работа студента 341 группы Осипова Никиты Алексеевича Научный iconКурсовая работа студента III курса Каргальцева А. В. Научный руководитель ст преп. Пантелеев А. Д. Санкт-Петербург
Эпоха и основная проблематика творчества христианских писателей III-IV в н э
Курсовая работа студента 341 группы Осипова Никиты Алексеевича Научный iconКурсовая работа по аналитической химии студента 213 группы Ляхова Антона Борисовича
Моделирование процессов разряда-ионизации серебра на поверхности твердого электрода
Курсовая работа студента 341 группы Осипова Никиты Алексеевича Научный iconКурсовая работа студента 445 группы
Чтобы упростить написание таких приложений, удобно использовать различные библиотеки и фреймворки, например Ubiq Mobile
Курсовая работа студента 341 группы Осипова Никиты Алексеевича Научный iconДипломная работа студента 544 группы Вахитова Александра Тимуровича Научный
Метод подстройки пользовательских приоритетов при поиске по коллекциям изображений 28
Курсовая работа студента 341 группы Осипова Никиты Алексеевича Научный iconДипломная работа студента 5 курса группы №543 Наумова Сергея Сергеевича Научный
Применение распараллеливания для итерационной триангуляции с измельчением вблизи границы
Курсовая работа студента 341 группы Осипова Никиты Алексеевича Научный iconДипломная работа студента 545 группы Сынтульского Сергея Научный Игорь Павлович Соловьев
Логический подход к спецификации мультиагентных систем с вероятностным поведением
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org