Skip to content

RandomMazeSolver is a program capable of generating and solving mazes randomly. It also makes use of the parallelism paradigms offered by the OpenMP library in order to speed the execution up.

License

Notifications You must be signed in to change notification settings

Scrayil/RandomMazeSolver

Repository files navigation

RandomMazeSolver

RandomMazeSolver is a program capable of generating and solving mazes randomly. It consists of two different versions:

  • the sequential one in which all the instructions are executed serially
  • the parallel one that is realized by using parallelization paradigms based onto the OpenMP library

The execution is based onto a configuration file in which some parameters can be specified.
The parameters include things like the number of executions to perform, the versions of the program to execute, the size of the maze, the number of particles to generate and so on.
Specific seeds can eventually be set in order to generate predictable mazes and their relative solutions.
Note: If not specified, at each execution seeds are randomly generated, but both versions in the same execution will share the same values for consistency.

Reporting

The project has been used as an example to show and evaluate the benefits of parallelization over the sequential execution of the code.
Results and reports have been included into this repository.
For simplicity maze's images have been generated by using ascii characters and they look as follows:

Solved maze's image

Here is a sample report that shows the records related to the above maze's image:

version,elapsed_time,maze_size,n_particles,generation_seed,solution_seed,maze_image_path
sequential,2614.78,51,10000,3934329779,968699857,"/home/scrayil/Desktop/dev/University/projects/PPFML/RandomMazeSolver/results/mazes/sequential_23-05-19T17:19:35_968699857.txt"
parallel,285.342,51,10000,3934329779,968699857,"/home/scrayil/Desktop/dev/University/projects/PPFML/RandomMazeSolver/results/mazes/parallel_23-05-19T17:19:35_968699857.txt"

Demo

The following animation has been consistently slowed down in order to show the generation and solution steps of a maze of size 51x51 with 10,000 particles.

Maze generation and solution steps animation

Notes

Showing intermediate steps while generating and solving big mazes by using a big amount of particles results into slow console updates, flickering and an harsh visual experience.
This will heavily slow down the code execution.

At the moment the mazes' images filenames generation does guarantee uniqueness if the generation and the solution of 2 consecutive mazes don't happen during the same second.
If 2 small mazes are solved consecutively in the same second (timestamp), the uniqueness is guaranteed only if different seeds have been used between the two executions. (default)

This software includes third-party code for parsing json files.

  • The json parser has been taken from nlohmann

License

Copyright 2023 Mattia Bennati
Licensed under the GNU GPL V2: https://www.gnu.org/licenses/old-licenses/gpl-2.0.html