Physical Engine

Physics engine: Part 1

Gravity

The basis of any physics engine is to deal with gravity.
Without going into detail, let's remember that gravity is a constant force applied to an object, and therefore an acceleration!
Acceleration affects speed in the same way that speed affects the position of an object.
Gravity on Earth (Gt) has a value of 9.8 m / s 2. This means that if you drop an object (and put aside any consideration of friction, its speed after one second will be 9.8m / s.

Gt = 9.8 m / s 2
v = Gt * t m / s

On the other hand, the gravity is expressed in meters whereas for us, everything will rather count the pixels!
Assuming that a meter = 100 pixels we are going to set our value of Gms at 980 pix / s 2 (we could almost round up to 1000 which would not be without interest! 🤔)

At each frame, you will update the speed and the position of the object according to the acceleration and especially the time that has elapsed!

local Gt = (980 / 1000*1000)                                    -- We divide by 1000 because we are going to deal with miliseconds
local oPerso = {
ax, ay = 0, 0, -- Acceleration
vx, vy = 0, 0, -- Speed
px, py = 0, 0 -- The position
}

function loop60fps()
local currentTime = system.time()
local dT = currentTime - previousTime
previousTime = currentTime
oPerso.vx = oPerso.vx + oPerso.ax * dT -- the speed in X
oPerso.vy = oPerso.vy + (oPerso.ay - Gt) * dT -- the speed in y
oPerso.px = oPerso.px + oPerso.vx * dT -- the position in x
oPerso.py = oPerso.py + oPerso.vy * dT -- y-position
end

And here is our position (px, py) now contains the coordinates of a free-falling object!
We did not do much, but we have already done the essential, because without gravity no movement of the character a time is unrealistic can not be considered!

Colliders

What we want now is to make sure that the character does not cross the ground (to begin with) and more generally no object.
The first idea that comes to mind is to place points around our character (let's call these points Colliders) and make sure that these points cannot enter the scenery.

Definition

A Collider is a vector whose origin is a point of the object at an instant t1 and the destination is the same point at an instantt2 = t1 + td
Note: In this post, Colliders will always be displayed in Yellow, and the collision point (if it exists) in red.

Use of colliders

In the example below the character is finishing a jump. I placed a Collider at his feet.
At frame f, all is well, he's out of the set.
At frame f + 1, before the collisions are calculated, the Collider is in the background.

The Collider collides with the ground and the point of intersection (in red) will be where we need to place the Collider and with it the character to ensure that it does not enter the ground.

Collider

Where to place the colliders and how many?

With only one point at the level of the feet, the detection with the ground is well done, but Hillgreen can get too close to the walls!
Indeed, the character will be able to move forward as long as the Collider does not touch the wall!

1 Collider

With 2 points at the feet, Hillgreen will no longer be able to get too close to the walls, the collider on the right making it possible to avoid this.
The collision with the ground will always be as effective.
But the character could get stuck in the air as shown in the second picture.

2 Colliders

Let's try with 3 points like in the following picture. It is not better!

3 Colliders

Good. You may have already understood, Colliders is good, but it will not be enough!
You can put 100, it will not solve your problem. You will always find a way to put your character in a position that you would like to avoid.

We need something else!
But before we talk about it, let's finish with the drawbacks of Colliders!

Limits of Colliders.

The collider is too strong!

The Collider blocks the character as soon as there is a colission. Therefore if your character is on the edge of a slope, applying a horizontal translation to your character will block it from the start of the climb.
In this case, you will have to decompose your vector (movement) into two distinct vectors.

  • The first oblique defining the maximum slope that your character can climb (45% for example)
  • The second directed downwards to find the point of collision with the slope.

Collider - slope

By doing this your character will run at the same speed on the flat as he does uphill.
Nothing prevents you from proceeding otherwise and decomposing the original vector into 2 different vectors.

Floating numbers are not infinite

A floating point number does not have infinite precision.
13.6 may well be 13.59999999 or 13.60000001 even though all the calculations you made are correct.
From then on, a problem will arise fairly quickly.
When you calculate the point of intersection of a Collider with the scenery, you expect (and you are right) to get a point that is on the edge of the collision polygon. It's logic.
Except that because of this imprecision of the floating point calculation, your point can be on the segment, very slightly outside the collision polygon, or else, and this is the worst case, very slightly inside 😬 .

In the latter case it is a disaster because, in the next frame, your Collider is inside the collision polygon, gravity will still push your character downwards. The character will therefore simply cross the ground as if nothing had happened when everything you did is correct.

So in the case of a Collider used for ground detection, you need to raise your character by an epsilon value.
This value should be:

  • Small enough not to be visible
  • Large enough to be beyond the precision threshold of floating point calculations

Epsilon = 0.0001 will do just fine!

Note: Another more efficient method but that I do not detail here would be to modify the value of t calculated in the segment / polygon intersection function so as not to return the exact point of intersection, but a point lying very slightly before .

And There you go. That's it for Colliders.
With a single point of collision, you can already handle collisions with the ground almost perfectly!

The first video posted here only had one Collider. Proof that it works!

The Repellers

With Colliders, we can already do cool things, but as we have seen, this is not enough.
We need something else to prevent a character from getting stuck in the wall.
This other thing is a Repulsor (all these terms are invented by me, no need to search the Internet for some additional information, you may not find anything 😕) whose goal is not to block your character in its progression, but to push it out of the scenery if by chance it enters!

Definition

A Repeller is a vector independent of movement and fixed with respect to the object to which it is linked.
Note: In this post, the Repellers will always be displayed in Blue, and the point of repulsion (if it exists) in red.

Use of repellents

In Hillgreen I currently have 7 repellents, but now we don't need that many!
I will immediately show you a light version with 2 colliders and 2 repulsors and you will immediately understand how it works.

Repeller

In the example above, the Colliders prevent the character from entering the ground, but they are close enough to each other to partially allow the character to enter the wall.
Except that the two Repulsors which start from the center of the character on the right and on the left will push the character out of the setting.
Thus, it is guaranteed that the character will not be displayed in the wall.

I think you get the idea, but I dig deeper a bit with the example below:

  • In the first picture, Hillgreen is on the hill. it does not fall because one of the Colliders collides with the ground. This is the desired effect.
  • In the second picture, Hillgreen has moved a little forward! the Colliders have found themselves in a vacuum, so he is falling. We see that one of the Repellers begins to collide with the wall. He will therefore push Hillgreen to the left.
  • The character can continue to run downwards. he is no longer in the wall.

Repeller - Explanation

It's simple, isn't it?
All the thinking will therefore be in the number and especially the placement of Colliders and Repellers, but know that there is no need to put heaps to have a satisfactory result.

Limits of the Repellers.

Repellers are less sensitive to problems with the precision of floating point numbers.
Moreover, if you one day come across one of these cases (which will be extremely rare) the error will not have the same impact as for colliders.

In the extreme you might wonder why use Colliders when you start to see that Repellers only have advantages!
And you almost wouldn't be wrong, except that the Repellers have 2 small flaws. I say "small" because you could quite decide to put up with these faults!

Independent of movement.

Repellers are independent of movement.
That is, if your object is moving extremely fast, it will be able to pass through objects!
Let's go back to the very first example used to explain how Colliders work.
I replace the Collider with a Repulsor (in blue).

Repeller

We realize that the repulsor has passed entirely inside the collision polygon. Once inside, it's over, it will no longer be possible to notice that there is a collision.
This only happens if your object is moving very fast, and you can reduce the problem by maximizing the length of the Repeller.

Repeller 2

This time (and in this very precise case), there is a collision because the Repeller is long enough.
This last example leads to the second repulsor problem.

The point of collision of the Repellers.

Colliders and Repellers do not return the same collision point to you.
In the example above, using a Collider, the character's feet would be brought back to the level of the left red dot, while in the case of the Repulsor, the character's feet would be brought back to the right red dot!

So we are not going to discuss which is the best point, and which is the good point of collision. You will make up your own mind. Both have advantages:

  • The Collider is more precise
  • The Repulsor will keep your character's speed constant whether they are running or jumping.

But know that you can do without Colliders!
The only risk you will take then is that your character will move too much and manage to pass through an object. You will therefore have to limit its speed so that this does not happen!

Calculation of collisions

Whether it is Colliders or Repellers, you will use the same Segment / Polygon intersection calculation function.
What will change is what you do with the returned result.

Let be a vector of origin Pv0 (x0, x0) and of destination Pv1 (x1, y1) which collides with a polygon.

  • In the case of a Collider, you will place the character at the level of the collision point.
  • In the case of a Repulsor, you will push back the character so that the point Pv1 (x1, y1) is the point of collision.

It's simple after all!

Which polygons to test?

A level of the game is made up of thousands of tiles.
Whatever the performance of your segment / polygon intersection calculation routine, it will not be possible to test all the polygons of the level.
It is therefore necessary to reduce as much as possible the number of polygons that will have to be tested.
The method is quite simple, it is "enough" to know which are the tiles which will be crossed by our vector.

Collision Tiles

In the example above, our Collider crosses the tiles that I have highlighted in blue.
So just test the collisions with these 3 tiles! You still have to find them 😬!

The algorithm to find them is not super complex, but it is significantly slow!
Above all, it is significantly slower than the collision calculation function itself.

So I put on my budding statistician hat to see what case we end up in and how many times these cases occur.
A short walk in my test level gave me the following results:

  • In 87% of cases, the source and the destination of the vector are in the same tile
  • In 21% of cases, the vector is in two tiles (either horizontally aligned or vertically aligned)
  • In 2% of cases, we find ourselves in the case of the image above, that is to say that there to 3 boxes to test.
  • Note: these results are those of Colliders, Repulsors, longer, return different results! *

Even if this has never happened, you still have to plan for the general case where there could be more than 3 tiles.

So, since the tile detection algorithm based on the right-hand plot agorithm of Bresenham is definitely too slow in Lua, we're not going to use it.

The easiest way is to handle special cases for the 98% of cases that occur most often.
Then for the remaining 2%, test all the tiles of the rectangle which contains the vector (on the image above, this corresponds to the blue tile and the yellow tile).

The tile selection algorithm is therefore as follows.
It works either way, but again, you can save some time dealing with the special cases!

function testTiles(px0, py0, px1, py1)                  -- tile search function
local floor = math.floor
local tileX0 = floor(px0 * 0.0125) -- we find the coordinates in the table of tiles
local tileY0 = floor(py0 * 0.0125) -- the tiles are 80x80 (at home)
local tileX1 = floor(px1 * 0.0125) -- here we multiply by 0.0125 to avoid a division by 80
local tileY1 = floor(py1 * 0.0125) -- Unfortunately, we cannot do without the expensive math.floor

-- if you want to deal with special cases, this is where it happens!

if tileX0 > tileX1 then -- we find the smallest coordinate in X
tileX0, tileX1 = tileX1, tileX0
end
if tileY0 > tileY1 then -- same for Y
tileY0, tileY1 = tileY1, tileY0
end

local tX, tY
local oBestCollision = {t = 2, shape = nil}

for tY = tileY0, tileY1 do -- we browse the rectangle of selected tiles
for tX = tileX0, tileX1 do
local workTile = tY * levelWidth + tX -- workTile is the index of the tile
local workTileID = tTile[workTile] -- workTileID the number of the tile
local shape = tTileShape[workTileID] -- does there exist a polygon on this tile
if shape then
local sx = tX * 80 -- we will have to replace the polygon in the vector coordinate system
local sy = tY * 80 -- we could as well place the vector in the coordinate system of the polygon
-- we are looking to see if there is a collision
local oCollison = linePolygonIntersection(x0, y0, x1, y1, shape, sx, sy)
-- t indicates the moment of the collision
if oCollison and oCollison.t < oBestCollision.t then
oBestCollision = oCollison -- the smallest t is the first collision
end
end
end
end

return oBestCollision -- we return the best collision
end

This algorithm is not complete. You will have noticed that I am using variables (like the table of tiles: tTile or tTileShape which contains the collision polygons) which come from nowhere.
The idea was above all to give you the broad outlines ...

The results

Good !
The big question is how long does this little collision method take?
Is this little whim of redoing a one-way collision module or if I would have done better to keep Box2D!

On the Samsung Galaxy J3, character collisions with the scenery take 1.4% of the available time (maximum average calculated over 25 frames)

It's fast as long as I only have the character to deal with, but not enough to let enemies go about their lives on their own!
In the original idea (and to simplify my life) I had in the idea to put the enemies in the level and let them fend for themselves, autonomously managing their collisions with the scenery and their reactions.
Okay, well that probably won't be possible (I'm not sure Box2D would have done better in real life). I'll have to think about another idea!

Suddenly, 1.4% (times 2 when playing for two) is quite acceptable. If I manage to contain the management of the two characters in 5% of available CPU time (yes there is still a lot of stuff missing, like collisions with moving objects) I will be very happy!

Conclusion

A cool thing to do when creating a physics engine is to provide a time parameter that will allow you to slow down the game, to make it run at idle speed (while remaining fluid of course).
This has two advantages:

  • If you manage to manage this parameter, it means that your engine is well done! We quickly go and modify a hard speed, here and there. With such a parameter it will not be possible or the slow motion rendering will not be as expected.
  • The sequence of animations is a rather complicated task. Making sure the transitions are going well (say the best you can) is not very easy. By playing at a slower speed, you immediately notice the small alignment problems! What is acceptable, and what needs to be improved!

Well, here.
You have everything you need to get started with your "primitive" physics engine (it will never do what Box2D is capable of) if you so desire.


Commentaires


Hillgreen Dream Team

Etienne: Développeur
Manu: Graphiste et développeur
Luis: 3D Graphes et animations
Reynald: Musiques et sons