   Tracing a contour from hex data?
  Running into a bit of a problem here, hoping someone can give me a lead.I'm making a 3D level editor and I need to produce some smooth closed contour lines passing through the centres of the tiles that are on edges of distinct land masses.I've done some preliminary work such as actually marking each hex with a unique land mass index and have removed internal hexes such that each mass now only has the tiles that are actually around the edges.If you look at my diagram, it's obviously the white line I need to produce (I will widen it and smooth it later) but nothing springs to mind for a rock solid way to actually get that line and only that line, without any wrong turns being made.I'd love to hear suggestions for an algorithm here. I tried googling but found nothing directly suitable. Many thanks in advance....   
  Er, so do you want the contour at the end?I would go for the vertices instead of the centers of the hexes:You have to find one valid contour vertex/edge.Then you start to go in one direction: CW or CCW. that means you can go along two edges.One edge will be the contour (if there's land on one side and sea on the other). Then you continue from this edge. You can go like this from all over the contour, until you reach the first one.You don't even have to pre-eliminate the internal hexes. You have to repeat the algorithm to find all islands or lakes of course, but with a god data structure, that won't mean a big problem I guess.This solution seems very easy, so I guess I misunderstood something.   ;  Yep, I want an exact copy of the white line I drew. Later on I'll use that as a sort of iso surface to push a higher-res line out by a hex radius so I get straight lines down straightaways and nicely rounded curves around the pokey outy bits (sorry for getting all technical there! :)The problem is shown by the section of tiles at the top left of the land where the line is. There are two actual problems as I see them:1) Picking a reliable place to start scanning in the first place. Scan converting until I hit the first tile of interest might solve that one, but that kinda depends on how 2) works...2) Deciding which way to turn to stick to the outside when you're coming "back in" from a sticky outy bit.tbh, this might actually be fairly simple, but I'm just not seeing it. I've been working 12-16 hour days on different methods/prototypes of this and I'm starting to feel a bit blind.Best bet to envision the problem is to imagine the diagram *without* the white line and try to pick a start condition.;  You could still use "my algorithm". You go along the contour, and mark which hex the edge belongs to. Then connect the center of the hexes in the same sequence.And it's very easy to find a valid edge to start with.   ;  But there is a question (sorry I'm a bit sleepy, maybe you mentioned that).How do you want to handle 1 hex wide land?   ;  If you look on the diagram at the very leftmost of the hexes (that has a line on) and then the one to its immediate lower right? Place a new green square below those and touching them.If you go back to the very leftmost one, the line should now extend from there to the new tile we just put in. However, that new tile has all the exact same properties as the one it currently goes to, so that's what I'm having trouble with.You can tell I'm feeling burnt out - I didn't even show the "problem" on my diagram!;Quote:Original post by szecsBut there is a question (sorry I'm a bit sleepy, maybe you mentioned that).How do you want to handle 1 hex wide land?That will be a closed loop that actually looks like a line. It will still have directionality so will expand into an oval. A single hex on its own would be an easy special case, but I might just make them illegal as they have little gameplay attached to them.   ;  Take take a break. And tr to be clearer. I still don't know how you want to handle 1 hex wide peninsulas (where the hexes has only two green neighbors, and the two neighbors don't touch each other)Other that that, my algorithm would work. Maybe not the best solution, but would work anyway. Since can go only on one contour, and the decision is dead simple:"the edge is between one green and one blue hex?" then it's a part of the contour. Then you continue from that edge. You can't miss, you can't make bad turns. You connect the centers of the green hex, that has the current contour element. That means some hexes will be repeated, but that should be very easy to handle in the code.EDIT: I've just read your new post. Then you could use my algo without problems. If you don't get it, take a break. I can't put it simpler.EDIT 2: some typos: I'm a blind idiot when I'm sleepy.   ;  Have you looked into marching squares?  I'm sure a similar approach could be taken for hexes.   ;  Marching squares would work, but since you are working with hexagons there would be 64 different states.The simplest method I can think of is to follow the edges closest to the outside that have not yet been visited. So the steps you would take would be:1. Remove all hexagons that are not land.1. Generate adjacency data.2. Remove all hexagons where all adjacent hexagons are land. (Remove all land that won't be part of the contour line.)3. Mark all remaining hexagons as unvisited.4. Pick any hexagon in the list to start from that is marked unvisited.5. Mark the hexagon as visited and add it to the poly-line.6. Move to the adjacent hexagon closest to a non-land hexagon that has not been marked visited. So basically find all the edges that connect to non-land polygons. Then find the closest edge to any of these "outside" edges, and make sure the edge you pick has not been marked before. Any of the edges will work. There should only be one unique choice except for first movement you make at the start of a poly-line. The one you pick determines if your polygon will be clockwise or counter-clockwise.7. Continue until you cannot find any adjacent hexagons that have not been visited before. Then connect back to the first hexagon in the poly-line.8. Create a new poly-line and repeat steps 4-7 until all hexagons have been marked visited.The above algorithm should work for all cases except when it is impossible to form a closed loop such as a one hexagon wide strip of land.However, you can modify the algorithm to work with that case. At step 7 instead of closing the poly-line go back to the first hexagon in the line and continue to move until you cannot find any more hexagons marked unvisited. Then if the first and last hexagons in the poly-line are adjacent then make them a closed loop.