Skip to content

Latest commit

 

History

History
52 lines (43 loc) · 3.4 KB

README.md

File metadata and controls

52 lines (43 loc) · 3.4 KB
Raw

Maze

Implementation of the Maze project.

Part 1. Implementation of the Maze project

You need to implement a Maze program that can generate and render perfect mazes and caves:

  • The program must be developed in C++ language of C++17 standard
  • The program code must be located in the src folder
  • When writing code it is necessary to follow the Google style
  • The program must be built with Makefile which contains standard set of targets for GNU-programs: all, install, uninstall, clean, dvi, dist, tests. Installation directory could be arbitrary, except the building one
  • GUI implementation, based on any GUI library with API for C++17: Qt, SFML, GTK+, Nanogui, Nngui, etc.
  • The program has a button to load the maze from a file, which is set in the format described above
  • Maximum size of the maze is 50x50
  • The loaded maze must be rendered on the screen in a field of 500 x 500 pixels
  • "Wall" thickness is 2 pixels
  • The size of the maze cells themselves is calculated so that the maze occupies the entire field allotted to it.

Part 2. Generation of a perfect maze

Add the ability to automatically generate a perfect maze.
A maze is considered perfect if it is possible to get from each point to any other point in exactly one way.

  • You must generate the maze according to Eller's algorithm
  • The generated maze must not have isolations and loops
  • Prepare full coverage of the perfect maze generation module with unit-tests
  • The user enters only the dimensionality of the maze: the number of rows and columns
  • The generated maze must be saved in the file format described [above] (#maze-description)
  • The created maze should be displayed on the screen as specified in the first part

Part 3. Solving the maze

Add the ability to show the solution to any maze currently shown on the screen:

  • The user sets the starting and ending points
  • The route, which is the solution, must be displayed with a line 2 pixel thick, passing through the middle of all the cells in the maze through which the solution runs.
  • The color of the solution line must be different from the color of the walls, and the field
  • Prepare full coverage of the maze solving module with unit-tests

Part 4. Cave Generation

Add cave generation using a cellular automaton:

  • The user selects the file that describes the cave according to the format described above
  • Use a separate window or tab in the user interface to display the caves
  • Maximum size of the cave is 50 x 50
  • The loaded cave must be rendered on the screen in a field of 500 x 500 pixels
  • The user sets the limits for "birth" and "death" of a cell, as well as the chance for the starting initialization of the cell
  • The "birth" and "death" limits can have values from 0 to 7
  • There should be a step-by-step mode for rendering the results of the algorithm in two variants:
    • Pressing the next step button will lead to rendering the next iteration of the algorithm
    • Pressing the automatic work button starts rendering iterations of the algorithm with a frequency of 1 step in N milliseconds, where the number of milliseconds N is set through a special field in the user interface
  • The size of cells in pixels is calculated so that the cave occupies the entire field allotted to it
  • Prepare full coverage of the cave generation module with unit-tests