[Solved]: How do I structure hexagon edge data?

Problem Detail: 

In my program, it draws them by offsetting every other row by half of the width, as pictured above. Each tile can be referenced by coordinates, also shown above.

I want to know how many blue tiles are accessible from a certain starting tile and a series of "roads." In this example, three blue tiles can be reached.

How would I represent roads? This is what I would need to know about it:

• how it is rotated (for drawing)
• which hexagons it borders
• which other roads it touches, if any
• where it should be drawn

I assume I could use recursion to to count the accessible blue squares if the above conditions are met.

Asked By : tyjkenn

Answered By : Andrej Bauer

Let us first calculate the coordinates $C(m,n)$ of the center of hexagon $(m,n)$. We assume that the origin is at the center of hexagon $(0,0)$ and that the hexagon radius (distance from center to vertex) is $r$. A short calculation shows that hexagon $(1,0)$ has its center at $$C(1,0) = a = (\sqrt{3} r, 0)$$ and hexagon $(0,1)$ has its center at $$C(0,1) = b = (\sqrt{3} r/2, 3 r/2).$$ Therefore, hexagon $(m,n)$ has its center at $$C(m,n) = m \cdot a + n \cdot b = (\sqrt{3} r (m + n/2), 3 r n / 2).$$ Notice that we should allow negative $m$ and $n$ if we want to cover the whole plane.

To get from the center $C(m,n)$ to one of the adjacent centers we need to add to $C(m,n)$ one of the vectors $a$, $b$, $-a$, $-b$, $a - b$, or $b - a$. (If we add $a + b$ or $-a-b$ we go too far). If we travel half the distance we will end up exactly in the midpoint of a side. Therefore, midpoints of sides have coordinates of the form $$C(m+1/2, n), C(m,n+1/2), C(m-1/2,n), C(m,n-1/2), C(m+1/2,n-1/2), C(m-1/2,n+1/2).$$ We have discovered how to encode sides: just use half-integer coordinates. But this is silly, it is better to multiply everything by two, which leads to the following system.

We represent both hexagons and sides as pairs of integers $(m,n)$. When $m$ and $n$ are both even this encodes a hexagon whose center is at $$C(m/2,n/2) = (m \cdot a + n \cdot b)/2.$$ If either $m$ or $n$ is odd then $(m,n)$ represents a side of a hexagon whose midpoint is at $C(m/,n/2)$.

It is also easy to tell which two hexagons a given side belongs to: the side $(2 i + 1, 2 j)$ belongs to hexagons $(2 i, 2 j)$ and the side $(2 i + 2, 2 j)$, while the side $(2 i, 2 j + 1)$ belongs to hexagons $(2 i, 2 j)$ and $(2 i, 2 j + 2)$.

Similarly, the sides of hexagon $(2 i, 2 j)$ are: $(2 i + 1, 2 j)$, $(2 i - 1, 2 j)$, $(2 i, 2 j + 1)$, $(2 i, 2 j - 1)$, $(2 i + 1, 2 j - 1)$ and $(2 i - 1, 2 j + 1)$.

We now have a good system for representing hexagons and sides as pairs of integers. We still need to solve the original problem, namely which blue hexagons are reachable from a starting hexagon by traveling along certain "black" paths. This is a graph-theoretic reachability problem if we think of sides as edges in a graph and their endpoints as vertices of a graph (as we reach each black side we verify whether it belongs to a blue hexagon). Many algorithms are known on how to solve this. Let me know if you need more details.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7261