Несколько раз мои друзья интересовались, как же я пишу игры / игровые движки. После очередного такого вопроса и ответа я решил сделать статью, раз эта тема так интересна.
В качестве языка программирования был выбран javascript, потому что возможности скачать IDE и компилятор у
Постановка задачи
Необходимо для нескольких объектов на плоскости реализовать взаимодействие с помощью фундаментальной силы гравитации.
Т.е. сделать что-то подобное притяжению звёзд в космосе.
Алгоритм
Для начала нужно уяснить отличие компьютерной физики от реальной. Реальная физика действует непрерывно (во всяком случае обратное не доказать на текущий момент). Компьютерная физика, как и компьютер действуют дискретно, т.е. мы не можем вычислять её непрерывно, поэтому разбиваем её вычисление на шаги с определённым интервалом (я предпочитаю интервал 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 классе на паскале, а до текущего момента переложен на все языки, которые я знаю
Также данный алгоритм можно использовать для другого фундаментального взаимодействия — электромагнитного (G > k, m > q). Я использовал этот алгоритм для построения линий магнитной индукции системы зарядов, но об этом в другой статье.
Всем спасибо за прочтение. Надеюсь данная статья Вам немного поможет в создании собственных игр.
Курс держим примерное на такое — спиральная галактика.
Комментарии (38)
KvanTTT
21.08.2015 13:06+2А где просчет столкновений? К сожалению, ничего интересного. Лучше бы потратили время на изучение Box2D, например.
oPOCCOMAXAo
21.08.2015 13:28Просчёт столкновений в следующей статье будет
semenyakinVS
21.08.2015 23:58Меня вот, кстати, всегда немного удивляло почему просчёт столкновений относят к физическому движку. Как по мне, этим должен заниматься отдельный менеджер, а движок должен заниматься расчёт изменений физических (а не габаритных, геометрических) свойств объектов на основе данных о взаимной расположении объектов в пространстве.
MacIn
22.08.2015 02:36+3Что такое «отдельный менеджер»? Что подразумевается под физическими изменениями? Почему габаритные — не физические? Без подколки, просто привык считать, что ф. движок просчитывает все, что связано и с положением в пространстве, и изменением положения, размерами — все, что связано с законами механики и пр. Задачка вида «было у нас 2 шара, они столкнулись и где нам их рисовать через 3 секунды после столкновения?» — вполне себе для ф. движка.
semenyakinVS
22.08.2015 11:56Да, согласен, не корректно сформулировал. Габаритные свойства тоже можно в чём-то отнести к физическим. Я имел в виду то, что часто не нужен просчёт взаимодействия негабаритных свойств объектов (расчёт сил, ускорений, и.т.д), но нужно только искать пересечение между габаритами объектов, между объектами и лучами, и.т.д. Для механизма решения задач поиска взаимоотношения геометрических форм в пространстве есть название: spatial database (пространственные базы данных). В физических движках поиск пересечений почти всегда включают в механизм расчёта физической реакции на эти пересечения. Именно это меня всегда удивляло. Всегда казалось, что это разные области ответственности и что из-за этого, во-первых, приходится тащить за собой данные о физических свойствах объектов когда тебе не нужны связанные с ними расчёты, а во-вторых отпадает возможность для разработчиков физических движков использовать готовые библиотеки для работы с пространственными базами данных, а на себя брать задачу создания более качественной реализации физической симуляции (ну, или наоборот — создавать более качественные пространственные базы данных и присоединять к ним механизмы физический симуляции).
mihalicyn
22.08.2015 07:33Попробуйте посмотреть в сторону потенциала Леннарда-Джонса (насколько я догадываюсь, Вы «вручную» собираетесь контролировать сближение объектов?).
oPOCCOMAXAo
22.08.2015 23:45Буду искать объекты, которые пересекаются и объединять их в центре масс (неупругое столкновение) или раздвигать их и давать скорость по закону сохранения импульса (упругое).
PapaBubaDiop
21.08.2015 13:28+4Отсутствие dt в коде реализации численной схемы — большая ошибка, особенно для программы, претендующей на учебник для новичков. И лучше его задать честной константой dt=0.025, как Вы указали вначале статьи.
Рано или поздно, он понадобится.
GlukKazan
21.08.2015 13:40Забавно как-то гравитация работает (столкновений, как я понимаю в этой версии нет). Если в демке натыкать мышкой несколько точек рядом, они медленно притягиваются друг другу по спирали, а затем запуливают друг друга в разные стороны с какой-то невменяемой скоростью.
GlukKazan
21.08.2015 13:49Под Хромом не работает
oPOCCOMAXAo
21.08.2015 13:58Немного правил константы, и Вы попали в момент, когда движение было слишком медленным. Сейчас всё работает
GlukKazan
21.08.2015 14:23+1Да, так лучше, но гравитация продолжает выглядеть странной.
oPOCCOMAXAo
21.08.2015 14:36+4Издержки пошагового вычисления: в определённый момент расстояние между объектами становится очень маленьким и сила стремится к бесконечности, поэтому они ускоряются до невероятной скорости. На следующий такт эти объекты слишком удаляются друг от друга и не могут затормозить из-за большого расстояния
Эта строка частично решает данную проблему:
if(r < 0.1) r = 0.1; // избегаем деления на очень маленькое число
Можно также ввести искусственное ограничение скорости или уменьшить интервал.GlukKazan
21.08.2015 14:52Спасибо. Весьма исчерпывающее объяснение. Будет интересно посмотреть реализацию вашего движка с обработкой коллизий, но присоединюсь к KvanTTT. Для практических целей, лучше использовать какой нибудь из уже существующих движков. Тот же Box2D, например.
VioletGiraffe
22.08.2015 20:53Я тоже делал N-body simulation, долго возился с величиной r, пока не понял, что это жуткий костыль. Как сделать правильную физическую симуляцию макрообъектов? Задать им размер? Принудительно заставить соблюдаться закон сохранения импульса?
oPOCCOMAXAo
22.08.2015 23:49Я бы задал размер и после столкновения пересчитал скорости по закону сохранения импульса. В своём конечном варианте я задал плотность константой и высчитывал радиус исходя из массы.
WinPooh73
21.08.2015 14:10При большом количестве частиц количество вычислений методом «в лоб» будет расти квадратично, что не очень хорошо. Ведь на движение каждой частицы наибольшее влияние оказывают её ближайшие соседи. Если не нужна сверхвысокая точность (а задача многих тел точно не решается даже численно), можно ограничиться только ими.
Попробуйте реализовать модель с меньшей алгоритмической сложностью. В качестве отправной точки рекомендую, например, event driven collision model. Она в общих чертах рассмотрена в книге «Алгоритмы» Седжвика и его же курсе «Algorithms I» на Курсере.
saluev
22.08.2015 16:25И вот на горизонте замаячил fast multipole method, про который, между прочим, было бы *действительно* интересно почитать.
mihalicyn
21.08.2015 16:38+4Забудем на время то, что в (1) сила — скаляр, а в (2) сила — вектор. И во 2 случае будем считать силу и ускорение скалярами.
Что-что? Может стоит лучше сказать, что в (1) речь идет о проекции силы на конкретное направление (на направление вдоль линии, соединяющей центры тел)? Это очень и очень существенное обстоятельство, если эта статья призвана кого-то и чему-то научить. :)
И да: посмотрите в сторону метода Рунге-Кутты.
Shchvova
21.08.2015 18:14+1У вас в движке большая проблема с просчетом близких орбит. Не работает банальный закон сохранения энергии — если два тела почти стоят, то в демке, да и с такой дискретной математикой, у них будут очень большие ускорения на близких расстояниях. Как результат — если просто поставить два тела, то они медленно будут сближаться, а потом разлетятся на сильно большей скорости чем им дала энергия падения.
Общим, я даже не знаю где эту модель можно применить. Нужно существенно доработать.
kahi4
Какой этот алгоритм? 2 закон Ньютона? Или редуцированный вариант численного метода интегрирования Эйлера? Так то их можно использовать практически везде, разве что пока у вас скорости не близкие к световым. Ну и разумеется если нужна большая точность, то Эйлера лучше заменить на что-то типа Дорвана-Принса.
Что касается статьи — зря вы выбрали dt = 1. Первая причина — ваша одна секунда равняется 0.02 с реальных, а, как следствие — все коэффициенты придется пересчитывать. Вторая — если будет просяд fps — все поедет. Нужно рассчитывать dt динамически.
Ну и setTimeout — используйте window.requestAnimationFrame.
А так статья интересная, но (только не в обиду) для гуманитариев. Второй закон Ньютона и интегрирование Эйлером — прям совсем база.
deniskreshikhin
>> Вторая — если будет просяд fps — все поедет. Нужно рассчитывать dt динамически.
А разве не наоборот, если dt будет динамическим, то будет трудно предсказывать столкновения?
Мне казалось что dt выбирают исходя из минимального размера объектов и максимальных скоростей.
poxu
dt должен быть фиксированным. Если между двумя кадрами прошло время dt*2 то надо просчитать физику на 2 шага.
juray
и привет, «телепорты» и проскакивания насквозь.
А собственно, кому должен? Всё зависит от постановки задачи.
В еве онлайн вот не побрезговали замедлением времени при увеличении количества участников.
kahi4
Да что вы утрируете то?
В js (да везде в общем то) dt должен быть динамичным, покуда requestAnimationFrame не стабильный (я уж молчу про setInterval) — то будет все заторможенно, то наоборот. Но если «промах» по времени был слишком большой (больше некого epsilon) — ставим dt равным этому порогу. Да, будет тормоз, но решит кучу других проблем.
poxu
Не совсем так. dt должен быть фиксированным. Если между двумя вызовами requestAnimationFrame прошло времени n*dt, то нужно обсчитать физику в n шагов.
poxu
Телепорты и проскальзывания насквозь получаются как раз из-за динамического dt. Если 2 объекта движутся навстречу друг другу, а dt сильно большой, то они пролетят сквозь друг друга. Но если большой dt разделить на интервалы поменьше, то коллизия будет зарегистрирована. Кроме того динамический dt не позволяет добиться одинакового поведения при одинаковых исходных условиях, что сильно затрудняет тестирование.
juray
Так и я про это же.
Но я не согласен, что из-за динамического. Если интервал большой, то статичность не поможет.
Так эти интервалы опять же и будут dt для физического движка.
И я это тоже имел в виду — считать надо эти субинтервалы, а не «между двумя кадрами».
oPOCCOMAXAo
Спасибо за совет, следующих статьях буду использовать именно этот метод
leshabirukov
В результате получим невоспроизводимость -> боль при отладке.
Ещё вспоминается Dune II, где можно было влиять на успех боя переключая скорость игры.
kahi4
Мне с постоянным dt сразу вспоминается GTA II, который без патча на современной системе работает с fps ~500 и одно нажатие клавиши отправляет вас в дорогу со скоростью звука.
masai
Кстати, управлять величиной FPS можно не только с помощью изменения dt. Если расчёт закончился раньше времени (для большого dt), то можно просто дать процессору отдохнуть.
masai
Если физический движок предназначен для какой-то игры, то нужна не точность, а быстродействие. Так что лучше вместо Дормана — Принса взять метод Верле, который позволяет получать координаты прямо из ускорений без вычисления скоростей.