Skip to main content

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
More algorithms will be added soon ;p

Example

Taking this (3x3)maze as an example. on the left(unsolved) and on the right, you can see it is solved. maze

  • 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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

maze_generator_and_solver-0.0.5.tar.gz (16.5 kB view hashes)

Uploaded Source

Built Distribution

maze_generator_and_solver-0.0.5-py3-none-any.whl (17.2 kB view hashes)

Uploaded Python 3

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page