Package de.bsommerfeld.pathetic.engine.pathfinder

Class AStarPathfinder

java.lang.Object

de.bsommerfeld.pathetic.engine.pathfinder.AbstractPathfinder

de.bsommerfeld.pathetic.engine.pathfinder.AStarPathfinder

All Implemented Interfaces:

Pathfinder

public final class AStarPathfinder
extends AbstractPathfinder

An A* pathfinding algorithm that uses a heuristic to guide the search toward the target. It balances the actual cost from the start (G-cost) with the estimated cost to the target (H-cost).

This implementation uses:

• A primitive min-heap for the open set (priority queue).
• Addressable heap handles for efficient G-cost updates (decrease-key).
• A spatial closed set with Bloom filters (SpatialData) to quickly check expanded nodes.

Thread-safety: Each pathfinding operation gets its own PathfindingSession, ensuring thread-safety for concurrent requests.

Field Summary

Fields inherited from class de.bsommerfeld.pathetic.engine.pathfinder.AbstractPathfinder

costProcessors, EMPTY_PATH_POSITIONS, navigationPointProvider, neighborStrategy, pathfinderConfiguration, validationProcessors

Constructor Summary

Constructors

Constructor	Description
AStarPathfinder(PathfinderConfiguration configuration)

Method Summary

Modifier and Type	Method	Description
protected Node	extractBestNode(MinHeap openSet)	Extracts the node with the lowest cost from the open set and retrieves the corresponding Node object.
protected void	initializeSearch()	Prepares the algorithm-specific initial setup required before executing the pathfinding logic.
protected void	insertStartNode(Node node, double fCost, MinHeap openSet)	Inserts the start node into the open set and updates any internal mapping.
protected void	markNodeAsExpanded(Node node)	Marks the given node as expanded (i.e., added to the "closed set").
protected void	performAlgorithmCleanup()	Abstract method for algorithm-specific cleanup, called after pathfinding execution.
protected void	processSuccessors(PathPosition start, PathPosition target, Node currentNode, MinHeap openSet, SearchContext searchContext)	Processes the successors of the current node, checking if they're in the open or closed set, calculating costs, validating traversability, and updating the open set as needed.

Methods inherited from class de.bsommerfeld.pathetic.engine.pathfinder.AbstractPathfinder

createStartNode, findPath, reconstructPath, registerPathfindingHook

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface de.bsommerfeld.pathetic.api.pathing.Pathfinder

findPath

Constructor Details

AStarPathfinder

public AStarPathfinder(PathfinderConfiguration configuration)

Method Details

insertStartNode

protected void insertStartNode(Node node,
 double fCost,
 MinHeap openSet)

Description copied from class: AbstractPathfinder

Inserts the start node into the open set and updates any internal mapping.

Specified by:

insertStartNode in class AbstractPathfinder

extractBestNode

protected Node extractBestNode(MinHeap openSet)

Description copied from class: AbstractPathfinder

Extracts the node with the lowest cost from the open set and retrieves the corresponding Node object.

Specified by:

extractBestNode in class AbstractPathfinder

initializeSearch

protected void initializeSearch()

Description copied from class: AbstractPathfinder

Prepares the algorithm-specific initial setup required before executing the pathfinding logic. This method is designed to be overridden by subclasses to implement their respective initialization logic, such as setting up data structures, precomputing values, or resetting internal state. It is called at the beginning of a pathfinding request.

Specified by:

initializeSearch in class AbstractPathfinder

processSuccessors

protected void processSuccessors(PathPosition start,
 PathPosition target,
 Node currentNode,
 MinHeap openSet,
 SearchContext searchContext)

Processes the successors of the current node, checking if they're in the open or closed set, calculating costs, validating traversability, and updating the open set as needed.

Specified by:

processSuccessors in class AbstractPathfinder

Parameters:

start - The starting position of the pathfinding request.

target - The target position of the pathfinding request.

currentNode - The node being expanded.

openSet - The priority queue holding nodes to explore.

searchContext - The context for the current search.

markNodeAsExpanded

protected void markNodeAsExpanded(Node node)

Description copied from class: AbstractPathfinder

Marks the given node as expanded (i.e., added to the "closed set"). Subclasses should implement this to update their specific closed set mechanism.

Specified by:

markNodeAsExpanded in class AbstractPathfinder

Parameters:

node - The node that has been taken from the open set and is being expanded.

performAlgorithmCleanup

protected void performAlgorithmCleanup()

Description copied from class: AbstractPathfinder

Abstract method for algorithm-specific cleanup, called after pathfinding execution. To be implemented by subclasses like AStarPathfinder.

Specified by:

performAlgorithmCleanup in class AbstractPathfinder