Simplifying a Tilemap

Topics: Developer Forum, User Forum
Jan 22, 2011 at 12:50 AM

I'm currently working on taking a grid of tiles and creating large convex hulls out of contiguous "islands" of tiles in the tilemap.

This is primarily to optimize the physics engine's work.  Each tile can have a unique collision polygon, and what I would like to do is merge all of the vertices for a contiguous group of tiles' collision polygons into one larger polygon.  To accomplish this I realize I need to identify the "islands" within my map, and then run one of the convex hull routines to shrink wrap a new convex hull around the point cloud consisting of all of the island's collision polygons.

To identify the "islands" I've begun working with the polygons from texture tool.  I create a fake texture where every collidable tile in the map is an opaque pixel and every non-collidable tile is transparent and then I run the PolygonTools.CreatePolygon method and pass it the fake texture.  This returns a list of vertices that almost identifies the regions perfectly.  The problem is, it seems to have some sort of threshold for combining vertices that are close together.  Here is a picture of the result:

The red lines in this image represent the polygons returned from the CreatePolygon call.  You'll notice it works perfectly for the rectangular regions.  It correctly outlines these islands.  It almost correctly outlines the more awkward shapes, but you'll notice it seems to merge some tiles together as if they are within a certain threshold.  I've played around with the hullthreshold parameter with only minimal results.  It did greatly improve when I lowered it, but it seems to have gotten to a point where any lower doesn't matter.

If I can get this working, I would go through each polygon and add the collision polygon of each tile intersected by the outline to some big polygon soup.  Then I would run the ShrinkWrap algorithm on this soup to produce a final, simplified convex hull of each "island". 

I was wondering if there is any way to improve the output from the CreatePolygon method.  I need it to make a perfect outline of each of these islands (although it is so close to being perfect).  One option I was considering is to "enlarge" my texture by making every tile correspond to four pixels, but I am unsure if that would make any difference.  Does anyone know of perhaps a better way to do this?

Thanks for your help and for a great physics library!

Developer
Jan 22, 2011 at 1:48 AM

I'm not sure exactly what your desired outcome is. Could you draw lines on your screen shot in say orange or white where you would like your polygon borders to end up. This would help me greatly in helping you.

Jan 22, 2011 at 2:31 AM
Edited Jan 22, 2011 at 2:35 AM

I'm sorry, the issue is difficult to explain.  The yellow lines I added to the image show the desired output.  I highlighted some of the issues with red circles.  Basically I need a polygon that goes around the perimeter of each grouping of tiles.

Developer
Jan 22, 2011 at 3:01 AM

I see now what your going for. I would say right now that your gonna need a custom algorithm to pull that off.

Are these regions going to be used directly in the physics engine or for something else?

I would write code to follow the edge and create vertices as I go and then remove collinear points from the finished polygon. If your using these polygons for the physics engine then you'll need to decompose them first.

If you need a more detailed description just let me know.

Developer
Jan 22, 2011 at 1:47 PM
Edited Jan 22, 2011 at 1:47 PM

I have some working code which creates an outline of a tilemapped environment and represents it via edge shapes. The main idea is to check all 4 sides of each tile. If there is an adjacent tile I do nothing, otherwise I add the tile edge to a heap. Then like Matt suggested I just combine all the edges which share a common point into a vertices object until i get a closed polygon. Then I remove all colinear points and convert it to a loop shape.

At the moment the code is part of a costum content importer for OgmoEditor maps. But I could try to extract the essentiall parts if you are interested.

Jan 22, 2011 at 7:34 PM

Thank you both for your suggestions.  It sounds like I was making this problem harder than it should be.

@matt: These regions won't be directly used in the physics engine, the vertices of each region indicate the location of a tile that is on the perimeter of the group of tiles. I will use these vertices to determine which tiles I need to consider when generating a larger collision hull for each group.

@Elsch: I think I understand what you mean and I'll give it a shot, at least for identifying perimeter tiles, since tiles don't necessarily have square collision shapes.

The biggest issue is that each tile can have a completely different collision shape (such as a ramp having a triangular shape). In the above image all of the tiles just happen to be squares.  I need to take the vertices of every perimeter tile's collision shape and create a larger collision shape from all of them.

Jan 25, 2011 at 2:31 AM

So I ended up optimizing any tiles that are squares using the methods you guys described.  It works perfectly, thank you.  I realized that to support tiles with all sorts of different collision shapes I would require some sort of concave-hull algorithm which so far as I could tell is not easily done.  Instead I just optimize square tiles using the aforementioned methods and then all other tiles are simply left as is.  The outlining of tiles along with triangle decomposition proved to work very well for my purposes.

Here's a screenshot of the results: