xico2001pt/ia-robot-mazes

Projeto da UC de Inteligência Artificial

IA Robot Mazes

Group: 20_1D

Members:

• Adriano Soares, [email protected]
• Filipe Campos, [email protected]
• Francisco Cerqueira, [email protected]

Instructions

This project uses pygame, therefore it must be installed before running the program, this can be done by running:

pip3 install pygame

After pygame has been installed simply run:

python3 main.py

inside the src folder.

ia-robot-mazes's Issues

Implement hint system

While in the human gameplay mode, the player should be able to ask for a hint, by clicking on some key (eg. H).
As a maze might have several solutions, the algorithm should:

1. Calculate the optimal solution using the instructions the player already selected (if the instructions are empty, skip to 3.1).
2. If a solution is found, then it must
   2.1. Append the following instruction to the path.
3. Otherwise, it should
   3.1. Calculate the optimal solution, starting with an empty set of instructions.
   Note: This optimal solution could be calculated only once in the beginning for efficiency purposes.
   3.2. Erase the path and append the first instruction to it.

Optionally, the controller could implement mechanisms to highlight instructions provided by the hint system (eg. a different color) and display the number of used hints.

Implement AI gameplay

Find cycles with maximum length and calculate heuristic value

Final state verification

Implement algorithm to find path with minimum direction changes

Screen size doesn't adapt to non-optimal solutions

For example, if an solution found by DFS with max_depth is found, it usually will be larger than the optimal solution therefore occupying more screen space. Currently the window size is set to accommodate the optimal solution on the start

Implement heuristic 2

Description:
Pre-compute the path with the lower number of direction changes between start and finish positions, obtain the direction changes made, group patterns with most elements and sum their length with the number of ungrouped direction changes. The heuristic value will be the absolute value of the difference between the current number of commands and the value computed previously.

Tasks:

• #6
• #7

Implement heuristic 1

Description:
Prioritize states in which the list of operators contains at least one of the directions that are fundamental to reach the final state. For instance, in a square matrix, if the robot is in the bottom left corner and the final state is in the top right corner, it should avoid visiting states that do not contain a single UP or RIGHT instructions. If the state does not contain one of these directions, it adds cost one to the heuristic for each direction needed.

Implement menu

The main menu of the game should provide the following configuration parameters:

• Level: Select the maze file (maybe with a preview of the map?)
• Mode: If the game should be played by the AI or the player

If the AI mode is selected, one more parameter should be provided:

• Algorithm: The algorithm that will be used to perform the search

Import all levels available

URL: https://erich-friedman.github.io/puzzle/robot/

Implement function to display images in GUI

Implement human gameplay

Implement gameplay/levels

Tasks:

• #10
• #11
• #12
• #21

Modify PygameGUI to provide a method to display images

To avoid loading the images in every frame, the GUI must store the images in a data structure that allows to easily access information.

A possible implementation of a solution to this problem would include a dictionary that stores the images information and each time an image should be drawn, it checks if it was already loaded before.

Implement gameover screen

In the human gameplay mode, this screen should display information about:

• The amount of time the player spent trying to solve the maze
• The number of wrong attempts the player did before submitting the correct answer
• The number of used hints