🔒 Locked

Tracing a contour from hex data?

Started by rubicondev May 19, 2010 at 5:19 PM 16 replies 3.1k views

Original Post

May 19, 2010 at 5:19 PM

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. hex tiles

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

szecs

May 19, 2010 at 5:30 PM

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.

rubicondev

May 19, 2010 at 5:38 PM

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.

szecs

May 19, 2010 at 5:44 PM

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.

szecs

May 19, 2010 at 5:51 PM

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?

rubicondev

May 19, 2010 at 5:51 PM

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!

rubicondev

May 19, 2010 at 5:53 PM

Quote:
Original post by szecs
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?

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.

szecs

May 19, 2010 at 5:59 PM

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.

Zipster

May 19, 2010 at 6:01 PM

Have you looked into marching squares? I'm sure a similar approach could be taken for hexes.

65536

May 20, 2010 at 12:04 AM

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.

May 20, 2010 at 1:47 AM

Just coming up with this now so I dunno if it will work in all cases.

A tile has six neighbors, let's number them from 0 to 5 in clockwise order where 0 is the one to the left and up.

In pseudo code:

cellIndex = findTopLeftCell();addToPath(cellIndex); // Add this cell to the patholdDirection = 0;firstCellIndex = cellIndex;for (; ; ){  for (i = 1; i < 6; ++ i){    testDirection = (oldDirection + i) % 6;    testCellIndex = getNeighborCellIndex(cellIndex, testDirection);    if (!cellIsEmpty(testCellIndex))      break;  }  if (i == 6){    // We're on single side that has no other connected neighbors than the previous one. So we must step back on the same cell.    if (cellIndex == firstCellIndex)      break; // found a complete path of a single cell      testDirection = oldDirection;    testCellIndex = getCellIndex(cellIndex, oldDirection);  }  if (testCellIndex == firstCellIndex)    break; // Found a complete path  cellIndex = testCellIndex; // Update current cell index  oldDirection = (testDirection + 3) % 6; // Swicth direction from "going to" to "coming from"  addToPath(cellIndex);}

The algorithm doesn't need you to first remove the "inner" tiles and handles single cell wide "lines".

Edit:
The algorithm should work equally well on a regular grid, using 4 neighbors instead of 6 for straight contours or 8 if stepping diagonally is allowed.
Edit2:
The find top left step could be replaced by a flood fill from a user selected starting cell. I.e flood fill from the selected cell until you find the top left cell.

szecs

May 20, 2010 at 2:37 AM

Pseudo:

Visited_Edge_List[];Hex_List[];edge_index=0;hex_index=0;Visited_Edge_List[0] = Find_a_valid__contour_segment();//referred as "coast" from nowwhile( Visited_Edge_List[0] != Visited_Edge_List[edge_index-1] )//this is                                  //fishy, but you get the idea: loop closed {    Next_Right_side_edge = next_right_from_edge(Visited_Edge_List[edge_index]);    Next_Left_side_edge = next_left_from_edge(Visited_Edge_List[edge_index]);    if( is_coast(Next_Right_side_edge) )    {        Visited_Edge_List[edge_index++] = Next_Right_side_edge;        if( Hex_List[hex_index-1] != Location_of_Green_Hex_by_Edge(Next_Right_side_edge) )        {   Hex_List[hex_index] = Index_of_Green_Hex_by_Edge(Next_Right_side_edge);            hex_index ++;        }        continue;    }    if( is_coast(Next_Left_side_edge) )    {        Visited_Edge_List[edge_index++] = Next_Left_side_edge;        if( Hex_List[hex_index-1] != Location_of_Green_Hex_by_Edge(Next_Left_side_edge) )        {   Hex_List[hex_index] = Index_of_Green_Hex_by_Edge(Next_Left_side_edge);            hex_index ++;        }        continue;    }}for( i = 1; i < hex_index; i++ )    Connect(Middle_of_Hex(Hex_List,Hex_List[i-1]));

Okay, I guess that just makes understanding harder.

[Edited by - szecs on May 20, 2010 2:37:58 AM]

rubicondev

May 20, 2010 at 2:45 AM

One thing I should've made clear - I don't have any "edges" to start with. The diagram above isn't a diagram but actually a screenie from my 2D editor. The hexes are sprites.

So really, there is no concept of an edge of a hex - centres is all I have and so far all these suggestions to use outside edges break down. I guess I could look into making some virtual edges somehow, but I think that needs exactly the same heuristic as what I'm already looking for without them, given my starting conditions.

Here's a better example of the problem.

more hexes

szecs

May 20, 2010 at 2:54 AM

You should be able to identify "edges" just from the indexing of the hex grid. Or is it not consistent? I mean

(0,0)(1,0)(2,0)(3,0)(4,0)(0,1)(1,1)(2,1)(3,1)(4,1)(0,2)(1,2)(2,2)(3,2)(4,2)(0,3)(1,3)(2,3)(3,3)(4,3)

