There are 12 common maze-solving algorithms to implement:

Blind Alley Filler, Blind Alley Sealer, Chain Algorithm, Collision Solver, Cul-de-sac Filler, Dead End Filler, Pledge Algorithm, Random Mouse, Recursive Backtracker, Shortest Paths Finder, Trémaux's Algorithm, Wall Follower

Maze-Solving Algo

http://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking

Okay, there is a much easier way forward with this:

1. start with a complete maze.
2. add one or several walls randomly, throughout the maze
3. use the logic in DungeonRooms that fixes mazes that are not fully connected

We only need the passage-focused method. The wall-focused method can be moved into examples.

There is a use-case where users of this library will want to generate mazes with large rooms in them. Games may find this useful.

This algo will be based on Prims. Though the recursive Backtracker might also work.

It would be nice to generate a maze that had a circular boundary, instead of a square one. Or triangular.

And it would be nice if more than one maze algorithm could be used in a designer-shapes sense.

Maybe Maze would have an option for creating a maze with an input grid? Like, the user just specifies "shape=circle" and "radius= 35", and then the generator has to be able to deal with that.

Sparse mazes are really interesting, but there is no classic maze-generation algorithm for them. Luckily, this shouldn't be hard.

I need to pick a classic algorithm that carves passages. But at each step I carve a small circle (of pre-determined diameter), instead of a single square.

Sparse maze generation will require a greater number of grid cells than a densely-packed maze, so it will take up more memory. But thus far, I don't think that will be a problem.

Create ShortestPaths first.

Get it polished.

Then just pare it down to make ShortestPath.

Finish moving the README docs around.

And don't forget to copy the Vocab section to the maze-gen section.

Improve plotting examples to optionally include start and end points, and solution.

Note on plotting: even-numbered rows should have optionally different heights than odd-numbered rows, and ditto even-numbered columns should have optionally different widths than odd-numbered columns.

Maze-Solving Algo

Maze-Solving Algorithm

http://weblog.jamisbuck.org/2011/1/20/maze-generation-wilson-s-algorithm

The algo doc info would look better like this:

Algorithm Documentation

Prims
-Algorithm
-Optional Parameters
-Results
-Notes

In-Class Documentation
-Algorithm
-Optional Parameters

The tostring method should have an option to print the maze with entrances (S/E) and a solution path (+).

I can't find any reference to this in the literature. But I feel like you should be able to solve a maze using Djikstra's algorithm. Or any graph search algorithm.

Implement the Wall Follower maze-solving-algorithm.

Be careful, it is the simplest algorithm to understand, but notorious for being super verbose in code.

Don't just build the first tests. Make sure the build process that involves those tests is what we want it to be.

The DeadEndFiller maze-solving algorithm is pretty simple.

I need a way to convert an array2d object to a 2D List. (Bonus points for converting it to other things, like a 1D array.)

When all the major solver algorithms have been implemented, verify that they work for mazes with one edge entrance and one body entrance.

Distribution needs of the mazelib library will be handled by setuptools, rather than distutils. While distutils is a "standard" library, it does not support unit tests. And... people clamor something about "metadata" too. Anyway, setuptools is the de factor standard in the community, so it would be useful to learn that.

Setuptools
Doc: https://pythonhosted.org/an_example_pypi_project/setuptools.html
Example: http://www.scotttorborg.com/python-packaging/minimal.html
Getting Started: http://pythonhosted.org/an_example_pypi_project/setuptools.html
Example with Tests: https://github.com/docopt/docopt/blob/master/setup.py

Supporting Python 2 and 3: You may have to get setup.py to run 2to3.py first.

There's no way around it, some solver algorithms are designed to find more than one solution.

The MazeSolverAlgo, it's subclasses, and Maze classes all need to be altered to handle multiple solutions.

The solutions should be ordered by there length (shortest first).

It might be useful for the user to be able to generate many mazes with the same algorithm and pick the hardest one. Or the easiest one. Or somewhere in the middle.

This would be easy enough to do, though possibly very time consuming.

def generate_monte_carlo(self, repeat, entrances=3, difficulty=1.0):

This method was just call the normal generate method, and add up the results in a list, and based on your difficulty setting, chooses the one of the appropriate difficulty.

Difficulty will be determined by the length of the solution. (Which will be great in all situations except for the two long runs in Ellers, maybe.)

Just throw a try/catch around each maze gen/solve attempt. This is Monte Carlo after all.

Move all documentation, except the master README to the /docs/ folder.

This will allow for expanded documentation (INSTALLATION.md), but also for images of mazes, which will make the documentation a lot more fun to read.

