Archive | Maze Solver RSS for this section

It solves!

So it can now solve funky shaped mazes so long as the entrance and exit points lay on the outer most edges.  Also that ridiculously big one took 116 seconds to solve.

Targettarget1-2
Advertisements

Homestretch

It’s so beautiful… All rectangular mazes can be solved and I should have no problem making it solve circular mazes or even mazes of weird shapes.  The only thing left to do is now just some code cleanup, optimization and then port it over to the android.  I’ll probably make a desktop version that will be able to solve rediculously large mazes.

TargetTarget1Target2Target3Target4Target5

 

 

Why do more when you can do less.

This has pretty much been my driving motivation, trying to optimize all my code to have the fastest runtime possible.  Before when I was running ZS’s thinning algorithm I was reading straight from the Matrix using the CvMat get and put methods.  I thought that maybe there was speed to be gained if before I converted my matrix into a two-dimentional integer array so I didn’t have to work with double values that the get and set methods provided.  I’ll let the picture speak for itself.

The decrease was rediculous, and I still wonder; could it possibly be even optimized more?  I’ll probably still play around with it and find out but I can definetly apply this to my A* algorithm.

Isthisreallife

On the straight and narrow

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.

Arrow8Target

Untitled

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.

Target

 

 

 

Untitled

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.

Astar

Let the stars align

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.

Yourdoignitwrong