Find hexes on a hex grid given an angle

Question

I'm trying to find an elegant solution to calculating the x, y values of hexes that are crossed or intersected by a line or ray at a given angle from a given hex position on a hex grid. I do not want to use linear interpolation with an end point. I want a function that can calculate values to an arbitrary length with just the the angle. Pretend someone is standing at hex 4, 4 and shoots a bullet at angle 30. Which hexes will it cross? In the case of angle 30 where the angle is exactly between two hexes, default to the clockwise hex. I think there must be an elegant solution and at a certain point the number of "straight" moves vs. shifts "right" or "left" must form a repeating pattern. Furthermore, for a given angle, it will only shift right or left at some repeating interval, but never both. How do you calculate this? My grid uses x, y, (z) coordinates with "pointy top" hexes.

The function I'm trying to write would look like this: getXYOffsets(angle):Array of int;

The return value being a list of x, y offsets used to calculate the next hex's xy indefinitely (like I said, the offset pattern will repeat at some point). For example, angle 0 will return an array of [1, 0] because a line shot that direction will move in the x direction infinitely and I just loop over that 2 value array to find my next x, y coordinates indefinitely. For second example, angle 30 will return an array of [0, 1, 1, 0] because I would draw my line from 0, 0 -> 0, 1 -> 1, 1 -> 1, 2 -> 2, 2... indefinitely. Obviously, less roundable angles will give longer returns arrays because you might have straight stretches that last a long time before finally "shifting". That's ok. I'll limit that after I get a solution to this math problem.

I just know this calculation is possible but my math is too weak to solve it. Any help would be SO appreciated!

Answer 1

Given a starting point x,y, do something like this:

1. For each adjacent cell (six of them), find the projection of the adjacent cell's center onto the direction ray.

2. Pick smallest one (distance to the ray) - aka the closest one. That is the next cell you'll select. Be sure you're moving in the desired direction, and not 180* from it (backwards), which can be determined by checking the sign of the dot product of your direction ray with a vector from the start position to the candidate cell. You already calculated this in (1), so don't redo it.

3. Advance x,y to the projected point on the ray that you calculated for the cell selected in (2) and calculated in (1).

4. if (still_inside_hex_grid) goto 1. (Please don't use GOTO, or you may be publicly mocked.)

This is a modified DDA algorithm, which may help you with the Googling.

Answer 2

I think I've found the best solution I am mathematically capable of to my problem and which uses a type of method signature I want (one that takes an angle as input and draws a draw to a given length. This code isn't pretty and I would welcome suggestions on how to make it more elegant.

public static function getHexLine(x:int, y:int, angle:Number, steps:int=5):Vector.<int> {
        if (angle < 0) {
            angle += 360;
        }
        //"quad" is a terrible variable name. There are 6 "quadrants": 
        //rb, cb, lb, lt, ct, rt (0, 1, 2, 3, 4, 5)
        //(r = "right", c = "center", l = "left", b = "bottom", t = "top")
        var quad:int = Math.floor(angle / 60);
        //We caculate offsets within an arc for 60 >= angle > 0. 
        //Use "quad" to then calculate the resultant position with the right formula.
        angle %= 60;
        var points:Vector.<int> = new <int>[x, y];
        for (var i:int = 1; i <= steps; i++) {
            var angleIncrAmt:Number = 60 / i;
            var angleIncrCount:int = Math.round(angle / angleIncrAmt); 
            var roundAngle:Number = angleIncrCount * angleIncrAmt;
            if (quad == 0) {
                points.push(
                    x + i - angleIncrCount, 
                    y + angleIncrCount
                );
            } else if (quad == 1) {
                points.push(
                    x - angleIncrCount, 
                    y + i
                );
            } else if (quad == 2) {
                points.push(
                    x - i, 
                    y + i - angleIncrCount
                );
            } else if (quad == 3) {
                //like q 0 but with signs reversed.
                points.push(
                    x - i + angleIncrCount, 
                    y - angleIncrCount
                );
            } else if (quad == 4) {
                //like q 1 but with signs reversed.
                points.push(
                    x + angleIncrCount, 
                    y - i
                );
            } else if (quad == 5) {
                //like q 2 but with signs reversed.
                points.push(
                    x + i, 
                    y - i + angleIncrCount
                );
            }
        }
        return points;
    }

Note that for javascript and ActionScript I would replace the if statement in the loop with a function call and assign that function before entering the loop. There's no reason to continually check "quad" once the loop begins that way. I haven't done that here in case anyone is using a language that doesn't treat functions as objects or allow lambdas (like Java pre-1.8 etc.).