Простейший физический движок

Вас интересуют игры? Хотите создать игру но не знаете с чего начать? Тогда вам сюда. В этой статье я рассмотрю простейший физический движок, с построения которого можно начать свой путь в GameDev'e. И да, движок будем писать с нуля.

Несколько раз мои друзья интересовались, как же я пишу игры / игровые движки. После очередного такого вопроса и ответа я решил сделать статью, раз эта тема так интересна.

В качестве языка программирования был выбран javascript, потому что возможности скачать IDE и компилятор у подопытного знакомого не было. Рисовать будем на canvas.

Постановка задачи


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

Алгоритм


Для начала нужно уяснить отличие компьютерной физики от реальной. Реальная физика действует непрерывно (во всяком случае обратное не доказать на текущий момент). Компьютерная физика, как и компьютер действуют дискретно, т.е. мы не можем вычислять её непрерывно, поэтому разбиваем её вычисление на шаги с определённым интервалом (я предпочитаю интервал 25 мс). Координаты объектов меняются после каждого шага и объекты выводятся на экран.

Теперь приступим к самой гравитации.

Закон всемирного тяготения (Ньютонова гравитация) гласит:
F = G * m1 * m2 / R^2 						(1)

где:
F [Н]- сила притяжения между двумя объектами
G = 6.67*10^-11 [м^3/(кг * с^2)]- гравитационная постоянная
m1, m2 [кг] - массы 1 и 2 объектов
R [м] - расстояние между центрами масс объектов


Как это нам поможет в определении новых координат? А мы эту силу будем прикладывать к этим объектам, используя второй закон Ньютона:
F = m * a 							(2)

где:
F [Н] - сила, приложенная к текущему объекту
m [кг] - масса текущего объекта
a [м/с^2] - ускорение текущего объекта


Забудем на время то, что в (1) сила — скаляр, а в (2) сила — вектор. И во 2 случае будем считать силу и ускорение скалярами.

Вот и получили изменение ускорения:
a = F / m 							(3)


Изменение скорости и координат следует из следующего:
a = v'   →   a = dv / dt   →   dv = a * dt
v = s'   →   v = ds / dt   →   ds = v * dt
v += dv
Pos += ds


где:
d - дифференциал (производная)
v - скорость
s - расстояние
Pos - точка, текущие координаты объекта


переходим от векторов к скалярам:
a.x = a * cos(α)
a.y = a * sin(α)
dv.x = a.x * dt
dv.y = a.y * dt
v.x += dv.x
v.y += dv.y
ds.x = v.x * dt
ds.y = v.y * dt
Pos.x += ds.x
Pos.y += ds.y

где:
cos(α) = dx / R
sin(α) = dy / R
dx = Pos2.x - Pos.x
dy = Pos2.y - Pos.y
R^2 = dx^2 + dy^2


Так как другого вида силы в проекте пока нет, то используем (1) в таком виде и немножко облегчим вычисления:
F = G * m * m2 / R^2
a = G * m2 / R^2


Код


Запускаемую страничку index.html создадим сразу и подключим код:
можно не смотреть
<!DOCTYPE html>
<html>
    <head>
        <title>Physics</title>
        <script type="text/javascript" src="script.js"></script>
    </head>
    <body></body>
</html>



Основное внимание уйдёт на файл с кодом программы script.js. Код для отрисовки откомментирован достаточно и он не касается темы:
посмотрим и забудем на время
var canvas, context;
var HEIGHT = window.innerHeight, WIDTH = window.innerWidth;

document.addEventListener("DOMContentLoaded", main, true);

function main(){
// создаём холст на весь экран и прикрепляем его на страницу
	canvas = document.createElement('canvas');
	canvas.height = HEIGHT;
	canvas.width = WIDTH;
	canvas.id = 'canvas';
	canvas.style.position = 'absolute';
	canvas.style.top = '0';
	canvas.style.left = '0';
	document.body.appendChild(canvas);
	context = canvas.getContext("2d");
	/*******
	другой код
	*******/
}

function Draw(){
    // очищение экрана
    context.fillStyle = "#000000";
    context.fillRect(0, 0, WIDTH, HEIGHT);
    
    // рисование кругов
    context.fillStyle = "#ffffff";
    for(var i = 0; i < star.length; i++){
        context.beginPath();
        
        context.arc(
            star[i].x - star[i].r,
            star[i].y - star[i].r,
            star[i].r,
            0,
            Math.PI * 2
        );
        
        context.closePath();
        context.fill();
    }
}


Теперь самое вкусное: код, который просчитывает физику.

