# 2D Boxes/Vertices merging

I want to optimize my colliders geometry, at the moment is composed by boxes (it's a tile based game) of the same dimensions, i want to remove the inner vertices to have, at the end, only the shell. Does anyone knows or can point me out to the right direction/algorithm? The only way I can think about it's some kind of region growing with coordinates updating in a recursive way.

• Surely your physics engine doesn't support collision testing against shapes like that? You'd more than likely want to create rectangles like this: i.imgur.com/ZjM7n8f.png In that case, you'd probably want to look at something like this: gamedev.stackexchange.com/questions/58527/… Commented May 30, 2014 at 16:26
• the collision engine support that, it's just a matter of performances for the future. Even if not necessary, for knowledge sake :)
– Mal
Commented May 30, 2014 at 16:40
• The "connected components labeling" algorithm can find everything connected together. You mark each "object" with a separate identifier (int or color), then you only keep the edges that are between two tiles from different objects. If you have only one object, or objects that don't touch, it's even simpler: keep only the edges between two tiles of different objects. Commented May 30, 2014 at 23:57

## 1 Answer

Since you're using a tile based game this may not be necessary at all. In general a tile is just an array of values. Each value can represent a different type of geometry to collide with, and in your case it looks like (judging by the picture) you only have AABBs of uniform size. If this is the case then you shouldn't have any floating point vertices at all! Collision with the grid involves truncating a floating point coordinate to see which grid cell it lays within.

This section only applies if you actually create individual AABBs from your tiles.

Since you're using a grid like this you can definitely create an algorithm to join multiple cells into a single AABB. The idea would be to, as a pre-processing step, use a simple algorithm in the likes of flood filling to find the biggest AABB you can that groups a lot of tiles together. Since this would be a pre-processing step and does not actually run in your release code, it can be a pretty naive algorithm and you move on to develop other interesting features of your game:

store a zero volume AABB called max

for each cell
create AABB around cell
visit all neighbors on the top of the AABB and expand if possible
repeat last line for the right, left and bottom of the AABB
if this AABB is greater than max, max = this AABB


If you're familiar with with the idea of a searching a graph with a depth first search (DFS), the idea could be to search all possible expansions for each grid cell and choose the one that eats up the most volume at any given step.

What you'd be implementing here is a type of approximate convex decomposition, and this topic can get very involved. Since you're only dealing with AABBs you can make very simple algorithms that get the job done, but if you want to you can do something more complicated... But I don't recommend this.