Maze Resolution
An algorithm can also find the way out of a maze
Maze Resolution
A maze is a path or collection of paths, typically from an entrance to a goal.
During my second year of Technical Degree (DUT) in Computer Science in 2014 we had to make a project in the context of mathematical modeling. My teammates and I chose to make an algorithm that could solve most of mazes.
By documenting ourselves, we realized that many algorithms exist to get out of a maze (even if we are immersed in the dark !). This curiosity about the representation of a maze in mathematics and computer science made us want to deepen our work. We have thus rendered with the algorithm, a graphical interface representing a maze and its generated exit path.
But then how did we draw a maze and make its appearance dynamic with computer programming ? Well, we have deduced that a maze is simply a matrix made up of squares where some are walls and some are paths. And in computer programming, a matrix is very simple to make because it's actually a two-dimensional array. Then, to distinguish the walls from the paths, we used a binary numbering: 1 and 0. The number 1 represents a wall and the number 0 a path. In the end, we had a table that looks like this in the code :
grille = new int[][]{
{ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 1 },
{ 1, 1, 0, 1, 0, 1, 0, 1, 0, 1 },
{ 1, 0, 0, 1, 0, 1, 1, 1, 0, 1 },
{ 1, 0, 1, 1, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 1, 0, 1, 1, 1, 0, 1 },
{ 1, 0, 1, 1, 0, 1, 0, 0, 0, 1 },
{ 1, 0, 0, 1, 0, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 0, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 0, 0 }
};
Finally, to make it visible on the screen, we replaced by a black image the number 1 (to represent the walls) and 0 with a white image (to represent the paths). Which gives us :
The resolution algorithm and its operation are explained in detail in the project report available in PDF below.