A Python program that generates a maze that solves itself using DFS

Overview

Maze Generator And Solver

Program Purpose: Generates a maze that then solves itself

Language: Python and Pygame

Algorithm: Randomized DFS / Floodfill / Recursive Backtracking

Link to Project

Wikipedia Algorithm Pseudocode

Inspired by The Coding Train

Screen.Recording.2021-06-04.at.11.57.55.PM.mov

How the program works

Generation
  1. Maintain a matrix that keeps track of visited cells
  2. Maintain a stack that keeps track of cells on the current path
  3. Start at the top left cell
  4. Randomly choose one of the available neighbor cells
  5. If there are none, go to previous cell in the stack
  6. Color visited cells blue, current cell blue, and remove the white wall
  7. Will eventually return to the top left cell and guarantees a maze
Solving
  1. Maintain a matrix that keeps track of visited cells
  2. Maintain a stack that keeps track of cells on the current path
  3. Start at the top left cell
  4. Randomly choose one of the available neighbor cells without a wall
  5. If there are none, go to previous cell in the stack
  6. Color visited cells green and current cell red
  7. Will eventually reach the bottom right cell, at which point the program restarts

Code Overview

  1. A matrix of cell classes: each cell instance maintains properties such as a wall array, visited / current booleans, and methods to draw to the screen
  2. Simulation Function
    1. Generation - Find next cell, check if it is inbounds and unvisited, remove the wall, move to that cell
    2. Solving - Find next cell, check if it is inbounds and unvisited, move to that cell

Install as executable file

Open the terminal / command line

pip install pyinstaller

Put maze.py inside of a folder called main (or whatever name you want)

Open up a terminal / command line inside the folder

pyinstaller --onefile -w maze.py

Go to dist and select main.exe

Owner
Joshua Liu
USACO Silver, APCSA 5, Python Programmer
Joshua Liu
Python programs, usually short, of considerable difficulty, to perfect particular skills.

Peter Norvig MIT License 2015-2020 pytudes "An étude (a French word meaning study) is an instrumental musical composition, usually short, of considera

Peter Norvig 19.9k Dec 27, 2022
A python script made for personal use to monitor for sports card restocks on target.com since they are sold out often

TargetProductMonitor A python script made for personal use to monitor for sports card resocks on target.com since they are sold out often. When a rest

Bryan Lorden 2 Jul 31, 2022
A Python feed reader library.

reader is a Python feed reader library. It aims to allow writing feed reader applications without any business code, and without enforcing a dependenc

266 Dec 30, 2022
The Great Autoencoder Bake Off

The Great Autoencoder Bake Off The companion repository to a post on my blog. It contains all you need to reproduce the results. Features Currently fe

Tilman Krokotsch 61 Jan 06, 2023
You will need to install a few python packages for this one.

Features Bait support Auto repair will repair every 10 catches Anti detection (still a work in progress) but using random times and click positions Pr

12 Sep 21, 2022
A set of scripts for a two-step procedure to measure the value of access to destinations across several modes of travel within a geographic area.

A set of scripts for a two-step procedure to measure the value of access to destinations across several modes of travel within a geographic area.

Institute for Transportation and Development Policy 2 Oct 16, 2022
Meera 2 May 12, 2022
Python wrapper to different clients to determine how a particular term is used.

Python wrapper to different clients to determine how a particular term is used.

Chris Mungall 3 Oct 24, 2022
Repository voor verhalen over de woningbouw-opgave in Nederland

Analyse plancapaciteit woningen In deze notebook zetten we cijfers op een rij om de woningbouwplannen van Nederlandse gemeenten in kaart te kunnen bre

Follow the Money 10 Jun 30, 2022
Python script that automates the tasks involved in starting a new coding project

Auto Project Builder Automates the repetitive tasks while starting a new project Installation Use the REQUIREMENTS.txt file to install the dependencie

Prathap S S 1 Feb 03, 2022
Ice Skating Simulator for Winter and Christmas [yay]

Ice Skating Simulator for Winter and Christmas [yay]

1 Aug 21, 2022
Holographic Declarative Memory for Python ACT-R

HDM This is the repository for the Holographic Declarative Memory (HDM) module for Python ACT-R. This repository contains: documentation: a paper, con

Carleton Cognitive Modeling Lab 1 Jan 17, 2022
Ramadhan countdown - Simple daily reminder about upcoming Ramadhan

Ramadhan Countdown Bot Simple bot for displaying daily reminder about Islamic pr

Abdurrahman Shofy Adianto 1 Feb 06, 2022
YBlade - Import QBlade blades into Fusion 360

YBlade - Import QBlade blades into Fusion 360 Simple script for Fusion 360 that takes QBlade blade description and constructs the blade: Usage First,

Jan Mrázek 37 Sep 25, 2022
Projeto para ajudar no aprendizado da linguagem Pyhon

Economize Este projeto tem o intuito de criar desáfios para a codificação em Python, fazendo com que haja um maior entendimento da linguagem em seu to

Lucas Cunha Rodrigues 1 Dec 16, 2021
This library is an abstraction for Splunk-related development, maintenance, or migration operations

This library is an abstraction for Splunk-related development, maintenance, or migration operations. It provides a single CLI or SDK to conveniently perform various operations such as managing a loca

NEXTPART 6 Dec 21, 2022
Script to calculate delegator epoch returns for all pillars

znn_delegator_calculator Script to calculate estimated delegator epoch returns for all Pillars, so you can delegate to the best one. You can find me o

2 Dec 03, 2021
Data Applications Project

DBMS project- Hotel Franchise Data and application project By TEAM Kurukunda Bhargavi Pamulapati Pallavi Greeshma Amaraneni What is this project about

Greeshma 1 Nov 28, 2021
Small exercises to get you used to reading and writing Python code!

Pythonlings Welcome to Pythonlings, an automated Python tutorial program (inspired by Rustlings and Haskellings). WIP This program is still working in

鹤翔万里 5 Sep 23, 2022
Syntax highlighting for yarn.lock and bun.lockb files

Yarn.lock Syntax Highlighting Syntax highlighting for yarn.lock and bun.lockb files Installation Plugin is not publushed yet on Package Control, to in

Alexander Kuznetsov 4 Jul 06, 2022