mikepound/mazesolving

A variety of algorithms to solve mazes from an input image

mazesolving

A variety of algorithms to solve mazes from an input image.

About

These are the python files associated with the computerphile video on maze solving. Feel free to use, alter, redistribute the code as you see fit.

I'm not actively developing this project, simply for time reasons. Mostly I want the code to be as it was (at least in general function) at the time of the video. If you're interested in improving the code, then you can fork it into your own repository and make any changes you wish. If you come up with something good, feel free to share it on the wiki, thanks to Jacob Mitchell for starting that.

Input

Some example mazes are included in the repository. These were generated either by hand, or using the software Daedalus. Once exported I edited the mazes to ensure that the following rules are adhered to:

• Each maze is black and white. White represents paths, black represents walls.
• All mazes are surrounded entirely by black walls.
• One white square exists on the top row of the image, and is the start of the maze.
• One white square exists on the bottom row of the image, and is the end of the maze.

Notes

This was just a side project I did for fun over a couple of evenings, I'm sure there are many improvements and extensions you could make if you wanted to. Some things to note:

• The data structures and representations can probably be improved for speed - I only focused a little on efficiency. Mostly I wanted to keep memory usage down, to allow the use of very large mazes.
• The very large mazes use a lot of ram. If you don't have 16Gb at least for the 10k+ x 10k+ mazes, you may run out of memory!
• The current format of the test mazes (short paths, very dense) means that in fact dijkstra and a* usually operate more slowly than simple algorithms. In these cases Dijkstra usually performs the same function as breadth first search, but with more computational overhead. There will be some forms of maze where they are significantly faster.
• Mazes don't need to be square - as long as they are surrounded by black walls. The input image will obviously be square.
• Large areas of white, using my algorithm, will essentially degenerate into an inefficient flood fill - avoid!

mazesolving's Issues

Customizing start and end points in maze

Hi,

The code works assuming that the start coordinate is always painted in white in the top row and end coordinate is always painted in white in the bottom row of the maze.

If we want to customize them, what are the changes needs to be made to specify start and end coordinates?

My Observation:
Assume the start point to be (101, 13)
Inside the mazes.py if we specify the start coordinate at line 19 as

self.start = Maze.Node((13,101)) instead of self.start = Maze.Node((0,x))

then the resultant image consisted of the path that is excluding the position (101, 13).
It is because the Neighbours[] is not configured properly for the assumed start point. It is not a proper way to change manually te Neighbours[] of assumed start node.

How to fix it? Or please suggest some other way to customize the start and end coordinates.

Thanks in advance!!

Open wiki?

Thank you for sharing this project and the video. I've had fun playing with it.

I noticed the recent addition to the README saying pull requests and issues generally aren't encouraged. Maintaining a project can be tedious, especially it's just a personal hobby project. I think it would be nice if people interested in the project could collaborate, even if you're not involved.

Would you consider making the project's wiki public or suggesting in the README some other avenue for people interested in discussing ideas and sharing their forks?

maze generation in python visuals

Hi Mike, I have a question regarding visualization in python of your maze generation with a* start algoritm.
Is there a way to visualize the maze being solved in real time (i.e. show the grid with the openset and the close set)?

I worked something out using graphics.py and in the past I used pygame. However somehow it was very taxing on the process.'

What package do you recon is best to use for real time visualisation in python?

Greetings Roel

Crashes when using 1-bit grayscale PNG input

Just tested it with the attached image
.

It is an "PNG image data, 619 x 995, 1-bit grayscale, non-interlaced"

The result was a crash

python3 solve.py maze.png solution.bmp
Loading Image
Creating Maze
Node Count: 101050
Time elapsed: 0.5865614414215088 

Starting Solve: Breadth first search
Nodes explored:  100926
Path found, length 1461
Time elapsed:  0.14136648178100586 

Saving Image
Traceback (most recent call last):
  File "/usr/lib/python3/dist-packages/PIL/Image.py", line 2195, in fromarray
    mode, rawmode = _fromarray_typemap[typekey]
KeyError: ((1, 1, 3), '|b1')

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "solve.py", line 88, in <module>
    img = Image.fromarray(out)
  File "/usr/lib/python3/dist-packages/PIL/Image.py", line 2198, in fromarray
    raise TypeError("Cannot handle this data type")
TypeError: Cannot handle this data type

It works fine when converting the input to "PNG image data, 619 x 995, 1-bit colormap, non-interlaced"

Issue with parser.parse_args()

Hi,

I am having problems running this code on my own computer. I get the follwoing error;

usage: solve.py [-h] [-m [{breadthfirst, depthfirst, dijkstra, astar, leftturn}]] input_file output_file solve.py: error: the following arguments are required: input_file, output_file

What do I need to do to solve this?

Thanks!

Python typeerror

I don't program in Python but it seems "Node" doesn't have a method for '>' operator?

C:\Users\micha\Desktop\mazesolving-master>python solve.py -m astar perfect4k.png 4k_solve.png
Loading Image
Creating Maze
Node Count: 2865504
Time elapsed: 32.22657132148743

