1
\$\begingroup\$

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!

Example of what I'm trying to do

\$\endgroup\$
4
  • \$\begingroup\$ You're overthinking it a bit by having a distinction between "shifting" and "straight". A simpler heuristic would view all six directions equally (e.g. @3Dave's answer). I'm also curious about the assertion that the pattern would repeat. For that to happen, the ray has to precisely hit the center of another cell along its path. Is there proof that this would happen for any arbitrary angle? \$\endgroup\$
    – Konafa
    Jul 31, 2018 at 1:17
  • \$\begingroup\$ I can't prove it, but I know it's true. :-) If you extend the line infinitely, it'll eventually hit the center of a hex. This is why I would limit the possible intervals of the angle in the end result. But I'm looking into @3Dave's answer. I may need to re-ask this question. \$\endgroup\$
    – jpwrunyan
    Jul 31, 2018 at 17:27
  • \$\begingroup\$ If you moved your angle slightly to the right, the line goes through (4,5) then (5,5) then (4,6) then (5,6). It's wibbly-wobbly. That'd probably be a good test case for whatever solution you come up with. (I wish I knew the answer to this question but I don't) \$\endgroup\$
    – amitp
    Aug 1, 2018 at 5:19
  • \$\begingroup\$ I think it may be possible to use a 2d DDA on the x/y coordinates after figuring out the angle on the X/Y plane of the hex grid. Not quite sure, but I'm going to try implementing it this weekend. If it works, I'll post the solution. If it doesn't I'll probably re-ask this question differently. \$\endgroup\$
    – jpwrunyan
    Aug 1, 2018 at 19:23

2 Answers 2

0
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Want to quickly say thanks for pointing out that this is a "DDA algorithm". Knowing the name of the concept helps immensely! Will get back to you once I get this answer to work. \$\endgroup\$
    – jpwrunyan
    Jul 31, 2018 at 15:58
  • \$\begingroup\$ Ok, so I actually store my hexes using x, y, z coordinates (as cubes in 3-d space). So it seems to me I need a DDA algorithm to find x, y, z coordinates at a certain angle... \$\endgroup\$
    – jpwrunyan
    Jul 31, 2018 at 17:17
  • \$\begingroup\$ Actually, I don't think a DDA algorithm is quite right. The reason for this is because a DDA algorithm can skip diagonally. If this were a square grid, I'd need an algorithm that could trace an orthogonal path from a given angle. \$\endgroup\$
    – jpwrunyan
    Aug 4, 2018 at 23:40
  • \$\begingroup\$ Ok, so I think this answer would have been better than the one I came up with, but at step #2 above you glossed over too much math for me to follow. I'd need you to break this down a bit more. Although I used a sort of DDA in my code, I'm not sure I did so in the fashion you intended. \$\endgroup\$
    – jpwrunyan
    Aug 5, 2018 at 21:09
0
\$\begingroup\$

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

Behold! It works.

\$\endgroup\$
2
  • \$\begingroup\$ Um... Didn't you catch a bug in that screenshot? (1, 2, -3) is a false positive and (2, 1, -3) is a false negative... \$\endgroup\$
    – Quentin
    Aug 6, 2018 at 8:40
  • \$\begingroup\$ Yes. That's part of why I uploaded it. And then I figured out the bug and edited the post but didn't update the picture. I actually figured out a much better way to do this and so my answer will be edited again in a moment. \$\endgroup\$
    – jpwrunyan
    Aug 7, 2018 at 0:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .