hexagonal_pathfinding_astar/
lib.rs

1//! This library is an implementation of the A-Star pathfinding algorithm tailored for traversing a bespoke
2//! collection of weighted hexagons. It's intended to calculate the most optimal path to a target
3//! hexagon where you are traversing from the centre of one hexagon to the next along a line orthogonal to a hexagon edge.
4//! The algorithm has been implemented for Offset, Axial and Cubic coordinate systems with a selection of helper functions
5//! which can be used to convert between coordinate systems, calculate distances between hexagons and more.
6//!
7//! The calculations are dpendent on the layout of your hexagon grid (coordinate system) and each hexagon has an associated complexity of traversing a particular node.
8//!
9//! E.g
10//! ```txt
11//!    ___________
12//!   /     ^     \
13//!  /      |      \
14//! /  C    |       \
15//! \       |       /
16//!  \      ▼      /
17//!   \___________/
18//! ```
19//!
20//! Which influences the calculation to find the best path.
21//!
22//! ## Hexagon Grids and  Orientation
23//!
24//! There are different ways in which a hexagon grid can be portrayed which in turn affects the discoverable neighbouring hexagons for path traversal.
25//!
26//! ### Axial Coordinates
27//!
28//! Axial coordinates use the convention of `q` for column and `r` for row. In the example below the `r` is a diagonal row. For hexagon layouts where the pointy tops are facing up the calculations remain exactly the same as you're effectively just rotating the grid by 30 degrees making `r` horizontal and `q` diagonal.
29//!
30//! ```txt
31//!              _______
32//!             /   0   \
33//!     _______/         \_______
34//!    /  -1   \      -1 /   1   \
35//!   /         \_______/         \
36//!   \       0 /   q   \      -1 /
37//!    \_______/         \_______/
38//!    /  -1   \       r /   1   \
39//!   /         \_______/         \
40//!   \       1 /   0   \       0 /
41//!    \_______/         \_______/
42//!            \       1 /
43//!             \_______/
44//! ```
45//!
46//! ### Cubic Coordinates
47//!
48//! You can represent a hexagon grid through three primary axes. We denote the axes `x`, `y` and `z`. The Cubic coordinate system is very useful as some calculations cannot be performed through other coordinate systems (they don't contain enough data), fortunately there are means of converting other systems to Cubic to make calculations easy/possible.
49//!
50//! A Cubic grid is structured such:
51//!
52//! ```txt
53//!              _______
54//!             /   0   \
55//!     _______/         \_______
56//!    /  -1   \ 1    -1 /   1   \
57//!   /         \_______/         \
58//!   \ 1     0 /   x   \ 0    -1 /
59//!    \_______/         \_______/
60//!    /  -1   \ y     z /   1   \
61//!   /         \_______/         \
62//!   \ 0     1 /   0   \ -1    0 /
63//!    \_______/         \_______/
64//!            \ -1    1 /
65//!             \_______/
66//! ```
67//!
68//! ### Offset Coordinates
69//!
70//! Offset assumes that all hexagons have been plotted across a plane where the origin points sits at the bottom left (in theory you can have negative coordinates expanding into the other 3 quadrants but I haven't tested these here).
71//!
72//! Each node has a label defining its position, known as `(column, row)`.
73//!
74//! #### Flat Topped - odd columns shifted up
75//!
76//! ```txt
77//!              _______
78//!             /       \
79//!     _______/  (1,1)  \_______
80//!    /       \         /       \
81//!   /  (0,1)  \_______/  (2,1)  \
82//!   \         /       \         /
83//!    \_______/  (1,0)  \_______/
84//!    /       \         /       \
85//!   /  (0,0)  \_______/  (2,0)  \
86//!   \         /       \         /
87//!    \_______/         \_______/
88//! ```
89//!
90//! #### Flat Topped - odd columns shifted down
91//!
92//! ```txt
93//!     _______           _______
94//!    /       \         /       \
95//!   /  (0,1)  \_______/  (2,1)  \
96//!   \         /       \         /
97//!    \_______/  (1,1)  \_______/
98//!    /       \         /       \
99//!   /  (0,0)  \_______/  (2,0)  \
100//!   \         /       \         /
101//!    \_______/  (1,0)  \_______/
102//!            \         /
103//!             \_______/
104//! ```
105//!
106//! ### Pointy Topped - odd rows shifted right
107//!
108//! Please refer to the README of the proect for an illustration - ascii hexagons with pointy tops are very hard to draw.
109//!
110//! ### Pointy Topped - odd rows shifted left
111//!
112//! Please refer to the README of the proect for an illustration - ascii hexagons with pointy tops are very hard to draw.
113
114pub mod astar_axial;
115pub mod astar_cubic;
116pub mod astar_offset;
117pub mod helpers;
118
119/// Specifies the orientation of the hexagon space in Offset layouts. This is
120/// important for determining the available neighbouring nodes during expansion.
121///
122/// Flat-top odd columns moved up
123///```txt
124///       ___
125///   ___/ O \
126///  / E \___/
127///  \___/
128///```
129/// Flat-top odd columns moved down
130/// ```txt
131///   ___
132///  / E \___
133///  \___/ O \
134///      \___/
135/// ```
136pub enum HexOrientation {
137	FlatTopOddUp,
138	FlatTopOddDown,
139	PointyTopOddRight,
140	PointyTopOddLeft,
141}
hexagonal_pathfinding_astar/lib.rs

hexagonal_pathfinding_astar/
lib.rs
