jostbr / pymaze Goto Github PK

It might be a good idea to create a new branch, development that we can push up to master when we know that it's fully stable. This would reduce the risk of a user running across a botched auto merge or bug.

We should add a licence to this. After, we should also add the badge to the readme by using
https://gist.github.com/lukas-h/2a5d00690736b4c3a7ba

This would allow other people to legally use this code.

When showing the graphs for solve_bfs and solve_bidirect_dfs, strange behavior is encountered. This is probably either a problem with the solution path or with the visualization code. This can be seen in early versions, and also current versions.

We can cut the time that it takes to run many maze solutions down by disabling output to the console.

This amounts to adding a flag in the Solver class. Add an if statement where we output text.

It would be great if we had a way to serialize a maze and then initialize a new maze with it. This can easily be done with the sqlite3 module. The first pass can just be an individual maze in a single database file. It can be extended later to save multiple mazes the the database if needed/requested.

I'm initially going to bundle this in to the Maze class, but long term it would really belong in some sort of utility class where non essential things can get bundled(how nice would it be to get the determinant of the maze!).

It would be great if you we could check if two cells are equal by overriding the equality operator. This would allow for better unit testing and may help with further applications.

From the Maze __init__ signature,
def __init__(self, num_rows, num_cols, cell_size):
we can see that we're taking cell_size in.

Furthermore, we set three member variables to values derived from cell_size

self.cell_size = cell_size
self.height = num_rows*cell_size
self.width = num_cols*cell_size

I propose that we take these out of the Maze class because

1. The information isn't used internally by the Maze, it's just accessed by maze_viz.
2. Display properties of the Maze aren't really part of a maze. A maze can exist without the notion of cell_size
3. Creates unnecessary coupling of information between objects

We should probably be using a linter to avoid different programming styles. We can add it to travis.yml to run with every pull request.

Our two styles boil down to either Google's or pep8. Any preferences?

It looks like a lot of these functions can be unit tested fairly easily. Pick a testing framework and I'll create some unit tests to help ensure nothing breaks with code changes!

It would be very nice to support the wall follower algorithm. We can go about this a couple of different ways.

Add another solve method.

We would rename def solve_maze to something like def solve_recursive_back and then add a new method, def solve_wall_follower.

Pros:
It keeps the code simple
Quick
Few auxiliary changes (for example, we may need to refactor def _validate_neighbors_solve

Cons
In the long run, the code may get incredibly unstructured if we support more.

Create a solver Class

Create a base class that represents a solution method.

For example,

class Solver
{
public: 
virtual MAZE solve();
}

class WallFollower : Solver
{
 MAZE solve();
}

class RecursiveBacktracer : Solver
{
   MAZE solve();
}

etc
etc

We could always create an interface to it at a later time so that users don't need to mess around with class instantiation.

Pros:
Better long term support

Cons:
Adds complexity
Not as easy to use?

Options:

1. Don't support the algorithm
2. Add a new method for it
3. Create the class system

It would be nice if we could display the current state of the build/unit tests with Coveralls

Right now we output how long and how many steps the solver took to solve the maze. It would be great to save this information somewhere so that a user can compare speeds.

It would be great if a circular maze, which is usually more complex to be comprehended by the human mind, could be implemented using the algorithm that is already here.
What I have in mind is the following cell structure:

The design above is not geometrically optimal but could be implemented the following way:

• The rows can be represented as a set of concentric circles and columns seperated by lines between two circles.
• The key difference would be that columns will be looped i.e., the last column will be connected to the first column
• In order to maintain an even distribution in the size of the cell, I recommend doubling the number of columns for every row without which there would be an exponential increase in cell size with increase in number of rows. This would greatly add to the complexity and at the same time maintain the cell size.
  -That would imply, only the rows (number of circles) will be given as input and the number of columns would be : pow(2,rows+2)
  -The condition for a cell to be start/exit would be row = num_rows-1

I have implemented the above condition but I am yet to commit the changes as visualizing this in matplotlib is not as simple as doing that for a grid. The following is a manual visualization from the raw outputs of generate_maze.

Please do let me know if you're more interested in this and have ideas about visualzing this implementation in matplotlib

Filenames examples/solve_breadth_first_recursive.py and examples/solve_depth_first_recursive.py seem to be reversed. In particular, the former solves the maze with depth-first and the latter with breadth-first.

It would be great if we could turn our maze into an adjacency matrix and see if we can solve it using matrix transformations (I'm not sure if that's possible). Ultimately, it would be fantastic if these could be solved on the GPU.

I've found your project quite interesting and have been spending some time inspecting the code.
In the "cell.py" file: Line 35 (is_walls_between function), could you please tell me why one has to consider both self.walls and neighbour.walls conditions. Isn't one of them a sufficient condition to check if there are walls in-between?

if self.row - neighbour.row == 1 and self.walls["top"] and neighbour.walls["bottom"]: return True elif self.row - neighbour.row == -1 and self.walls["bottom"] and neighbour.walls["top"]: return True elif self.col - neighbour.col == 1 and self.walls["left"] and neighbour.walls["right"]: return True elif self.col - neighbour.col == -1 and self.walls["right"] and neighbour.walls["left"]: return True

I might be wrong and if it is necessary to use both these conditions, am I missing any corner cases?

You might get more traffic if you add some topics to the project (and your other ones!).

We should create a src directory for the source files.

We should be showing examples of people using this like a library with import MazeGenerator. Take the example code out of maze.py and maze_viz.py and put them in a new directory called examples

We have three failing unit tests in the cell tests. I believe they all involve adding cell exits on corners and removing corner walls. @jostbr You might have a better idea at what's going on in there.

a requirements file would be super helpful

As it is now, the README file only mentions the depth-first search and could use a slight update.