sa_pathfinding

class sa_pathfinding.algorithms.astar.generic_astar.GenericAstar(env: sa_pathfinding.environments.generics.env.Environment, heuristic: sa_pathfinding.heuristics.heuristic.Heuristic, start: sa_pathfinding.environments.generics.state.State = None, goal: sa_pathfinding.environments.generics.state.State = None, verbose: bool = False)

This class implements the A* search algorithm.

By default, the open and closed lists are both simple lists. The open list is maintained as a heap using heapq, sorted on f-cost with ties broken to high g-cost. This means that cost of removing the best node from the open list on each step is O(lg(n)). Both lists are checked for membership in O(n) time using the env state __eq__() in a loop.

The open and closed lists are checked for membership via the _is_on_open() and _is_on_closed() methods. If you define a custom environment and can structure the open and closed list checks in a way that beats O(n) checks, then extend GenericAstar by inheriting from it and overriding the above methods to optimize an A* implementation for your environment. An example of this is GridOptimizedAstar where a 2d status structure was added as an effective overlay on the grids such that indexes align with grid positions, creating constant time checks for both lists.

All attributes are read-only properties.

Variables:

• ( (verbose) – obj:’list’ of :obj:’State’): The closed list for the A* search algorithm.
• ( – obj:’Environment’): A class that represents the environment being being searched.
• ( – obj:’Node’): A class that represents the node to search to. The default is a random passable node from the provided ‘env’.
• ( – obj:’Heuristic’): A class that represents the chosen heuristic to run the search with. The default is the octile distance heuristic. Pre-supported heuristics include: octile distance, manhattan distance, and euclidean distance.
• ( – obj:’dict’): A dictionary of documentary info on the execution of the search.
• ( – obj:’int’): Number of nodes expanded in the search.
• ( – obj:’list’ of :obj:’State’): The open list for the A* search algorithm.
• ( – obj:’list’ of :obj:’State’): The path returned by the execution of the search. It is empty by default and is empty if the search fails.
• ( – obj:’Node’): A class that represent the node to start the search from. The default is a random passable node from the provided ‘env’.
• ( – obj:’bool’): A boolean flag set at the end of search execution, where true indicates search success and false indicates failure
• ( – obj:’bool’): A boolean flag that, when true, enables the printing of information about the search as it runs.

closed

closed list

Type:list of SearchNode

get_path() → List[sa_pathfinding.environments.generics.state.State]

get_path() executes the search from beginning to end. No other method needs to be called after instantiation to complete a successful search.

Returns:

List[State] where list is empty if search does not return

a path and full of connected nodes if a path was found.

heuristic

heuristic name.

Type:str

open

open list

Type:list of SearchNode

step()

step generator

Yields:

Tuple[SearchNode, List[SearchNode]] –

A tuple of the node expanded and its

children that were added to the open list.

Example

>>> print([repr(node) + ' ' + repr(to_open)) for node, to_open in astar.step()])
[SearchNode<...> [SearchNode<...>, SearchNode<...>, ...], ...]