====== 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 finds the optimal path to the desired goal state. If there is no optimal path, the returned value should be ''None''. You should use the maze environment ''kuimaze2.SearchProblem''. For fulfilling the task, you need to select and implement a heuristic function. The impact of selecting different functions is well explained in [[http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html|link]].  


===== Learning outcomes =====

This task will teach you about:
   * Time complexity
   * Space complexity
   * Resulting path quality


===== 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 =====

The evaluation consists of two parts:

^ Subject of evaluation ^ Eval. type ^ Points ^ note ^
| Algorithm quality | Automatic evaluation| 0-5 | Does the solution work correctly? |
| Code quality | Manual evaluation | 0-2 | Is the solution implementation clear? |

Algorithm quality:
  * Tested on multiple mazes with various size and complexity.
  * The solution shall run without errors.
  * Is the path valid? (It shouldn't cross walls, go outside of the maze, and should be continuous on the 4-neighbourhood.)
  * Is the path optimal?
  * Is the algorithm efficient? Doesn't it explore more states than actually needed to find the optimal path?

Code quality:
  * suitable comments or the code is so clear that it does not need comments
  * reasonable length of methods
  * the names of variables, functions, methods, etc. are meaningful and help in understanding and reading the code
  * no repetitive code (no copy-paste in the same code)
  * saving processing time and memory (i.e. no unnecessary nested loops)
  * ...

You can follow [[https://www.python.org/dev/peps/pep-0008/|PEP8]], although we do not check all PEP8 demands. Most of the IDEs (certainly PyCharm) point out mishaps with regards to PEP8. You can also read some other sources for inspiration about clean code (e.g., [[https://github.com/zedr/clean-code-python|here]]) or about idiomatic python (e.g., [[https://medium.com/the-andela-way/idiomatic-python-coding-the-smart-way-cc560fa5f1d6|medium]], [[http://python.net/~goodger/projects/pycon/2007/idiomatic/handout.html|python.net]]).

===== 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|}}