Discussion: Ideal Collision Algorithm

[Lutalli]

Abstract

In this post I would like to share some of my thoughts about collision handling. I’ll first state the final effect that I want (the goal), then list a few different schemes (including some that I have seen and I have come up with on my own) and compare them with the requirements (e.g. point out the problems), during that and at last ask a couple of questions.

Goal

I am going to develop a pixel 2D platform game and have already many ideas. One of them is that I wish it can hold a principe of “freedom”. There are some examples that satisfy this principe:

Requirement 1. The objects in a map should be able to have continuous coordinates - One can move every object pixel by pixel (unlike the tile map). Also every object should be able to own a script so that we can customize the behavior of it and the possibility is extended in a far way.

Requirement 2. The objects can have arbitrary sizes (for now we don’t consider the shape of the hit-box).

Requirement 3. The player can have an arbitrary speed, especially a pretty large one (this is a little unusual but I want it to be possible).

The first requirement seemed to be solved: See Free/Flexible tile map?. The difficulty of solving the other two is, the collision should still work perfectly while those points are achieved.

By the way, in the whole discussion we firstly assume that the hit-box shape of the player is a rectangle.

Now we have a look at some different collision handling schemes and evaluate them.

Algorithm 1: Correction

I think this is the most classical idea to handle collisions. In each frame it uses the messages that contain the information of collisions among kinematic collision objects to make a calculation to correct the player’s position when he goes into blocks. For details see for example Resolving collisions.

There are two problems:

Problem 1.1. Sometimes the collision direction (a vector) is determined differently from what people hope (see this explain), what can cause bugs like, that the player gets stuck on the wall (Wall-clipping collision issue) and that the player falls suddenly when walking on one-directional platforms (Directional platforms help). At the moment I don’t know if we can avoid such problems when the correction method is still used.

Question 1. Is it possible to solve the bugs mentioned above if we insist on using this algorithm? If yes, how?

klaytonkowalski advised using raycast instead, what we are going to analyze below. As he also mentioned, in Asset Portal there’re some modules made from others. Currently I have looked through the codes from platypus, Defold Simple Platformer (deleted?) as well as True Tile Collisions. The first two use raycast. It looks like - I’m not sure - the third one uses tile map and limit the tiles into specific formats. After a glance I think it describes collisions mathematically instead of using collision shapes. More important is, I would like to write the code from this part on my own since collision handling is a very basic core part in a game so I must understand the theory.

Another problem is:

Problem 1.2. If the speed of the player is too large, it’s possible that it runs through the wall.

This may happen because when the player is really fast, at the frame after the frame where he started to move, he has already reached the the opposite. So no collisions between the player and the wall are detected, and that contradicts Requirement 3.

Algorithm 2: Central Raycast

It detects the collisions by drawing linear rays from the player’s center out and finding the intersections. See physics.raycast() from API reference. In the two examples above, platypus and Defold Simple Platformer, this method is used. It avoids the Problem 1.1 and Problem 1.2, but another bug may appear:

Problem 2.1. Sometimes the rays don’t intersect the obstacles.

Two reasons could cause this problem: The first is pretty small objects. Since the rays are only lines, “gaps” between them can’t be avoided. And if there’re objects that are smaller than the gap, they won’t be detected. The following figure shows the situation.

If we meet some sharp corner a similar problem will also occur:

I actually made a thin tile and a slope in platypus and got the expected result from the test:

(The correct effect should be that the player can stand on them stably.) That contradicts Requirement 2.

The second factor, again, is the possibly too large speed of the player. The distance between the rays becomes big when we look at a place far away from the player, and an obstacle may be missed by the rays even if its size is normal. This doesn’t matter when the player is not so fast, because the player can’t directly move so far, and when he approaches that obstacle the gap becomes small, then the rays are able to catch it. But if the speed is too large, the player may skip the obstacle.

(Here we can suppose the player tries to jump up vertically. It should be stopped by the bottom of the obstacle but it may skip it - in 1 frame - because of the high speed.)

Of course we can add more rays, but it doesn’t solve the problem perfectly.

---

Now I’m going to give a few approaches from my own thoughs.

Algorithm 3: Targeted Raycast

This method uses raycast too, but instead of drawing 8 rays from the center of the player, it draws rays from the player to the place where the player is going to reach at the next frame. For instance, as the figure below shows, we can use rays to connect the corresponding vertexes of the player’s shape at the current frame and the shape that we plan to reach at the next frame, find the nearest intersection point on each ray, calculate the distances of these points on their rays, and find out the shortest one (the green segment in the figure). At last we calculate a new vector by reducing the length of player’s current velocity to this distance, and move the player by that vector.

