Hey folks,

I need some help creating a complex polygon. The image below serves as a visual aid:



The brown tiles are walls, and the green tiles are floors. I want to trace the walls of the map, starting with the upper-left-most corner, and proceeding in a counter-clockwise fashion until the polygon is closed.

Of course, with the polygon I'm attempting to create, there is a bit of tricky stuff going on. When tracing the outer walls, at first, is simple -- whenever you reach a corner of the map, make a left turn (current angle minus 90 degrees). Things get hairy, though, when tracing the interior of the wall area.

When Point5 is plotted, a left turn no longer will work -- as the tracing will attempt to go "inside" the wall. A right-turn is required to continue. Same for Points 6, 7, and 8. Point 9 and on all continue the trace with left turns.

What I can't figure out is the best way to determine whether the trace needs to iterate with a left turn, or if a right turn is required. I'm not good with math, so this particular problem is really throwing me for a loop.

Any suggestions?

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Yes, as i'm doing something in a similar fashion, i've experimented a bit with it.

The way i came up with includes several passes:

1. seperating the tilesmaps in isles, in your case this would be one wall and one floor isle, through recoursive search of adjacent tiles.

2. create outlining segments for each tile in the isle (either cw or ccw not mixed) and remove each duplicate (where a.start == b.end && a.end == b.start)

3. merge the remaining if they have the same direction like o---o---o becomes o-------o
3.1 Sort so they interconnect and form a closing loop

4. finally use a triangulation method to create the polygon out of the linestrip

If you need some kind of visualization if you have a hard time to follow, i can do that, just let me know

This is not the most efficient and probably not the easiest or best solution, although it does work and gives reasonably fast results for me.
If you come up with something else, let me know

_________________
Long pork is people!

wzl's burrow

Well, I've been working on this full-blast since I started it (about 66 hours ago... don't worry, I *did* sleep on occasion), and I FINALLY figured it out.

The algorithm has been tested with several layouts (from very simple, to as complex as the layout pictured below), and seems to be working just fine.

The idea is that I wanted the "void" between walls to be (more or less) invisible, while only using two tile types -- wall, and floor. Now, using blocks would have been simple, but quite boring IMO. Could also have gone the route of making graphics for all possible wall configurations, but that would require a lot of hassle (for map-building, AND graphics design, AND modifying graphics).

With this algorithm, the effect is accomplished. It basically starts at point 0*0 (in pixels), and "follows" the wall tiles in a counter-clockwise manner. It goes through each tile, incrementing the X/Y of a point, until a corner is found. When a corner is found, a point is plotted at the proper X/Y coordinate, and turns relatively either left (by default) or right (if there is a wall at the relative-right of the current tile being tested).

It was a pain in the butt getting this thing going, but, you know what? It's GOING.

Here's a basic rundown of the algorithm (in pseudocode):



It's still rough (I could probably move the check for relative-right tiles higher up in the hierarchy, since that check is required in all cases, and takes precedence over pretty much everything else), but I'm happy that I got it working!

To demonstrate the code in action, here is a "before-and-after" image, which shows the map as plain tiles, and with the tracing highlighted, and then with the "final" product:

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Cool. I couldn't think of a decent way of handling this.



Shouldn't that be relative-left? Confused me for a while.

_________________
10 PRINT "Bad Monkey ";
20 GOTO 10

very nice... how about wall isles that are standing alone without connection to the outer boundaries? or pieces that are only diagonally connected do another. those usually hold the most problems

_________________
Long pork is people!

wzl's burrow

No, relative-right. Reason is that we're going CCW, and there are rules that go along with that. Specifically:

When going right (positive X), we MUST be on the bottom of the wall.
When going down (positive Y), we MUST be on the left side of the wall.
When going left (negative X), we MUST be on the top of the wall.
When going up (negative Y), we MUST be on the right side of the wall.

If you start at the origin (0/0 -- the upper-left corner) and start following the line going down, keep following it -- you'll see that the traversal adheres to these rules at all times. Following these rules are what makes the algorithm work.


I'm currently working on a "helper" function that will traverse the map (in a different manner from the algorithm above) and seek non-contiguous walled areas. I'm having fits with that, too (seems to be getting stuck in a sort of infinite loop in the middle of the map, around tile 3/3 -- the downward turn toward the center of the map).

Basically what I'm trying is starting from the tile at 0/0, and then going in all four cardinal directions looking for adjacent wall tiles. If any are found, traversal nodes are added for each tile adjacent to the current tile, and the tile location is stored in a list. Once we exhaust all traversal nodes (ideally when there are no more contiguous wall tiles), we begin to scan the map for wall tiles that aren't already in the list of traversed tile locations. Lather, rinse, repeat.

Now if I can just get the thing to work.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Sorry, neglected to address this before.

Walls that are diagonal to each other are not taken into account at all. Since I don't plan to have any angled walls (God forbid, this is enough trouble as-is), the case of walls adjacent to one another diagonally can be completely ignored. Thank goodness.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Behold!

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

sweetness, congrats.

Man this kinda reminds me of the game i'm currently at coding

http://dl.dropbox.com/u/12237727/Grit/MapEditor.png

_________________
Long pork is people!

wzl's burrow

Sweet Jesus.

Glad it's not me...

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."