Jump Point Search (JPS) is an branch pruning algorithm that allows path-finding to be computed faster especially in square grids. This is a different approach where I tried optimizing it for hexagonal grids. The end idea is to be able to use this in a spherical geometry and be able to find shortest paths in a soccer-ball-like surface.
https://www.redblobgames.com/grids/hexagons/
https://github.com/juan-zv/hexagonal-jps-visual
For the Jump Point Search demonstration, we need to define the grid, the hexagons and their behavior, the JPS forced neighbors and jump points, and the path finding method. In python I created a class for the hexagonal grid with methods for the different parts of the algorithm demonstration.
Each hexagon can have different orientations:
We will follow the flat top orientation and imagine the possible neighbors as follow:
Class Initialization:
class HexGrid:
def __init__(self, grid):
self.grid = grid
self.rows = len(grid)
self.cols = len(grid[0]) if grid else 0
self.directions = {
0: (0, -1), # North
1: (+1,-1), # Northeast
2: (+1, 0), # Southeast
3: (0, +1), # South
4: (-1, 0), # Southwest
5: (-1, -1) # Northwest
}
An example of a grid would be:
grid = [
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 1, 1, 1, 0],
[0, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
]
Where 0 are walkable hexagons and 1 are obstacles.
Because there are different systems to display a hexagonal grid (offset, cube, axial, doubled, etc.) we want to focus on one for now. The offset system is the easiest to understand and we will be using its variants. Depending on what the offset row or columns will be, we call the offset variant a different name. There are even rows, odd rows, even columns, and odd columns as offset variants. these are some examples of what they would look like:
0 1 2 3 4 5 6 7
0 # # # # # # # #
1 # # # # # # # #
2 # # # # # # # #
3 # # # # # # # #
4 # # # # # # # #
5 # # # # # # # #
6 # # # # # # # #
7 # # # # # # # #
Even column offset
# # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # #
Odd column offset
# # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # #
Even row offset
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
Odd row offset
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
For this specific example we will use the Odd Column or Odd-q layout: