This project has been created as part of the 42 curriculum by mkhoubaz & iissoufo

A-Maze-ing

Description

A-Maze-ing is a project that involves creating a program to solve mazes. The program takes a maze (created using DFS) as input and finds the path from the start point to the end point. The maze is represented as a 2D grid, where walls are visualized by curses library. The program uses a path_finding (BFS) algorithm to navigate through the maze and find the optimal path.

Instructions

1.Clone the repository to your local machine.

    git clone <repository-url>

2.Install the necessary dependencies.

    make install

3.Activate the virtual environment.

    source ./.venv/bin/activate

4.Run the program using the Makefile.

    make run

5.To clean up the compiled files, use the following command:

    make clean

You can also run the program directly

    python3 a_maze_ing.py config.txt

Resources

• DFS Algorithm
• BFS Algorithm
• Curses Library
• CPython Documentation

AI Used

Using AI to debug and search for packages.

Config file

Mandatory Parameters:

• WIDTH (integer) - Horizontal size of the maze
• HEIGHT (integer) - Vertical size of the maze
• ENTRY (coordinates) - Starting point in format X,Y
• EXIT (coordinates) - Ending point in format X,Y
• OUTPUT_FILE (string) - Filename for output file
• PERFECT (boolean) - True for perfect maze, False for non-perfect

Format:

WIDTH=20
HEIGHT=10
ENTRY=0,0
EXIT=19,9
OUTPUT_FILE=maze_output.txt
PERFECT=True

Maze Generation algorithm

The maze is generated using the Depth-First Search (DFS) algorithm. This algorithm starts at a entry cell and explores as far as possible along each branch before backtracking. It creates a perfect maze, meaning there are no loops and only one unique path between any two points in the maze.

Why DFS for maze generation?

DFS is a popular choice for maze generation because it is simple to implement and produces mazes with long, winding paths. It creates a perfect maze, which can be more challenging to solve compared to mazes with loops. Additionally.

Reusable parts

The maze generation can be reused in other project (Pac-Man) as it creates a grid-based maze structure that can be adapted for different game mechanics. The path_finding algorithm (BFS) can also be reused for any project that requires finding the shortest path in a grid or graph, such as navigation systems or puzzle games.

Team and project management

Team roles

• mkhoubaz: Responsible for implementing the maze generation algorithm (DFS) and path_finding algorithm (BFS), as well parsing the configuration file and packaging the project.

• iissoufo: Responsible for visualizing the maze using the curses library, and encoding the maze into a text file. Also, main file (a_maze_ing.py).

Anticipated plans

• Start by defining the structure of the project and how it will be represented in code.
• Implement the maze generation algorithm (DFS) to create the maze based on the specified dimensions and parameters.
• Implement the path_finding algorithm (BFS) to find the optimal path from the entry point to the exit point in the maze.
• Use the curses library to visualize the maze and the path found.
• Implement the functionality to encode the maze into a text file as specified in the configuration.
• Test the program with different configurations to ensure it works correctly and efficiently.
• Refine the code and optimize it for better performance if necessary.
• Document the code and create a README file to explain how to use the program and its features.
• Finally, package the project and prepare it for submission.

It evolved until the end of the project, as we had to adapt our plans based on the challenges we faced and the insights we gained during development.

What can be improved?

• Use a more efficient maze generation algorithm, such as Prim's or Kruskal's algorithm, to create more complex mazes.
• Change path_finding algorithm to A* for better performance in larger mazes.
• More advanced visualization techniques, such as using colors or animations to enhance the user experience.

Tools used

Curses library for visualization.

Advanced features

• Animation of maze generation and path finding process.
• Banner when program starts.
• Player mode where user can use arrow or WASD keys to navigate through the maze manually.
• Show Path to exit after player reaches the exit or if they get stuck.
• Final message when player find the exit.