graphs.bidirectional_a_star
===========================

.. py:module:: graphs.bidirectional_a_star

.. autoapi-nested-parse::

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



Attributes
----------

.. autoapisummary::

   graphs.bidirectional_a_star.HEURISTIC
   graphs.bidirectional_a_star.TPosition
   graphs.bidirectional_a_star.delta
   graphs.bidirectional_a_star.grid
   graphs.bidirectional_a_star.init


Classes
-------

.. autoapisummary::

   graphs.bidirectional_a_star.AStar
   graphs.bidirectional_a_star.BidirectionalAStar
   graphs.bidirectional_a_star.Node


Module Contents
---------------

.. py:class:: 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()  # doctest: +NORMALIZE_WHITESPACE
   [(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)]


   .. py:method:: get_successors(parent: Node) -> list[Node]

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



   .. py:method:: retrace_path(node: Node | None) -> list[TPosition]

      Retrace the path from parents to parents until start node



   .. py:method:: search() -> list[TPosition]


   .. py:attribute:: closed_nodes
      :type:  list[Node]
      :value: []



   .. py:attribute:: open_nodes


   .. py:attribute:: reached
      :value: False



   .. py:attribute:: start


   .. py:attribute:: target


.. py:class:: 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()  # doctest: +NORMALIZE_WHITESPACE
   [(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)]


   .. py:method:: retrace_bidirectional_path(fwd_node: Node, bwd_node: Node) -> list[TPosition]


   .. py:method:: search() -> list[TPosition]


   .. py:attribute:: bwd_astar


   .. py:attribute:: fwd_astar


   .. py:attribute:: reached
      :value: False



.. py:class:: 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


   .. py:method:: __lt__(other: Node) -> bool


   .. py:method:: calculate_heuristic() -> float

      Heuristic for the A*



   .. py:attribute:: f_cost


   .. py:attribute:: g_cost


   .. py:attribute:: goal_x


   .. py:attribute:: goal_y


   .. py:attribute:: h_cost


   .. py:attribute:: parent


   .. py:attribute:: pos


   .. py:attribute:: pos_x


   .. py:attribute:: pos_y


.. py:data:: HEURISTIC
   :value: 0


.. py:data:: TPosition

.. py:data:: delta

.. py:data:: grid
   :value: [[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,...


.. py:data:: init
   :value: (0, 0)