It is currently Thu Dec 12, 2013 5:53 pm

 All times are UTC

 Page 1 of 1 [ 10 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Creating complex polygonsPosted: Tue Jan 31, 2012 1:41 am
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
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."

Top

 Post subject: Re: Creating complex polygonsPosted: Tue Jan 31, 2012 11:38 am
 Fish Doggy

Joined: Thu Sep 09, 2004 1:17 pm
Posts: 1656
Location: burrowed
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

Top

 Post subject: Re: Creating complex polygonsPosted: Thu Feb 02, 2012 5:54 am
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
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):

Code:
Create a "temporary" point at 0/0
Create a tile tracker (simply stores X/Y of current tile)
Create a directional tracker (stores direction of travel)
Set initial direction to down (90 degrees)

Loop until done:

Get current point's offset (in case it is "inside" a tile)

If our next tile is a wall:
If there is a wall to our relative-right:
Go "inside" tile by 1/4
Plot point
Turn right
Reiterate this tile
OR: If there is NOT a wall to our relative-right:
Continue in current direction
Plot tile

OR: If our next tile is NOT a wall:
(Reiterate this tile after the following checks)
If the next tile in current heading is out of map bounds:
If there is a wall to our right:
Go "inside" tile by 1/4
Plot point
Turn Right
OR: If there is NOT a wall to our right:
Go to edge of map according to heading
Plot point
Turn Left

OR: If the next tile in current heading is within bounds:
If there is a wall to our right:
Go "inside" tile by 1/4
Plot point
Turn right
OR: If we are "hugging" the map bounds:
Go "inside" tile by 3/4
Plot point
Turn left
OR: No wall to right, not on edge of map
If we are on "outside" edge of tile:
Plot point
Turn left
OR: We are "inside" tile:
Plot point

If our last plotted point is at the same coordinate as the first, we're done!
End loop

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."

Top

 Post subject: Re: Creating complex polygonsPosted: Thu Feb 02, 2012 8:37 am
 Bibliotherapist

Joined: Wed Nov 03, 2004 1:28 pm
Posts: 6888
Location: Wilts, Englandshire
Cool. I couldn't think of a decent way of handling this.

rotInMilc wrote:
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).

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

_________________
20 GOTO 10

Top

 Post subject: Re: Creating complex polygonsPosted: Thu Feb 02, 2012 1:03 pm
 Fish Doggy

Joined: Thu Sep 09, 2004 1:17 pm
Posts: 1656
Location: burrowed
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

Top

 Post subject: Re: Creating complex polygonsPosted: Thu Feb 02, 2012 5:39 pm
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
Shouldn't that be relative-left? Confused me for a while.

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.

weezl wrote:
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

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."

Top

 Post subject: Re: Creating complex polygonsPosted: Thu Feb 02, 2012 5:42 pm
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
weezl wrote:
...or pieces that are only diagonally connected do another.

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."

Top

 Post subject: Re: Creating complex polygonsPosted: Fri Feb 03, 2012 12:28 pm
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
rotInMilc wrote:
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.

(snip)

Now if I can just get the thing to work.

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."

Top

 Post subject: Re: Creating complex polygonsPosted: Fri Feb 03, 2012 2:07 pm
 Fish Doggy

Joined: Thu Sep 09, 2004 1:17 pm
Posts: 1656
Location: burrowed
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

Top

 Post subject: Re: Creating complex polygonsPosted: Fri Feb 03, 2012 2:19 pm
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
weezl wrote:
Man this kinda reminds me of the game i'm currently at coding

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

Sweet Jesus.

_________________
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."

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 10 posts ]

 All times are UTC

Who is online

Users browsing this forum: No registered users and 1 guest

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ Forums    Forum Rules and Posting Guidelines Wiki Discussion    Help    Content Issues Game Programming Discussion    C and C++ Game Programming    Java Game Programming    Language Agnostic Programming    .NET Game Programming    VB Game Programming    Mobile Game Programming    Web-Based Game Programming    Other Languages    OpenGL Development    Direct X Development Game Development Discussion    Game Design    Game Media Off-Topic Discussion    Announcements    Off-Topic    Community Projects    News