На каждый объект мы будем хранить только массу, координаты и скорость. Ах да, ещё надо радиус — он нам понадобится для рассчёта столкновений, но об этом в следующей статье.

Итак, «класс» объекта будет таким:
function Star(){
    this.x = 0;
    this.y = 0;
    this.vx = 0;
    this.vy = 0;
    this.r = 2; // Radius
    this.m = 1;
}

var star = new Array(); // в этом массиве будут храниться все объекты
var count = 50; // начальное количество объектов
var G = 1; // задаём константу методом подбора

Генерация случайных объектов в самом начале:
var aStar;
for(var i = 0; i < count; i++){
    aStar = new Star();
    aStar.x = Math.random() * WIDTH;
    aStar.y = Math.random() * HEIGHT;
    star.push(aStar);
}


Шаг вычисляться будет в следующей функции:
function Step(){
    var a, ax, ay, dx, dy, r;
    
    // важно провести вычисление каждый с каждым
    for(var i = 0; i < star.length; i++) // считаем текущей
        for(var j = 0; j < star.length; j++) // считаем второй
        {
            if(i == j) continue;
            dx = star[j].x - star[i].x;
            dy = star[j].y - star[i].y;
            
            r = dx * dx + dy * dy;// тут R^2
            if(r < 0.1) r = 0.1; // избегаем деления на очень маленькое число
            a = G * star[j].m / r;
            
            r = Math.sqrt(r); // тут R
            ax = a * dx / r; // a * cos
            ay = a * dy / r; // a * sin
            
            star[i].vx += ax * dt;
            star[i].vy += ay * dt;
        }
    // координаты меняем позже, потому что они влияют на вычисление ускорения
    for(var i = 0; i < star.length; i++){
        star[i].x += star[i].vx * dt;
        star[i].y += star[i].vy * dt;
    }
    
    // выводим на экран
    Draw();
}


Ну и долгожданный запуск таймера:
var dt = 0.02; // шаг вычисления
timer = setInterval(Step, dt * 1000);


Посмотреть работу можно здесь, а код здесь.

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

Минусы


Сложность алгоритма растёт экспоненциально, поэтому увеличение объектов влечёт заметное проседание FPS. Решение с помощью Quad tree или других алгоритмов не поможет, но в реальных играх объекты не взаимодействуют по принципу каждый с каждым.

Тестирование производилось на машине с процессором Intel Pentium с частотой 2.4 GHz. При 1000 объектов с интервал вычисления уже превышал 20 мс.

Использование


В качестве силы можно использовать суперпозицию разных сил в (3). Например, тягу двигателя, силу сопротивления грунта и воздуха, а также соударения с другими объектами. Алгоритм можно легко расширить на три измерения, достаточно ввести z аналогично x и y.

Этот алгоритм был написан мною ещё в 9 классе на паскале, а до текущего момента переложен на все языки, которые я знаю просто потому, что могу в качестве личного Hello World'a. Даже в терминале.

Также данный алгоритм можно использовать для другого фундаментального взаимодействия — электромагнитного (G → k, m → q). Я использовал этот алгоритм для построения линий магнитной индукции системы зарядов, но об этом в другой статье.

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

Средняя зарплата в IT

113 000 ₽/мес.
Средняя зарплата по всем IT-специализациям на основании 10 037 анкет, за 2-ое пол. 2020 года Узнать свою зарплату
Реклама
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее

