DANTE

B-CPE-200-MAR-2-1-dante-vincent.montero-fontaine

To do:

The goal of this project is to generate mazes (in a reasonable amount of time), solve them (in a reasonable amount of time), and print the solution.

It has 2 folders : solver with a binary named “solver” in it, generator with binary named “generator” in it. Each folder contains a Makefile compiling the binary and a Makefile at the root compiles all binaries.

What is a maze ?

Here is the maze format description:

Mazes are rectangular.

They are coded in ASCII.

The ‘X’s represent the walls and the’*’s represent the free spaces.

It is possible to move to the four surrounding squares (up, down, right, left).

“Start” is in the upper left-hand corner (0;0)

“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.

Resolution: in order to write the solution in the maze, we use ‘o’ for the solution path.

This project used weighted graph to solve a maze. We used recursive backtracking as the generator algorithm and A* as the solver.

System functions and libC are allowed for this project, but no external libraries.

How to test it ?

make and then do ./generator/generator ROWS COLS perfect/imperfect (imperfect by default) and ./solver/solver MAP

To redirect a file, just do ./generator/generator ROWS COLS > NAME.txt

You also have a tester.sh file at your disposition, just use it like this: ./tester.sh ROWS COLS perfect/imperfect

With ROWS and COLS being sizes of the maze you want to write, the file will then generate and then print the solved maze, with the path shown with red os

Our team !

Joan Ruiz	Vincent Montero Fontaine