Maze-Solving Algo

http://weblog.jamisbuck.org/2010/12/29/maze-generation-eller-s-algorithm

Maze-Solving Algo.

Everything like Recursive Backtracking. Hell, maybe I should make these two algorithms recursive, just for giggles.

It shouldn't be in /generators.
And it would probably be best if this import was handled in the generators init.py file... instead of duplicating that import statement.

Maze-Solving Algo

Won't most maze-solve algorithms need this? If so, boom. Done.

It might be useful to have custom exceptions:

AlgorithmFailureError
MazeCreationError
MazeSolvingError

class InvalidAlgorithmInputException(Exception):

    def __init__(self, message='This algo cannot be solved with these inputs.'):
        Exception.__init__(self, message)

The Algorithm
Optional Parameters
Results
Notes

But wait until DeadEndFiller is totally complete.

10 out of the 12 algorithms seem to need it... they should just share it, already.

def _find_neighbors(self, posi, grid, visited=True):
    (row, col) = posi
    ns = []

    if row > 1 and grid[row-2, col] == visited:
        ns.append((row-2, col))
    if row < self.H-2 and grid[row+2, col] == visited:
        ns.append((row+2, col))
    if col > 1 and grid[row, col-2] == visited:
        ns.append((row, col-2))
    if col < self.W-2 and grid[row, col+2] == visited:
        ns.append((row, col+2))

    shuffle(ns)

    return ns

I used my old Array2D class to store the maze data. This was cute, but not useful here.

The bulk of the work done by these maze algorithms is in getting/setting an element in the maze based on position. This means what I really want is a fast way to get/set elements by index.

A simple 2D list would be MUCH faster here.

And after working with these mazes for a while I believe speed is more important than size in memory.

http://weblog.jamisbuck.org/2011/1/24/maze-generation-hunt-and-kill-algorithm

Maze-Solving Algo

There is still one in /generators/ for some reason.

Make sure you cause no problems when you remove it.

Currently, entrances can only be on the maze boundaries... this is probably what is most common.
But I would like to allow for entrances to be randomly placed ANYWHERE in the maze.

(Don't forget, the user can current manually set start and stop to wherever they want.)

• src
  • generate
    • init.py
    • GenAlgo.py
    • Prims.py
  • solve
    • init.py
    • SolveAlgo.py
  • utils
    • init.py
    • array2d.py
  • init.py
  • mazelib.py
• test
  • init.py
  • test_array2d.py
  • test_mazelib.py
• init.py --> from src.mazelib import *

Make sure that mazelib is valid in Python 2.7.x and 3.x.x.

I have already taken the first step and removed all dependencies on external libraries.

Do a little research: Does the WallFollower algorithm work if the start position is somewhere within the maze, rather than on the edge?

I'm not sure it will. I need to test this.

If indeed it doesn't work, then I need to see if I can build a pre-processor to lead from the start to any edge position, then start the algorithm from there.

It is frequently useful in games to have a maze with one or many large rooms in it.

To support this fun use of mazes, it would be nice to have a maze algorithm that allows an initial set of open rooms to be passed to it.

This algorithm would be fragile though, as you could design a malicious set of rooms that would make for an unsolvable maze.

Maze-Solving Algo

Should I alter one or two of the generators/solvers to support 3D mazes?
Should I merely create a couple 3D-specific algorithms?
This would mean creating and supporting a 3D array data structure.

Jamis Buck created this example using a 3D version of Growing Tree: http://jamisbuck.org/mazes/minecraft.html#

This is a research topic. I think it is doable... if you're willing for the algorithm to be painfully slow. Can it be done smartly?

https://stackoverflow.com/questions/7369945/algorithm-for-maze-generation-with-no-dead-ends
http://www.michaelchaney.com/2014/03/unicursal-mazes/
http://people.cs.aau.dk/~normark/prog3-03/html/notes/fu-intr-2_themes-hilbert-sec.html
https://en.wikipedia.org/wiki/Space-filling_curve

Should my solvers give back a list of ALL solutions?
Just the one solution?

Should it be heavily dependent upon which solver you use? I know some solvers will only give back one solution anyway.

What is a good standard to work from?
What makes sense in light of the 12 classic solver algorithms?

find_neighbors(self, posi, grid, visited=True):

is being treated backwards:

 if row > 1 and grid[row-2, col] == visited:

It works, but the word 'visited' is wrong.

Maze-Solving Algo.

This is a classic. And should be stupid easy to code. Though it will definitely be slow and have a convergence problem.