Your Task
In this project, you will implement the Depth-First Search (DFS) algorithm to help a nonplayable character (NPC) navigate a maze. The maze is represented as a 2D grid, with walls represented as blocks and open paths represented as empty spaces. The NPC is represented by an ASCII character in the game, and can move in four directions (up, down, left, and right).
Your task is to implement the DFS algorithm to find a path for the NPC to reach the endpoint in the maze. The NPC must navigate around walls to reach the endpoint. You will also need to implement a visualization of the NPC’s movement in the maze.
Preparing and Loading Input File (P Task)
Create an input file containing the maze and the NPC and end positions, with walls represented by blocks and open paths represented by empty spaces. An example maze is shown below, with S (starting point) and E (endpoint).
##########
# #
# ###### #
# # E# #
# # ### #
# # # #
# ### # ##
# # # #
# ### #S #
# #
##########
Reads the input file. Identifies the start and end positions of the NPC and the end point of the maze.
Implementing DFS Algorithm (P Task)
Implement the DFS algorithm to traverse the maze. Return the path from the NPC’s starting position to the endpoint of the maze.
Visualization (C/D Task)
Provide a graphical interface to display the maze and the NPC’s movement. The NPC’s position is represented by a moving character or sprite. Walls and the endpoint are also displayed. The path can be highlighted in a different color than the walls and open paths.
Performance Evaluation (D/HD Task)
Test the program with different mazes of varying sizes and complexity. Evaluate the performance of the DFS algorithm on these mazes. Measures the time taken to find the path and the number of nodes explored.
