# labyrinth - Python maze generator and solver
This package contains utilities for generating and solving [mazes](https://en.wikipedia.org/wiki/Maze)
using a variety of different algorithms.
## About
See the [docs](https://github.com/will2dye4/labyrinth/blob/master/docs/about.md) for a history of
this project and an introduction to the mathematical underpinnings of the maze generation and
solution algorithms implemented in this package.
## Installation
The easiest way to install the package is to download it from [PyPI](https://pypi.org) using `pip`.
Note that `labyrinth` depends on [Python](https://www.python.org/downloads/) 3.7 or newer; please
ensure that you have a semi-recent version of Python installed before proceeding.
Run the following command in a shell (a UNIX-like environment is assumed):
```
$ pip install labyrinth-py
```
The package does not have any dependencies besides Python itself. If you wish to
sandbox your installation inside a virtual environment, you may choose to use
[virtualenvwrapper](https://virtualenvwrapper.readthedocs.io/en/latest/) or a similar
utility to do so.
When successfully installed, a program called `maze` and another program called `maze-ui`
will be placed on your `PATH`. See the Usage section below for details about how to use
these programs.
## Usage
The `maze` program is a command-line interface for generating mazes.
At any time, you can use the `-h` or `--help` flags to see a summary of options that
the program accepts.
```
$ maze -h
usage: maze [-h] [-a {dfs,kruskal,prim,wilson}] [-g | -m | -l | -s] [dimensions]
Generate mazes using a variety of different algorithms.
positional arguments:
dimensions Dimensions of the maze to generate (e.g., 10x10)
optional arguments:
-h, --help show this help message and exit
-a {dfs,kruskal,prim,wilson}, --algorithm {dfs,kruskal,prim,wilson}
The algorithm to use to generate the maze
-g, --gui, --ui Display a GUI showing the maze being generated
-m, --medium, --medium-size
Open the GUI with medium sized cells instead of small (the default)
-l, --large, --large-size
Open the GUI with large sized cells instead of small (the default)
-s, --solve Show the solution to the maze (only applies to non-GUI mode)
```
Typical usage is `maze <dimensions>`, where `<dimensions>` is a string like `10x10`
describing the dimensions of the maze to generate (width x height). The program will
generate a random maze of the given size and print an ASCII representation of the maze
to the console. Add the `-s` (`--solve`) flag to display the solution to the maze as well.
### Algorithms
By default, `maze` will use a depth-first search algorithm to generate the maze.
To specify a different algorithm, use the `-a` or `--algorithm` flags to `maze`. The
available algorithms are `dfs`, `kruskal`, `prim`, and `wilson`. See the
[docs](https://github.com/will2dye4/labyrinth/blob/master/docs/generation_algorithms.md)
for a description of each of these algorithms.
### Output
When running in non-GUI mode (the default), the `maze` program prints output to the console. Sample
output from running the `maze` program with a custom size is as follows.
```
$ maze 20x10
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+ +---+ + +---+ + + + + + + +---+ +---+ + +
| | | | | | | | | | | |
+ +---+ +---+---+---+---+---+---+---+---+ + + + + +---+---+---+ +
| | | | | | | | | |
+ + +---+---+---+---+ + + + +---+ + +---+---+---+ +---+ + +
| | | | | | | | | | | |
+---+ +---+---+---+---+ + + +---+ +---+ + +---+ + + +---+ +
| | | | | | | | | | |
+ + + + + + + +---+---+ +---+---+---+---+ +---+---+---+---+ +
| | | | | | | | | | | |
+ + + +---+---+ +---+ + +---+---+ + +---+---+ +---+---+ +---+
| | | | | | | | | |
+ +---+---+ + +---+---+---+---+ +---+ +---+---+ +---+---+---+ + +
| | | | | | | | | |
+ +---+ +---+ + + +---+---+---+ +---+ + +---+ +---+ + + +
| | | | | | | | | | | |
+ + +---+---+---+ +---+ +---+---+---+---+ +---+---+---+ +---+---+ +
| | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
```
The following is an example of using the `-a` flag to specify a maze generation
algorithm (see above) and the `-s` flag to show the solution to the maze.
```
$ maze 20x10 -a kruskal -s
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| X X X | | | | | | | | | |
+ +---+ + + +---+ +---+ + +---+ + +---+ + + +---+ +---+
| | X X X | | | | | | | | | | | | |
+ +---+---+---+ + + + + +---+ +---+---+---+---+ + + + + +
| | | | | X | | | | |
+---+ + + + +---+---+---+---+---+---+ + + + +---+---+ +---+ +
| | | | | X | | | | | | | | | |
+ + + + + + + + +---+---+---+---+---+---+ + + + + +---+
| | X | | | | | | |
+---+---+ +---+ + + +---+ +---+---+---+---+ + +---+ + +---+---+
| | X | | | | X X | | | |
+ +---+---+ + +---+ +---+---+---+ +---+ + +---+---+ +---+ + +
| | X X | | | | | | | X | X X | | |
+ +---+---+ + + + + + + +---+ + +---+ +---+---+---+ + +
| | | | | | X X X X X | | X | | X | | |
+ + + + + + +---+---+---+ +---+ + + + + +---+ +---+---+
| | | | | | X X | X | X X X X X X |
+ + + + + + + +---+ +---+---+---+ + + +---+---+---+---+ +
| | | | | | | X X X X X | | | X |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
```
#### Exit Codes
When the program runs successfully, it exits with a code of zero (0). If the program
encounters an error in parsing the arguments that were passed to it, it exits with a code
of two (2).
### GUI Mode
In order to visualize the process of generating mazes, the program also has a GUI mode,
which can be activated with the `-g` (`--gui`) flag to `maze`, or by simply invoking `maze-ui`
instead of `maze`. By default, the GUI will render the maze with small cells, but the `-m` (`--medium`)
or `-l` (`--large`) flags may be passed instead of the `-g` flag to increase the size of the cells.
When running in GUI mode, only error output is printed to the console, and a window will open containing
a visual representation of the maze and controls for generating new mazes using the different algorithms
described [here](https://github.com/will2dye4/labyrinth/blob/master/docs/generation_algorithms.md).
Once a maze has been generated, clicking and dragging from the top left corner of the maze allows the user
to solve the maze if they wish; the goal is to reach the bottom right corner. While a maze is being
generated or solved, the GUI also displays statistics that show the size of the maze, the length of the
current path through the maze, and how much time has elapsed since the maze was generated (i.e., how long
it has taken you to solve it!).
By default, the generation of new mazes will be animated, showing the current path being added to the maze
at each step of the process, but this behavior can be disabled by unchecking the `Animate` box on
the right side of the GUI. When animation is enabled, the `Speed` slider can also be adjusted
to increase or decrease the delay between steps in the animation. Clicking the `Algorithm...` button
will open a dialog box for selecting which algorithm should be used to generate mazes (see above).
Clicking the `Maze Size...` button will open a dialog box for adjusting the size of the maze. Both the
dimensions of the maze and the size of the cells can be customized. The maximum allowed maze size is 100 x 100.
When the `Graph Mode` box is checked, the conventional grid view of the maze will be replaced by a
representation of the graph structure underlying the maze. This mode can be toggled on and off as desired
to compare the traditional visual representation of the maze to the vertices and edges that the program
is actually using to model the maze.
In addition to generating mazes, `maze-ui` is also capable of solving mazes. Once a maze has been
generated, clicking the `Solve` button will show the path through the maze (from the top left corner
to the bottom right corner). If animation is enabled (see above), the drawing of the correct path will
be animated, although the actual process of finding the solution—which is based on a depth-first
search of a "junction graph" of the maze—is not animated.
A few screenshots of the program running in GUI mode are shown below.
## References
This project owes a massive debt of gratitude to the
[series of articles on maze generation](https://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap)
featured on [Jamis Buck's blog](https://weblog.jamisbuck.org). The step-by-step breakdown of various
algorithms, along with simple diagrams and animations showing how the algorithms work, were invaluable in
creating my own adaptations of these algorithms. The
[article on maze-solving algorithms](https://www.kidscodecs.com/maze-solving-algorithms/) on the website of
[*Beanz* magazine](https://www.kidscodecs.com) also came in handy for understanding the concept of the
"junction graph" and using tree traversal to solve mazes.
In addition to the articles linked to above, I also found the following resources helpful while working
on this project:
* https://en.wikipedia.org/wiki/Maze_generation_algorithm
* https://en.wikipedia.org/wiki/Maze_solving_algorithm
* https://tkdocs.com/shipman/
Raw data
{
"_id": null,
"home_page": "https://github.com/will2dye4/labyrinth.git",
"name": "labyrinth-py",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.7,<4.0",
"maintainer_email": "",
"keywords": "dfs,depth first search,kruskal's algorithm,labyrinth,labyrinth generator,labyrinth gui,labyrinth solver,labyrinth ui,maze,maze generator,maze gui,maze solver,maze ui,prim's algorithm,wilson's algorithm",
"author": "William Dye",
"author_email": "",
"download_url": "https://files.pythonhosted.org/packages/a3/a4/6728bbe013a9fbc50bff71f84e80b61306af3dc3dd663d09d07065623694/labyrinth_py-1.0.4.tar.gz",
"platform": null,
"description": "# labyrinth - Python maze generator and solver\n\nThis package contains utilities for generating and solving [mazes](https://en.wikipedia.org/wiki/Maze)\nusing a variety of different algorithms.\n\n## About\n\n\n\nSee the [docs](https://github.com/will2dye4/labyrinth/blob/master/docs/about.md) for a history of\nthis project and an introduction to the mathematical underpinnings of the maze generation and\nsolution algorithms implemented in this package.\n\n## Installation\n\nThe easiest way to install the package is to download it from [PyPI](https://pypi.org) using `pip`.\nNote that `labyrinth` depends on [Python](https://www.python.org/downloads/) 3.7 or newer; please\nensure that you have a semi-recent version of Python installed before proceeding.\n\nRun the following command in a shell (a UNIX-like environment is assumed):\n\n```\n$ pip install labyrinth-py\n```\n\nThe package does not have any dependencies besides Python itself. If you wish to\nsandbox your installation inside a virtual environment, you may choose to use\n[virtualenvwrapper](https://virtualenvwrapper.readthedocs.io/en/latest/) or a similar\nutility to do so.\n\nWhen successfully installed, a program called `maze` and another program called `maze-ui`\nwill be placed on your `PATH`. See the Usage section below for details about how to use\nthese programs.\n\n## Usage\n\nThe `maze` program is a command-line interface for generating mazes.\n\nAt any time, you can use the `-h` or `--help` flags to see a summary of options that\nthe program accepts.\n\n```\n$ maze -h\nusage: maze [-h] [-a {dfs,kruskal,prim,wilson}] [-g | -m | -l | -s] [dimensions]\n\nGenerate mazes using a variety of different algorithms.\n\npositional arguments:\n dimensions Dimensions of the maze to generate (e.g., 10x10)\n\noptional arguments:\n -h, --help show this help message and exit\n -a {dfs,kruskal,prim,wilson}, --algorithm {dfs,kruskal,prim,wilson}\n The algorithm to use to generate the maze\n -g, --gui, --ui Display a GUI showing the maze being generated\n -m, --medium, --medium-size\n Open the GUI with medium sized cells instead of small (the default)\n -l, --large, --large-size\n Open the GUI with large sized cells instead of small (the default)\n -s, --solve Show the solution to the maze (only applies to non-GUI mode)\n```\n\nTypical usage is `maze <dimensions>`, where `<dimensions>` is a string like `10x10`\ndescribing the dimensions of the maze to generate (width x height). The program will\ngenerate a random maze of the given size and print an ASCII representation of the maze\nto the console. Add the `-s` (`--solve`) flag to display the solution to the maze as well.\n\n### Algorithms\n\nBy default, `maze` will use a depth-first search algorithm to generate the maze.\nTo specify a different algorithm, use the `-a` or `--algorithm` flags to `maze`. The\navailable algorithms are `dfs`, `kruskal`, `prim`, and `wilson`. See the\n[docs](https://github.com/will2dye4/labyrinth/blob/master/docs/generation_algorithms.md)\nfor a description of each of these algorithms.\n\n### Output\n\nWhen running in non-GUI mode (the default), the `maze` program prints output to the console. Sample\noutput from running the `maze` program with a custom size is as follows.\n\n```\n$ maze 20x10\n+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n| | | | | | | |\n+---+---+---+ +---+ + +---+ + + + + + + +---+ +---+ + +\n| | | | | | | | | | | |\n+ +---+ +---+---+---+---+---+---+---+---+ + + + + +---+---+---+ +\n| | | | | | | | | |\n+ + +---+---+---+---+ + + + +---+ + +---+---+---+ +---+ + +\n| | | | | | | | | | | |\n+---+ +---+---+---+---+ + + +---+ +---+ + +---+ + + +---+ +\n| | | | | | | | | | |\n+ + + + + + + +---+---+ +---+---+---+---+ +---+---+---+---+ +\n| | | | | | | | | | | |\n+ + + +---+---+ +---+ + +---+---+ + +---+---+ +---+---+ +---+\n| | | | | | | | | |\n+ +---+---+ + +---+---+---+---+ +---+ +---+---+ +---+---+---+ + +\n| | | | | | | | | |\n+ +---+ +---+ + + +---+---+---+ +---+ + +---+ +---+ + + +\n| | | | | | | | | | | |\n+ + +---+---+---+ +---+ +---+---+---+---+ +---+---+---+ +---+---+ +\n| | | |\n+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n```\n\nThe following is an example of using the `-a` flag to specify a maze generation\nalgorithm (see above) and the `-s` flag to show the solution to the maze.\n\n```\n$ maze 20x10 -a kruskal -s\n+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n| X X X | | | | | | | | | |\n+ +---+ + + +---+ +---+ + +---+ + +---+ + + +---+ +---+\n| | X X X | | | | | | | | | | | | |\n+ +---+---+---+ + + + + +---+ +---+---+---+---+ + + + + +\n| | | | | X | | | | |\n+---+ + + + +---+---+---+---+---+---+ + + + +---+---+ +---+ +\n| | | | | X | | | | | | | | | |\n+ + + + + + + + +---+---+---+---+---+---+ + + + + +---+\n| | X | | | | | | |\n+---+---+ +---+ + + +---+ +---+---+---+---+ + +---+ + +---+---+\n| | X | | | | X X | | | |\n+ +---+---+ + +---+ +---+---+---+ +---+ + +---+---+ +---+ + +\n| | X X | | | | | | | X | X X | | |\n+ +---+---+ + + + + + + +---+ + +---+ +---+---+---+ + +\n| | | | | | X X X X X | | X | | X | | |\n+ + + + + + +---+---+---+ +---+ + + + + +---+ +---+---+\n| | | | | | X X | X | X X X X X X |\n+ + + + + + + +---+ +---+---+---+ + + +---+---+---+---+ +\n| | | | | | | X X X X X | | | X |\n+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n```\n\n#### Exit Codes\n\nWhen the program runs successfully, it exits with a code of zero (0). If the program\nencounters an error in parsing the arguments that were passed to it, it exits with a code\nof two (2).\n\n### GUI Mode\n\nIn order to visualize the process of generating mazes, the program also has a GUI mode,\nwhich can be activated with the `-g` (`--gui`) flag to `maze`, or by simply invoking `maze-ui`\ninstead of `maze`. By default, the GUI will render the maze with small cells, but the `-m` (`--medium`)\nor `-l` (`--large`) flags may be passed instead of the `-g` flag to increase the size of the cells.\nWhen running in GUI mode, only error output is printed to the console, and a window will open containing\na visual representation of the maze and controls for generating new mazes using the different algorithms\ndescribed [here](https://github.com/will2dye4/labyrinth/blob/master/docs/generation_algorithms.md).\nOnce a maze has been generated, clicking and dragging from the top left corner of the maze allows the user\nto solve the maze if they wish; the goal is to reach the bottom right corner. While a maze is being\ngenerated or solved, the GUI also displays statistics that show the size of the maze, the length of the\ncurrent path through the maze, and how much time has elapsed since the maze was generated (i.e., how long\nit has taken you to solve it!).\n\nBy default, the generation of new mazes will be animated, showing the current path being added to the maze\nat each step of the process, but this behavior can be disabled by unchecking the `Animate` box on\nthe right side of the GUI. When animation is enabled, the `Speed` slider can also be adjusted\nto increase or decrease the delay between steps in the animation. Clicking the `Algorithm...` button\nwill open a dialog box for selecting which algorithm should be used to generate mazes (see above).\nClicking the `Maze Size...` button will open a dialog box for adjusting the size of the maze. Both the\ndimensions of the maze and the size of the cells can be customized. The maximum allowed maze size is 100 x 100.\n\nWhen the `Graph Mode` box is checked, the conventional grid view of the maze will be replaced by a\nrepresentation of the graph structure underlying the maze. This mode can be toggled on and off as desired\nto compare the traditional visual representation of the maze to the vertices and edges that the program\nis actually using to model the maze.\n\nIn addition to generating mazes, `maze-ui` is also capable of solving mazes. Once a maze has been\ngenerated, clicking the `Solve` button will show the path through the maze (from the top left corner\nto the bottom right corner). If animation is enabled (see above), the drawing of the correct path will\nbe animated, although the actual process of finding the solution—which is based on a depth-first\nsearch of a \"junction graph\" of the maze—is not animated.\n\nA few screenshots of the program running in GUI mode are shown below.\n\n\n\n\n\n\n\n\n\n\n\n\n\n## References\n\nThis project owes a massive debt of gratitude to the\n[series of articles on maze generation](https://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap)\nfeatured on [Jamis Buck's blog](https://weblog.jamisbuck.org). The step-by-step breakdown of various\nalgorithms, along with simple diagrams and animations showing how the algorithms work, were invaluable in\ncreating my own adaptations of these algorithms. The \n[article on maze-solving algorithms](https://www.kidscodecs.com/maze-solving-algorithms/) on the website of\n[*Beanz* magazine](https://www.kidscodecs.com) also came in handy for understanding the concept of the\n\"junction graph\" and using tree traversal to solve mazes.\n\nIn addition to the articles linked to above, I also found the following resources helpful while working\non this project:\n\n* https://en.wikipedia.org/wiki/Maze_generation_algorithm\n* https://en.wikipedia.org/wiki/Maze_solving_algorithm\n* https://tkdocs.com/shipman/\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Generate and solve mazes using various algorithms",
"version": "1.0.4",
"project_urls": {
"Homepage": "https://github.com/will2dye4/labyrinth.git",
"Repository": "https://github.com/will2dye4/labyrinth.git"
},
"split_keywords": [
"dfs",
"depth first search",
"kruskal's algorithm",
"labyrinth",
"labyrinth generator",
"labyrinth gui",
"labyrinth solver",
"labyrinth ui",
"maze",
"maze generator",
"maze gui",
"maze solver",
"maze ui",
"prim's algorithm",
"wilson's algorithm"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "538db7482a511dc1611cffc6b093652fc3de1a206ecb4bd4d347817db5589caa",
"md5": "691936df4c1d008a93a420f0a7d641de",
"sha256": "1a2ab0fa1a4fcc2e6f7703d0d3dcba13336a0897e0f88902beba285846f399fe"
},
"downloads": -1,
"filename": "labyrinth_py-1.0.4-py3-none-any.whl",
"has_sig": false,
"md5_digest": "691936df4c1d008a93a420f0a7d641de",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.7,<4.0",
"size": 27270,
"upload_time": "2023-09-19T19:51:52",
"upload_time_iso_8601": "2023-09-19T19:51:52.720885Z",
"url": "https://files.pythonhosted.org/packages/53/8d/b7482a511dc1611cffc6b093652fc3de1a206ecb4bd4d347817db5589caa/labyrinth_py-1.0.4-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "a3a46728bbe013a9fbc50bff71f84e80b61306af3dc3dd663d09d07065623694",
"md5": "1af5e2543b38c10c54c73457cba81d36",
"sha256": "73102aca9d004ac31322cf06944c0069985679dc463feafdd8e48861068dc131"
},
"downloads": -1,
"filename": "labyrinth_py-1.0.4.tar.gz",
"has_sig": false,
"md5_digest": "1af5e2543b38c10c54c73457cba81d36",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7,<4.0",
"size": 23980,
"upload_time": "2023-09-19T19:51:54",
"upload_time_iso_8601": "2023-09-19T19:51:54.289591Z",
"url": "https://files.pythonhosted.org/packages/a3/a4/6728bbe013a9fbc50bff71f84e80b61306af3dc3dd663d09d07065623694/labyrinth_py-1.0.4.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-09-19 19:51:54",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "will2dye4",
"github_project": "labyrinth",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "labyrinth-py"
}
JSON
