graphs.a_star
=============

.. py:module:: graphs.a_star


Attributes
----------

.. autoapisummary::

   graphs.a_star.DIRECTIONS
   graphs.a_star.grid


Functions
---------

.. autoapisummary::

   graphs.a_star.search


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

.. py:function:: search(grid: list[list[int]], init: list[int], goal: list[int], cost: int, heuristic: list[list[int]]) -> tuple[list[list[int]], list[list[int]]]

   Search for a path on a grid avoiding obstacles.
   >>> grid = [[0, 1, 0, 0, 0, 0],
   ...         [0, 1, 0, 0, 0, 0],
   ...         [0, 1, 0, 0, 0, 0],
   ...         [0, 1, 0, 0, 1, 0],
   ...         [0, 0, 0, 0, 1, 0]]
   >>> init = [0, 0]
   >>> goal = [len(grid) - 1, len(grid[0]) - 1]
   >>> cost = 1
   >>> heuristic = [[0] * len(grid[0]) for _ in range(len(grid))]
   >>> heuristic = [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
   >>> for i in range(len(grid)):
   ...     for j in range(len(grid[0])):
   ...         heuristic[i][j] = abs(i - goal[0]) + abs(j - goal[1])
   ...         if grid[i][j] == 1:
   ...             heuristic[i][j] = 99
   >>> path, action = search(grid, init, goal, cost, heuristic)
   >>> path  # doctest: +NORMALIZE_WHITESPACE
   [[0, 0], [1, 0], [2, 0], [3, 0], [4, 0], [4, 1], [4, 2], [4, 3], [3, 3],
   [2, 3], [2, 4], [2, 5], [3, 5], [4, 5]]
   >>> action  # doctest: +NORMALIZE_WHITESPACE
   [[0, 0, 0, 0, 0, 0], [2, 0, 0, 0, 0, 0], [2, 0, 0, 0, 3, 3],
   [2, 0, 0, 0, 0, 2], [2, 3, 3, 3, 0, 2]]


.. py:data:: DIRECTIONS

.. py:data:: grid
   :value: [[0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 1, 0, 0, 1, 0], [0, 0, 0, 0, 1, 0]]