Pathfinding
Pathfinding is the process of finding the shortest or most efficient path between two points in a defined environment.
Algorithm |
Class |
Optimal |
|---|---|---|
Depth-first search |
False |
|
Greedy Best-First Search |
False |
|
Breadth-first search |
True (only in an
unweighted environment)
|
|
Dijkstra |
True |
|
A* |
True |
|
Iterative deepening A* |
True |
BFS
- class w9_pathfinding.pf.BFS
Breadth-First Search (BFS) pathfinding algorithm.
BFS explores all nodes at the current depth before moving to the next level.
It guarantees to find the optimal path only in unweighted environments (when all edges have equal cost).
- Parameters:
env (Environment) – The environment in which to search for paths.
- find_path(start, goal)
Find a path between two nodes.
- Parameters:
start (node) – The starting node.
goal (node) – The goal node.
- Returns:
A list of node representing the path from start to goal. If path is found the list will start with start and end with goal. If no path is found, returns an empty list.
- Return type:
list of nodes
- Raises:
ValueError – If either start or goal is not a valid node in the environment.
BiBFS
- class w9_pathfinding.pf.BiBFS
Bidirectional Breadth-First Search (BiBFS) algorithm.
BiBFS performs two simultaneous BFS searches: one from the start and one from the goal. When the two frontiers meet, a valid path is reconstructed. This algorithm can significantly reduce search time in large environments compared to BFS.
It guarantees to find the optimal path only in unweighted environments (when all edges have equal cost).
- Parameters:
env (Environment) – The environment in which to search for paths.
- find_path(start, goal)
Find a path between two nodes.
- Parameters:
start (node) – The starting node.
goal (node) – The goal node.
- Returns:
A list of node representing the path from start to goal. If path is found the list will start with start and end with goal. If no path is found, returns an empty list.
- Return type:
list of nodes
- Raises:
ValueError – If either start or goal is not a valid node in the environment.
DFS
- class w9_pathfinding.pf.DFS
Depth-First Search (DFS) pathfinding algorithm.
DFS explores as far as possible along each branch before backtracking.
It does not guarantee to find the optimal path.
- Parameters:
env (Environment) – The environment in which to search for paths.
- find_path(start, goal)
Find a path between two nodes.
- Parameters:
start (node) – The starting node.
goal (node) – The goal node.
- Returns:
A list of node representing the path from start to goal. If path is found the list will start with start and end with goal. If no path is found, returns an empty list.
- Return type:
list of nodes
- Raises:
ValueError – If either start or goal is not a valid node in the environment.
Dijkstra
- class w9_pathfinding.pf.Dijkstra
Dijkstra’s algorithm for optimal pathfinding in weighted environments.
Dijkstra’s algorithm computes the lowest-cost path between nodes by expanding nodes in order of increasing path cost.
It guarantees to find the optimal path in any environment.
- Parameters:
env (Environment) – The environment in which to search for paths.
- find_path(start, goal)
Find a path between two nodes.
- Parameters:
start (node) – The starting node.
goal (node) – The goal node.
- Returns:
A list of node representing the path from start to goal. If path is found the list will start with start and end with goal. If no path is found, returns an empty list.
- Return type:
list of nodes
- Raises:
ValueError – If either start or goal is not a valid node in the environment.
BiDijkstra
- class w9_pathfinding.pf.BiDijkstra
Bidirectional Dijkstra’s algorithm for optimal pathfinding in weighted environments.
This algorithm runs two simultaneous Dijkstra searches — one from the start, one from the goal — and stops when the frontiers meet. Often faster than regular Dijkstra.
It guarantees to find the optimal path in any environment.
- Parameters:
env (Environment) – The environment in which to search for paths.
- find_path(start, goal)
Find a path between two nodes.
- Parameters:
start (node) – The starting node.
goal (node) – The goal node.
- Returns:
A list of node representing the path from start to goal. If path is found the list will start with start and end with goal. If no path is found, returns an empty list.
- Return type:
list of nodes
- Raises:
ValueError – If either start or goal is not a valid node in the environment.
AStar
- class w9_pathfinding.pf.AStar
A* search algorithm for optimal pathfinding.
A* extends Dijkstra by using a heuristic function to estimate the remaining cost to the goal, allowing faster search in many environments.
It guarantees to find the optimal path in any environment.
- Parameters:
env (Environment) – The environment in which to search for paths.
- Raises:
ValueError – If the environment does not support heuristics.
- find_path(start, goal)
Find a path between two nodes.
- Parameters:
start (node) – The starting node.
goal (node) – The goal node.
- Returns:
A list of node representing the path from start to goal. If path is found the list will start with start and end with goal. If no path is found, returns an empty list.
- Return type:
list of nodes
- Raises:
ValueError – If either start or goal is not a valid node in the environment.
BiAStar
- class w9_pathfinding.pf.BiAStar
Bidirectional A* search algorithm for optimal pathfinding.
This algorithm runs two simultaneous A* searches — one from the start, one from the goal — and stops when the frontiers meet. Often faster than regular A*.
It guarantees to find the optimal path in any environment.
- Parameters:
env (Environment) – The environment in which to search for paths.
- Raises:
ValueError – If the environment does not support heuristics.
- find_path(start, goal)
Find a path between two nodes.
- Parameters:
start (node) – The starting node.
goal (node) – The goal node.
- Returns:
A list of node representing the path from start to goal. If path is found the list will start with start and end with goal. If no path is found, returns an empty list.
- Return type:
list of nodes
- Raises:
ValueError – If either start or goal is not a valid node in the environment.
GBS
- class w9_pathfinding.pf.GBS
Greedy Best-First Search (GBS) algorithm.
GBS uses only the heuristic function to guide the search, always choosing the node that appears closest to the goal.
It can be fast, but does not guarantee to find the optimal path.
- Parameters:
env (Environment) – The environment in which to search for paths.
- Raises:
ValueError – If the environment does not support heuristics.
- find_path(start, goal)
Find a path between two nodes.
- Parameters:
start (node) – The starting node.
goal (node) – The goal node.
- Returns:
A list of node representing the path from start to goal. If path is found the list will start with start and end with goal. If no path is found, returns an empty list.
- Return type:
list of nodes
- Raises:
ValueError – If either start or goal is not a valid node in the environment.
IDAStar
- class w9_pathfinding.pf.IDAStar
Iterative Deepening A* (IDA*) algorithm.
IDA* combines the space efficiency of DFS with the optimality of A*. It performs repeated depth-limited searches, gradually increasing the limit based on estimated cost.
It guarantees to find the optimal path in any environment.
- Parameters:
env (Environment) – The environment in which to search for paths.
- Raises:
ValueError – If the environment does not support heuristics.
- find_path(start, goal, max_distance=10.0)
Find a path between two nodes.
- Parameters:
start (node) – The starting node.
goal (node) – The goal node.
max_distance (float, default is 10.) – The maximum allowed path cost (g + h) to consider during the search. If the optimal path exceeds this cost, the algorithm returns an empty list.
- Returns:
A list of node representing the path from start to goal. If path is found the list will start with start and end with goal. If no path is found, returns an empty list.
- Return type:
list of nodes
- Raises:
ValueError – If either start or goal is not a valid node in the environment.
ResumableBFS
- class w9_pathfinding.pf.ResumableBFS
Resumable Breadth-First Search (BFS) for shortest-path queries from a fixed source.
This class performs a single-source BFS from a given start_node, and allows querying shortest-path distances and paths to any node. Unlike standard BFS, the results are cached and reused efficiently for multiple distance/path queries without re-running the full search.
Useful in scenarios where multiple path or distance lookups are needed from the same source node.
It guarantees to find the optimal path only in unweighted environments (when all edges have equal cost).
- Parameters:
env (Environment) – The environment in which to search for paths.
start_node (node) – The source node to start BFS from.
- Raises:
ValueError – If start_node is not a valid node in the environment.
- distance(node)
Get the minimum number of steps required to reach node from the start_node.
- Parameters:
node (node) – The target node.
- Returns:
The number of steps from start_node to node. Returns float(‘inf’) if the node is unreachable.
- Return type:
float
- Raises:
ValueError – If node is not a valid node in the environment.
- find_path(node)
Find the shortest path from the start node to the given node, minimizing the number of steps.
- Parameters:
node (node) – The target node.
- Returns:
A list of nodes representing the shortest (step-wise) path from start_node to node. If path is found the list will start with start_node and end with node. Returns an empty list if the target node is unreachable.
- Return type:
list
- Raises:
ValueError – If node is not a valid node in the environment.
- start_node
The current start node for the BFS traversal. This is the source node from which all distances and paths are computed.
You can get or set this property. Setting a new start node will reset internal state and rerun BFS’s algorithm in the next query.
ResumableDijkstra
- class w9_pathfinding.pf.ResumableDijkstra
Resumable Dijkstra’s algorithm for shortest-path queries from a fixed source.
This class performs a single-source Dijkstra traversal from a given start_node, and allows querying shortest-path distances and paths to any node. Unlike standard Dijkstra’s algorithm, the results are cached and reused efficiently for multiple distance/path queries without re-running the full search.
It guarantees to find the optimal path in any environment.
- Parameters:
env (Environment) – The environment in which to search for paths.
start_node (node) – The source node to start Dijkstra’s algorithm from.
- Raises:
ValueError – If start_node is not a valid node in the environment.
- distance(node)
Get the shortest-path cost from the start node to the given node.
- Parameters:
node (node) – The target node.
- Returns:
The minimum cost from start_node to node. Returns float(‘inf’) if the node is unreachable.
- Return type:
float
- Raises:
ValueError – If node is not a valid node in the environment.
- find_path(node)
Find the optimal path from the start node to the given node.
- Parameters:
node (node) – The target node.
- Returns:
A list of nodes representing the optimal path from start_node to node. If path is found the list will start with start_node and end with node. Returns an empty list if the target node is unreachable.
- Return type:
list
- Raises:
ValueError – If node is not a valid node in the environment.
- start_node
The current start node for the Dijkstra’s traversal. This is the source node from which all distances and paths are computed.
You can get or set this property. Setting a new start node will reset internal state and rerun Dijkstra’s algorithm in the next query..