Repository: ManevilleF/hexx
Pull request #72 (2023-04-04 08:54:55)

Direction way
# Problem to solve

The current `direction_to` and `diagonal_to` methods can produce inaccurate results, as sometimes there is a *Tie*  between two directions.
As a consequence, the `corner_wedge` produces some inaccuracies.

# Solution

Added a `DirectionalWay` enum which can represent both a single direction and a *tie* and two new methods:
- `Hex::way_to`
- `Hex::diagonal_way_to`

This type can be *unwraped* to a single direction, and compared with directions directly


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 7703314..d13cd33 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -13,6 +13,31 @@
 * Added `packed` feature to make `Hex` `repr(C)` (#67)
 * Added an `algorithm` module with a `a_star` implementation (#69)
 
+### Directions to
+
+The *direction_to* functions were reworked to avoid a 
+edge case where on some coordinates two directions can be valid (a *tie*).
+
+* Added new `DirectionWay` type
+* Added `Hex::way_to` which returns a `DirectionWay<Direction>`
+* Added `Hex::diagonal_way_to` which returns a `DirectionWay<DiagonalDirection>`
+* Deprecated `Hex::direction_to` in favor of `way_to`
+* Deprecated `Hex::diagonal_to` in favor of `diagonal_way_to`
+
+This type can represent the classic *Single* case (One direction) or the *Tie*. This may
+seem like an over complication, but `DirectionWay<T>` implements `PartialEq<T>`, which means
+you can still do this:
+
+```rust
+let a = hex(1, 0);
+let b = hex(43, 12);
+if a.way_to(b) == Direction::Top {
+    //
+}
+```
+
+But now with accurate results !
+
 ### ExactSizeIterator
 
 * (**BREAKING**) `Hex::ring` now returns a `ExactSizeIterator` instead of a `Vec` (#68)
diff --git a/README.md b/README.md
index a5ce192..a79d6b1 100644
--- a/README.md
+++ b/README.md
@@ -79,8 +79,8 @@
  // Rotate `point_b` around `point_a` by 2 times 60 degrees clockwise
  let rotated = point_b.rotate_right_around(point_a, 2);
  // Find the direction between the two points
- let dir_a = point_a.direction_to(point_b);
- let dir_b = point_b.direction_to(point_a);
+ let dir_a = point_a.main_direction_to(point_b);
+ let dir_b = point_b.main_direction_to(point_a);
  assert!(dir_a == -dir_b);
  // Compute a wedge from `point_a` to `point_b`
  let wedge = point_a.wedge_to(point_b);
diff --git a/benches/length.rs b/benches/length.rs
index 5d8ec59..b933d36 100644
--- a/benches/length.rs
+++ b/benches/length.rs
@@ -9,7 +9,7 @@ const fn old_hex_length(hex: Hex) -> i32 {
 pub fn length_benchmark(c: &mut Criterion) {
     let mut group = c.benchmark_group("Hex Length");
     group.significance_level(0.1).sample_size(1_000);
-    let dist = 1_000_000;
+    let dist = 100_000;
 
     group.bench_with_input(BenchmarkId::new("Length", dist), &dist, |b, dist| {
         b.iter(|| Hex::length(Hex::splat(*dist)))
diff --git a/benches/lines.rs b/benches/lines.rs
index a52043a..576d61b 100644
--- a/benches/lines.rs
+++ b/benches/lines.rs
@@ -4,12 +4,12 @@ use hexx::*;
 pub fn line_benchmark(c: &mut Criterion) {
     let mut group = c.benchmark_group("Hex line");
     group.significance_level(0.1).sample_size(1_000);
-    let dist = 1_000_000;
+    let dist = 100_000;
 
     group.bench_with_input(BenchmarkId::new("Line", dist), &dist, |b, dist| {
         b.iter(|| {
             let p = black_box(Hex::ZERO);
-            p.line_to(black_box(Hex::splat(*dist)))
+            p.line_to(black_box(Hex::splat(*dist))).collect::<Vec<_>>()
         })
     });
     group.finish();
diff --git a/benches/rings.rs b/benches/rings.rs
index a8bd464..92ee4af 100644
--- a/benches/rings.rs
+++ b/benches/rings.rs
@@ -3,20 +3,20 @@ use hexx::*;
 
 pub fn rings_benchmark(c: &mut Criterion) {
     let mut group = c.benchmark_group("Hex Rings");
-    group.significance_level(0.1).sample_size(1_000);
-    let dist: u32 = 100_000;
+    group.significance_level(0.1).sample_size(100);
+    let dist: u32 = 1000;
 
     group.bench_with_input(BenchmarkId::new("Ring", dist), &dist, |b, dist| {
-        b.iter(|| Hex::ring(black_box(Hex::ZERO), *dist))
+        b.iter(|| Hex::ring(black_box(Hex::ZERO), *dist).collect::<Vec<_>>())
     });
     group.bench_with_input(BenchmarkId::new("Rings", dist), &dist, |b, dist| {
-        b.iter(|| Hex::rings(black_box(Hex::ZERO), 0..=*dist))
+        b.iter(|| Hex::rings(black_box(Hex::ZERO), 0..=*dist).collect::<Vec<_>>())
     });
     group.bench_with_input(BenchmarkId::new("Spiral Rings", dist), &dist, |b, dist| {
-        b.iter(|| Hex::spiral_range(black_box(Hex::ZERO), 0..=*dist))
+        b.iter(|| Hex::spiral_range(black_box(Hex::ZERO), 0..=*dist).collect::<Vec<_>>())
     });
     group.bench_with_input(BenchmarkId::new("Range", dist), &dist, |b, dist| {
-        b.iter(|| Hex::range(black_box(Hex::ZERO), *dist))
+        b.iter(|| Hex::range(black_box(Hex::ZERO), *dist).collect::<Vec<_>>())
     });
     group.finish();
 }
diff --git a/benches/wedges.rs b/benches/wedges.rs
index 3bd63ae..c1a980d 100644
--- a/benches/wedges.rs
+++ b/benches/wedges.rs
@@ -3,14 +3,33 @@ use hexx::*;
 
 pub fn wedge_benchmark(c: &mut Criterion) {
     let mut group = c.benchmark_group("Hex Wedge");
-    group.significance_level(0.1).sample_size(1_000);
-    let dist = 1_000_000;
+    group.significance_level(0.1).sample_size(100);
+    let dist = 1000;
 
     group.bench_with_input(BenchmarkId::new("Wedge", dist), &dist, |b, dist| {
-        b.iter(|| Hex::full_wedge(black_box(Hex::ZERO), *dist as u32, DiagonalDirection::Left))
+        b.iter(|| {
+            Hex::wedge(
+                black_box(Hex::ZERO),
+                0..=*dist as u32,
+                DiagonalDirection::Left,
+            )
+            .collect::<Vec<_>>()
+        })
+    });
+    group.bench_with_input(BenchmarkId::new("Full Wedge", dist), &dist, |b, dist| {
+        b.iter(|| {
+            Hex::full_wedge(black_box(Hex::ZERO), *dist as u32, DiagonalDirection::Left)
+                .collect::<Vec<_>>()
+        })
     });
     group.bench_with_input(BenchmarkId::new("Triangle", dist), &dist, |b, dist| {
-        b.iter(|| shapes::triangle(*dist as u32))
+        b.iter(|| shapes::triangle(*dist as u32).collect::<Vec<_>>())
+    });
+    group.bench_with_input(BenchmarkId::new("Corner Wedge", dist), &dist, |b, dist| {
+        b.iter(|| {
+            Hex::corner_wedge(black_box(Hex::ZERO), 0..=*dist as u32, Direction::Top)
+                .collect::<Vec<_>>()
+        })
     });
     group.finish();
 }
diff --git a/src/direction/mod.rs b/src/direction/mod.rs
index b82e206..88c652d 100644
--- a/src/direction/mod.rs
+++ b/src/direction/mod.rs
@@ -11,9 +11,12 @@ mod impls;
 /// Test module
 #[cfg(test)]
 mod tests;
+/// Direction way module
+pub(crate) mod way;
 
 pub use diagonal_direction::DiagonalDirection;
 pub use hex_direction::Direction;
+pub use way::DirectionWay;
 
 /// Angle constants used for directions
 pub mod angles {
diff --git a/src/direction/way.rs b/src/direction/way.rs
new file mode 100644
index 0000000..5ca8808
--- /dev/null
+++ b/src/direction/way.rs
@@ -0,0 +1,117 @@
+use std::ops::Neg;
+
+use crate::{DiagonalDirection, Direction};
+
+/// Describes a direction way, which can be a `Single` direction or a `Tie` betwen two directions.
+///
+/// # Comparison
+///
+/// to compare it with its inner [`Direction`] or [`DiagonalDirection`] you can use
+/// `Self::contains` or the [`PartialEq`] implementation:
+///
+/// ```rust
+/// # use hexx::*;
+/// let a = hex(1,4);
+/// let b = hex(6,-2);
+/// let way = a.way_to(b);
+/// let diag_way = a.diagonal_way_to(b);
+/// if way == Direction::Top {
+///   // do something
+/// }
+/// if diag_way == DiagonalDirection::Left {
+///   // do something
+/// }
+/// ```
+///
+/// You can also `unwrap` the way to safely retrieve a single direction, with potential inaccuracy
+/// in case of a `Tie`
+pub enum DirectionWay<T> {
+    /// Single direction
+    Single(T),
+    /// Tie between two directions
+    Tie([T; 2]),
+}
+
+pub trait Way: Copy + Neg<Output = Self> {
+    fn left(self) -> Self;
+    fn right(self) -> Self;
+}
+
+impl<T: PartialEq> PartialEq<T> for DirectionWay<T> {
+    fn eq(&self, other: &T) -> bool {
+        self.contains(other)
+    }
+}
+
+impl<T> DirectionWay<T> {
+    #[inline]
+    #[must_use]
+    #[allow(clippy::missing_const_for_fn)]
+    /// Resolves the current way and returns the `Single` direction or the first of the two in `Tie`.
+    pub fn unwrap(self) -> T {
+        match self {
+            Self::Single(v) | Self::Tie([v, _]) => v,
+        }
+    }
+
+    #[inline]
+    #[must_use]
+    /// Does the way include the given `dir` ?
+    pub fn contains(&self, dir: &T) -> bool
+    where
+        T: PartialEq,
+    {
+        match self {
+            Self::Single(d) => d.eq(dir),
+            Self::Tie([a, b]) => a.eq(dir) || b.eq(dir),
+        }
+    }
+}
+
+impl<T: Way> DirectionWay<T> {
+    #[inline]
+    pub(crate) fn way_from(is_neg: bool, eq_left: bool, eq_right: bool, dir: T) -> Self {
+        match [is_neg, eq_left, eq_right] {
+            [false, true, _] => Self::Tie([dir, dir.left()]),
+            [true, true, _] => Self::Tie([-dir, (-dir).left()]),
+            [false, _, true] => Self::Tie([dir, dir.right()]),
+            [true, _, true] => Self::Tie([-dir, (-dir).right()]),
+            [true, _, _] => Self::Single(-dir),
+            _ => Self::Single(dir),
+        }
+    }
+}
+
+impl<T> From<T> for DirectionWay<T> {
+    #[inline]
+    fn from(value: T) -> Self {
+        Self::Single(value)
+    }
+}
+
+impl<T> From<[T; 2]> for DirectionWay<T> {
+    #[inline]
+    fn from(value: [T; 2]) -> Self {
+        Self::Tie(value)
+    }
+}
+
+impl Way for Direction {
+    fn left(self) -> Self {
+        self.left()
+    }
+
+    fn right(self) -> Self {
+        self.right()
+    }
+}
+
+impl Way for DiagonalDirection {
+    fn left(self) -> Self {
+        self.left()
+    }
+
+    fn right(self) -> Self {
+        self.right()
+    }
+}
diff --git a/src/hex/mod.rs b/src/hex/mod.rs
index 26c3152..f412846 100644
--- a/src/hex/mod.rs
+++ b/src/hex/mod.rs
@@ -15,7 +15,7 @@ mod tests;
 pub(crate) use iter::ExactSizeHexIterator;
 pub use iter::HexIterExt;
 
-use crate::{DiagonalDirection, Direction};
+use crate::{DiagonalDirection, Direction, DirectionWay};
 use glam::{IVec2, IVec3, Vec2};
 use std::cmp::{max, min};
 
@@ -625,39 +625,78 @@ impl Hex {
     }
 
     #[must_use]
-    /// Find in which [`DiagonalDirection`] wedge `rhs` is relative to `self`
+    #[doc(alias = "diagonal_direction_to")]
+    #[deprecated(
+        since = "0.6.0",
+        note = "Prefer `diagonal_way_to` for more accurate result or `main_diagonal_to`"
+    )]
+    /// Find in which [`DiagonalDirection`] wedge `rhs` is relative to `self`.
+    ///
+    /// > This method can be innaccurate in case of a *tie* between directions, prefer
+    /// [`Self::diagonal_way_to`] instead
     pub fn diagonal_to(self, rhs: Self) -> DiagonalDirection {
+        self.main_diagonal_to(rhs)
+    }
+
+    #[must_use]
+    /// Find in which [`DiagonalDirection`] wedge `rhs` is relative to `self`.
+    ///
+    /// > This method can be innaccurate in case of a *tie* between directions, prefer
+    /// using [`Self::diagonal_way_to`] instead
+    pub fn main_diagonal_to(self, rhs: Self) -> DiagonalDirection {
+        self.diagonal_way_to(rhs).unwrap()
+    }
+
+    #[must_use]
+    /// Find in which [`DiagonalDirection`] wedge `rhs` is relative to `self`
+    pub fn diagonal_way_to(self, rhs: Self) -> DirectionWay<DiagonalDirection> {
         let [x, y, z] = (rhs - self).to_cubic_array();
         let [xa, ya, za] = [x.abs(), y.abs(), z.abs()];
-        let (v, dir) = match xa.max(ya).max(za) {
-            v if v == xa => (x, DiagonalDirection::Right),
-            v if v == ya => (y, DiagonalDirection::BottomLeft),
-            v if v == za => (z, DiagonalDirection::TopLeft),
-            _ => unreachable!(),
-        };
-        if v < 0 {
-            -dir
-        } else {
-            dir
+        match xa.max(ya).max(za) {
+            v if v == xa => {
+                DirectionWay::way_from(x < 0, xa == ya, xa == za, DiagonalDirection::Right)
+            }
+            v if v == ya => {
+                DirectionWay::way_from(y < 0, ya == za, ya == xa, DiagonalDirection::BottomLeft)
+            }
+            _ => DirectionWay::way_from(z < 0, za == xa, za == ya, DiagonalDirection::TopLeft),
         }
     }
 
     #[must_use]
+    #[deprecated(
+        since = "0.6.0",
+        note = "Prefer `way_to` for more accurate result or `main_direction_to"
+    )]
     /// Find in which [`Direction`] wedge `rhs` is relative to `self`
+    ///
+    /// > This method can be innaccurate in case of a *tie* between directions, prefer
+    /// using [`Self::way_to`] instead
     pub fn direction_to(self, rhs: Self) -> Direction {
+        self.main_direction_to(rhs)
+    }
+
+    /// Find in which [`Direction`] wedge `rhs` is relative to `self`
+    ///
+    /// > This method can be innaccurate in case of a *tie* between directions, prefer
+    /// using [`Self::way_to`] for accuracy
+    #[must_use]
+    pub fn main_direction_to(self, rhs: Self) -> Direction {
+        self.way_to(rhs).unwrap()
+    }
+
+    #[must_use]
+    /// Find in which [`Direction`] wedge `rhs` is relative to `self`
+    pub fn way_to(self, rhs: Self) -> DirectionWay<Direction> {
         let [x, y, z] = (rhs - self).to_cubic_array();
         let [x, y, z] = [y - x, z - y, x - z];
         let [xa, ya, za] = [x.abs(), y.abs(), z.abs()];
-        let (v, dir) = match xa.max(ya).max(za) {
-            v if v == xa => (x, Direction::BottomLeft),
-            v if v == ya => (y, Direction::Top),
-            v if v == za => (z, Direction::BottomRight),
-            _ => unreachable!(),
-        };
-        if v < 0 {
-            -dir
-        } else {
-            dir
+        match xa.max(ya).max(za) {
+            v if v == xa => {
+                DirectionWay::way_from(x < 0, xa == ya, xa == za, Direction::BottomLeft)
+            }
+            v if v == ya => DirectionWay::way_from(y < 0, ya == za, ya == xa, Direction::Top),
+            _ => DirectionWay::way_from(z < 0, za == xa, za == ya, Direction::BottomRight),
         }
     }
 
diff --git a/src/hex/rings.rs b/src/hex/rings.rs
index 73d0e1b..b6a508b 100644
--- a/src/hex/rings.rs
+++ b/src/hex/rings.rs
@@ -218,7 +218,7 @@ impl Hex {
         clockwise: bool,
     ) -> impl ExactSizeIterator<Item = Self> {
         let range = self.unsigned_distance_to(rhs);
-        let direction = self.diagonal_to(rhs);
+        let direction = self.diagonal_way_to(rhs).unwrap();
         self.custom_full_wedge(range, direction, clockwise)
     }
 
@@ -303,7 +303,7 @@ impl Hex {
         let left = self.wedge(range.clone(), direction.diagonal_left());
         let right = self.wedge(range, direction.diagonal_right());
         left.chain(right)
-            .filter(move |h| self.direction_to(*h) == direction)
+            .filter(move |h| self.way_to(*h) == direction)
     }
 
     /// Retrieves all successive [`Hex`] half ring edges from `self` to `rhs`
@@ -311,7 +311,7 @@ impl Hex {
     /// See also [`Self::corner_wedge_to`] and [`Self::wedge_to`]
     pub fn corner_wedge_to(self, rhs: Self) -> impl Iterator<Item = Self> {
         let range = self.unsigned_distance_to(rhs);
-        self.corner_wedge(0..=range, self.direction_to(rhs))
+        self.corner_wedge(0..=range, self.way_to(rhs).unwrap())
     }
 
     #[allow(clippy::cast_possible_truncation)]
diff --git a/src/lib.rs b/src/lib.rs
index 02698e0..d9a2e3f 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -66,8 +66,8 @@
 //! // Rotate `point_b` around `point_a` by 2 times 60 degrees clockwise
 //! let rotated = point_b.rotate_right_around(point_a, 2);
 //! // Find the direction between the two points
-//! let dir_a = point_a.direction_to(point_b);
-//! let dir_b = point_b.direction_to(point_a);
+//! let dir_a = point_a.main_direction_to(point_b);
+//! let dir_b = point_b.main_direction_to(point_a);
 //! assert!(dir_a == -dir_b);
 //! // Compute a wedge from `point_a` to `point_b`
 //! let wedge = point_a.wedge_to(point_b);


Test patch:
diff --git a/src/hex/tests.rs b/src/hex/tests.rs
index 83ee9de..e56acbc 100644
--- a/src/hex/tests.rs
+++ b/src/hex/tests.rs
@@ -226,8 +226,8 @@ fn rotation() {
     let neighbors = Hex::ZERO.all_neighbors();
     for elems in neighbors.windows(2) {
         let [next, prev] = [elems[0], elems[1]];
-        let prev_dir = Hex::ZERO.direction_to(prev);
-        let next_dir = Hex::ZERO.direction_to(next);
+        let prev_dir = Hex::ZERO.way_to(prev).unwrap();
+        let next_dir = Hex::ZERO.way_to(next).unwrap();
         assert_eq!(prev.right(), next);
         assert_eq!(next.left(), prev);
         assert_eq!(prev_dir.right(), next_dir);