So pretty much the best perk of university is pretty much having unlimited access to acedemic journals. After looking up thinning algorithms forever I couldn’t find any that really did the job or even worked. The closest thing was probably Lantuéjoul’s formula and I don’t even know If I implemented it correctly because my resulting image wasn’t continuous. Anyways I came across ZS’s thinning algorithm but couldn’t find a copy. I eventually found which journal it was in and voila! Anyways I’ve pretty much been rewriting my whole code over since I’ve found all these new algorithms but hopefully it can generalize to all mazes which is my final goal.
There are so many useful algorithms it’s crazy. Just found out skeletonizeing and it is exactly what I’m looking for. I can just break down the maze into a series of points at the intersections and run A* on them. Also It solves getting the entrance and exit points for me to the code I wrote now is obsolete. I also think that this code would be perfect for what I want so I can generalize it to solving all maze types.
Well A* works amazingly, some concerns are:
1)It uses a lot of memory, not sure how well it will run on the android.
2)It’s not the fastest, takes a will to go through the entire maze on a desktop so I assume it will take far longer on the phone’s hardware
Fortunately I have a solution that should get rid of those issues. Right not it really doesn’t need to scan through every single pixels, the only places on that map that really matter are intersections; where user has to make a decision on where to go. If I can write a method (who knows how) that will get the center points of these intersections, the ammount of nodes will be reduced significantly from ~60000 elements in my closed list to around 20.
Also I previously mentioned using insertion sort, turns out O(n) with 60000 elements is not so good. Binary heaps were the right answer with O(1) to get the smallest element and O(log n) to delete and insert.
Writing the code to get rid of this redundant information presents the largest challange, off the top of my head I’m thinking using houghlines and finding areas that are roughly the lanelength^2. However code like that will only really be applicable to the rectangular maze case, if I ever want to generalize it to solve any maze I’ll have to come up with a better solution.
For now I think I will just get the rectangular case working flawlessly for any rectangular maze then go from there.
It’s time to code the spine of this whole operation, implementing A* to find the shortest path. I thought this would be challenging which is why I guess I put it off for so long but it’s actually lots of fun trying to optimize it.
Anyways after some testing, I’m not sure A* is the best solution, it ends up solving a lot of the maze anyway and the closed list grows in excess ot 50000 elements. I’ve come up with another idea where I might either take A* with no heuristics which is pretty much Dijkstras (spelt it correct on the first try, wsup) and only keep track of elements on the edge as there is no point in scanning an item in the closed list that is impossible to hit.
While trying to implement it I did however come across many cool data types like heaps, trees and even had to pull out the good Ol’ big O notation from MACM to choose the best sorting algorithm which I think is this case is insertion sort since the data will always be presented in a best case scenario and gives O(n). Binary heaps might also do the job better so it’s time to play around and see.
I changed the entrance and exit detection code a bit so know it it can pretty much work on any rectangular maze. There is just a few more things that need to be changed to make it solid. I’ve also thought about another method to detect the entrance and exit where you would trace along the outside of the maze and look for breaks in the border. I’m not sure how well this would work though as It seems my way could be change to suit non-rectangle mazes more easliy. I’ll probably have to implement both ways and compare them.
I leave you with pretty images of some examples of sample data sets and the output.
I’ve been working on a project for quite a while before I decided to make a blog for it so from here on in I will try to keep it updated. For a new project I thought of a topic that was thought to be, at the time, impossible for me to make. I came up with an idea of making a maze solver, a program where you could just point your camera at the maze and it will draw the solution over top of the image. I had no prior knowledge of any of the things needed to even know where to begin, I just dove in head first.
I tried to find a starting point by looking at the source code of open source barcode scanners, this yielded no success however. One day while I was going through wikipedia pages I came across computer vision and this is where everything changed for me. The beauty of CV is that there are infinitely many data sets you can input into the system and it’s up to your program to extract only the relevant things. Upon reading, I found that there were many algorithms already made for exactly what I needed to acomplish, it was just a matter of now setting up my IDE to use the library of my choice, OpenCV through JavaCV that provides wrappers to OpenCV.
Setting up the IDE took quite a while, but after working through many hair pulling bugs I finally got setup and ready to go. Immediately I got my android setup and ready to capture and decode the images, after that it was all up hill from there. After working with the android I found that the time it took at run the code and test it on the phone was taking up a lot of time so I decided to just program it for the computer then when I’m done, port it over to the phone to speed up development. At the beginning there were so many challenges it wasn’t even funny like how to distinguish the maze from objects around it.
After messing around with many functions I finally found that thresholding, canny edge detection and Houghlines were the answer to this problem, getting the right lines however definitely took a lot of time but many println’s later I finally found out which theta’s were needed to get the outer most lines. After getting those lines I took the intersections and warped the matrix containing the maze onto a new image with a fixed size. It is on this new image where a new problem arose, how to get where the entrance and exit lies.
Thinking and messing around for some bit lead me to grabbing the points of the contour that layed on the outer most lines and checking if the distance between points on the same line were roughly separated by the length of the maze lanes. After getting many points that satisfied that criteria I now had to filter them and get the correct two. Simply checking the locations of them and checking how many neighbours were close by, if if was surrounded on 3 sides by black lines and the distance from the edge grabs the right 2. Here is where I now am, the current problem is solving the maze.
To navigate the maze I will probably take the binary image and use K * to iterate through it, the problem lies in the fact that it could just go around the maze and not through it. I took a break from solving it because my school gave out free USB drives and I thought these would be perfect to have a local svn on that I can use to keep track of my changes to work on it at school and home. After encrypting the drive with Truecrypt, so if I lose it no one steals the code, I began to set it up. Like all things in life, it’s never as easy as it seems. I couldn’t install subclipse on eclipse indigo so I tried to update to juno and see if it would work. Nope. I tried installing subversive yet I kept getting errors upon errors when trying to install. After giving up and going to bed, next morning I uninstalled Java SE 7 u7 and went back to 6 u35 and it worked flawlessly. I now have my usb to carry around and keep track of changes. Now it’s time to get back to it and solve this maze.