3
\$\begingroup\$

I am trying to implement field of view (FOV) in a hex grid. I am using the cube coordinate system from here. Then, I am using shadow casting to find FOV as from here.

I have a system like in the image, below. The numbers at the corners are coordinates. The numbers in the center are formatted as [Ring index],[Hex Index].

A rough diagram of the system I use.

I need to used both ring index and hex index to calculate angles used for shadow casting. I spent several days on it, but I still cannot find a way to make these two sets of numbers convertible.

How do I calculate hex coordinates from a ring and index?

\$\endgroup\$
  • 1
    \$\begingroup\$ Did you read the part about rings in the tutorial? \$\endgroup\$ – William Mariager Oct 14 '16 at 8:00
  • \$\begingroup\$ I just follow the pseudo code to implemented it. I may have to read again. \$\endgroup\$ – Joshua Oct 14 '16 at 8:20
  • \$\begingroup\$ @WilliamMariager I read it again but it didn't help. Its approach is start from one of the six corners and go down the direction for the radius amount of time. However, my need it to start from the top center. Therefore, I need a generic equation for conversion. \$\endgroup\$ – Joshua Oct 14 '16 at 9:01
  • \$\begingroup\$ @DMGregory I have indicate the order in the image above (this number in center). If it doesn't have the top center one, it will start from the right one (like 1,1). \$\endgroup\$ – Joshua Oct 15 '16 at 14:54
3
\$\begingroup\$

First, let's define a standard ordering of basis vectors to use. These are the offsets to each of the six hexes in the closest ring around our center, in clockwise order from top-left.

int3[] spokes = {
   new int3( 0,  1, -1),
   new int3( 1,  0, -1),
   new int3( 1, -1,  0),
   new int3( 0, -1,  1),
   new int3(-1,  0,  1),
   new int3(-1,  1,  0)
};

These mark where the ring turns a corner. From a corner tile in each spoke direction, the ring continues clockwise along a nice predictable straight line, until it hits the corner tile in the next spoke direction.

So, we can reach any ring coordinates in just two moves:

  • A straight line out from the center, along a spoke direction, to one of the corner tiles
  • A straight line clockwise from a corner tile, to the tile we want.

Here's how that might look in code:

int3 RingIndexToCubeCoords(int3 center, int radius, int index) {

    // Handle degenerate case:
    if(radius == 0)
        return center;

    // Number of tiles in a complete ring:
    int ringSize = 6 * radius;

    // Convert to a zero-based index starting from spoke[0].
    // This makes the math simpler in the next steps.
    // The modulo at the end wraps the end of the ring back around to zero.
    int tweakedIndex = (index + ceil(radius/2) - 1) % ringSize;

    // Find the closest spoke counter-clockwise from the given index.
    // (ie. "Which sixth of the ring are we in?")
    int spokeIndex = floor(tweakedIndex/radius);

    // Compute the ring index of the corner tile at the end of this spoke:
    int cornerIndex = spokeIndex * radius;

    // Compute how much further we still need to go:
    int excess = tweakedIndex - cornerIndex;

    // Start at the center of the ring.
    int3 result = center;

    // Progress outward along the spoke to the corner tile at the given radius.
    result += radius * spoke[spokeIndex];

    // Proceed clockwise along the ring to the chosen tile:
    result += excess * spoke[(spokeIndex + 2) % 6];

    return result;
}

The reverse can be done too:

void CubeCoordsToRingIndex(int3 tile, int3 center, out int radius, out int index) {
    // Compute the difference between the tile's position and the center.
    int3 offset = tile - center;
    int3 absOffset = abs(offset); // componentwise absolute value.

    int spokeIndex = 0;

    // Find which spoke is at the counter-clockwise end of this span.
    // There are less branchy ways to do this, but they're more cryptic-looking.
    if(absOffset.y >= absOffset.x) {
        if(absOffset.z >= absOffset.y) {
            spokeIndex = offset.z > 0 ? 3 : 0;
        } else {
            spokeIndex = offset.y > 0 ? 5 : 2;
        }
    } else if (absOffset.x >= absOffset.z) {
        spokeIndex = offset.x > 0 ? 1 : 4;
    } else {
        spokeIndex = offset.z > 0 ? 3 : 0;
    }

    // Compute radius as half the Manhattan distance from the center.
    radius = (absOffset.x + absOffset.y + absOffset.z)/2;

    // Find the counter-clockwise corner tile.
    int3 corner = radius * spokes[spokeIndex];

    // Find the distance of our tile from this corner tile.
    absOffset = abs(tile - corner);
    int excess = (absOffset.x + absOffset.y + absOffset.z)/2;

    // Our tile is at the corner's index, plus this excess.
    index = radius * spokeIndex + excess;

    // Convert indexing system to one that starts near the middle of the top of the ring.
    int ringSize = 6 * radius;
    index = (index + ringSize - ceil(radius/2))) % ringSize + 1;
}
\$\endgroup\$
  • \$\begingroup\$ I am still at work so I cannot verify it right now. I will check it once I get back home. \$\endgroup\$ – Joshua Oct 17 '16 at 4:12
  • \$\begingroup\$ I haven't tested it myself yet, so there's a good chance there's an off-by-one error lurking in there somewhere. If it gives you any trouble, send along a detailed description of where it goes funny and we'll get it debugged. :) \$\endgroup\$ – DMGregory Oct 17 '16 at 12:43
  • \$\begingroup\$ OK, RingIndexToCubeCoords seems to be right but CubeCoordsToRingIndex is not. I am still figuring out. It seems that there is a bit off at the index calculation. \$\endgroup\$ – Joshua Oct 17 '16 at 14:21
  • \$\begingroup\$ For example, center is [0,0,0] and the tile is [2,1,-3]. I get excess = 2, radius = 3 and spokeIndex = 0 which are all correct except the index = 17 \$\endgroup\$ – Joshua Oct 17 '16 at 14:28
  • \$\begingroup\$ The +1 is making one off error in the last statement. Other things seems to be fine and I have tried several center and tiles. Once you have corrected it. I will accept your answer. Another thing is that I do not think ceil and floor is necessary because we are using integer division. I using (radius+1)/2 and radius/2 instead. \$\endgroup\$ – Joshua Oct 17 '16 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.