Bidirectional A* pathfinding algorithm for H3 hexagonal cells. More...

#include <astar.h>

Inheritance diagram for H3AStar:

Collaboration diagram for H3AStar:

Classes
struct	H3IndexHash
	Hash function for H3Index in unordered containers. More...

struct	Node
	Internal node structure for A* priority queue. More...

Public Member Functions
	H3AStar (QObject *parent=nullptr)
	Constructs an H3AStar pathfinder.

	~H3AStar () override
	Destructor.

std::vector< H3Index >	findShortestPath (H3Index start, H3Index end)
	Finds the shortest path between two H3 cells.

void	setBlockedCells (const std::unordered_set< H3Index > &blocked)
	Sets cells that cannot be traversed (obstacles).

Public Attributes
	: void newCell(H3Index h3Index)

Private Member Functions
std::vector< H3Index >	findPathAtResolution3 (H3Index start, H3Index end, const LatLng &endCoord)
	Finds path at resolution 3 using bidirectional A*.

std::vector< H3Index >	refineEndSegmentGradual (H3Index prevInPath, H3Index parentEnd, H3Index originalEnd, int endRes)
	Refines path segment near the end point to target resolution.

std::vector< H3Index >	refineStartSegmentGradual (H3Index originalStart, H3Index nextInPath, int startRes) const
	Refines path segment near the start point to target resolution.

std::vector< H3Index >	refinePath (const std::vector< H3Index > &pathRes3, H3Index originalStart, H3Index originalEnd, int startRes, int endRes)
	Refines entire coarse path to target resolution.

std::vector< H3Index >	findLocalPathAtResolution (H3Index start, H3Index end, H3Index limitParent) const
	Finds local path within a parent cell boundary.

Static Private Member Functions
static H3Index	findBoundaryCellInDirection (const std::vector< H3Index > &cells, H3Index from, H3Index direction)
	Finds boundary cell in a direction for path refinement.

static std::vector< H3Index >	getChildrenAtResolution (H3Index parent, int resolution)
	Gets all children of a cell at specified resolution.

static std::array< H3Index, MAX_NEIGHBORS >	getNeighbors (H3Index cell)
	Gets the 6 neighbors of a hexagonal cell.

static double	getDistanceBetweenCells (H3Index cell1, H3Index cell2)
	Calculates geographic distance between two cells.

static double	heuristic (H3Index cell, const LatLng &targetCoord)
	Heuristic function for A* (distance to target).

static std::vector< H3Index >	reconstructPath (const std::unordered_map< H3Index, H3Index, H3IndexHash > &previous, H3Index start, H3Index end)
	Reconstructs path from the visited nodes map.

static H3Index	cellToParentRes3 (H3Index index)
	Converts any cell to its parent at resolution 3.

static H3Index	cellToChildRes3 (H3Index index)
	Converts resolution 3 cell to child at original resolution.

Private Attributes
std::unordered_set< H3Index >	blockedCells {}
	Set of blocked (impassable) cells.

