Skip to content

Maze

Jump to bottom
alinamuliak edited this page Jun 1, 2021 · 11 revisions

For realization for the maze solver, the Maze and _CellPosition classes are created.

To work with these classes, first, there should be a file with the right structure.

The file with maze should have the next structure:

  • the starting position is marked as -1, AssertionError if not found;
  • the ending position is marked as 2, AssertionError if not found;
  • the walls are marked as 1;
  • the empty position is marked as 0.

Here is an example:

1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1
1 0 0 1 0 1 1 1 0 0 0 1 0 1 0 1
1 1 0 1 0 0 0 1 1 0 1 0 0 1 0 1
1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1
1 0 1 0 1 0 0 1 1 1 1 1 0 1 0 1
1 0 1 1 1 0 1 1 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 0 0 1 0 1 0 1 1 1
1 0 1 0 1 0 0 0 1 1 0 1 0 1 0 1
1 0 1 0 1 0 1 1 0 0 1 0 0 0 0 1
1 0 1 0 1 0 0 0 1 0 1 1 0 1 1 1
1 0 1 1 1 1 1 0 0 0 1 0 0 0 0 1
1 0 0 0 0 0 1 1 1 0 1 0 1 1 0 1
1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 1
1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

class Maze

Global Variables:

  • FREE = 0
  • MAZE_WALL = 1
  • EXIT = 2
  • PATH_TOKEN = 3
  • TRIED_TOKEN = 4

Attributes:

  • maze: The list of lists representing the maze.
  • _start: The starting position of the maze; marked as -1 on the maze.
  • _exit: The exit position of the maze; marked as 2 on the maze.
  • visualization: The bool value; if true - visualization will be displayed.

Methods:

  • __init__: takes the name of the file with the maze and the visualization parameter which is set to True by default; init the Maze object with all the attributes using the next method.
  • _build_maze: Read the given file, creates a list of lists to save all the columns and rows of the maze; when -1 or 2 is found it assigns this positions to self._start and self._end in accordance.
  • find_path: Attempts to solve the maze by finding a path from the starting cell to the exit. Returns True if a path is found and False otherwise. While solving the maze it changes cells, where: 0 - not tried cells; 1 - walls; 2 - exit; 3 - found path; 4 - tried cells.

Algorithm

Starting from the starting position, the algorithm selects the following steps as follows: up, right, down, and left. The step is considered valid if the indexes are within the maze scope and the cell is free.

After making the step, the correct cell is added to the stack, and the _mark_path function marks this cell as a path to the exit. If following this path the algorithm comes to a standstill (meaning that there are no valid moves up, right, down, or left), removing cells from the stack, we go back until there is another way. While returning back, all cells in the path that did not lead to the finish are marked as tried by the _mark_tried function.

The algorithm is repeated until a finish is found or the algorithm returns to the starting position, for which there are no valid steps left; in that case - the maze is not solved.

If the visualization parameter is set to True, then at each step of the move selection the corresponding cell is marked with pink color when passing and grey if returning back.

  • _valid_move: Returns True if the given cell position is a valid move.
  • _exit_found: Helper method to determine if the exit was found. Return True if the given position is the end of the maze, otherwise - False.
  • _mark_tried: Drops a TRIED_TOKEN at the given cell.
  • _mark_path: Drops a PATH_TOKEN at the given cell.
  • __str__: Returns a text-based representation of the maze.

class _CellPosition

  • private data class for holding a cell position. Attributes:
  • row: The row of a certain cell position.
  • col: The column of a certain cell position.

Example of the program:

For the file with the content shown in the example above, the final maze will look like this:

1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 3 1 1 4 4 4 4 4 1 4 4 4 1 4 1 
1 3 3 1 4 1 1 1 4 4 4 1 4 1 4 1 
1 1 3 1 4 4 4 1 1 4 1 4 4 1 4 1 
1 3 3 4 4 1 4 1 4 4 1 4 1 4 4 1 
1 3 1 4 1 4 4 1 1 1 1 1 4 1 4 1 
1 3 1 1 1 4 1 1 3 3 3 3 3 4 4 1 
1 3 4 4 1 1 1 3 3 1 0 1 3 1 1 1 
1 3 1 4 1 3 3 3 1 1 0 1 3 1 4 1 
1 3 1 4 1 3 1 1 4 4 1 0 3 4 4 1 
1 3 1 4 1 3 3 3 1 4 1 1 3 1 1 1 
1 3 1 1 1 1 1 3 3 3 1 0 3 3 3 1 
1 3 3 3 3 3 1 1 1 3 1 0 1 1 3 1 
1 1 1 0 1 3 1 4 1 3 1 0 1 0 3 1 
1 0 0 0 1 3 3 3 3 3 1 0 0 1 3 3 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

And with the visualization parameter set to true:

solved maze

The given realization of the Maze solver uses turtle and dataclasses python modules, and lliststack module implementation of which was provided on lessons of the Fundamentals of Programming at UCU.

To enable visualization, text, box and drawMaze functions are implemented, which are taken from the given resourse and are used not for the algorithm, but for visualization.

Clone this wiki locally