Dante’s Star: Maze Generation & Solver

Project Description

In Dante’s Star, we simulate Dante Alighieri's journey through Hell, represented as a maze. Drawing inspiration from "The Divine Comedy," this program generates mazes and finds the fastest path from start to end - a representation of Dante's journey from the entrance to the exit of Hell.

The project is split into nine sections, mirroring the nine circles of Hell Dante traverses. Utilizing C language and the power of system functions and the standard C library (libC), the program aspires to generate mazes in a reasonable time frame, solve them, and print the solution.

Key Features

• Maze Generation: Generates a maze, with the default configuration being an imperfect maze.

• Maze Solving: Finds the fastest path through the maze.

• ASCII Representation: Mazes are represented in ASCII, with 'X' as walls and '*' as free spaces.

• Solution Printing: Prints the solution on standard output, marking the path with 'o'.

• Error Handling: All error messages are written on the error output, and the program exits with the 84 error code (0 if there is no error).

Maze Specifications

• Mazes are rectangular.

• The 'X's represent the walls, and the '*'s represent the free spaces.

• Movement is allowed in the four surrounding squares (up, down, right, left).

• "Start" is in the upper left-hand corner (0;0), and "Finish" is in the bottom right-hand corner.

• A solution is a series of free, adjacent squares, from "Start" to "Finish" included.

• "Start" and "Finish" can be occupied. In this case, there is no solution.

• The last line of the maze doesn’t terminate with a return line.

• For the resolution, 'o' is used to indicate the solution path in the maze.

Maze Types:

Imperfect Maze:

• Contains clusters

• Must have at least one solution

Perfect Maze:

• No loops and clusters

• Must have a solution

• Following a wall leads to traversing the entire maze

Examples:

Perfect Maze generation:

Imperfect Maze

Solver