In general this method solves the “high-speed problem” because the rays are parallel, but the problem with small obstacles still can’t be avoided. Again, we can add more rays (e.g. starting with the mid-points of the four sides) to make the detection more precise, but gaps always exist (extremely speaking, we want to be able to deal with a 1px × 1px obstacle). (I think this algorithm is good enough if we don’t require so small objects, though.)

However, what if we add so many rays, that from every pixel point on the sides a ray starts? The gaps won’t exist any more actually. It’s crazy, since so many calculations must be done every frame! But when we observe how the rays look like, we will find that parallelograms are formed.

Here is the scheme that I think could be the final solution:

Algorithm 4: Parallelogram Raycast

Gaps always appear because the rays are one-dimensional. In order to continuously catch every point we need two-dimensional models. Thus I’m considering if the rays can be extended to have a width; or, if we can use parallelograms to detect intersections. If so, then we’ll be able to have a great algorithm. Like the figure below, we draw parallelograms between the current and the target place, and use them to get collision information.

(Maximally we only need to draw two parallelograms and which sides should be start from is determined by the direction of the velocity. When the player moves horizontally or vertically only one is needed.)

This method can be considered as “natural”. It looks like as if we try to move the player to the target place pixel by pixel, and after every small step the collision is tested. If we think of the pixels as very tiny, then it’s like a continuous physical process in our real world (at least from a macro perspective). It won’t meet any high-speed problem or small-obstacle problem.

But at the moment it’s only an idea and I don’t know if it’s actually good and if it’s realizable. That’s where I need your help:

Question 2. Is it possible to realize this method, which uses parallelograms to detect intersections? And concretely, how would we use it - would the result of the collision detection be a set of sides (since there’re so many intersection points) or something else?

Question 3. Is there any other problem? How difficult would the calculation be (this is relevant to the running fluency of the game)?

---

And, in the end, two general questions:

Question 4. Are there mistakes or points that I didn’t explain well in my statements? And would you like to add something?

Question 5. Do you know any other methods (especially a method that can achieve my goal)?

(Also I’m a little interested in how the engine deals with the collision detections, both kinematic and dynamic. It’s nice if someone can explain this in a summary.)

Thanks a lot!

[britzl]

First of all: Amazing summary of different algorithms for handling collisions in platformer games!

@Lutalli

Problem 1.1. Sometimes the collision direction (a vector) is determined differently from what people hope (see this explain), what can cause bugs like, that the player gets stuck on the wall (Wall-clipping collision issue) and that the player falls suddenly when walking on one-directional platforms (Directional platforms help). At the moment I don’t know if we can avoid such problems when the correction method is still used.

Question 1. Is it possible to solve the bugs mentioned above if we insist on using this algorithm? If yes, how?

We do have some problems with stitching of tilemap segments where a collision shape can get stuck or get weird collision normals for a frame or two. I will defer to @JCash to hear his opinion on possible solutions in the engine. But if you do not use tilemaps for collisions and instead block out the geometry manually you’d be able to avoid some of these problems.

@Lutalli

Question 2. Is it possible to realize this method, which uses parallelograms to detect intersections? And concretely, how would we use it - would the result of the collision detection be a set of sides (since there’re so many intersection points) or something else?

Question 3. Is there any other problem? How difficult would the calculation be (this is relevant to the running fluency of the game)?

I’m not sure if this approach is used elsewhere? Have you searched for it?

@Lutalli

Question 4. Are there mistakes or points that I didn’t explain well in my statements? And would you like to add something?

Question 5. Do you know any other methods (especially a method that can achieve my goal)?

I think it will be quite difficult to create a super generic solution that works well for any kind of level design, no matter how crazy the level design will be. I think you may have to go for a solution that is to some extent tailored to your game, taking into consideration minimum width of platforms, angle of slopes etc.

Sometimes the approach taken by classics such as Mario Brothers will suffice. Other times you may need to expand on it and look at how games such as Super Mario Brothers (slopes) or Sonic (rounded shapes) solved collisions.

Perhaps use a single sphere shape (dynamic) for the player and let the physics engine (Box2D) do the rest could work? Although you’d sacrifice a bit of control that way.

[Lutalli]

@britzl

I’m not sure if this approach is used elsewhere? Have you searched for it?

Until now I haven’t looked for the use of this method yet, I just came up with this possibility. And I don’t know concretely how to make it work. I hope it’s well realizable…

@britzl

I think it will be quite difficult to create a super generic solution that works well for any kind of level design, no matter how crazy the level design will be. I think you may have to go for a solution that is to some extent tailored to your game, taking into consideration minimum width of platforms, angle of slopes etc.

Yeah, if there is really no way to handle it perfectly - although I believe there is - I’ll consider a limitation.

@britzl