Starting Solve: A-star Search
Traceback (most recent call last):
File "solve.py", line 89, in
main()
File "solve.py", line 86, in main
solve(sf, args.method, args.input_file, args.output_file)
File "solve.py", line 29, in solve
[result, stats] = solver(maze)
File "C:\Users\micha\Desktop\mazesolving-master\astar.py", line 80, in solve
unvisited.insert(vnode)
File "C:\Users\micha\Desktop\mazesolving-master\priority_queue.py", line 59, in insert
heapq.heappush(self.pq, entry)
TypeError: '<' not supported between instances of 'Node' and 'Node'

Manhattan Distance Extremely Slow -- A*

When playing around with this code I have found a bit of an anomaly in regards to A*.

I have generated a Maze of size 1000x1000 and just to play around with the code I wanted to switch the remaining distance (F cost) to see how it changes run time.

Just to note, the maze generates 641967 nodes.

When I run the maze with remaining = 0 these are the results I get:

• Nodes Explored: 641799
• Time Elapsed: 28.96

If I then change it so that:
remaining = math.sqrt( ((vpos[0] - endpos[0]) ** 2) + ((vpos[1] - endpos[1]) ** 2) )
(Euclidian Distance) these are the results I get:

• Nodes Explored: 620100
• Time Elapsed: 12.91

And then I use the remaining that was originally with the code,
remaining = abs(vpos[0] - endpos[0]) + abs(vpos[1] - endpos[1])
these are the results I get:

• Nodes Explored: 595880
• Time Elapsed: 34.63

How is this possible? The A* with Manhattan distance obviously eliminates more nodes than the other two but somehow performs the slowest? Is it that the call to abs is slow? I haven't been able to find any evidence that this the case. Any guidance would be helpful.

i got this errors

t.Neighbours[2] = n
AttributeError: 'NoneType' object has no attribute 'Neighbours'

Add topics to this Github repository

This will allow people to find it more easily and it also means that it can be very easily grouped with similar projects.

I think the maze, pathfinding and python topics would be suitable for this repo.

Core dumped on vertical15k

python ../solve.py vertical15k.png vertical15k_out.png

Loading Image
/usr/lib/python2.7/dist-packages/PIL/Image.py:2224: DecompressionBombWarning: Image size (225030001 pixels) exceeds limit of 89478485 pixels, could be decompression bomb DOS attack.
DecompressionBombWarning)
Creating Maze
('Node Count:', 18716772)
('Time elapsed:', 271.5947608947754, '\n')
('Starting Solve:', 'Breadth first search')
('Nodes explored: ', 16954823)
('Path found, length', 14820)
('Time elapsed: ', 83.27104091644287, '\n')
Saving Image
Segmentation fault (core dumped)

It didn't run out of memory (6%)

I was able to do the perfect2k.png without a problem in a few seconds.

remove semicolons at line ends

... Python doesn't need all these ';'

(thanks for the fun video's on computerphile, which is how I got here)

PIL version?

I think i have a different version of PIL than the one used in this project.
Specifically mine does not have the .width property on Image, instead it has the .size property.

changing the code to accommodate this is trivial, but I would like to contribute with out introducing breaking changes.

the version i have is 1.1.7 of python 2.7 from here:
http://www.pythonware.com/products/pil/

output that lead me to this conclusion:
D:\projects\mazesolving>python solve.py -m breadthfirst examples/tiny.png out.png
Loading Image
Creating Maze
Traceback (most recent call last):
File "solve.py", line 90, in
main()
File "solve.py", line 87, in main
solve(sf, args.method, args.input_file, args.output_file)
File "solve.py", line 19, in solve
maze = Maze(im)
File "D:\projects\mazesolving\mazes2.py", line 15, in init
width = im.width
File "C:\Python27\Lib\site-packages\PIL\Image.py", line 512, in getattr
raise AttributeError(name)
AttributeError: width

D:\projects\mazesolving>python
Python 2.7.12 (v2.7.12:d33e0cf91556, Jun 27 2016, 15:19:22) [MSC v.1500 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
->>> from PIL import Image
->>> im = Image.open(examples/tiny.png)
Traceback (most recent call last):
File "", line 1, in
NameError: name 'examples' is not defined
->>> im = Image.open("examples/tiny.png")
->>> dir(im)
['_Image__transformer', '_PngImageFile__idat', 'doc', 'getattr', 'init', 'module', 'repr', '_copy', '_dump', '_expand', '_makeself', '_new', '_open', 'category', 'convert', 'copy', 'crop', 'decoderconfig', 'decodermaxblock', 'draft', 'filename', 'filter', 'format', 'format_description', 'fp', 'fromstring', 'getbands', 'getbbox', 'getcolors', 'getdata', 'getextrema', 'getim', 'getpalette', 'getpixel', 'getprojection', 'histogram', 'im', 'info', 'load', 'load_end', 'load_prepare', 'load_read', 'mode', 'offset', 'palette', 'paste', 'png', 'point', 'putalpha', 'putdata', 'putpalette', 'putpixel', 'quantize', 'readonly', 'resize', 'rotate', 'save', 'seek', 'show', 'size', 'split', 'tell', 'text', 'thumbnail', 'tile', 'tobitmap', 'tostring', 'transform', 'transpose', 'verify']
->>> im.size
(10, 10)

Braid2k has no black border

might be an issue on my end but when I download the file to test my own code there isn't a black border around the edge.

add threading

could you add threading to the solve.py script it would just make the script faster