Реализация точечной коллизии в 2D

Сегодня я хотел бы рассказать о своей реализации точечного определения границ игровых объектов в 2D и просчёта их пересечений на примере того как я это сделал в игре AsteroidsOnline.

Этот способ так же можно применит для любой другой 2D игры.

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

В моём случае почти все объекты не круглые: края астероидов, кораблей да тем более оружие лазер - это ваще отрезок.

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

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

Открыл фотожлоб, взял спрайт корабля и отметил на нём точки, заранее разделив группы по отсекам корабля, вот наглядность того что получилось:

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

Delphi Code

type
  TPointDetermination = record
    gl_dx : single; // дельта x, которые надо +- к позиции спрайта в OGL пространстве
    gl_dy : single; // дельта y, которые надо +- к позиции спрайта в OGL пространстве
    gl_x : single; // искомое gl_x точки, расчитанное уже с учётом поворота
    gl_y : single; // искомое y расчитанное уже с учётом поворота
  end;

  TTriangleDetermination = record
    xy1 : TPointDetermination;
    xy2 : TPointDetermination;
    xy3 : TPointDetermination;
  end;

  TArrOfTriangleDeterm = array of TTriangleDetermination;

const
  c_SPR_W = 48; // размеры спрайта корабля в пикселях
  c_SPR_H = 48;
  c_SPR_GL_W = 1; // размеры спрайта в 3d пространстве
  c_SPR_GL_H = 1;

...

procedure TShip.CalcDxDy(aSpr_x, aSpr_y: single; var a_gl_dx, a_gl_dy: single);
begin
  a_gl_dx := aSpr_x * (c_SPR_GL_W / c_SPR_W);
  a_gl_dy := aSpr_y * (c_SPR_GL_H / c_SPR_H);
end;

procedure TShip.InitDetermZones;
  procedure InitTriangle(var aTD: TTriangleDetermination; aX1, aY1, aX2, aY2, 
    aX3, aY3: single);
  begin
    with aTD.xy1 do CalcDxDy(aX1, aY1, gl_dx, gl_dy);
    with aTD.xy2 do CalcDxDy(aX2, aY2, gl_dx, gl_dy);
    with aTD.xy3 do CalcDxDy(aX3, aY3, gl_dx, gl_dy);
  end;
begin
  // носовая часть - 4 треугольника
  SetLength(fForeShip, 4);
  InitTriangle(fForeShip[0], -10, 13, -2, 24, -2, 13);
  InitTriangle(fForeShip[1], -2, 13, -2, 24, 2, 24);
  InitTriangle(fForeShip[2], -2, 13, 2, 24, 2, 13);
  InitTriangle(fForeShip[3], 2, 13, 2, 24, 10, 13);
  // корпус
  SetLength(fBody, 2);
  InitTriangle(fBody[0], -10, -14, -10, 12, 10, 12);
  InitTriangle(fBody[1], -10, -14, 10, 12, 10, -14);
  // двигатель
  SetLength(fEngine, 2);
  InitTriangle(fEngine[0], -15, -21, -15, -15, 15, -15);
  InitTriangle(fEngine[1], -15, -21, 15, -15, 15, -21);
  // левое крыло
  SetLength(fLeftWing, 9);
  InitTriangle(fLeftWing[0], -23, -16, -23, -1, -21, -16);
  InitTriangle(fLeftWing[1], -21, -16, -23, -1, -21, 2);
  InitTriangle(fLeftWing[2], -21, -16, -21, 2, -16, 2);
  InitTriangle(fLeftWing[3], -21, -18, -21, -16, -16, -18);
  InitTriangle(fLeftWing[4], -16, 2, -16, 6, -11, 6);
  InitTriangle(fLeftWing[5], -21, -16, -16, -14, -16, -18);
  InitTriangle(fLeftWing[6], -21, -16, -16, 2, -16, -14);
  InitTriangle(fLeftWing[7], -16, -14, -16, 2, -11, -14);
  InitTriangle(fLeftWing[8], -16, 2, -11, 6, -11, -14);
  // правое крыло
  SetLength(fRightWing, 9);
  InitTriangle(fRightWing[0], 23, -16, 23, -1, 21, -16);
  InitTriangle(fRightWing[1], 21, -16, 23, -1, 21, 2);
  InitTriangle(fRightWing[2], 21, -16, 21, 2, 16, 2);
  InitTriangle(fRightWing[3], 21, -18, 21, -16, 16, -18);
  InitTriangle(fRightWing[4], 16, 2, 16, 6, 11, 6);
  InitTriangle(fRightWing[5], 21, -16, 16, -14, 16, -18);
  InitTriangle(fRightWing[6], 21, -16, 16, 2, 16, -14);
  InitTriangle(fRightWing[7], 16, -14, 16, 2, 11, -14);
  InitTriangle(fRightWing[8], 16, 2, 11, 6, 11, -14);
  // точка выстрела лазера из левого крыла
  with fLaserLeft do CalcDxDy(-19, -4, gl_dx, gl_dy);
  // точка выстрела лазера из правого крыла
  with fLaserRight do CalcDxDy(19, -4, gl_dx, gl_dy);