Sometimes the approach taken by classics such as Mario Brothers will suffice. Other times you may need to expand on it and look at how games such as Super Mario Brothers (slopes) or Sonic (rounded shapes) solved collisions.

Perhaps use a single sphere shape (dynamic) for the player and let the physics engine (Box2D) do the rest could work? Although you’d sacrifice a bit of control that way.

Maybe I will have a look at other algorithms later. I shall try my best to use my own script to control these things, instead of dynamic objects.

[Lutalli]

Another remark: Algorithm 3 is still in theory and I haven’t made it work in practice yet. Recently I was doing an experiment to test this method and met some (pretty weird) bugs. I don’t know if it’s the algorithm’s problem or my code’s problem…

[Lutalli]

Well, now I think the “targeted raycast” algorithm can’t actually work, although it sounds beautiful. In the following I’m going to first tell how I realized it and then explain the problems.

We look at a simple demo project here: TargetedRaycastDemo.zip (31.1 KB)

The realization is included in the move function from player.script. This function will be called in function update when the player’s velocity is nonzero.

In function init: move_speed is the speed of player’s horizontal and vertical movement while moving. The hit box is considered as a rectangle, in this demo the center of this rectangle is exactly the center of the player (equal to go.get_position()). We’re going to draw rays starting from 8 points on the hit box respectively (4 vertexes and 4 mid-points of the edges). According to the size of the hit box we can evaluate their coordinates.

Notice the +1's and -1's in the code - they are added in order to make the rays start inside the hit box. Without these patches you would see there were a 1px distance between the edges of the player and the obstacle when colliding:

The figure below shows the difference (the blue one is the hit box, the red ones are the rays).

In move function:

• min_frac stands for the shortest fraction for the segments that are determined by the collisions along the eight rays.
• collision_position is the collision position on the ray with the least fraction.
• collision_corr_startpoint_rel is the corresponding start point’s coordinate (relative to player’s position) of that ray.
• collision_normal is the normal vector of the collision from that ray.

The for loop after that finds that nearest collision.

If a collision is detected, then we move the player according to the nearest collision position and the corresponding start point. In the code, besides collision_position - collision_corr_startpoint_rel there’re also an extra + collision_normal, which is another patch for the movement’s accuracy. Without this the player would be placed into the obstacle - just 1px deep - and then no more collisions would be detected (by the corresponding ray) because the raycasts that start inside the obstacle would be ignored. And the effect would become that the player could directly cross the obstacle:

So we need to move back the player 1px in the direction of the collision, and as a tricky summary we can just add + collision_normal, since it’s a unit vector.

Note: In fact, we can mention “distance of perfect 1px” only if the distance is horizontal or vertical. Firstly, the drawn stuff must stick to the pixel grid, and so in principle their coordinates are always integers. Secondly, although their coordinates are saved as floats in the actual data structures, these values are still not continuous. So there’re always slight deviations.)

If no collisions are detected, just move the player according to ds as usual.

Until now it seems to be able to work well:

However, there still exists two serious problems:

Problem 1

If the player’s speed is pretty small, a “convulsion” will appear when the player is colliding with the obstacle (and the smaller the player’s speed is, the more obviously visible the problem is). For example, if I set move_speed to 5:

Sometimes the player goes into the obstacle for maximally 1px, and then jerks back. The problem is important for the case with the gravity, because at the beginning of the vertical acceleration caused by the gravity, player’s speed is totally small as well. And so he will keep convulsing on the ground, sometimes even fall through it.

I believe the reason is the “dissonance” between player’s movement and the raycasts (sorry for my poor English, I don’t know if that word describes it properly). When the player is pretty slow, and so the movement in one frame (ds) is pretty small, it may happen that, the player did move, but the speed is too small for the rays to spread, and min_frac stays 1. In other words, no collisions are detected. The situation can also be observed from the printed outputs of player’s position together with collision_detected (if I interpreted the outputs correctly).

Problem 2

The second problem appears when the player meets the corner:

I haven’t thought of what is actually going on there yet, but to my feeling, like Problem 1, this algorithm has such problems generally because it has to deal with precise things at the micro, pixel level, which is so troublesome …

Thusly this idea fails. Or does someone know how to rescue it from these bugs?

[Lutalli]

@britzl

We do have some problems with stitching of tilemap segments where a collision shape can get stuck or get weird collision normals for a frame or two. I will defer to @JCash to hear his opinion on possible solutions in the engine. But if you do not use tilemaps for collisions and instead block out the geometry manually you’d be able to avoid some of these problems.

So, has the solution to those weird collision normals been found?

[britzl]

@Lutalli

So, has the solution to those weird collision normals been found?

We know what the problem is but have not yet fixed it I’m afraid.