# Lapyrinth
This **Mazer Maker Solver** made entirely in Python is a program where you can generate maze with many different algorithm and solving them with different pathfinders. Nothing more, nothing less.
## Summary
### 1. [Features](#1---features)
### 2. [Installation](#2---installation)
### 3. [Generate a maze](#3---generate-a-maze)
### 4. [Example of mazes](#4---example-of-mazes)
### 5. [Save a maze](#5---save-a-maze)
### 6. [Load a maze](#6---load-a-maze)
### 7. [Solve a maze](#7---solve-a-maze)
### 8. [Maze Generation Benchmarks](#8---maze-generation-benchmarks)
### 9. [Pathfinders Benchmarks](#9---pathfinders-benchmarks)
### 10. [Improve the project](#10---improve-the-project)
## 1 - Features
- Generate any maze of any size
- Choose different algorithms from 11 of them (and more with different parameters)
- Generate an image of the maze generated
- Save the maze to load it later
- Solve them with various pathfinders among 9 of them
- Generate an image of the maze solved
## 2 - Installation
To begin, download and uncompress the **[latest version](https://github.com/Pietot/Maze-Maker-Solver/archive/refs/heads/main.zip)** or clone it by using one of the following command:
```
https://github.com/Pietot/Maze-Maker-Solver.git
```
or
```
git@github.com:Pietot/Maze-Maker-Solver.git
```
Then, you need to install all dependencies by opening a CLI (command line interface) and write these lines
```
cd "{the path to the project directory}"
pip install -r requirements.txt
```
## 3 - Generate a maze
To generate your first maze, write these lines at the end of <a href="https://github.com/Pietot/Maze-Maker-Solver/blob/main/maze.py">maze.py</a>:
```python
# Optional
start = (1, 7)
end = (5, 9)
# Or Maze(x) for a maze of x*x cells
maze = Maze(x, y, start, end)
# Choose the algorithm you want below
maze.binary_tree()
# If you want to make a so-called imperfect maze.
# You can specify the number of wall to removed
# or the probability that a wall will be removed
maze.make_imperfect_maze("number", 5)
# If you want to print the maze in the CLI
print(maze)
# If you want to generate a .png file of the maze
maze.generate_image()
```
or write the same lines in another python file in the same directory as <a href="https://github.com/Pietot/Maze-Maker-Solver/blob/main/maze.py">maze.py</a> but with an import at the beginning of the file like this:
```python
from maze import Maze
# Optional
start = (1, 7)
end = (5, 9)
# Or Maze(x) for a maze of x*x cells
maze = Maze(x, y, start=start, end=end)
# Choose the algorithm you want below
maze.binary_tree()
# If you want to make a so-called imperfect maze.
# You can specify the number of wall to removed
# or the probability that a wall will be removed
maze.make_imperfect_maze("number", 5)
# If you want to print the maze in the CLI
print(maze)
# If you want to generate a .png file of the maze
maze.generate_image()
```
> **Note**: Obviously, the larger the maze, the longer it will take to create and generate the image.
## 4 - Example of mazes
That's it. See, it's very simple. You can go with all of these algorithms:
- Kruskal
<p align="center">
<img src="assets/images/kruskal.png" width="49%" alt="Image illustrating a maze after using Kruskal's algorithm">
<img src="assets/gifs/kruskal.gif" width="49%" alt="Animation showing the process of Kruskal's algorithm"> <br><br>
</p>
- Randomized Depth First Search
<p align="center">
<img src="assets/images/rdfs.png" width="49%"alt="Image illustrating a maze after using Randomized Depth First Search algorithm"/>
<img src="assets/gifs/rdfs.gif" width="49%"alt="Animation showing the process of Randomized Depth First Search algorithm"> <br><br>
</p>
- Prim
<p align="center">
<img src="assets/images/prim.png" width="49%"alt="Image illustrating a maze after using Prim's algorithm"/>
<img src="assets/gifs/prim.gif" width="49%"alt="Animation showing the process of Prim's algorithm"> <br><br>
</p>
- Hunt and Kill
<p align="center">
<img src="assets/images/hunt_and_kill.png" width="49%"alt="Image illustrating a maze after using Hunt and Kill algorithm"/>
<img src="assets/gifs/hunt_and_kill.gif" width="49%"alt="Animation showing the process of Hunt and Kill algorithm"> <br><br>
</p>
- Eller (may vary depending on parameters)
<p align="center">
<img src="assets/images/eller.png" width="49%"alt="Image illustrating a maze after using Eller's algorithm"/>
<img src="assets/gifs/eller.gif" width="49%"alt="Animation showing the process of Eller's algorithm"> <br><br>
</p>
- Iterative Division
<p align="center">
<img src="assets/images/iterative_division.png" width="49%"alt="Image illustrating a maze after using Iterative Division algorithm"/>
<img src="assets/gifs/iterative_division.gif" width="49%"alt="Animation showing the process of Iterative Division algorithm"> <br><br>
</p>
- Binary Tree (may vary depending on parameters)
<p align="center">
<img src="assets/images/binary_tree.png" width="49%"alt="Image illustrating a maze after using Binary Tree algorithm"/>
<img src="assets/gifs/binary_tree.gif" width="49%"alt="Animation showing the process of Binary Tree algorithm"> <br><br>
</p>
- Sidewinder (may vary depending on parameters)
<p align="center">
<img src="assets/images/sidewinder.png" width="49%"alt="Image illustrating a maze after using Sidewinder algorithm"/>
<img src="assets/gifs/sidewinder.gif" width="49%"alt="Animation showing the process of Sidewinder algorithm"> <br><br>
</p>
- Growing Tree (may vary depending on parameters)
<p align="center">
<img src="assets/images/growing_tree.png" width="49%"alt="Image illustrating a maze after using Growing Tree algorithm"/>
<img src="assets/gifs/growing_tree.gif" width="49%"alt="Animation showing the process of Growing Tree algorithm"> <br><br>
</p>
- Aldous-Broder
<p align="center">
<img src="assets/images/aldous_broder.png" width="49%"alt="Image illustrating a maze after using Aldous-Broder algorithm"/>
<img src="assets/gifs/aldous_broder.gif" width="49%"alt="Animation showing the process of Aldous-Broder algorithm"> <br><br>
</p>
- Wilson
<p align="center">
<img src="assets/images/wilson.png" width="49%"alt="Image illustrating a maze after using Wilson's algorithm"/>
<img src="assets/gifs/wilson.gif" width="49%"alt="Animation showing the process of Wilson's algorithm"> <br><br>
</p>
## 5 - Save a maze
If you want to save the maze you've created, three options are available to you:
#### - Save the entire object:
```py
# Filename is optional
filename = "maze_object"
maze.save_maze("pkl", filename)
```
Pros / Cons:
- Saves all the data of the maze
- Can't be edited
- Easy to load
- Heavy file (~15Mo for a 1000x1000 cell maze)
#### - Save the maze's array as a binary file:
```py
# Filename is optional
filename = "maze_binary"
maze.save_maze("npy", filename)
```
Pros / Cons:
- Only saves the maze's array
- Can't be edited
- Fast to load
- Heavy file (~15Mo for a 1000x1000 cell maze)
#### - Save the maze's array as a text file:
```py
# Filename is optional
filename = "maze_text"
maze.save_maze("txt", filename)
```
Pros / Cons:
- Only saves the maze's array
- Easy to read and edit
- Slow to load
- Light file (~7.5Mo for a 1000x1000 cell maze)
## 6 - Load a maze
If you want to load the maze you've saved, two options are available to you depending on the file format:
#### - Load a .pkl file:
```py
from maze import load_object
maze = load_object("maze_object.pkl")
```
#### - Load a .npy or a .txt file:
```py
from maze import Maze
maze = Maze()
maze.load_maze("maze_binary.npy")
# Or
maze.load_maze("maze_text.txt")
```
> **Note**: The file must be in the same directory as the script or you must specify the path to the file.
## 7 - Solve a maze
Here's the code to follow to solve a maze:
```py
from maze import Maze
import pathfinders
maze = Maze(10)
maze.iterative_division()
path = pathfinders.depth_first_search(maze)
# If you want to print the solved maze in the CLI
pathfinders.print_path(maze, path)
# If you want to generate a .png file of the solved maze
pathfinders.generate_path(maze, path)
```
Here are all the pathfinders available:
- Right Hand Rule
<p align="center">
<img src="assets/gifs/right_hand.gif" width="49%"alt="Animation showing the process of the Right Hand rule pathfinder"> <br><br>
</p>
- Left Hand Rule
<p align="center">
<img src="assets/gifs/left_hand.gif" width="49%"alt="Animation showing the process of the Left Hand rule pathfinder"> <br><br>
</p>
- Random Mouse
<p align="center">
<img src="assets/gifs/random_mouse.gif" width="49%"alt="Animation showing the process of the Random Mouse pathfinder"> <br><br>
</p>
- Pledge (may vary depending on parameters)
<p align="center">
<img src="assets/gifs/pledge.gif" width="49%"alt="Animation showing the process of Pledge's pathfinder"> <br><br>
</p>
- Dead End Filler
<p align="center">
<img src="assets/gifs/dead_end_filler.gif" width="49%"alt="Animation showing the process of Dead End Filler pathfinder"> <br><br>
</p>
- Depth First Search
<p align="center">
<img src="assets/gifs/dfs.gif" width="49%"alt="Animation showing the process of Deep First Search pathfinder"> <br><br>
</p>
- Breadth First Search
<p align="center">
<img src="assets/gifs/bfs.gif" width="49%"alt="Animation showing the process of Breadth First Search pathfinder"> <br><br>
</p>
- Greedy Best First Search
<p align="center">
<img src="assets/gifs/gbfs.gif" width="49%"alt="Animation showing the process of Greedy Best First Search pathfinder"> <br><br>
</p>
- A\*
<p align="center">
<img src="assets/gifs/a_star.gif" width="49%"alt="Animation showing the process of A* pathfinder"> <br><br>
</p>
## 8 - Maze Generation Benchmarks
Wonder which algorithm is **faster**?
Well.. I already did it for you! So here you are:
- Chart for slow algorithms:
<img src="assets/svg/generation_slow.svg"><br><br>
- Chart for moderately fast algorithms:
<img src="assets/svg/generation_medium.svg"><br><br>
- Chart for fast algorithms:
<img src="assets/svg/generation_fast.svg"><br><br>
- Chart for all algorithms:
<img src="assets/svg/generation_full.svg"><br><br>
> **Note**: Aldous-Broder and Wilson algorithms were not tested because they are truly random (""luck"" based in other words), so their times are very inconsistent on a generation to another. But for an idea, they are even slower than Kruskal's algorithm
If you want the values of these graphs, watch this:
<img src="assets/images/csv_generation_screen.png">
<p align="center">
<br>
<a href="assets/csv/maze_generation_time.csv">Download csv here
</a>
<br>
</p>
> **Note**: These values can change depending on the version of Python and your PC<br><br>
> For these benchmarks, I used Python 3.12.0 implemented with CPython on a ryzen 5 3600, rtx 2060 with 2\*8GB of RAM clocked at 3600Hz on Windows 10.<br>
> These benchmarks were all tested at the same time (multiprocessing) so the results are higher than if they were tested one by one
## 9 - Pathfinders Benchmarks
Wonder which pathfinder is the most **efficient**?
Well.. I also already did it for you! So here you are:
> **Note** For better comparison, I used the same maze with default start/end for all pathfinders, for all size. Moreover, I used one set of mazes generated with RDFS (algorithm with the lowest dead-end rate) and another set of mazes generated with Kruskal (algorithm with the highest dead-ends rate). They're all available in the <a href="assets/pkl">pkl directory</a>.
- Chart for fast pathfinders on RDFS mazes:
<img src="assets/svg/pathfinder_fast_rdfs.svg"><br><br>
- Chart for all pathfinders on RDFS mazes:
<img src="assets/svg/pathfinder_full_rdfs.svg"><br><br>
- Chart for fast pathfinders on Kruskal mazes:
<img src="assets/svg/pathfinder_fast_kruskal.svg"><br><br>
- Chart for all pathfinders on Kruskal mazes:
<img src="assets/svg/pathfinder_full_kruskal.svg"><br><br>
## 10 - Improve the project
If you like this project and/or want to help or improve it, you can:
- Create an issue if you find a bug or want to suggest a feature or any improvement (no matter how small it is).
- Create a pull request if you want to add a feature, fix a bug or improve the code.
- Contact me if you want to talk about the project or anything else (Discord: pietot).
> **Note**: If you want to be guided/helped, you already have a file named <a href="IMPROVEMENT.txt">IMPROVEMENTS.TXT</a> in the project directory, where you can see all the improvements that can be made.
Raw data
{
"_id": null,
"home_page": "https://github.com/Pietot/Lapyrinth",
"name": "Lapyrinth",
"maintainer": "Pi\u00e9t\u00f4t",
"docs_url": null,
"requires_python": ">=3.10",
"maintainer_email": null,
"keywords": "maze, pathfinding, algorithm, labyrinth, pathfinder, maze generator",
"author": "Pi\u00e9t\u00f4t",
"author_email": "baptiste.blasquez@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/43/f2/e20abb7c262ab9bc6a3b210e6f9024bcb3cf126ee88e84ca06d9c9715e3c/Lapyrinth-1.13.tar.gz",
"platform": null,
"description": "# Lapyrinth\r\n\r\n\r\n\r\n\r\nThis **Mazer Maker Solver** made entirely in Python is a program where you can generate maze with many different algorithm and solving them with different pathfinders. Nothing more, nothing less.\r\n\r\n## Summary\r\n\r\n### 1. [Features](#1---features)\r\n\r\n### 2. [Installation](#2---installation)\r\n\r\n### 3. [Generate a maze](#3---generate-a-maze)\r\n\r\n### 4. [Example of mazes](#4---example-of-mazes)\r\n\r\n### 5. [Save a maze](#5---save-a-maze)\r\n\r\n### 6. [Load a maze](#6---load-a-maze)\r\n\r\n### 7. [Solve a maze](#7---solve-a-maze)\r\n\r\n### 8. [Maze Generation Benchmarks](#8---maze-generation-benchmarks)\r\n\r\n### 9. [Pathfinders Benchmarks](#9---pathfinders-benchmarks)\r\n\r\n### 10. [Improve the project](#10---improve-the-project)\r\n\r\n## 1 - Features\r\n\r\n- Generate any maze of any size\r\n\r\n- Choose different algorithms from 11 of them (and more with different parameters)\r\n\r\n- Generate an image of the maze generated\r\n\r\n- Save the maze to load it later\r\n\r\n- Solve them with various pathfinders among 9 of them\r\n\r\n- Generate an image of the maze solved\r\n\r\n## 2 - Installation\r\n\r\nTo begin, download and uncompress the **[latest version](https://github.com/Pietot/Maze-Maker-Solver/archive/refs/heads/main.zip)** or clone it by using one of the following command:\r\n\r\n```\r\nhttps://github.com/Pietot/Maze-Maker-Solver.git\r\n```\r\n\r\nor\r\n\r\n```\r\ngit@github.com:Pietot/Maze-Maker-Solver.git\r\n```\r\n\r\nThen, you need to install all dependencies by opening a CLI (command line interface) and write these lines\r\n\r\n```\r\ncd \"{the path to the project directory}\"\r\npip install -r requirements.txt\r\n```\r\n\r\n## 3 - Generate a maze\r\n\r\nTo generate your first maze, write these lines at the end of <a href=\"https://github.com/Pietot/Maze-Maker-Solver/blob/main/maze.py\">maze.py</a>:\r\n\r\n```python\r\n# Optional\r\nstart = (1, 7)\r\nend = (5, 9)\r\n# Or Maze(x) for a maze of x*x cells\r\nmaze = Maze(x, y, start, end)\r\n# Choose the algorithm you want below\r\nmaze.binary_tree()\r\n# If you want to make a so-called imperfect maze.\r\n# You can specify the number of wall to removed\r\n# or the probability that a wall will be removed\r\nmaze.make_imperfect_maze(\"number\", 5)\r\n# If you want to print the maze in the CLI\r\nprint(maze)\r\n# If you want to generate a .png file of the maze\r\nmaze.generate_image()\r\n```\r\n\r\nor write the same lines in another python file in the same directory as <a href=\"https://github.com/Pietot/Maze-Maker-Solver/blob/main/maze.py\">maze.py</a> but with an import at the beginning of the file like this:\r\n\r\n```python\r\nfrom maze import Maze\r\n\r\n# Optional\r\nstart = (1, 7)\r\nend = (5, 9)\r\n# Or Maze(x) for a maze of x*x cells\r\nmaze = Maze(x, y, start=start, end=end)\r\n# Choose the algorithm you want below\r\nmaze.binary_tree()\r\n# If you want to make a so-called imperfect maze.\r\n# You can specify the number of wall to removed\r\n# or the probability that a wall will be removed\r\nmaze.make_imperfect_maze(\"number\", 5)\r\n# If you want to print the maze in the CLI\r\nprint(maze)\r\n# If you want to generate a .png file of the maze\r\nmaze.generate_image()\r\n```\r\n\r\n> **Note**: Obviously, the larger the maze, the longer it will take to create and generate the image.\r\n\r\n## 4 - Example of mazes\r\n\r\nThat's it. See, it's very simple. You can go with all of these algorithms:\r\n\r\n- Kruskal\r\n<p align=\"center\">\r\n<img src=\"assets/images/kruskal.png\" width=\"49%\" alt=\"Image illustrating a maze after using Kruskal's algorithm\">\r\n<img src=\"assets/gifs/kruskal.gif\" width=\"49%\" alt=\"Animation showing the process of Kruskal's algorithm\"> <br><br>\r\n</p>\r\n\r\n- Randomized Depth First Search\r\n<p align=\"center\">\r\n<img src=\"assets/images/rdfs.png\" width=\"49%\"alt=\"Image illustrating a maze after using Randomized Depth First Search algorithm\"/> \r\n<img src=\"assets/gifs/rdfs.gif\" width=\"49%\"alt=\"Animation showing the process of Randomized Depth First Search algorithm\"> <br><br>\r\n</p>\r\n\r\n- Prim\r\n<p align=\"center\">\r\n<img src=\"assets/images/prim.png\" width=\"49%\"alt=\"Image illustrating a maze after using Prim's algorithm\"/> \r\n<img src=\"assets/gifs/prim.gif\" width=\"49%\"alt=\"Animation showing the process of Prim's algorithm\"> <br><br>\r\n</p>\r\n\r\n- Hunt and Kill\r\n<p align=\"center\">\r\n<img src=\"assets/images/hunt_and_kill.png\" width=\"49%\"alt=\"Image illustrating a maze after using Hunt and Kill algorithm\"/> \r\n<img src=\"assets/gifs/hunt_and_kill.gif\" width=\"49%\"alt=\"Animation showing the process of Hunt and Kill algorithm\"> <br><br>\r\n</p>\r\n\r\n- Eller (may vary depending on parameters)\r\n<p align=\"center\">\r\n<img src=\"assets/images/eller.png\" width=\"49%\"alt=\"Image illustrating a maze after using Eller's algorithm\"/> \r\n<img src=\"assets/gifs/eller.gif\" width=\"49%\"alt=\"Animation showing the process of Eller's algorithm\"> <br><br>\r\n</p>\r\n\r\n- Iterative Division\r\n<p align=\"center\">\r\n<img src=\"assets/images/iterative_division.png\" width=\"49%\"alt=\"Image illustrating a maze after using Iterative Division algorithm\"/> \r\n<img src=\"assets/gifs/iterative_division.gif\" width=\"49%\"alt=\"Animation showing the process of Iterative Division algorithm\"> <br><br>\r\n</p>\r\n\r\n- Binary Tree (may vary depending on parameters)\r\n<p align=\"center\">\r\n<img src=\"assets/images/binary_tree.png\" width=\"49%\"alt=\"Image illustrating a maze after using Binary Tree algorithm\"/> \r\n<img src=\"assets/gifs/binary_tree.gif\" width=\"49%\"alt=\"Animation showing the process of Binary Tree algorithm\"> <br><br>\r\n</p>\r\n\r\n- Sidewinder (may vary depending on parameters)\r\n<p align=\"center\">\r\n<img src=\"assets/images/sidewinder.png\" width=\"49%\"alt=\"Image illustrating a maze after using Sidewinder algorithm\"/> \r\n<img src=\"assets/gifs/sidewinder.gif\" width=\"49%\"alt=\"Animation showing the process of Sidewinder algorithm\"> <br><br>\r\n</p>\r\n\r\n- Growing Tree (may vary depending on parameters)\r\n<p align=\"center\">\r\n<img src=\"assets/images/growing_tree.png\" width=\"49%\"alt=\"Image illustrating a maze after using Growing Tree algorithm\"/> \r\n<img src=\"assets/gifs/growing_tree.gif\" width=\"49%\"alt=\"Animation showing the process of Growing Tree algorithm\"> <br><br>\r\n</p>\r\n\r\n- Aldous-Broder\r\n<p align=\"center\">\r\n<img src=\"assets/images/aldous_broder.png\" width=\"49%\"alt=\"Image illustrating a maze after using Aldous-Broder algorithm\"/> \r\n<img src=\"assets/gifs/aldous_broder.gif\" width=\"49%\"alt=\"Animation showing the process of Aldous-Broder algorithm\"> <br><br>\r\n</p>\r\n\r\n- Wilson\r\n<p align=\"center\">\r\n<img src=\"assets/images/wilson.png\" width=\"49%\"alt=\"Image illustrating a maze after using Wilson's algorithm\"/> \r\n<img src=\"assets/gifs/wilson.gif\" width=\"49%\"alt=\"Animation showing the process of Wilson's algorithm\"> <br><br>\r\n</p>\r\n\r\n## 5 - Save a maze\r\n\r\nIf you want to save the maze you've created, three options are available to you:\r\n\r\n#### - Save the entire object:\r\n\r\n```py\r\n# Filename is optional\r\nfilename = \"maze_object\"\r\nmaze.save_maze(\"pkl\", filename)\r\n```\r\n\r\nPros / Cons:\r\n\r\n- Saves all the data of the maze\r\n- Can't be edited\r\n- Easy to load\r\n- Heavy file (~15Mo for a 1000x1000 cell maze)\r\n\r\n#### - Save the maze's array as a binary file:\r\n\r\n```py\r\n# Filename is optional\r\nfilename = \"maze_binary\"\r\nmaze.save_maze(\"npy\", filename)\r\n```\r\n\r\nPros / Cons:\r\n\r\n- Only saves the maze's array\r\n- Can't be edited\r\n- Fast to load\r\n- Heavy file (~15Mo for a 1000x1000 cell maze)\r\n\r\n#### - Save the maze's array as a text file:\r\n\r\n```py\r\n# Filename is optional\r\nfilename = \"maze_text\"\r\nmaze.save_maze(\"txt\", filename)\r\n```\r\n\r\nPros / Cons:\r\n\r\n- Only saves the maze's array\r\n- Easy to read and edit\r\n- Slow to load\r\n- Light file (~7.5Mo for a 1000x1000 cell maze)\r\n\r\n## 6 - Load a maze\r\n\r\nIf you want to load the maze you've saved, two options are available to you depending on the file format:\r\n\r\n#### - Load a .pkl file:\r\n\r\n```py\r\nfrom maze import load_object\r\n\r\nmaze = load_object(\"maze_object.pkl\")\r\n```\r\n\r\n#### - Load a .npy or a .txt file:\r\n\r\n```py\r\nfrom maze import Maze\r\n\r\nmaze = Maze()\r\nmaze.load_maze(\"maze_binary.npy\")\r\n# Or\r\nmaze.load_maze(\"maze_text.txt\")\r\n```\r\n\r\n> **Note**: The file must be in the same directory as the script or you must specify the path to the file.\r\n\r\n## 7 - Solve a maze\r\n\r\nHere's the code to follow to solve a maze:\r\n\r\n```py\r\nfrom maze import Maze\r\n\r\nimport pathfinders\r\n\r\nmaze = Maze(10)\r\nmaze.iterative_division()\r\npath = pathfinders.depth_first_search(maze)\r\n# If you want to print the solved maze in the CLI\r\npathfinders.print_path(maze, path)\r\n# If you want to generate a .png file of the solved maze\r\npathfinders.generate_path(maze, path)\r\n```\r\n\r\nHere are all the pathfinders available:\r\n\r\n- Right Hand Rule\r\n<p align=\"center\">\r\n<img src=\"assets/gifs/right_hand.gif\" width=\"49%\"alt=\"Animation showing the process of the Right Hand rule pathfinder\"> <br><br>\r\n</p>\r\n\r\n- Left Hand Rule\r\n<p align=\"center\">\r\n<img src=\"assets/gifs/left_hand.gif\" width=\"49%\"alt=\"Animation showing the process of the Left Hand rule pathfinder\"> <br><br>\r\n</p>\r\n\r\n- Random Mouse\r\n<p align=\"center\">\r\n<img src=\"assets/gifs/random_mouse.gif\" width=\"49%\"alt=\"Animation showing the process of the Random Mouse pathfinder\"> <br><br>\r\n</p>\r\n\r\n- Pledge (may vary depending on parameters)\r\n<p align=\"center\">\r\n<img src=\"assets/gifs/pledge.gif\" width=\"49%\"alt=\"Animation showing the process of Pledge's pathfinder\"> <br><br>\r\n</p>\r\n\r\n- Dead End Filler\r\n<p align=\"center\">\r\n<img src=\"assets/gifs/dead_end_filler.gif\" width=\"49%\"alt=\"Animation showing the process of Dead End Filler pathfinder\"> <br><br>\r\n</p>\r\n\r\n- Depth First Search\r\n<p align=\"center\">\r\n<img src=\"assets/gifs/dfs.gif\" width=\"49%\"alt=\"Animation showing the process of Deep First Search pathfinder\"> <br><br>\r\n</p>\r\n\r\n- Breadth First Search\r\n<p align=\"center\">\r\n<img src=\"assets/gifs/bfs.gif\" width=\"49%\"alt=\"Animation showing the process of Breadth First Search pathfinder\"> <br><br>\r\n</p>\r\n\r\n- Greedy Best First Search\r\n<p align=\"center\">\r\n<img src=\"assets/gifs/gbfs.gif\" width=\"49%\"alt=\"Animation showing the process of Greedy Best First Search pathfinder\"> <br><br>\r\n</p>\r\n\r\n- A\\*\r\n<p align=\"center\">\r\n<img src=\"assets/gifs/a_star.gif\" width=\"49%\"alt=\"Animation showing the process of A* pathfinder\"> <br><br>\r\n</p>\r\n\r\n## 8 - Maze Generation Benchmarks\r\n\r\nWonder which algorithm is **faster**?\r\n\r\nWell.. I already did it for you! So here you are:\r\n\r\n- Chart for slow algorithms:\r\n\r\n<img src=\"assets/svg/generation_slow.svg\"><br><br>\r\n\r\n- Chart for moderately fast algorithms:\r\n\r\n<img src=\"assets/svg/generation_medium.svg\"><br><br>\r\n\r\n- Chart for fast algorithms:\r\n\r\n<img src=\"assets/svg/generation_fast.svg\"><br><br>\r\n\r\n- Chart for all algorithms:\r\n\r\n<img src=\"assets/svg/generation_full.svg\"><br><br>\r\n\r\n> **Note**: Aldous-Broder and Wilson algorithms were not tested because they are truly random (\"\"luck\"\" based in other words), so their times are very inconsistent on a generation to another. But for an idea, they are even slower than Kruskal's algorithm\r\n\r\nIf you want the values of these graphs, watch this:\r\n\r\n<img src=\"assets/images/csv_generation_screen.png\">\r\n<p align=\"center\">\r\n<br>\r\n<a href=\"assets/csv/maze_generation_time.csv\">Download csv here\r\n</a>\r\n<br>\r\n</p>\r\n\r\n> **Note**: These values can change depending on the version of Python and your PC<br><br>\r\n> For these benchmarks, I used Python 3.12.0 implemented with CPython on a ryzen 5 3600, rtx 2060 with 2\\*8GB of RAM clocked at 3600Hz on Windows 10.<br>\r\n> These benchmarks were all tested at the same time (multiprocessing) so the results are higher than if they were tested one by one\r\n\r\n## 9 - Pathfinders Benchmarks\r\n\r\nWonder which pathfinder is the most **efficient**?\r\n\r\nWell.. I also already did it for you! So here you are:\r\n\r\n> **Note** For better comparison, I used the same maze with default start/end for all pathfinders, for all size. Moreover, I used one set of mazes generated with RDFS (algorithm with the lowest dead-end rate) and another set of mazes generated with Kruskal (algorithm with the highest dead-ends rate). They're all available in the <a href=\"assets/pkl\">pkl directory</a>.\r\n\r\n- Chart for fast pathfinders on RDFS mazes:\r\n\r\n<img src=\"assets/svg/pathfinder_fast_rdfs.svg\"><br><br>\r\n\r\n- Chart for all pathfinders on RDFS mazes:\r\n\r\n<img src=\"assets/svg/pathfinder_full_rdfs.svg\"><br><br>\r\n\r\n- Chart for fast pathfinders on Kruskal mazes:\r\n\r\n<img src=\"assets/svg/pathfinder_fast_kruskal.svg\"><br><br>\r\n\r\n- Chart for all pathfinders on Kruskal mazes:\r\n\r\n<img src=\"assets/svg/pathfinder_full_kruskal.svg\"><br><br>\r\n\r\n## 10 - Improve the project\r\n\r\nIf you like this project and/or want to help or improve it, you can:\r\n\r\n- Create an issue if you find a bug or want to suggest a feature or any improvement (no matter how small it is).\r\n\r\n- Create a pull request if you want to add a feature, fix a bug or improve the code.\r\n\r\n- Contact me if you want to talk about the project or anything else (Discord: pietot).\r\n\r\n> **Note**: If you want to be guided/helped, you already have a file named <a href=\"IMPROVEMENT.txt\">IMPROVEMENTS.TXT</a> in the project directory, where you can see all the improvements that can be made.\r\n",
"bugtrack_url": null,
"license": null,
"summary": "A program capable of creating mazes with many different algorithms and solving them with different pathfinders.",
"version": "1.13",
"project_urls": {
"Homepage": "https://github.com/Pietot/Lapyrinth"
},
"split_keywords": [
"maze",
" pathfinding",
" algorithm",
" labyrinth",
" pathfinder",
" maze generator"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "4cf418fa1f005157f9b91c41ae00fdf6a300e73ed07bbfc80b4ecd3e7fc06616",
"md5": "12e8aab80d9083148245467b530de8d2",
"sha256": "bae600d2bd3c19e7111e63ea8339f46d39ff2adacac26b2b23df10a40fc0b07a"
},
"downloads": -1,
"filename": "Lapyrinth-1.13-py3-none-any.whl",
"has_sig": false,
"md5_digest": "12e8aab80d9083148245467b530de8d2",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.10",
"size": 27313,
"upload_time": "2024-06-28T21:35:52",
"upload_time_iso_8601": "2024-06-28T21:35:52.327734Z",
"url": "https://files.pythonhosted.org/packages/4c/f4/18fa1f005157f9b91c41ae00fdf6a300e73ed07bbfc80b4ecd3e7fc06616/Lapyrinth-1.13-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "43f2e20abb7c262ab9bc6a3b210e6f9024bcb3cf126ee88e84ca06d9c9715e3c",
"md5": "c37fd8acf74ec059bea26b19f68e66cb",
"sha256": "b2b97a7b96e3ce6a0fe6ebea4a4a9e76343d11d73bb493ac93c5a633d76adf28"
},
"downloads": -1,
"filename": "Lapyrinth-1.13.tar.gz",
"has_sig": false,
"md5_digest": "c37fd8acf74ec059bea26b19f68e66cb",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.10",
"size": 26293,
"upload_time": "2024-06-28T21:35:54",
"upload_time_iso_8601": "2024-06-28T21:35:54.927308Z",
"url": "https://files.pythonhosted.org/packages/43/f2/e20abb7c262ab9bc6a3b210e6f9024bcb3cf126ee88e84ca06d9c9715e3c/Lapyrinth-1.13.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-06-28 21:35:54",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "Pietot",
"github_project": "Lapyrinth",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"requirements": [],
"lcname": "lapyrinth"
}
JSON
