Collision checking part 2 of 2

This is part two of the collision implementation of our game Ambient Pressure. See last blog post. This blog post is about the lagging issue that was solved by putting multiple Wall blocks into bigger blocks.


It was observed that there was a drop in performance. The reason for the drop was thought to be due to the collision handling code being too expensive (taking too much time for the computer to execute). We thought this was the case because such drop of performance had not been observed before the collision was implemented and the the extensive amount of collision checks we saw was required suggested this was the case.

The lines represents collision checks between the player the wall blocks.

After consulting our tutor he suggested a method to reduce the number of computations needed with the potential of reducing lag. The method was to minimize the amount of collider shapes created in the game by replacing the individual wall blocks with fewer but bigger collider rectangles spanning over the area of multiple adjacent wall blocks.

Following our tutors suggestion an rectangle finding algorithm was created for the map creating text file.

This is how our map look inside our text file:

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,2,2,1,1,1
1,1,1,1,1,1,1,1,0,0,0,0,0,0,5,0,0,2,2,1,1,1
1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,2,1,1,1,1
1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,2,2,2,3,2,8,0
1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,2,2,2,2,2,8,0
1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1
1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1
1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,6,0,0,1,1,1
1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,0,0,1,1,1
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,5,0,0,7,1,1,1
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,1
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,1
1,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,1,1,1,1
1,1,1,1,1,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,1
1,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,1
1,4,0,0,0,0,0,0,0,5,0,0,1,1,0,0,0,9,0,0,1,1
1,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,1
1,1,1,1,1,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,1
1,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,2,2,1,1,1,1
1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,2,2,1,1,1,1
1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1
1,1,1,1,3,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

The 1's represents walls, the 0's represents open space the other shown numbers represents other specific in-game objects like pickups, enemies, the player spawning point, etc.

The following algorithm was chosen for this purpose because it was practical to implement and was thought to give us the result aimed for.

The algorithm works by reading the text file as a two-dimensional map of integers. The algorithm Goes through all positions of the map one row at a time until it finds a 1 representing a wall block.

When a wall block is found the algorithm starts to define a collider rectangle. In this stage it is currently known that the collider rectangle at least has the width and height of one wall block.

After this the algorithm tries to find the biggest formable square shape, consisting of only wall blocks, downward and right from the first found wall block by looking at all of the adjacent coordinates both below and to the right of the biggest currently found square block. When ever there is a wall block adjacent to the square one block below or one block to the right of the collider square that is not a 1 the search for bigger square sizes ends.

When the biggest square is found the algorithm goes into a new state where it tries to find the biggest rectangle rightward. It follow the same principles as last state with the difference that it is now only checks rightward and that if anything other than a 1 is found in the first step it goes over to searching for a the biggest rectangle downwards instead.

When the biggest possible rectangle is found by this algorithm the algorithm creates a collider of that size.

Implementing this algorithm gave the result aimed for:

This might not be the most efficient way to optimize tiled based collision blocks. It was just a quick solution that optimized the collision checking significantly. It may also be compatible with other two-dimensional collision checking optimizations such as these quadtrees which could increase collision performance even more.