graphs.bidirectional_a_star

https://en.wikipedia.org/wiki/Bidirectional_search

Attributes

HEURISTIC

TPosition

delta

grid

init

Classes

AStar

BidirectionalAStar

Node

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)