Hex division is unstable

[nuggetInc]

There are two major problems with the current Hex division implementations:

1. Only the axial coordinates are divided. Not considering the third axis gives unstable results (e.g. Hex(2, -1, -1) / 2 == Hex(1, 0, -1) while Hex(1, 1, -2) / 2 == Hex(0, 0, 0)).
2. Hexes shouldn’t be divisible by another hex (or at least I don’t see a way). Often when dividing hexes the resulting hex is in a location that doesn’t fully make sense (e.g. Hex(1, -1, 0) / Hex(-1, 1, 0) == Hex(-1, -1, 2) which is further from the center than the initial two).

One possible solution for dividing by integers would be to use floating point numbers and round those, but this might result in similar issues due to rounding errors.

It might have to be considered removing hex division altogether until a solid solution is found.

This is a first issue, feedback is appreciated.

[ManevilleF]

Thank you for noticing this !

1. The third axis (cubic coordinates) is always equal to -x-y in order to have x + y + z == 0. Therefore I don't use it as I can compute it from the axial coordinates.

2. I agree that the division doesn't make much sense unlike Add, Sub and Mul. I implemented it as glam does it for IVec2

I think any integer-based primitive will have the same rounding issue. Therefore I only see the following solutions:

• Remove division altogether as you suggest
• Implement the % operator (Rem) and add documentation on the rounding issue.

What do you think ?

[nuggetInc]

There might actually be a third option where you only divide the two largest axis or the two axis with the largest remainder (I'm not completely sure which one will work best).

This will probably still give issues with deciding exactly where exactly to place the new hex, but it at least prevents skipping too many hexes (e.g. Hex(1, 1, -2) / 2 == Hex(0, 0, 0)).

Otherwise adding documentation on this issue will help a lot with any possible confusion.

[ManevilleF]

Again, there are only 2 axis, the third one is just a computed value.

I think the solution to your problem and not skip tiles is to use floating points, either:

• Divide as f32 and use Hex::round
• Move to world space with hex_to_world_pos, divide, and then go back to the hexagon space with world_pos_to_hex

Or, to use a lerp implementation maybe

[nuggetInc]

Using hex_to_world_pos, divide and world_pos_to_hex would result in a dependency on a layout instance.

I understand that the Hex struct only stores x and y, and that z is then computed with -x - y. But this doesn't mean you can't use z in functions.

It's easy to create a temporary variable for z, take for example this modified round function from https://www.redblobgames.com/grids/hexagons/implementation.html#rounding

Hex hex_round(FractionalHex h) {
    int x = int(round(h.q));
    int y = int(round(h.r));
    int z = int(round(-h.q - h.r));
    double x_diff = abs(q - h.q);
    double y_diff = abs(r - h.r);
    double z_diff = abs(s - (-h.q - h.r);
    if (q_diff > r_diff and q_diff > s_diff) {
        q = -r - s;
    } else if (r_diff > s_diff) {
        r = -q - s;
    }
    return Hex(q, r);
}

It still respects the fact we use axial coordinates, but also uses z for the logic.

[ManevilleF]

The z or s "axis" is an arbitrary value, not an axis, that represents the Z position of a cube. You can use it of course, like any value, and it's useful in the Hex rotation methods.

For the rounding, Hex::round uses a different algorithm that doesn't use the zvalue as described in this article but it probably gives the same results (Note, I should probably test both and benchmark them). Therefore I think that doing the following:

fn rounded_div(self, rhs: Self) -> Self {
    let [mut xf, mut yf] = [self.x as f32, self.y as f32];
    xf /= rhs.x as f32;
    yf /= rhs.y as f32;
    Hex::round((xf, yf))
}

Should avoid the classic rounding issue and not skip any Hex

EDIT: To add context, this is the method used in the 'line_to' method, which doesn't skip hexes by lerping and using the rounding method

[nuggetInc]

Looks good to me.

Apologies for not being clearer about what I meant with the z axis, but I'm glad it got sorted out.

All that would be left is to decide on which of these methods should be the default.

[ManevilleF]

@nuggetInc I opened a merge request adressing this.

At this point I'm not sure which division should be the default. Does it make sense to force floating point division on everything by default ? and on the other hand, does it make sense to have classic integer division?

[nuggetInc]

Not completely sure what's the best place to comment on this is now, feel free to direct me.

I personally think it makes most sense to use floating point division even for Div<i32>, because I think the expected (and correct) behavior of rounding should result in a new length equal to the old length divided.

For the case that someone does need the "classic" rounding a divide_lossy method could be added.

[ManevilleF]

I personally think it makes most sense to use floating point division even for Div<i32>, because I think the expected (and correct) behavior of rounding should result in a new length equal to the old length divided.

If you divide with rounding you have no guarantee that the new length will be equal to the old length divided, I tested this in #21 (check the tests) and did not have the expected result

[nuggetInc]

It seems you're right. certain hex positions such as (-1, 3) land on a border when dividing by 2 and thus are subject to rounding errors.

If we consider the length as the "correct" value, then we might as well use it for the division. I just came up with this algorithm by looking at a grid of hexes and the way lines avoid rounding errors:

fn divide(self, rhs: i32) -> Self {
    let new_length = self.length() / rhs;

    let s = new_length as f32 / self.length() as f32;
    Self::ZERO.lerp(self, s)
}

The way it works is we first divide the length (lets say 3) to find the new expected length (dividing by 2 so 1). Then we figure out how far along the new length is along the old (in this case 1/3). And at last we use lerp to find a hex at that point.

All previous problems with rounding seem to have been fixed with this solution.

Should we switch to this?

[ManevilleF]

@nuggetInc @alice-i-cecile Could you both review #28 and confirm that the PR correctly adresses the division issue ? Also, I didn't update Div<Self> as I'm not sure what the expected behaviour would be.

After that I will release the 0.3.0