====== 1. Search in KUI Maze ======

You will program the [[https://en.wikipedia.org/wiki/A*_search_algorithm|A* algorithm]] in order to search through the given [[https://en.wikipedia.org/wiki/State_space_search|state space]].


===== Task =====

Implement an A* algorithm that 
  * always finds the cheapest path to one of the goal states, if any path exists;
  * if there is no path to any goal, the algorithm returns value ''None'';
  * during the search for the optimal path, the algorithm minimizes the number of explored states.

You should use the maze environment ''[[courses:be5b33kui:semtasks:kuimaze:10_searchproblem|kuimaze2.SearchProblem]]''. 

For the algorithm to work correctly, you need to choose and implement a suitable heuristic function. The impact of selecting different heuristic functions is well explained at [[http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html|this webpage]]. **The cost of transition** between two neighbouring positions is always **larger or equal to the Euclidean distance** of these two positions, and it generally does not have to be the same for all pairs of positions.  





===== How to =====
   - [[..:kuimaze:00_install|Install]] the ''kuimaze2'' package, if you have not done so yet.
   - Learn about the [[..:kuimaze:10_searchproblem|SearchProblem]] environment. (The ''kuimaze2'' module contains ''example_search.py''. This file also serves as a tutorial how to work with the environment.)
   - Create the file ''agent.py'' according to the guidelines.

<WRAP important round>
   * Your solution must be compatible with the [[..:..:labs:python_version|required version of Python]]. Otherwise it is possible that the automatic evaluation system will malfunction!
</WRAP>


===== Agent class and its methods =====

In file ''agent.py'', implement class ''Agent'' with the following methods:

^ Method ^ input parameters ^ output parameters ^ note ^
| ''%%__%%init%%__%%'' | ''environmnent: SearchProblem'' | //none// | Agent initialization. |
| ''find_path'' | //none// | path | Returns the found path or ''None'' if no path exists. A path is a list of ''State''s, including the start state and the goal state.|

==== Tips ====
The following Python modules may be useful in implementing some parts of the A* algorithm: [[https://docs.python.org/3.11/library/queue.html|queue]], [[https://docs.python.org/3.11/library/heapq.html|heapq]].
===== Submission =====

  * The due date for submission is visible in the [[https://cw.felk.cvut.cz/brute|BRUTE]].
  * Upload a ZIP archive with the module ''agent.py'' and any other possible modules you created to [[https://cw.felk.cvut.cz/brute|BRUTE]]. **All the files must be in the archive's root folder! The archive cannot contain any other folders!** You should NOT submit any files contained in the downloaded kuimaze2 module.



===== Evaluation =====

See a more detailed info about [[.evaluation|evaluation]].
===== Screenshots =====

This screenshot comes from a previous version of ''kuimaze''. The current version produces slightly different images. Main difference: diagonal moves are not allowed now.
{{:courses:b3b33kui:cviceni:prohledavani_stavoveho_prostoru:normal9.png|}}