====== Search (1st assignment) ======

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

Program an A* algorithm that finds the optimal path to the desired end state. If there is no optimal path, the returned value should be ''None''. You should use the maze environment ''kuimaze.InfEasyMaze''. 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 =====

   - Create the file ''agent.py'' according to the guidelines.
   - Use the testing environment supplied in the ZIP {{:courses:b3b33kui:cviceni:prohledavani_stavoveho_prostoru:kuimaze_search.zip|kuimaze_search.zip}} file for testing before submission.
     - Extract the ZIP file in the folder with your project.
     - You need to have the following **python3** packages AI-gym, numpy and pillow for proper use of the scripts. You can get these packages by running this command from your terminal:
<code bash>
pip3 install gym numpy
sudo apt-get install python3-pil.imagetk
</code>

For mac and windows users, the python3-pil.imagetk won't work. You need to use the following command instead:
<code bash>
pip3 install pillow
</code>

<WRAP important round>
   * The code must be compatible with **Python 3**. Otherwise it is possible that the automatic evaluation system will malfunction!
</WRAP>

All the methods and functions in {{:courses:b3b33kui:cviceni:prohledavani_stavoveho_prostoru:kuimaze_search.zip|kuimaze_search.zip}} are documented in the subfolder ''/kuimaze_doc/'' or available at this [[https://cw.felk.cvut.cz/cmp/courses/be5b33kui/kuimaze_doc/index.html|link]]. 


===== Agent class and its methods =====
The ZIP file contains the file ''easy_example.py''. This file serves as a tutorial to the environment as seen on this code snippet with the basic functions:
<code python>
import kuimaze # package import
MAP = 'maps/normal/normal9.bmp'
env = kuimaze.InfEasyMaze(map_image=MAP) # create the environment
observation = self.environment.reset() # returns start_pos, goal_pos
positions_with_costs = env.expand(position) # returns [(pos, cost)] list
</code>

Implement your agent in the file ''agent.py'' as the class ''BaseAgent''. 

The final agent must have the following methods:
^ Method ^ input parameters ^ output parameters ^ note ^
| ''%%__%%init%%__%%'' | ''environmnent'' | //none// | Agent initialization.|
| ''find_path'' | //none// | path | Generates the path. The method returns a list of coordinates for the path. It must start with the starting position and end at the goal position [(x1, y1), (x2, y2), ... ]. If there is no path, it should return ''None''.|


===== Evaluation =====

The evaluation splits into two:
   - Minimal solution that returns a correct path. If there is no path, it returns an empty set.
   - Manual evaluation of the code and its form (clean code).

^ Evaluation ^ min ^ max ^ note ^
| Algorithm quality | 0 | 5 | Evaluation given by the automatic evaluation system. |
| Code quality | 0 | 2| Comments, code structure, cleanliness, proper naming... |

Algorithm quality:
  * tested on multiple mazes with various size and complexity
  * is the path valid? - does not cross walls and is continuous on the 8-neighbourhood
  * is the path optimal?

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


===== Submission =====

The date for submission is visible in the [[https://cw.felk.cvut.cz/upload/|Upload system]].

* Upload a ZIP archive with the module ''agent.py'' and any other possible modules you created to the [[https://cw.felk.cvut.cz/upload/|Upload system]]. **All the files must to be in the archive's root folder! The archive cannot contain any other folders!**


===== Screenshots =====

Possible final screenshot:
{{:courses:b3b33kui:cviceni:prohledavani_stavoveho_prostoru:normal9.png|}}