Introduction

This project implements the programming project MAGOS, which means Maze GeneratOr and Solver and is composed of some subprojects: Canvas, Maze, Render, Builder, Solver.

The project is a perfect maze generator and solver.

A perfect maze is a maze where each location (cell) is reachable from any other one, and where there is one, and only one, path connecting each pair of locations.

Authorship

Marcos Antonio Cavalcanti Junior

[email protected]

Structure

The folder and files structure is the following:

• include folder contains the headers of classes

• helpers folder contains other resources useful to implementation

• src folder contains the implementation of the classes

• test folder contains codes to test classes and other codes

• build folder will contain compilation files generated with help of CMake

• run folder will contain the executables generated

• data folder will contain data used by the project, like images, configurations, inputs, ouputs, etc

  • builder folder will contain imagens generated by the builder application
  • solver folder will contain imagens generated by the solver application

Compilation

You can go to root directory of the project and:

$ mkdir build
$ cd build/
$ cmake ..
$ make

Or, if you would like to do all from root:

$ mkdir build
$ cmake -H. -Bbuild
$ make -C build/ --no-print-directory

Execution

All executables will be placed in run/ folder. So, you can run typing:

$ ./run/[EXECUTABLE]

These are the main executables:

• builder builds a new maze using Hash Table strategy
• solver solves a maze (currently, using the Backtracking strategy)
• magos performs the game it self building and solving a maze

More details about each executables can be found at CMakeLists.txt file.

Doxygen

A configuration file is set in the root directory, doxygen.cfg. If you want to generate yours, you can type:

$ doxygen -g [NAME]

Its recommended to custom the following tags: PROJECT_NAME, OUTPUT_DIRECTORY and EXTRACT_PRIVATE.

To generate the files containing the documentation, type:

$ doxygen doxygen.cfg

Video

You can use ffmpeg to make video files of building and solving processes. For example:

ffmpeg -framerate 10 -i building_%06d.png -c:v libx264 -r 30 -pix_fmt yuv420p  -vf "pad=ceil(iw/2)*2:ceil(ih/2)*2" builder.mp4

ffmpeg -framerate 10 -i solving_%06d.png -c:v libx264 -r 30 -pix_fmt yuv420p  -vf "pad=ceil(iw/2)*2:ceil(ih/2)*2" solver.mp4

TODO

• On class Maze

  • introduce valid_coord() in to_index() and get_cell(), and implement exceptions
  • implement methods to get states of cells and walls
  • refactor order of bits: four first to be walls states
  • turn Cell type back to private
  • refactor method to reset states in set_state()
  • refactor number of bits used, from 8 to 6

• On class Render

  • refactor draw_cell() to use methods provided by Maze
  • document with details
  • draw cell and path of solution

• On class MagosGame

  • prevent executable to run without parameters

• Implement Builder and Solver classes (each class name will refer to the method used)

  • class HashBuilder
  • class Solver

• On class HashBuilder

  • introduce render object
  • save snapshots of maze
  • remove internal render and receive it by parameter
  • create step() method
  • rename class roulette and port it to inside HashBuilder
  • implement Hash Table as a std::vector (internal class)
  • number format in file names

• On class HashTable

  • implement exceptions ( key2index(), merge_by_key() )
  • document with details
  • separate build_maze() to build_maze() + build_step() (use class Roulette?)
  • delete statement on destructor

• On class Solver

  • comment with details
  • number format in file names

• General/Missing

  • improve comments
  • implement delete statements
  • update draw_cell()
  • number format in file names
  • comment Magos Game class