Static Private Attributes
static constexpr uint16_t	MAX_CELLS_RES_3 {41'162}
	Maximum number of cells at resolution 3 (~41K cells globally).

static constexpr int	MAX_NEIGHBORS {6}
	Maximum neighbors for a hexagonal cell (always 6).

Detailed Description

Bidirectional A* pathfinding algorithm for H3 hexagonal cells.

The H3AStar class provides an efficient pathfinding implementation that:

Uses bidirectional search (from start and goal simultaneously)
Employs hierarchical resolution refinement (coarse to fine)
Supports obstacle avoidance via blocked cells

Algorithm Complexity

Standard A*: O(b^d)
Bidirectional A*: O(b^(d/2))

Where b = branching factor (6 for hexagons), d = path depth

Example Usage: H3AStar astar;

astar.setBlockedCells(mazeWalls);

// Connect to visualization signal

connect(&astar, &H3AStar::newCell, this, &MyClass::onCellExplored);

// Find path

auto path = astar.findShortestPath(startCell, endCell);

H3AStar
Bidirectional A* pathfinding algorithm for H3 hexagonal cells.
Definition astar.h:45

H3AStar::findShortestPath
std::vector< H3Index > findShortestPath(H3Index start, H3Index end)
Finds the shortest path between two H3 cells.
Definition astar.cpp:12

H3AStar::setBlockedCells
void setBlockedCells(const std::unordered_set< H3Index > &blocked)
Sets cells that cannot be traversed (obstacles).
Definition astar.cpp:10

See also: H3MazeGenerator for maze generation; H3Worker for async execution

Definition at line 45 of file astar.h.

Constructor & Destructor Documentation

◆ H3AStar()

H3AStar::H3AStar ( QObject * parent = nullptr )

explicit

Constructs an H3AStar pathfinder.

Parameters

parent Optional parent QObject for memory management.

Definition at line 6 of file astar.cpp.

◆ ~H3AStar()

H3AStar::~H3AStar ( )

overridedefault

Destructor.

Member Function Documentation

◆ cellToChildRes3()

H3Index H3AStar::cellToChildRes3 ( H3Index index )

staticprivate

Converts resolution 3 cell to child at original resolution.

Definition at line 580 of file astar.cpp.

◆ cellToParentRes3()

H3Index H3AStar::cellToParentRes3 ( H3Index index )

staticprivate

Converts any cell to its parent at resolution 3.

Definition at line 573 of file astar.cpp.

Referenced by findShortestPath().

Here is the caller graph for this function:

◆ findBoundaryCellInDirection()

H3Index H3AStar::findBoundaryCellInDirection	(	const std::vector< H3Index > &	cells,
		H3Index	from,
		H3Index	direction
	)

staticprivate

Finds boundary cell in a direction for path refinement.

Definition at line 448 of file astar.cpp.

Referenced by refineEndSegmentGradual(), and refineStartSegmentGradual().

Here is the caller graph for this function:

◆ findLocalPathAtResolution()

std::vector< H3Index > H3AStar::findLocalPathAtResolution	(	H3Index	start,
		H3Index	end,
		H3Index	limitParent
	)		const

private

Finds local path within a parent cell boundary.

Definition at line 256 of file astar.cpp.

References blockedCells, H3AStar::Node::cell, getDistanceBetweenCells(), getNeighbors(), heuristic(), MAX_CELLS_RES_3, and reconstructPath().

Referenced by refineEndSegmentGradual(), and refineStartSegmentGradual().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ findPathAtResolution3()

std::vector< H3Index > H3AStar::findPathAtResolution3	(	H3Index	start,
		H3Index	end,
		const LatLng &	endCoord
	)

private

Finds path at resolution 3 using bidirectional A*.

Parameters

start	Start cell (will be converted to res 3).
end	End cell (will be converted to res 3).
endCoord	Geographic coordinates of end point for heuristic.

Returns: Path at resolution 3.

Definition at line 74 of file astar.cpp.

References blockedCells, H3AStar::Node::cell, getDistanceBetweenCells(), getNeighbors(), and heuristic().

Referenced by findShortestPath().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ findShortestPath()

std::vector< H3Index > H3AStar::findShortestPath	(	H3Index	start,
		H3Index	end
	)

Finds the shortest path between two H3 cells.

Uses bidirectional A* search with hierarchical resolution refinement:

Searches at resolution 3 for coarse path
Refines start and end segments to target resolution

Parameters

start	The starting H3 cell index.
end	The destination H3 cell index.

Returns: Vector of H3 cell indices representing the path (empty if no path found).

Note: Emits newCell() signal for each explored cell during search.

Warning: Both start and end must be valid H3 indices at the same resolution.

Definition at line 12 of file astar.cpp.

References blockedCells, cellToParentRes3(), ConversionError, CoordinateError, findPathAtResolution3(), InvalidCell, refinePath(), and SameStartEnd.

Referenced by H3_VIEWER::H3Worker::doWork().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ getChildrenAtResolution()

std::vector< H3Index > H3AStar::getChildrenAtResolution	(	H3Index	parent,
		int	resolution
	)

staticprivate

Gets all children of a cell at specified resolution.

Parameters

parent	Parent cell index.
resolution	Target resolution.

Returns: Vector of child cell indices.

Definition at line 485 of file astar.cpp.

Referenced by refineEndSegmentGradual(), and refineStartSegmentGradual().

Here is the caller graph for this function:

◆ getDistanceBetweenCells()

double H3AStar::getDistanceBetweenCells	(	H3Index	cell1,
		H3Index	cell2
	)

staticprivate

Calculates geographic distance between two cells.

Parameters

cell1	First cell index.
cell2	Second cell index.

Returns: Distance in radians.

Definition at line 525 of file astar.cpp.

Referenced by findLocalPathAtResolution(), and findPathAtResolution3().

Here is the caller graph for this function:

◆ getNeighbors()

std::array< H3Index, H3AStar::MAX_NEIGHBORS > H3AStar::getNeighbors ( H3Index cell )

staticprivate

Gets the 6 neighbors of a hexagonal cell.

Parameters

cell	The cell to get neighbors for.

Returns: Array of 6 neighbor indices (0 for invalid/pentagon edges).

Definition at line 504 of file astar.cpp.

Referenced by findLocalPathAtResolution(), and findPathAtResolution3().

Here is the caller graph for this function:

◆ heuristic()

double H3AStar::heuristic	(	H3Index	cell,
		const LatLng &	targetCoord
	)

staticprivate

Heuristic function for A* (distance to target).

Parameters

cell	Current cell.
targetCoord	Target coordinates.

Returns: Estimated distance to target.

Definition at line 542 of file astar.cpp.

Referenced by findLocalPathAtResolution(), and findPathAtResolution3().

Here is the caller graph for this function:

◆ reconstructPath()

std::vector< H3Index > H3AStar::reconstructPath	(	const std::unordered_map< H3Index, H3Index, H3IndexHash > &	previous,
		H3Index	start,
		H3Index	end
	)

staticprivate

Reconstructs path from the visited nodes map.

Parameters

previous	Map of cell -> previous cell in path.
start	Start cell.
end	End cell.

Returns: Reconstructed path from start to end.

Definition at line 551 of file astar.cpp.

Referenced by findLocalPathAtResolution().

Here is the caller graph for this function:

◆ refineEndSegmentGradual()

std::vector< H3Index > H3AStar::refineEndSegmentGradual	(	H3Index	prevInPath,
		H3Index	parentEnd,
		H3Index	originalEnd,
		int	endRes
	)

private

Refines path segment near the end point to target resolution.

Parameters

prevInPath	Previous cell in the coarse path.
parentEnd	Parent cell at resolution 3.
originalEnd	Original end cell at target resolution.
endRes	Target resolution.

Returns: Refined path segment.

Definition at line 322 of file astar.cpp.

References findBoundaryCellInDirection(), findLocalPathAtResolution(), and getChildrenAtResolution().

Referenced by refinePath().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ refinePath()

std::vector< H3Index > H3AStar::refinePath	(	const std::vector< H3Index > &	pathRes3,
		H3Index	originalStart,
		H3Index	originalEnd,
		int	startRes,
		int	endRes
	)

private

Refines entire coarse path to target resolution.

Parameters

pathRes3	Coarse path at resolution 3.
originalStart	Original start cell.
originalEnd	Original end cell.
startRes	Start cell resolution.
endRes	End cell resolution.

Returns: Fully refined path.

Definition at line 413 of file astar.cpp.

References refineEndSegmentGradual(), and refineStartSegmentGradual().

Referenced by findShortestPath().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ refineStartSegmentGradual()

std::vector< H3Index > H3AStar::refineStartSegmentGradual	(	H3Index	originalStart,
		H3Index	nextInPath,
		int	startRes
	)		const

private

Refines path segment near the start point to target resolution.

Parameters

originalStart	Original start cell at target resolution.
nextInPath	Next cell in the coarse path.
startRes	Target resolution.

Returns: Refined path segment.

Definition at line 373 of file astar.cpp.

References findBoundaryCellInDirection(), findLocalPathAtResolution(), and getChildrenAtResolution().

Referenced by refinePath().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ setBlockedCells()

void H3AStar::setBlockedCells ( const std::unordered_set< H3Index > & blocked )

Sets cells that cannot be traversed (obstacles).

Call this method before findShortestPath() to define obstacles such as maze walls.

Parameters

blocked Set of H3 cell indices that are impassable.

Definition at line 10 of file astar.cpp.

References blockedCells.

Referenced by H3_VIEWER::H3Worker::setWalls().

Here is the caller graph for this function:

Member Data Documentation

◆ pad0

H3AStar::__pad0__

Definition at line 85 of file astar.h.

◆ blockedCells

std::unordered_set<H3Index> H3AStar::blockedCells {}

private

Set of blocked (impassable) cells.

Definition at line 130 of file astar.h.

Referenced by findLocalPathAtResolution(), findPathAtResolution3(), findShortestPath(), and setBlockedCells().

◆ MAX_CELLS_RES_3

constexpr uint16_t H3AStar::MAX_CELLS_RES_3 {41'162}

staticconstexprprivate

Maximum number of cells at resolution 3 (~41K cells globally).

Definition at line 99 of file astar.h.

Referenced by findLocalPathAtResolution().

◆ MAX_NEIGHBORS

constexpr int H3AStar::MAX_NEIGHBORS {6}

staticconstexprprivate

Maximum neighbors for a hexagonal cell (always 6).

Definition at line 102 of file astar.h.

The documentation for this class was generated from the following files:

src/models/astar.h
src/models/astar.cpp

Classes

Public Member Functions

Public Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ H3AStar()

◆ ~H3AStar()

Member Function Documentation

◆ cellToChildRes3()

◆ cellToParentRes3()

◆ findBoundaryCellInDirection()

◆ findLocalPathAtResolution()

◆ findPathAtResolution3()

◆ findShortestPath()

◆ getChildrenAtResolution()

◆ getDistanceBetweenCells()

◆ getNeighbors()

◆ heuristic()

◆ reconstructPath()

◆ refineEndSegmentGradual()

◆ refinePath()

◆ refineStartSegmentGradual()

◆ setBlockedCells()

Member Data Documentation

◆ __pad0__

◆ blockedCells

◆ MAX_CELLS_RES_3

◆ MAX_NEIGHBORS

◆ pad0