next »

[clockwrk_routine]

I started reworking how my tile editor builds it collision in unity, using the polygon collider 2d component.  The polygon collider 2d component takes a sequential paths of points and generates a shape based on those points.  My problem is generating those paths when your collision data for your tiles is stored in a 2d array so it looks something like this:

0 X X 0
X X 0 0
X X 0 0
0 X X 0

I considered doing a bunch of "if block is in X dirrection: move to block" checks, until I got a complete path around the shape, adding checked blocks to a list of already visited, but I'm wondering if there is a more efficient method out there.

edit:
I found what I was looking for:
http://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/theo.html

edit:
nvm same solution but I now know what I should be looking for, contour tracing algorithms.

[surt]

You might want to combine that with connected-component labelling to extract the individual islands.

[Columbo]

The problem looks quite similar to marching squares (http://en.wikipedia.org/wiki/Marching_squares), the challenge would be repurposing the concept to be able to trace a line around.

Maybe you could attack it in two passes:

Pass 1: Run the marching squares algorithm to generate all the intersection points and categorize all of the cells in your array.
Pass 2: Iterate through the cells, as soon as you hit one with some content, trace the contour generating your line point until you come full circle back to where you started, as you go mark the cells as processed so that you can skip them as you continue iterating.

As a bonus, by using a marching square based approach, you could choose to have more complexity so that instead of always having 45-degree or 90 degree aligned slopes, you could have other slopes too. Although that might not really fit in with your tile editor.

[clockwrk_routine]

^ Yea that's exactly what I'm trying to implement now : )
thanks surt and columbo

[gimymblert]

seems similar to this problem (unity3D)

[clockwrk_routine]

Looks like I didn't need to do any categorizing/connected component labeling, I ran marching squares in one pass marking all the visited cells as I went along, gathering every island path into an array.  I used polygoncollider2d.setpath for each path, and unity seemed to merge the paths togethers.  Also kept whether there were any holes in the polygon intact which is nice.