A big source of gameplay bugs for us was the physics system. The problem was that placing tiles around with each of them having a separate physics body causes undefined Box2D behaviour: It does not know how to resolve a collision when the player bumps exactly into a physics shapes corner. We did some research into this issue and there were mainly three ways to solve it (http://www.box2d.org/forum/viewtopic.php?f=3&t=8409):
Put a circle collider on the player. This resolves the issue, but the player also slides off edges of platforms, which makes the gameplay suffer, so it’s not an option.
Use ghost vertices and edge chains. Ghost vertices are a way of giving extra information to the collision solver, and are meant so solve this exact problem. However, PhysicsEditor does not support edge shapes (which are required for this to work), and all of our setup was already done with rectangles – collision logic relied on it.
Try to merge the tile physics shapes as much as we can so that there’s no intersecting physics shapes in the form of tiles.
We went with the third option. Firstly, I developed an algorithm that partitions all of the tiles into a grid, then sweeps through the grid horizontally and merges everything it can. The code for it is nasty and in need of improvement, especially to deal with cases when CGCObjGround is not actually used for tile-able objects. Given more time, I would create a new class and call it CGCObjNonTiledGround, then use that for the special types of platforms. Anyway, the algorithm that accomplishes this is in the VOnGroupResourceAcquire_PostObject() (It’s too long to post it here).
It’s long and difficult to understand, partially due to the fact that everything in OGMO gets placed at the centre point, meaning that the grid is 2 times denser than the screen size divided by a single screen tile. This meant that for contiguous rows of tiles, we’d need to skip every second array cell, since it wouldn’t contain anything. But we needed to have it so that a platform that’s 1.5 tiles higher than others is also taken into the calculation, for example.
This first sweep was all there is to it at the beginning. It solved getting stuck while walking on the ground.
However, during the beta sprint, we found that the player started getting stuck on walls instead. And there’s no reason they wouldn’t – I only solved the horizontal case. The most time-efficient method of dealing with this (that I could think of) was to perform a second sweep, this time vertically, and join up more shapes. I created a struct to hold data for the second sweep:
And stored it in the first sweep. I then performed the vertical sweep and did more of the same merging, but only if the physics shapes from the first sweep were the same size and type. This constraint meant that I could only fix most of the problems, but not all of them.
Information such as whether the ground tile can be passed by the player or not, was contained within its physics shape. This meant that I would lose data if I merged the physics shapes, so that’s the first case when the algorithm was not good enough. The second case was the size. Since I was only using rectangle shapes, I could only merge to form new rectangles at the current form of the algorithm. This got rid of most of the bugs, but some persisted due to that limitation.
Talking about performance – to save physics calculation effort, I made the original physics shapes of ground tiles arbitrarily small and disabled them after the optimised shapes get created. I made sure to destroy the intermediate shapes from the first sweep as well. The final shapes are kept track of and destroyed by the object group when it gets destroyed:
Here is a screenshot of how an optimised level looks:
If I did it again
If I were to do this again, I would use a different algorithm. I think I could have only realised this based on the experience I had. I would re-write the way we do passing through platforms logic so that it does not depend on physics shape bitmask flags, but rather on the height of what the player is trying to pass through. This gets rid of one limitation. I would then use an edge tracing algorithm (which I thought about using to begin with) to create polygon shapes for the whole area of ground. That gets rid of the rectangular shape constraint. I had this idea to begin with, but I made the choice to implement the horizontal joining algorithm, as it was simpler and I did not anticipate the vertical intersections of tile physics shapes to cause a problem. Now that I know the problem would still occur, I would go with the edge-tracing algorithm to detect the whole island of ground and merge it to a single object.
Godsend Programming #11: Physics Optimisation
A big source of gameplay bugs for us was the physics system. The problem was that placing tiles around with each of them having a separate physics body causes undefined Box2D behaviour: It does not know how to resolve a collision when the player bumps exactly into a physics shapes corner. We did some research into this issue and there were mainly three ways to solve it (http://www.box2d.org/forum/viewtopic.php?f=3&t=8409):
We went with the third option. Firstly, I developed an algorithm that partitions all of the tiles into a grid, then sweeps through the grid horizontally and merges everything it can. The code for it is nasty and in need of improvement, especially to deal with cases when CGCObjGround is not actually used for tile-able objects. Given more time, I would create a new class and call it CGCObjNonTiledGround, then use that for the special types of platforms. Anyway, the algorithm that accomplishes this is in the VOnGroupResourceAcquire_PostObject() (It’s too long to post it here).
It’s long and difficult to understand, partially due to the fact that everything in OGMO gets placed at the centre point, meaning that the grid is 2 times denser than the screen size divided by a single screen tile. This meant that for contiguous rows of tiles, we’d need to skip every second array cell, since it wouldn’t contain anything. But we needed to have it so that a platform that’s 1.5 tiles higher than others is also taken into the calculation, for example.
This first sweep was all there is to it at the beginning. It solved getting stuck while walking on the ground.
However, during the beta sprint, we found that the player started getting stuck on walls instead. And there’s no reason they wouldn’t – I only solved the horizontal case. The most time-efficient method of dealing with this (that I could think of) was to perform a second sweep, this time vertically, and join up more shapes. I created a struct to hold data for the second sweep:
And stored it in the first sweep. I then performed the vertical sweep and did more of the same merging, but only if the physics shapes from the first sweep were the same size and type. This constraint meant that I could only fix most of the problems, but not all of them.
Information such as whether the ground tile can be passed by the player or not, was contained within its physics shape. This meant that I would lose data if I merged the physics shapes, so that’s the first case when the algorithm was not good enough. The second case was the size. Since I was only using rectangle shapes, I could only merge to form new rectangles at the current form of the algorithm. This got rid of most of the bugs, but some persisted due to that limitation.
Talking about performance – to save physics calculation effort, I made the original physics shapes of ground tiles arbitrarily small and disabled them after the optimised shapes get created. I made sure to destroy the intermediate shapes from the first sweep as well. The final shapes are kept track of and destroyed by the object group when it gets destroyed:
Here is a screenshot of how an optimised level looks:
If I did it again
If I were to do this again, I would use a different algorithm. I think I could have only realised this based on the experience I had. I would re-write the way we do passing through platforms logic so that it does not depend on physics shape bitmask flags, but rather on the height of what the player is trying to pass through. This gets rid of one limitation. I would then use an edge tracing algorithm (which I thought about using to begin with) to create polygon shapes for the whole area of ground. That gets rid of the rectangular shape constraint. I had this idea to begin with, but I made the choice to implement the horizontal joining algorithm, as it was simpler and I did not anticipate the vertical intersections of tile physics shapes to cause a problem. Now that I know the problem would still occur, I would go with the edge-tracing algorithm to detect the whole island of ground and merge it to a single object.
Related files
GCObjGroupGround.h – https://drive.google.com/open?id=0B_BnvnFZLH7mc0Q5Sm5FSG9uam8
GCObjGroupGround.cpp – https://drive.google.com/open?id=0B_BnvnFZLH7maG5od2FTWlpSb1U