hexagonal_pathfinding_astar 1.0.0

A-Star pathfinding algorithm tailored for traversing a bespoke collection of weighted hexagons
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

//! This library is an implementation of the A-Star pathfinding algorithm tailored for traversing a bespoke
//! collection of weighted hexagons. It's intended to calculate the most optimal path to a target
//! hexagon where you are traversing from the centre of one hexagon to the next along a line orthogonal to a hexagon edge.
//! The algorithm has been implemented for Offset, Axial and Cubic coordinate systems with a selection of helper functions
//! which can be used to convert between coordinate systems, calculate distances between hexagons and more.
//!
//! 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.
//!
//! E.g
//! ```txt
//!    ___________
//!   /     ^     \
//!  /      |      \
//! /  C    |       \
//! \       |       /
//!  \      ▼      /
//!   \___________/
//! ```
//!
//! Which influences the calculation to find the best path.
//!
//! ## Hexagon Grids and  Orientation
//!
//! There are different ways in which a hexagon grid can be portrayed which in turn affects the discoverable neighbouring hexagons for path traversal.
//!
//! ### Axial Coordinates
//!
//! 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.
//!
//! ```txt
//!              _______
//!             /   0   \
//!     _______/         \_______
//!    /  -1   \      -1 /   1   \
//!   /         \_______/         \
//!   \       0 /   q   \      -1 /
//!    \_______/         \_______/
//!    /  -1   \       r /   1   \
//!   /         \_______/         \
//!   \       1 /   0   \       0 /
//!    \_______/         \_______/
//!            \       1 /
//!             \_______/
//! ```
//!
//! ### Cubic Coordinates
//!
//! 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.
//!
//! A Cubic grid is structured such:
//!
//! ```txt
//!              _______
//!             /   0   \
//!     _______/         \_______
//!    /  -1   \ 1    -1 /   1   \
//!   /         \_______/         \
//!   \ 1     0 /   x   \ 0    -1 /
//!    \_______/         \_______/
//!    /  -1   \ y     z /   1   \
//!   /         \_______/         \
//!   \ 0     1 /   0   \ -1    0 /
//!    \_______/         \_______/
//!            \ -1    1 /
//!             \_______/
//! ```
//!
//! ### Offset Coordinates
//!
//! 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).
//!
//! Each node has a label defining its position, known as `(column, row)`.
//!
//! #### Flat Topped - odd columns shifted up
//!
//! ```txt
//!              _______
//!             /       \
//!     _______/  (1,1)  \_______
//!    /       \         /       \
//!   /  (0,1)  \_______/  (2,1)  \
//!   \         /       \         /
//!    \_______/  (1,0)  \_______/
//!    /       \         /       \
//!   /  (0,0)  \_______/  (2,0)  \
//!   \         /       \         /
//!    \_______/         \_______/
//! ```
//!
//! #### Flat Topped - odd columns shifted down
//!
//! ```txt
//!     _______           _______
//!    /       \         /       \
//!   /  (0,1)  \_______/  (2,1)  \
//!   \         /       \         /
//!    \_______/  (1,1)  \_______/
//!    /       \         /       \
//!   /  (0,0)  \_______/  (2,0)  \
//!   \         /       \         /
//!    \_______/  (1,0)  \_______/
//!            \         /
//!             \_______/
//! ```
//!
//! ### Pointy Topped - odd rows shifted right
//!
//! Please refer to the README of the proect for an illustration - ascii hexagons with pointy tops are very hard to draw.
//!
//! ### Pointy Topped - odd rows shifted left
//!
//! Please refer to the README of the proect for an illustration - ascii hexagons with pointy tops are very hard to draw.

pub mod astar_axial;
pub mod astar_cubic;
pub mod astar_offset;
pub mod helpers;

/// Specifies the orientation of the hexagon space in Offset layouts. This is
/// important for determining the available neighbouring nodes during expansion.
///
/// Flat-top odd columns moved up
///```txt
///       ___
///   ___/ O \
///  / E \___/
///  \___/
///```
/// Flat-top odd columns moved down
/// ```txt
///   ___
///  / E \___
///  \___/ O \
///      \___/
/// ```
pub enum HexOrientation {
	FlatTopOddUp,
	FlatTopOddDown,
	PointyTopOddRight,
	PointyTopOddLeft,
}