Box2D C++ tutorials - Ghost vertices

Last edited: July 14 2013

Chinese version -> 中文

(Note: This topic doesn't really fit in too well with the rest of the tutorial topics because they are based on Box2D v2.1.2 which does not have edge shapes. I kinda forgot about that when I started making it. This subject will only be useful if you are using Box2D v2.2 onwards.)

Ghost vertices


In the 'jumpability' topic I said that the winner of the title for most commonly asked questions asked by new Box2D users is "how can I tell if my player character is on the ground?". But I may have been wrong... we have another very strong contender for this title.

Perhaps at least as common is the question "why does my character get stuck when moving along flat ground?". This usually occurs as a result of the ground being made up of a series of fixtures (either polygon or edge shapes) placed next to each other to make up a flat surface, and a character body with a rectangular fixture trying to move along it.

The cause of this arrangement is in turn usually a side-effect of having level layouts defined as tiles in a fixed grid, which makes life easy in many ways but is somewhat sub-optimal when trying to represent a surface that should genuinely be one smooth piece (a dedicated Box2D editor would help a lot with this </shameless plug>).

Let's take a look at the classic case where this problem occurs and find out why, and then look at two ways to get around the problem. One way is to change the layout of the shapes involved, which is more of a hatchet job than a silver bullet but it is often good enough for many cases. The other way is to make use of 'ghost vertices' which will be the main focus of this topic.


Why does the character get stuck?


Here is the typical scenario where this problem shows up. The dynamic box is some kind of player or enemy moving towards the right. Just as it reaches the boundary between the two boxes in the ground below, it seems to get stuck on the corner of the box on the right. Box2D ghost vertex From the anatomy of a collision topic, we know that Box2D responds to collisions between two fixtures by calculating how much they overlap, and finding the quickest way to push them apart. For this discussion, the key thing to note about this procedure is that little word 'two'. Collisions are not resolved in threes, neither are they resolved in fours. Of course, five is right out.

So there are actually two individual collisions going on which will be resolved separately: Box2D ghost vertex In each of these the quickest way to push the overlapping fixtures apart is calculated. In the case on the left the solution is almost certainly to push the 'player' up and the ground down: Box2D ghost vertex But the case on the right is not so cut and dried because this is a corner vs corner collision which are the most complicated. Recall again from the anatomy of a collision topic, that a small change in the position of the fixtures could cause a big difference in the resulting impulse that was calculated to separate them. As the 'player' body moves along the ground, it's actually moving up and down a tiny bit as the collision response works to keep it on top of the ground fixture. Here is an exaggerated image of this situation: Box2D ghost vertex So at the moment the player collides with the new ground box, one of two things could happen. Zooming right in close to the corner we could see two possibilities... Box2D ghost vertex ... if the player was already further across the new box horizontally than it was submerged into it vertically, we would get the outcome on the left. But if the player was overlapping more vertically than horizontally, we would get the outcome on the right, and this is how the player can momentarily get stuck on the ground that appears flat.


Fixing the problem - clipping polygon corners


As we can see above, having two corners at right angles to each other can result in a collision-correcting impulse which pushes the player back horizontally, which is the absolute worst direction. To improve on this we could clip off the corners of the player polygon, or the ground polygons, or both, to get a slightly better collision-correcting impulse direction. For example, an outcome like this would be much better: Box2D ghost vertex For many cases, just making the player like this could be good enough. It's certainly an easy fix to try.

Of course, if you are able to make your player fixture into a circle, that's even better.


Fixing the problem - edge shapes


(Note: Box2D v2.1.2 does not have edge shapes)
Using edge shapes will give a huge improvement over polygon shapes. An edge shape is simply a line between two points, and these can be placed side by side to act as a ground in the same way as the boxes above. Theoretically, the same collision-correcting impulse problem applies with edges as it does for polygons, but in practise, for some reason it occurs much less frequently. I really don't know why this is, so if you do, please let us know :)

One nice thing about replacing polygons with edges is that you no longer need to worry about keeping them convex and within 8 vertices (for Box2D defaults) as you do with polygons. And when you have an area of ground which should be perfectly flat, it's trivial to replace the many edges with a single edge.


Really fixing the problem - ghost vertices


(Note: Box2D v2.1.2 does not have edge shapes)
Box2D v2.2 introduced the concept of 'ghost vertices' for edge shapes. Each edge shape obviously has two main vertices used to define its position and detect when the edge has collided with something. These main vertices can each have a ghost vertex on the 'outside', as in this diagram: Box2D ghost vertex The ghost vertices get their name because they don't play a part in collision detection - other bodies can happily pass through the lines from v0-v1 and v2-v3 without colliding with the edge. So... what's the point of these ghost edges then? The point is that they play a part in collision response.

For example when a collision is detected at the v2 end of the main segment, both the v1-v2 and v2-v3 lines will be used to calculate the collision-response impulse. Remember how the whole getting stuck problem was caused by not being able to resolve collisions with more than one other fixture at a time? Well essentially, this is exactly what the ghost vertex system does for us. The result is that the collision response will act as if there was no discontinuous point at v2.

Using these ghost vertices is most commonly done by way of the b2ChainShape which sets up a string of edge shapes and takes care of all the ghost vertices automatically, placing the ghost vertices of each edge to match the main vertices of the edge on each side of it. If you need to set up a single edge with ghost vertices, you could do it like this:
1
2
3
4
5
6
  b2EdgeShape edgeShape;
  edgeShape.Set( v1, v2 );
  edgeShape.m_vertex0.Set( v0 );
  edgeShape.m_vertex3.Set( v3 );
  edgeShape.m_hasVertex0 = true;
  edgeShape.m_hasVertex3 = true;
...where the vertex numbers are as in the diagram above. Note that the main edge is v1-v2 since it's in middle, and the ghosts being on the outside are v0 and v3.


Other things to remember


One thing to be careful of when making use of ghost vertices to get smooth collisions between edges, is making the edges too small in comparison to the 'player' or whatever will be colliding with them. For example if a collision occurs at the v2 end of the edge and the edges are so small that both v2 and v3 are completely inside the player fixture, the ghost system can fail. Here is a good example of a ground made up from edges that were too small and needed to be made larger (the red dots are the vertices making up the ground surface). Box2D ghost vertex

Sourcecode


Since this topic needs a more recent version of Box2D than the rest of the tutorial topics, I'll keep the source code here separately. This is a 'test' for the testbed. iforce2d_ghost_vertices.h

Finally, here is a video showing a comparison between polygons (bottom), edges without ghost vertices (middle), and edges with ghost vertices (top). Even with polygons, I found this 'sticking in the ground' to be very rare, in fact far too rare to make a video with! So in this example the ground has been made dynamic which slows down the rate of collision resolution, the player is made of a light lower body and a heavy upper body (50 times more dense!) and then strong forces are applied downwards on the upper body.


Even then the sticking was still rare, so I also added a downwards impulse just as the player got close to one of the 'sticky' points. Given that it took all this effort to get the player to stick on the non-ghost-vertex edges, they are probably just fine for most uses. But if you want a guaranteed solution you might want to try the ghost-vertex method - even with all this evil meddling, the player never got stuck once.