B4A Library MazeSolver - C++ Powered DFS Algorithm w/ Path Optimization

Informatix

Expert
Licensed User
I did a small mistake in my benchmark and I computed the improvement with a wrong formula (the right one being ((old - new) / old) * 100). The fixed number is around +30%. Still very good.

EDIT: I think I should change the sign too. So the result should be written -30% (the new result reduces the previous result by 30%).
 
Last edited:

Informatix

Expert
Licensed User
Benchmark info: Average solving times for a sample of 10,000+ 20x20 solved mazes with a 20% obstacle density.
In your benchmark, did you remove the directional bias (results may be better for some search directions than others) and positional bias (results may be better for some distance than others)? The number of obstacles should vary too in a non-random manner to avoid the density bias.
And it would be interesting to know the worst time.
 

Informatix

Expert
Licensed User
Could you add a limit parameter in your SolveMaze function? Because it's not the size or the density of the grid that are the major causes of StackOverflow but the number of calls to the function. A limit value would allow to stop the search past a certain number of recursive calls. This setting would also allow us to create our own bi-directional searches in different threads.
 

wonder

Expert
Licensed User
I tried the version v1.3 and saw no speed improvement over the previous version with my benchmark.
The speed improvement refers only to my optimization algorithm, I simplified the math.

Maze = ms.SolveMazeInitialize(20, 20)
Thank you, corrected. :)

The bi-directional search (SolveMazePlus) seems bugged. The results are wrong and the computation time is very long.
I'll look into it as soon as possible. If you have time, show a concrete example, maybe I'll find the flaw faster.

In your benchmark, did you remove the directional bias?
Your algorithm remains untouched, but I'll send you the source code just to be safe.

Could you add a limit parameter in your SolveMaze function?
Sure, I'll do it soon. :)

------------------------------------------------------------------------

Thank you so much for your interest! :)
 

Informatix

Expert
Licensed User
I'll look into it as soon as possible. If you have time, show a concrete example, maybe I'll find the flaw faster.
All results are wrong. For example, when the shortest path is 14, SolveMazePlus returns 4, 7, 9, anything but never 14. And it's 10 times slower than SolveMaze. The problem is really obvious.

Your algorithm remains untouched, but I'll send you the source code just to be safe.
I was talking of the benchmark code.
 

wonder

Expert
Licensed User
Last edited:

wonder

Expert
Licensed User
Library updated to v1.50
- Now supporting iteration instead of recursion (no more crashes!).
- New LoadBitmap() function. Create your mazes on MS-Paint.
- New GenerateRandomData() function. Easier testing and benchmarking.

Proven its stability, please consider this version as a final version.
I won't be working on this library anytime soon.
Feel free to explore and modify my source code.

Thank you all for your support. :)
 
Top