Finding a "coast": if one side is green, and the other is blue: it's a coast. Otherwise not.

I'm not sure if you can avoid the use of the contour. Maybe you can avoid it with a very complex algorithm to handle all cases.

szecs

May 20, 2010 at 3:03 AM

Maybe the marching squares/hex is a simpler stuff.
Since you have fewer cases with hex, than with squares. You only have to check 3 hexes, instead of four squares.

Anyway, you have 3 different approaches now, that should be enough :P

May 20, 2010 at 4:15 AM

I was bored at work so I tested the algorithm that I gave (on a grid), works like a charm:
(The red lines are half an arrow so that you can see the direction)

You can also allow for diagonals (8 neighbors):

It handles "thin" cells ok:

Even a single cell is ok:

And lines:

Everything I threw at it worked ok:

May 20, 2010 at 4:22 AM

Oh.. and the source:
(Will not compile out of the box, but you should be able to fix it up).

typedef std::pair<uint, uint> CellIndex;bool getNeighborCellIndex(CellIndex& neighborIndex, const CellIndex& cellIndex, const uint direction, const uint w, const uint h){	static const int directions[4][2] = 	{		0, -1,		1, 0,		0, 1,		-1, 0,	};	neighborIndex.first = cellIndex.first + directions[direction][0];	if (neighborIndex.first >= w)		return false;	neighborIndex.second = cellIndex.second + directions[direction][1];	if (neighborIndex.second >= h)		return false;	return true;}void traceContour(std::vector<CellIndex>& contour, const Image* const im, const uint x, const uint y, const uint w, const uint h, const uint p){	CellIndex cellIndex = CellIndex(x, y);	contour.push_back(cellIndex);	uint oldDirection = 0;	CellIndex firstCellIndex = cellIndex;	for (; ; ){		uint testDirection;		CellIndex testCellIndex;		uint i;		for (i = 1; i < 4; ++ i){			testDirection = (oldDirection + i) & 3;			if (getNeighborCellIndex(testCellIndex, cellIndex, testDirection, w, h)){				uint pp;				im->getIndex(testCellIndex.first, testCellIndex.second, pp);				if (pp == p)					break;			}		}		if (i == 4){			// We're on single side that has no other connected neighbors than the previous one. So we must step back on the same cell.			if (cellIndex == firstCellIndex)				break; // found a complete path of a single cell  			testDirection = oldDirection;			if (!getNeighborCellIndex(testCellIndex, cellIndex, testDirection, w, h))				break; // Should never happen!		}		if (testCellIndex == firstCellIndex)			break; // Found a complete path		cellIndex = testCellIndex; // Update current cell index		oldDirection = (testDirection + 2) & 3; // Swicth direction from "going to" to "coming from"		contour.push_back(cellIndex);	}}bool getNeighborCellIndexDiag(CellIndex& neighborIndex, const CellIndex& cellIndex, const uint direction, const uint w, const uint h){	static const int directions[8][2] = 	{		0, -1,		1, -1,		1, 0,		1, 1,		0, 1,		-1, 1,		-1, 0,		-1, -1,	};	neighborIndex.first = cellIndex.first + directions[direction][0];	if (neighborIndex.first >= w)		return false;	neighborIndex.second = cellIndex.second + directions[direction][1];	if (neighborIndex.second >= h)		return false;	return true;}void traceContourDiag(std::vector<CellIndex>& contour, const Image* const im, const uint x, const uint y, const uint w, const uint h, const uint p){	CellIndex cellIndex = CellIndex(x, y);	contour.push_back(cellIndex);	uint oldDirection = 0;	CellIndex firstCellIndex = cellIndex;	for (; ; ){		uint testDirection;		CellIndex testCellIndex;		uint i;		for (i = 1; i < 8; ++ i){			testDirection = (oldDirection + i) & 7;			if (getNeighborCellIndexDiag(testCellIndex, cellIndex, testDirection, w, h)){				uint pp;				im->getIndex(testCellIndex.first, testCellIndex.second, pp);				if (pp == p)					break;			}		}		if (i == 8){			// We're on single side that has no other connected neighbors than the previous one. So we must step back on the same cell.			if (cellIndex == firstCellIndex)				break; // found a complete path of a single cell  			testDirection = oldDirection;			if (!getNeighborCellIndexDiag(testCellIndex, cellIndex, testDirection, w, h))				break; // Should never happen!		}		if (testCellIndex == firstCellIndex)			break; // Found a complete path		cellIndex = testCellIndex; // Update current cell index		oldDirection = (testDirection + 4) & 7; // Swicth direction from "going to" to "coming from"		contour.push_back(cellIndex);	}}

rubicondev

May 20, 2010 at 5:24 AM

Had it running from your pseudo code, but thanks anyway. Kudos for writing pseudo code that actually did work first time, and even more of it for solving my problem.

Nice one! :)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.