Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I've got a 2D-map, largely consisting of rectangular tiles, but with some none-rectangular objects mixed in as well (tilted lines on corners for example).

Take this image as an example:

enter image description here

I now need all the largest possible (straight) lines around the two bodies inside that map. There are no additional required attributes to the lines.

In this image, I've marked the lines that I'm trying to find, each one with a different color to make sure there are no confusions:

enter image description here

It's important however, that the algorithm doesn't produce lines inside those two objects, as it would be a waste of resources.

Are there algorithms suited for that or will I have to research an algorithm myself?

By the way, the algorithm will run at loading-time of the game, so it doesn't need to be optimized for runtime-speed. Also, principally, an algorithm that is just able to find the lines around bodies which consist only of square or rectangular tiles would suffice as well.

share|improve this question
I don't see any image :\ –  zacharmarz Jul 18 '11 at 9:27
The images are located here: i.imgur.com/uk5ax.png and i.stack.imgur.com/x6u3W.png –  TravisG Jul 18 '11 at 10:35
add comment

1 Answer

up vote 1 down vote accepted

If you're dealing with discrete positions (eg. a tile-map or pixel based map), then an easy way to find the contours would be the Marching Squares algorithm (Wikipedia).

share|improve this answer
That algorithm helps me to find the outline - but that's just a part of the problem. I still need to extract the lines from the outline, as well as the exact pixel-position of the lines. After all, I can't do anything with lines which are as thick as a tile itself. –  TravisG Jul 18 '11 at 9:56
Based on the movement of the marching square, you should be able to tell if the edge is left, right, bottom or top. An alternative would be a radial sweep algorithm, where you start at a corner point and check against the edges of the "tiles" –  bummzack Jul 18 '11 at 11:44
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.