Hey guys in my first english post I decided to share how I implemented collision. For those who don't know, I'm currently playing with the Slick2D framework for Java developing some kind of RPG/tower defense thing (Yeah, I know, not a really clear idea).

Tile based collision really isn't much of a secret and there are tons of articles and tutorials on that topic. But I wanted a bit more complex shapes than saying whether a square tile is blocked or not. My first approach (which you can see on the right side) simply calculated a rectangle or polygon for each tile and placed them on the map. The result worked but was quite slow since for each tile you have to do a complicated collision. (By the way, for collision between any kind of shapes I'm just using the built-in functions of Slick, which might not be very fast or well implemented, but they work for now.)

So I started looking for a good way to merge those shapes. The most obvious approach seemed to just look for overlapping (or a least touching) shapes and merge them. But the implementation simply didn't create the desired results so I tried a different approach. I wanted to place some "dots" on the map determining where an edge of a blocked area might be. There are 3x3 dots per tile on the edges, corners and the center. To visualize this a added some dots to the picture on the left side (which also contains all possible collision tiles at moment - red areas are blocked). These dots can simply be stored in a matrix of booleans where the value if true if the specific "dot" is set.

The dots of the tiles overlap since the tiles share their corners and edges. The matrix is twice as big as the map (`width in tiles * 2 + 1` resp. `height in tiles * 2 + 1` to be exact). Then for each tile in the map do the following:

Then by looking at a 2x2 are at a time it is easy to determine if there should be an edge between any of the points in that area:

With that mapping it is now time to construct the polygons which is quite easy, since all we have to do is starting at one point and recurse through the connections until we hit the start again:

Now we have all the polygons, but some of them might be the edge of a hole within another polygon! Especially since I added a blocking ring around the whole map this is a problem, because this way the whole map would be covered by a gigantic blocking rectangle. So I still needed an algorithm to combine polygons (the built-in one in slick was broken, remember?). I found some solution in a forum and adapted it to work with my polygons. So here is the merging algorithm:

The big magic here pretty much is just using a list which contains the polygons ordered by their size and the walking through it and whenever one polygon is contained in another one, it is subtracted from the containing one. I won't go into the subtraction algorithm here as that would certainly blow the scope of this post. If you want you can have a look at the source code here and there.

The solution is still not perfect and at the moment I'm not caching the results anywhere so the maps take quite some time to load. The first problem is that currently the algorithm doesn't create any square edges because the corner is interpolated with a diagonal. The second one is that the number of points in the polygon is not optimized, they simply contain a lot of points which all lie on a straight line. And all in all polygons might not even be the best solution for collision since the detection doesn't scale well. Anyway, to the right is a screen shot of the final result.