Generate maze using randomized DFS and Solve it using Path Finding algorithms
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. s start by ng the module, depending on what kind of project it is:
import importlib
mgs = importlib.import_module("maze-generator-and-solver.main")
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)
- 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.
NOTE: create(...) use randomized DFS, so a (3x3) maze created on your system might return some different values.
#use:
maze = create(3, 3) # to create a maze of (3 x 3) grid
maze = create(90, 90, 30) # to create a maze of (3 x 3) grid
print(maze)
''' output of both the function call will be similar to this:
{
"mazeArr": [0,3,6,7,8,5,2,1,4,1,2,5,8,7,6,3,0],
"mazeGraph": {
"v": 9,
"AdjList": {},
"length": 9
}
}
'''
maze = create(3, 5) # to create a maze of (3 x 5) grid
maze = create(90, 150, 30) # to create a maze of (3 x 5) grid
print(maze)
''' output of both the function call will similar to this
{
"mazeArr": [0,3,4,7,6,9,12,13,10,11,14,11,8,5,2,1,2,5,8,11,10,13,12,9,6,7,4,3,0],
"mazeGraph": {
"v": 15,
"AdjList": {},
"length": 15
}
}
'''
# all these functions return the same structures, an array and a Graph object
click here or 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]) '''
- 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).
#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
print(path)
'''
output of a 3x3 maze will be similar to:
[0,1,4,7,8]
output of a 3x5 maze will be similar to:
[0,3,6,7,8,11,14]
'''
click here or 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.
NOTE: create(...) use randomized DFS, so a (3x3) maze created on your system might return some different values.
create:
maze = mgs.create(3, 3)
print(maze["mazeArray"])
# mazeArray: [0,1,4,5,8,7,6,3,6,7,8,5,2,5,4,1,0]
search:
path = mgs.search(maze.mazeGraph, 0, maze.mazeGraph.v-1)
print(path["stackArray"])
#stackArray: [0,1,4,5,8]
That's it, you are ready to create and solve maze :smile:. You can play with a working maze generator/solver (using py) 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.7.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | 444dd1ff22eb81f674e06bdcf30c98d4ac91eb008a1f5714ff3b03fcf8b105ab |
|
MD5 | 86589976fe79753d4d33c211591189f2 |
|
BLAKE2b-256 | 88cc7415ccaeeaf50feb42b4cf0abe01f3368c6c612e915c3b35dcfefc256e04 |
Hashes for maze_generator_and_solver-0.0.7-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 09d22b181c8cf754540964df613dc624c7dd8f1a42f2d210b4e5b6ac8b7a0b52 |
|
MD5 | 4f4af475f2c091e4dabeda422c8ab946 |
|
BLAKE2b-256 | 368caa29f3990f7936670cb8caa1822a65505849cc7987992532de189a8fb4e3 |