end;

Тут само главно постараться сделать максимальный предрасчёт. В данном случае я предрасчитал для каждой вершины треугольников их dx и dy уже в 3D пространстве относительно центра спрайта, т.к. координаты спрайта в GLScene находятся именно в его центре.
Хмм, теперь мне становится понятно почему пиксели в фотожабе я отмерял от центра спрайта.)
Но эти дельты работают ток если корабль расположен носом так же как и на искомом спрайте, т.е. без учёта поворота спрайта в сцене.

Как раз этот расчёт(поворот точек) я и положил на плечи прогресса каденсера класса корабля:

Delphi Code

procedure TShip.CalcGLxy(const a_gl_dx, a_gl_dy: single; var aX, aY: single); var     ang, co, si : single; begin     ang := DegToRad(fRotation);     si := sin(ang);     co := cos(ang);     aX := a_gl_dx * co - a_gl_dy * si + fPosition[0];     aY := a_gl_dx * si + a_gl_dy * co + fPosition[1]; end; procedure TShip.CalcDetermZones; var     i : integer; begin     // носовая часть     for i := 0 to 4 - 1 do       with fForeShip[i] do     begin       with xy1 do CalcGLxy(gl_dx, gl_dy, gl_x, gl_y);       with xy2 do CalcGLxy(gl_dx, gl_dy, gl_x, gl_y);       with xy3 do CalcGLxy(gl_dx, gl_dy, gl_x, gl_y);     end;     // корпус     for i := 0 to 2 - 1 do       with fBody[i] do     begin       with xy1 do CalcGLxy(gl_dx, gl_dy, gl_x, gl_y);       with xy2 do CalcGLxy(gl_dx, gl_dy, gl_x, gl_y);       with xy3 do CalcGLxy(gl_dx, gl_dy, gl_x, gl_y);    end;     // двигатель     for i := 0 to 2 - 1 do       with fEngine[i] do     begin       with xy1 do CalcGLxy(gl_dx, gl_dy, gl_x, gl_y);       with xy2 do CalcGLxy(gl_dx, gl_dy, gl_x, gl_y);       with xy3 do CalcGLxy(gl_dx, gl_dy, gl_x, gl_y);    end;     // левое крыло     for i := 0 to 9 - 1 do       with fLeftWing[i] do     begin       with xy1 do CalcGLxy(gl_dx, gl_dy, gl_x, gl_y);       with xy2 do CalcGLxy(gl_dx, gl_dy, gl_x, gl_y);       with xy3 do CalcGLxy(gl_dx, gl_dy, gl_x, gl_y);    end;     // правое крыло     for i := 0 to 9 - 1 do       with fRightWing[i] do     begin       with xy1 do CalcGLxy(gl_dx, gl_dy, gl_x, gl_y);       with xy2 do CalcGLxy(gl_dx, gl_dy, gl_x, gl_y);       with xy3 do CalcGLxy(gl_dx, gl_dy, gl_x, gl_y);    end;     // точка выстрела лазера из левого крыла     with fLaserLeft do CalcGLxy(gl_dx, gl_dy, gl_x, gl_y);     // точка выстрела лазера из правого крыла     with fLaserRight do CalcGLxy(gl_dx, gl_dy, gl_x, gl_y);     // BBox     ... end; procedure TShip.CadencerProgress(const aDTime: Double); var   ... begin   ...   CalcDetermZones;   MakePackShip;   ... end;

Так же в CalcDetermZones() расчитывается BBox корабля. В дальнейшем столкновение по точкам проверяется лишь тогда, когда BBox'ы объектов пересекаются.

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

Далее я применил данный алгоритм для астероидов и оружия, вот что получилось:

На данном скрине видны BBox'ы объектов (жёлтые обрамления) и точечная зона астероида (красным цветом).
Корабль находится в движении, как и лазерные лучи и из-за довольно медленной интерполяции на клиенте расстояние между фактической позицией объекта и его изображением значительно. Но это я уже поправил)

Теперь можно подумать об оптимизации.
Пока что столкновения у меня проверяются ток когда BBox'ы пересекаются, а пересечения   BBox'ов проверяется между всеми объектами, конечно же тут напрашивается QuadTree, которое я пока что не сделал.
Далее, если указывать зоны при инициализации в виде всех треугольников, а это повторение одних и тех же точек несколько раз, то это накладно для памяти и для кол-ва операций каждый тик каденсера. Поэтому в этом месте можно завести массив всех точек определения с ихними предрасчётами, а в определениях треугольников хранить лишь индексы этого массива.

Ну, на этом вроде всё)