Generate maze using randomized DFS and Solve it using Path Finding algorithms
Reason this release was yanked:
pip is shit.. you can use npm instead and then convert it to python for your use
Project description
Maze Generation & Solving
Generate/Solve Maze of any dimension using DFS and search algorithms like, Dijkstra, etc.
Features
- Create maze of different sizes.
- Solve maze using path finding algorithm like Dijkstra(adding more later).
Usage
This module provides 2 functions, create(...) and search(...). Both of these functions require some parameter that needs to be given by the user. Let's start by importing module in your project,
import maze_generator_and_solver as mgs
Generate/Create a maze
There are 2 ways of using the create(...) function to generate a maze, both of them return same structure so you can use either of them as per the need.
#definition:
create(width=3, height=3, cellSize=1) # width (default: 3), height (default: 3), cellsize (default: 1)
#use:
maze = mgs.create(3, 3) # to create a maze of (5 x 5) grid
maze = mgs.create(3, 5) # to create a maze of (3 x 5) grid
maze = mgs.create(90, 90, 30) # to create a maze of (3 x 3) grid
maze = mgs.create(90, 150, 30) # to create a maze of (3 x 5) grid
# all these functions return the same structures, an array and a Graph objec
scroll down to get a better understanding with the help of an example
Solve the maze
To search/solve the maze use the search(...) function,
#definition:
search(graph, root, target, searchAlgoId=1)
# graph: the graph object returned by 'create(...) function', root: starting index,
# target: ending index, searchAlgoId: the id the search algorithm being used (default: 1[dijkstra])
#use:
# 'maze' was defined above when create function was called
path = mgs.search(maze["mazeGraph"], 0, maze["mazeGraph"].v-1) # retuns a stack object that contains the solution/path
scroll down to get a better understanding with the help of an example
Search Algorithm IDs
Algorithm ID | Search Algorithm |
---|---|
1 | Dijkstra |
Example
Taking this (3x3)maze as an example. on the left(unsolved) and on the right, you can see it is solved.
- The create(...) function returns 2 structure, one is a simple 1D Array and the other one is a custom Graph structure.
- The array contains maze/grid index in the order they should be visited (including bactracked indexes). This is useful if you want to create some kind of animation to create a maze.
- The Graph, as the name suggest, will return an object that has a Map object(adjList). This Map object maps all the index connected to each other.
[0,1,4,5,8,7,6,3,6,7,8,5,2,5,4,1,0] #mazeArr
{"v":9,"AdjList":{Map(9) 0: {0 => GNode}, ...},"length":9} #mazeGraph
# GNode: {d: Set(..), visited: true|false}
NOTE: create(...) use randomized DFS, so a (3x3) maze created on your system might return some different values.
- The search(...) function returns a custom Stack object, it contains the array(stackArray) that will provide the solution / path to take from root(0) to target(8).
[0,1,4,5,8] #stackArr
That's it, you are ready to create and solve maze :smile:. You can play with a working maze generator/solver at https:#0-harshit-0.github.io/maze
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for maze_generator_and_solver-0.0.5.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | 13fabcd01ec50ad61bddcffec08026d4915c34f4aacbac56510fb88bd3bb506a |
|
MD5 | 5de1f274581febbc0f456920fc5750be |
|
BLAKE2b-256 | 5fa2a075fcb2ed37e089b4f9ef1c84982771c5bdabfdc160f1ec74766bb70026 |
Hashes for maze_generator_and_solver-0.0.5-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1cdd058a0265c254edd42b559c267deb0ae9e35a08f0aaf66bed7d2eba33c432 |
|
MD5 | 909d3f596656a42506130ef8187b5fec |
|
BLAKE2b-256 | 9db0aa0c4184162375b757d383a1c211a5d73de0d64ed165eb3f68d3454f6c5b |