maniac-en / maze_solver

Training repo from a course

Maniac's Maze Solver (mms)

Maze solving program built using python tkinter

What and why?

This program is built for educational purpose of visualizing the Depth-first search algorithm using a maze where-in the maze is built as well as solved both using the DFS!

How to run

• Initialize your virtual environment
• This should setup and build a binary called mms in your path

pip install --editable .

• Now run mms to run the maze solver!

By-default the maze size is 15 rows and 15 columns but you can also change it in command line argument as follows:

(venv) ~/w/maze_solver (main) $ mms --help
Usage: mms [OPTIONS]

  Welcome to Maniac's Maze solver

Options:
  --maze-size <INTEGER INTEGER>...
                                  row, column for the maze  [default: 15, 15]
  --help                          Show this message and exit.

(venv) ~/w/maze_solver (main) $ mms --maze-size 12, 19

Demo Video

• Red path is overall solution and partial gray paths are backtracked paths.
• Video somehow doesn't load in firefox, works fine in chrome/chromium based!

mms.mov

maze_solver's Issues

maze size cli arg

--maze-size row col

Update Readme

Add test cases/docstrings

Add test status checks via GitHub actions

Extend the maze start and finish in solution

Currently the solution for maze starts from center of first cell and finishes at
center of last cell. Extend it such that it starts from beginning of first cell
and goes till ending of last cell.

Ideal place to add this functionality would be within Maze._solve method:

maze_solver/maze.py

Lines 123 to 125 in 0890c03

	def _solve(self) -> bool:
	self._reset_cells_visited()
	return self._solve_r(0, 0)

`Cell.draw_move` func has wrong implementation

It should call Window.draw_line instead of Cell.draw method because:

• The goal of Cell.draw_move is to draw a Line from center of one cell to another

maze_solver/cell.py

Lines 56 to 66 in 182ee06

	def draw_move(self, to_cell, undo=False) -> bool:
	self.move_color = "red" if not undo else "gray"
	x1, y1 = self.get_center()
	x2, y2 = to_cell.get_center()
	if x1 is None or\
	y1 is None or\
	x2 is None or\
	y2 is None:
	return False
	self.draw(x1, y1, x2, y2, self.move_color)
	return True

• Window.draw_line draws Line from one Point to another Point whereas Cell.draw is responsible to draw a Cell where one Point is it's left-most corner and another Point is it's right-most corner

maze_solver/cell.py

Lines 18 to 45 in 182ee06

	def draw(self, x1, y1, x2, y2, fill_color="black") -> None:
	self._x1 = x1
	self._y1 = y1
	self._x2 = x2
	self._y2 = y2
	self.left_line = Line(Point(x1, y1), Point(x1, y2))
	self.top_line = Line(Point(x1, y1), Point(x2, y1))
	self.right_line = Line(Point(x2, y1), Point(x2, y2))
	self.bottom_line = Line(Point(x1, y2), Point(x2, y2))
	if self._win:
	bg_color = self._win.background
	self.left_fill_color = fill_color if self.has_left_wall else bg_color
	self.top_fill_color = fill_color if self.has_top_wall else bg_color
	self.right_fill_color = fill_color if self.has_right_wall else bg_color
	self.bottom_fill_color = fill_color if self.has_bottom_wall else bg_color
	self._win.draw_line(self.left_line, self.left_fill_color)
	self._win.draw_line(self.top_line, self.top_fill_color)
	self._win.draw_line(self.right_line, self.right_fill_color)
	self._win.draw_line(self.bottom_line, self.bottom_fill_color)
	else:
	bg_color = "white"
	self.left_fill_color = fill_color if self.has_left_wall else bg_color
	self.top_fill_color = fill_color if self.has_top_wall else bg_color
	self.right_fill_color = fill_color if self.has_right_wall else bg_color
	self.bottom_fill_color = fill_color if self.has_bottom_wall else bg_color
	return

maze_solver/graphics.py

Lines 32 to 35 in 182ee06

	def draw_line(self, line, fill_color="black") -> None:
	if line:
	line.draw(self.__canvas, fill_color)
	return