Looking for an algorithm similar to fast voxel traversal, but for 2D hexagonal grids. I'd like to return the list of pairs of integer hex coords and gridline intersections whose hex-cells are intersected by a ray or line segment.

I can find just 1(!) example online of this on shadertoy here: https://www.shadertoy.com/view/XdSyzK​ which I have tried to implement but in vain. The hex to cartesian conversion used is not the same as on https://www.redblobgames.com/grids/hexagons/​​​​​​ ​which is an approach I understand thoroughly and have based all hex stuff on. Any help trying to understand what's going on with that toy would be helpful - i'd ask there but it's three years old. There's another example on shadertoy which is a rewrite of the first one here https://www.shadertoy.com/view/ldSyRK​ and also another example here https://www.shadertoy.com/view/lsXyzX​ but this would appear to be looping through all the hexes and checking the hex is on the line - it's not traversal.

To be clear, I'm looking for an algorithm that does traversal from floating point to floating point positions, and NOT like a bresenham line for hexagon grids, which goes from integer hex-center to hex-center. I am aware of the few resources online for that too…

Any help appreciated.

Probably the question belongs in the Math forum rather than here, but here goes.

One option that comes to mind is that, given you are on a known edge of a known hexagon, you trivially know what hex is at the other side. Of that hex, the set borderlines is known as well.

So the question becomes “which of those lines is hit first when you extrapolate?” If you answer that question, you are back with the “known edge of a known hex” assumption and you can repeat the question for the next hexagon.

Instead of lines, the 6 points of the next hexagon are enough as well. If you know at which side of the line they are, finding the edge where you cross to the next hexagon is simple.

dan4 said:
To be clear, I'm looking for an algorithm that does traversal from floating point to floating point positions, and NOT like a bresenham line for hexagon grids, which goes from integer hex-center to hex-center.

It's actually the same thing: your segment of an arbitrary straight line is approximated arbitrarily well by a segment of a straight lline between two (very far) hex centers, and it can be drawn with the same algorithms except for skipping the initial and final portions of the line.

Take your hex grid and extend every line segment into a full line of infinite length. Collide your ray with each line thus formed, then check if the collision point is on the border of a hexagon (and if so which border) or not.

Thanks for the responses.

I have a working solution now in C#.

public static readonly float SQRT_3 = Mathf.Sqrt(3);

public delegate bool Callback(Vector2Int hex, Vector2 intersection, float t);

public static void Traversal(Vector2 p0, Vector2 p1, float scale, Callback callback, int iterations = 1000)
{
    Vector2 HexToCart(Vector2 hex)
    {
        float cY = hex.y * scale / (2f / 3f * SQRT_3);
        float cX = hex.x * scale + cY * SQRT_3 / 3f;

        return new Vector2(cX, cY);
    }

    Vector2 CartToHex(Vector2 cart)
    {
        float vX = (cart.x - cart.y * SQRT_3 / 3f) / scale;
        float vY = (2f / 3f * cart.y * SQRT_3) / scale;

        return new Vector2(vX, vY);
    }

    Vector2Int HexRound(Vector2 hex)
    {
        Vector3 cube = new Vector3(hex.x, hex.y, -hex.x - hex.y);

        int rx = Mathf.RoundToInt(cube.x);
        int ry = Mathf.RoundToInt(cube.y);
        int rz = Mathf.RoundToInt(cube.z);

        float x_diff = Mathf.Abs(rx - cube.x);
        float y_diff = Mathf.Abs(ry - cube.y);
        float z_diff = Mathf.Abs(rz - cube.z);

        if (x_diff > y_diff && x_diff > z_diff)
            rx = -ry - rz;
        else if (y_diff > z_diff)
            ry = -rx - rz;

        return new Vector2Int(rx, ry);
    }

    //Delta of the line p0, p1
    Vector2 delta = (p1 - p0);

    //Unit vectors of three hexagonal directions
    Vector2 n0 = new Vector2(1, 0);
    Vector2 n1 = new Vector2(+.5f, SQRT_3 * .5f);
    Vector2 n2 = new Vector2(-.5f, SQRT_3 * .5f);

    //The sign of each of the three directions
    int s0 = (int)Mathf.Sign(Vector2.Dot(n0, delta));
    int s1 = (int)Mathf.Sign(Vector2.Dot(n1, delta));
    int s2 = (int)Mathf.Sign(Vector2.Dot(n2, delta));

    //Orient the directions so they are the three normals nearest to the line
    n0 *= s0;
    n1 *= s1;
    n2 *= s2;

    //Scale the directions to the size of the grid
    n0 /= scale;
    n1 /= scale;
    n2 /= scale;

    //The steps in integer hex coordinates for each of the three directions
    Vector2Int step0 = new Vector2Int( 1, 0) * s0;
    Vector2Int step1 = new Vector2Int( 0, 1) * s1;
    Vector2Int step2 = new Vector2Int(-1, 1) * s2;

    //Calculate the current hex that the ray origin is contained within
    Vector2Int current_hex = HexRound(CartToHex(p0));

    for (int i = 0; i < iterations; i++)
    {
        //Get the difference between the center of the current hex and the start of the ray
        Vector2 rdelta = p0 - HexToCart(current_hex);

        //Get the distances to each edge
        float d0 = (.5f - Vector2.Dot(n0, rdelta)) / Vector2.Dot(n0, delta);
        float d1 = (.5f - Vector2.Dot(n1, rdelta)) / Vector2.Dot(n1, delta);
        float d2 = (.5f - Vector2.Dot(n2, rdelta)) / Vector2.Dot(n2, delta);

        //Find the nearest edge
        float t = d0;
        Vector2Int step = step0;

        if (d1 < t)
        {
            t = d1;
            step = step1;
        }

        if (d2 < t)
        {
            t = d2;
            step = step2;
        }

        //Break at the end of the line
        if (t > 1)
            break;

        //Calculate where the line intersects with the edge
        Vector2 intersect = p0 + delta * t;

        //Increment the current hex tile across the nearest edge
        current_hex += step;

        //Do callback and break on return true
        if (callback(current_hex, intersect, t))
            break;
    }
}