Attributes¶

Classes¶

Module Contents¶

class graphs.bidirectional_a_star.AStar(start: TPosition, goal: TPosition)¶

>>> astar = AStar((0, 0), (len(grid) - 1, len(grid[0]) - 1))
>>> (astar.start.pos_y + delta[3][0], astar.start.pos_x + delta[3][1])
(0, 1)
>>> [x.pos for x in astar.get_successors(astar.start)]
[(1, 0), (0, 1)]
>>> (astar.start.pos_y + delta[2][0], astar.start.pos_x + delta[2][1])
(1, 0)
>>> astar.retrace_path(astar.start)
[(0, 0)]
>>> astar.search()
[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (2, 3), (3, 3),
 (4, 3), (4, 4), (5, 4), (5, 5), (6, 5), (6, 6)]

get_successors(parent: Node) → list[Node]¶

Returns a list of successors (both in the grid and free spaces)

retrace_path(node: Node | None) → list[TPosition]¶

Retrace the path from parents to parents until start node

search() → list[TPosition]¶

closed_nodes: list[Node] = []¶

open_nodes¶

reached = False¶

start¶

target¶

class graphs.bidirectional_a_star.BidirectionalAStar(start: TPosition, goal: TPosition)¶

>>> bd_astar = BidirectionalAStar((0, 0), (len(grid) - 1, len(grid[0]) - 1))
>>> bd_astar.fwd_astar.start.pos == bd_astar.bwd_astar.target.pos
True
>>> bd_astar.retrace_bidirectional_path(bd_astar.fwd_astar.start,
...                                     bd_astar.bwd_astar.start)
[(0, 0)]
>>> bd_astar.search()
[(0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (2, 4),
 (2, 5), (3, 5), (4, 5), (5, 5), (5, 6), (6, 6)]

retrace_bidirectional_path(fwd_node: Node, bwd_node: Node) → list[TPosition]¶

search() → list[TPosition]¶

bwd_astar¶

fwd_astar¶

reached = False¶

class graphs.bidirectional_a_star.Node(pos_x: int, pos_y: int, goal_x: int, goal_y: int, g_cost: int, parent: Node | None)¶

>>> k = Node(0, 0, 4, 3, 0, None)
>>> k.calculate_heuristic()
5.0
>>> n = Node(1, 4, 3, 4, 2, None)
>>> n.calculate_heuristic()
2.0
>>> l = [k, n]
>>> n == l[0]
False
>>> l.sort()
>>> n == l[0]
True

__lt__(other: Node) → bool¶

calculate_heuristic() → float¶

Heuristic for the A*

f_cost¶

g_cost¶

goal_x¶

goal_y¶

h_cost¶

parent¶

pos¶

pos_x¶

pos_y¶

graphs.bidirectional_a_star.HEURISTIC = 0¶

graphs.bidirectional_a_star.TPosition¶

graphs.bidirectional_a_star.delta¶

graphs.bidirectional_a_star.grid = [[0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0], [1,...¶

graphs.bidirectional_a_star.init = (0, 0)¶