Pathfinding Glossary
This glossary provides concise definitions of key terminology encountered in the study of pathfinding and graph search algorithms.
- A* Algorithm
- A graph traversal and pathsearch algorithm used extensively in AI, robotics, and mapping. It finds the shortest path from a start node to a goal node by minimizing
f(n) = g(n) + h(n), effectively balancing actual cost incurred and estimated cost remaining. - Admissible Heuristic
- A crucial property of heuristics for A*. A heuristic is admissible if it never overestimates the true minimum cost from node n to the goal. Admissibility is a requirement for A* to guarantee the optimality (the shortest path) of its solution.
- Branching Factor
- In a graph or tree, the number of edges emanating from a node. In pathfinding on grids, the branching factor is typically 4 or 8 depending on allowed movement (cardinal only vs. cardinal + diagonal).
- Chebyshev Distance
- A heuristic metric for 8-directional grids where diagonal movement cost is equal to cardinal movement cost. It is defined as
max(|x1 - x2|, |y1 - y2|). - Closed Set (Explored)
- A data structure (typically a Hash Set) holding nodes that have already been fully evaluated. Checking against this set prevents the algorithm from re-processing nodes, which avoids infinite loops and cycles.
- Completeness
- A property of a search algorithm. An algorithm is complete if it is guaranteed to find a solution if one exists.
- Consistent (Monotonic) Heuristic
- A stronger condition than admissibility. A heuristic is consistent if for every node n and every neighbor m of n,
h(n) ≤ cost(n, m) + h(m). A consistent heuristic ensures that once A* reaches a node, it has found the optimal path to it. - Euclidean Distance
- The "straight-line" distance between two points in Euclidean space. Formula:
√[(x1 - x2)² + (y1 - y2)²]. Often used as a heuristic in any-angle pathfinding. - Graph
- A mathematical abstraction consisting of a set of vertices (nodes) and edges (connections). Graphs model environments in pathfinding applications.
- Heuristic (h)
- An "educated guess" used to guide search algorithms toward the goal. A good heuristic significantly narrows the search space compared to blind search algorithms.
- Manhattan Distance
- A distance metric for 4-directional grid-based pathfinding where diagonal movement is disallowed. It represents the sum of the absolute differences of the coordinates:
|x1 - x2| + |y1 - y2|. - Node (Vertex)
- An individual point or location within the graph environment. In grid-based pathfinding, a node typically represents a single grid cell.
- Open Set (Frontier)
- A data structure (typically a Priority Queue or Min-Heap) containing nodes that have been discovered (neighbors of expanded nodes) but not yet evaluated. The node with the lowest
f(n)is extracted from the frontier to be expanded next. - Optimality
- A property of a search algorithm. An algorithm is optimal if it is guaranteed to return the lowest-cost solution when multiple solutions exist.
- Priority Queue (Min-Heap)
- The ideal data structure for the Open Set. It allows efficient insertion of new nodes and fast extraction of the node with the minimum
f(n)value (O(log n)operations).