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:

points[y * 2][x * 2] |= tile[0][0]; // Top-left points[y * 2 + 1][x * 2] |= tile[1][0]; // Center-left // and so on for all 3x3 dots...

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:

// We use this mapping to store which point is connected to which others HashMap<Position, Set<Position>> edge_map = new HashMap<Position, Set<Position>>(); // Run through all 2x2 areas in the matrix for (int x = 1; x < matrix[0].length; x++) { for (int y = 1; y < matrix.length; y++) { // Extract the 2x2 area boolean nw = matrix[y - 1][x - 1]; boolean ne = matrix[y - 1][x]; boolean sw = matrix[y][x - 1]; boolean se = matrix[y][x]; // Area is completely blocked if (nw && ne && sw && se) { continue; } // Time to find an edge! Position posA = null, posB = null; // Diagonal edge from top-right to bottom-left if (ne && sw) { posA = new Position(x - 1, y); posB = new Position(x, y - 1); } // Diagonal edge from top-left to bottom-right else if (nw && se) { posA = new Position(x - 1, y - 1); posB = new Position(x, y); } // And so on for all other cases... // [...] // Found an edge if (posA != null) { // Make sure the mapping contains both points if (!edge_map.containsKey(posA)) { edge_map.put(posA, new HashSet<Position>()); } if (!edge_map.containsKey(posB)) { edge_map.put(posB, new HashSet<Position>()); } // Add the edge in both directions edge_map.get(posA).add(posB); edge_map.get(posB).add(posA); } } }

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:

ArrayList<Polygon> polygons = new ArrayList<Polygon>(); // Make a copy of all connected positions Position[] positions = edge_map.keySet().toArray(new Position[] {}); // We have two points per tile so scale it down tile_width /= 2; tile_height /= 2; for (Position current_position : positions) { // We have already used that position in another polygon so skip it if (!edge_map.containsKey(current_position)) { continue; } boolean is_first = true; Position next = current_position; ArrayList<Position> vertices = new ArrayList<Position>(); // While we have not reached the first position _again_ (so ignore // first time)... while (!next.equals(current_position) || is_first) { boolean success = false; is_first = false; // Add that point to the polygon vertices.add(next); // Get all possible edges from the mapping Set<Position> others = edge_map.get(next); // Nowhere else to go - should only happen when closing after // reaching the end if (others == null) { break; } for (Position other : others) { // If we haven't used that edge yet, continue from there if (!vertices.contains(other)) { next = other; success = true; break; } } // We hit a dead end - should only happen when closing after // reaching the end if (!success) { break; } } // Remove all the used points from the mapping edge_map.keySet().removeAll(vertices); Polygon poly = new Polygon(); for (Position vertex : vertices) { // Scale each point up to the real map size (by half a tile) poly.addPoint((vertex.x - 3) * tile_width, (vertex.y - 3) * tile_height); } polygons.add(poly); }

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:

ArrayList<Polygon> merged = new ArrayList<Polygon>(); // A PriorityQueue is used to sort the polygons by their size PriorityQueue<Polygon> coll_set = new PriorityQueue<Polygon>(20, new Comparator<Polygon>() { @Override public int compare(Polygon arg0, Polygon arg1) { int size0 = (int) (arg0.getHeight() * arg0.getWidth()); int size1 = (int) (arg1.getHeight() * arg1.getWidth()); return size1 - size0; } }); coll_set.addAll(polys); // The biggest polygon is handled first Polygon highest = coll_set.poll(); // Handle all polygons while (highest != null) { // Check all remaining (smaller) polygons against the biggest one for (Polygon poly : coll_set) { if (highest.contains(poly)) { // If the biggest polygon contains any of the other // polygons, the other // is considered to be a hole and subtracted from the // biggest one coll_set.remove(poly); coll_set.addAll(ShapeUtil.subtract(highest, poly)); // Don't add the biggest one since it has been split up and // each part // will be checked again highest = null; break; } } if (highest != null) { // Polygon is fully handled, so add it merged.add(highest); } // Check the next biggest polygon highest = coll_set.poll(); } return merged;

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.