Комментарии 38

    +8
    Также данный алгоритм можно использовать для другого фундаментального взаимодействия

    Какой этот алгоритм? 2 закон Ньютона? Или редуцированный вариант численного метода интегрирования Эйлера? Так то их можно использовать практически везде, разве что пока у вас скорости не близкие к световым. Ну и разумеется если нужна большая точность, то Эйлера лучше заменить на что-то типа Дорвана-Принса.

    Что касается статьи — зря вы выбрали dt = 1. Первая причина — ваша одна секунда равняется 0.02 с реальных, а, как следствие — все коэффициенты придется пересчитывать. Вторая — если будет просяд fps — все поедет. Нужно рассчитывать dt динамически.

    Ну и setTimeout — используйте window.requestAnimationFrame.

    А так статья интересная, но (только не в обиду) для гуманитариев. Второй закон Ньютона и интегрирование Эйлером — прям совсем база.
    • НЛО прилетело и опубликовало эту надпись здесь
        0
        dt должен быть фиксированным. Если между двумя кадрами прошло время dt*2 то надо просчитать физику на 2 шага.
          0
          и привет, «телепорты» и проскакивания насквозь.

          А собственно, кому должен? Всё зависит от постановки задачи.
          В еве онлайн вот не побрезговали замедлением времени при увеличении количества участников.
            0
            Да что вы утрируете то?
            В js (да везде в общем то) dt должен быть динамичным, покуда requestAnimationFrame не стабильный (я уж молчу про setInterval) — то будет все заторможенно, то наоборот. Но если «промах» по времени был слишком большой (больше некого epsilon) — ставим dt равным этому порогу. Да, будет тормоз, но решит кучу других проблем.
              0
              Не совсем так. dt должен быть фиксированным. Если между двумя вызовами requestAnimationFrame прошло времени n*dt, то нужно обсчитать физику в n шагов.
              0
              Телепорты и проскальзывания насквозь получаются как раз из-за динамического dt. Если 2 объекта движутся навстречу друг другу, а dt сильно большой, то они пролетят сквозь друг друга. Но если большой dt разделить на интервалы поменьше, то коллизия будет зарегистрирована. Кроме того динамический dt не позволяет добиться одинакового поведения при одинаковых исходных условиях, что сильно затрудняет тестирование.
                0
                Если 2 объекта движутся навстречу друг другу, а dt сильно большой, то они пролетят сквозь друг друга.


                Так и я про это же.
                Но я не согласен, что из-за динамического. Если интервал большой, то статичность не поможет.

                Но если большой dt разделить на интервалы поменьше

                Так эти интервалы опять же и будут dt для физического движка.

                И я это тоже имел в виду — считать надо эти субинтервалы, а не «между двумя кадрами».
          0
          Второй закон Ньютона и интегрирование Эйлером — прям совсем база.
          Тогда, когда был придуман этот алгоритм я даже производных ещё не знал, а метод Эйлера только на 2 курсе универа нам преподнесли.
          Ну и setTimeout — используйте window.requestAnimationFrame.
          Спасибо за совет, следующих статьях буду использовать именно этот метод
            +2
            Нужно рассчитывать dt динамически.

            В результате получим невоспроизводимость -> боль при отладке.
            Ещё вспоминается Dune II, где можно было влиять на успех боя переключая скорость игры.
              0
              Мне с постоянным dt сразу вспоминается GTA II, который без патча на современной системе работает с fps ~500 и одно нажатие клавиши отправляет вас в дорогу со скоростью звука.
                0
                Кстати, управлять величиной FPS можно не только с помощью изменения dt. Если расчёт закончился раньше времени (для большого dt), то можно просто дать процессору отдохнуть.
              +1
              Ну и разумеется если нужна большая точность, то Эйлера лучше заменить на что-то типа Дорвана-Принса.

              Если физический движок предназначен для какой-то игры, то нужна не точность, а быстродействие. Так что лучше вместо Дормана — Принса взять метод Верле, который позволяет получать координаты прямо из ускорений без вычисления скоростей.
              +2
              А где просчет столкновений? К сожалению, ничего интересного. Лучше бы потратили время на изучение Box2D, например.
                0
                Просчёт столкновений в следующей статье будет
                  0
                  Меня вот, кстати, всегда немного удивляло почему просчёт столкновений относят к физическому движку. Как по мне, этим должен заниматься отдельный менеджер, а движок должен заниматься расчёт изменений физических (а не габаритных, геометрических) свойств объектов на основе данных о взаимной расположении объектов в пространстве.
                    +3
                    Что такое «отдельный менеджер»? Что подразумевается под физическими изменениями? Почему габаритные — не физические? Без подколки, просто привык считать, что ф. движок просчитывает все, что связано и с положением в пространстве, и изменением положения, размерами — все, что связано с законами механики и пр. Задачка вида «было у нас 2 шара, они столкнулись и где нам их рисовать через 3 секунды после столкновения?» — вполне себе для ф. движка.
                      0
                      Да, согласен, не корректно сформулировал. Габаритные свойства тоже можно в чём-то отнести к физическим. Я имел в виду то, что часто не нужен просчёт взаимодействия негабаритных свойств объектов (расчёт сил, ускорений, и.т.д), но нужно только искать пересечение между габаритами объектов, между объектами и лучами, и.т.д. Для механизма решения задач поиска взаимоотношения геометрических форм в пространстве есть название: spatial database (пространственные базы данных). В физических движках поиск пересечений почти всегда включают в механизм расчёта физической реакции на эти пересечения. Именно это меня всегда удивляло. Всегда казалось, что это разные области ответственности и что из-за этого, во-первых, приходится тащить за собой данные о физических свойствах объектов когда тебе не нужны связанные с ними расчёты, а во-вторых отпадает возможность для разработчиков физических движков использовать готовые библиотеки для работы с пространственными базами данных, а на себя брать задачу создания более качественной реализации физической симуляции (ну, или наоборот — создавать более качественные пространственные базы данных и присоединять к ним механизмы физический симуляции).
                    0
                    Попробуйте посмотреть в сторону потенциала Леннарда-Джонса (насколько я догадываюсь, Вы «вручную» собираетесь контролировать сближение объектов?).
                      0
                      Буду искать объекты, которые пересекаются и объединять их в центре масс (неупругое столкновение) или раздвигать их и давать скорость по закону сохранения импульса (упругое).
                  0
                  А что делает этот код физическим движком? Функция Step()?
                    0
                    Прочил определение и отстал. Привык считать, что движок — это компонент для других программ (библиотека или фреймворк).
                    +4
                    Отсутствие dt в коде реализации численной схемы — большая ошибка, особенно для программы, претендующей на учебник для новичков. И лучше его задать честной константой dt=0.025, как Вы указали вначале статьи.
                    Рано или поздно, он понадобится.
                      +1
                      вернул dt обратно
                      0
                      Забавно как-то гравитация работает (столкновений, как я понимаю в этой версии нет). Если в демке натыкать мышкой несколько точек рядом, они медленно притягиваются друг другу по спирали, а затем запуливают друг друга в разные стороны с какой-то невменяемой скоростью.
                        0
                        Под Хромом не работает
                          0
                          Немного правил константы, и Вы попали в момент, когда движение было слишком медленным. Сейчас всё работает
                            +1
                            Да, так лучше, но гравитация продолжает выглядеть странной.
                              +4
                              Издержки пошагового вычисления: в определённый момент расстояние между объектами становится очень маленьким и сила стремится к бесконечности, поэтому они ускоряются до невероятной скорости. На следующий такт эти объекты слишком удаляются друг от друга и не могут затормозить из-за большого расстояния
                              Эта строка частично решает данную проблему:
                              if(r < 0.1) r = 0.1; // избегаем деления на очень маленькое число
                              

                              Можно также ввести искусственное ограничение скорости или уменьшить интервал.
                                0
                                Спасибо. Весьма исчерпывающее объяснение. Будет интересно посмотреть реализацию вашего движка с обработкой коллизий, но присоединюсь к KvanTTT. Для практических целей, лучше использовать какой нибудь из уже существующих движков. Тот же Box2D, например.
                                0
                                Я тоже делал N-body simulation, долго возился с величиной r, пока не понял, что это жуткий костыль. Как сделать правильную физическую симуляцию макрообъектов? Задать им размер? Принудительно заставить соблюдаться закон сохранения импульса?
                                  0
                                  Я бы задал размер и после столкновения пересчитал скорости по закону сохранения импульса. В своём конечном варианте я задал плотность константой и высчитывал радиус исходя из массы.
                        0
                        При большом количестве частиц количество вычислений методом «в лоб» будет расти квадратично, что не очень хорошо. Ведь на движение каждой частицы наибольшее влияние оказывают её ближайшие соседи. Если не нужна сверхвысокая точность (а задача многих тел точно не решается даже численно), можно ограничиться только ими.
                        Попробуйте реализовать модель с меньшей алгоритмической сложностью. В качестве отправной точки рекомендую, например, event driven collision model. Она в общих чертах рассмотрена в книге «Алгоритмы» Седжвика и его же курсе «Algorithms I» на Курсере.
                          0
                          И вот на горизонте замаячил fast multipole method, про который, между прочим, было бы *действительно* интересно почитать.
                          +4
                          Забудем на время то, что в (1) сила — скаляр, а в (2) сила — вектор. И во 2 случае будем считать силу и ускорение скалярами.

                          Что-что? Может стоит лучше сказать, что в (1) речь идет о проекции силы на конкретное направление (на направление вдоль линии, соединяющей центры тел)? Это очень и очень существенное обстоятельство, если эта статья призвана кого-то и чему-то научить. :)

                          И да: посмотрите в сторону метода Рунге-Кутты.
                            +1
                            У вас в движке большая проблема с просчетом близких орбит. Не работает банальный закон сохранения энергии — если два тела почти стоят, то в демке, да и с такой дискретной математикой, у них будут очень большие ускорения на близких расстояниях. Как результат — если просто поставить два тела, то они медленно будут сближаться, а потом разлетятся на сильно большей скорости чем им дала энергия падения.
                            Общим, я даже не знаю где эту модель можно применить. Нужно существенно доработать.
                              0
                              Совсем уж простой физический движок.

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

                              Самое читаемое