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

MazeSolver 1.51
Fast Path Finding Algorithm

Version 1.0 - Pause the video at any time to see a solution (optimized mode).

[Updated 2016-07-11]
Please read the latest posts first


_.-*-._.-*-._.-*-._.-*-._.-*-._.-*-._.-*-._.-*-.__.-*-._.-*-._.-*-._.-*-._.-*-._.-*-._.-*-._.-*-._

That's right, we're down to the nanosecond benchmark! In this library, all computations are done in natively, so one can expect blazing fast results.
All credit for the original Recursive_FLMAlgo_SDA path finding algorithm goes to [B]Informatix[/B].
This project is based on his code and wouldn't be possible without him. Thank you, Fred. :)

_.-*-._.-*-._.-*-._.-*-._.-*-._.-*-._.-*-._.-*-.__.-*-._.-*-._.-*-._.-*-._.-*-._.-*-._.-*-._.-*-._
Solving methods:
Informatix's Recursive_FLMAlgo_SDA is a very fast 2D exploration algorithm. In a way, it mimics what happens in real-life if one decided to explore a maze without a map.
There's no guarantee that it will always find the shortest path, but the results are still pretty good. I decided to give you, the end-user, the ability to trade between solving time and optimal path accuracy (relative to a DFS type algorithm). You may solve the maze in 3 different ways, here's how it works:

Standard: Fastest solving time possible
- No changes to the original algorithm.
- Solve(maze, startX, startY, destX, destY, False, recursionLimit)

Optimized: Slower than Standard
- The result is given by exploring the maze one single time (A to B). The solution is optimized by discarding any unnecessary waypoints.
- Solve(maze, startX, startY, destX, destY, True, recursionLimit)

Optimized Plus: Slower than Optimized
- The result is given by exploring the maze two times, A to B and B to A. Both solutions are optimized and compared. The shortest one (in A to B form) is returned.
- SolvePlus(maze, startX, startY, destX, destY, recursionLimit)

Note:
- To activate the iterative mode use -1 as the recursionLimit.
- For unlimited recursion use 0.​

Stability:
For larger mazes, when using recursive mode (slightly faster) there's always the risk of stack overflow.

Usage:
B4X:
Sub Process_Globals
    Dim Maze as Long 'Type MUST be Long
    Dim ms as MazeSolver
    ms.setPRNGSeed(DateTime.Now) 'OPTIONAL: Only if you wish to use ms.MazeMatrixGenerateRandomData()
End Sub

B4X:
'Creates an empty maze world
'If you're solving mazes in a loop, create the maze world outside (before) the loop.
Maze = ms.Initialize(20, 20) 'sizeX, sizeY: Arbitrary
B4X:
'To populate the maze world with obstacles or walls use this function:
ms.IntMatrixSetElement(Maze, x, y, 1) '1 for obstacle, 0 for empty space.
B4X:
'Solves the maze in Standard mode. Path optimization is optional.
'optimizePath: If set to TRUE, it will then solve in maze in Optimized mode.
ms.Solve(Maze, startX, startY, destX, destY, optimizePath, recursionLimit)
B4X:
'Solves the maze in Optimized Plus mode.
ms.SolvePlus(Maze, startX, startY, destX, destY, recursionLimit)
B4X:
'The solution is stored in two (x,y) waypoint arrays.

'Gets the array size for both arrays. Returns 0 if there was no solution for the maze.
ms.IntMatrixGetWaypointArraySize(Maze)

'Gets the X coordinate of a given waypoint
ms.IntMatrixGetWaypointX(Maze, Index)

'Gets the Y coordinate of a given waypoint
ms.IntMatrixGetWaypointY(Maze, Index)
B4X:
'[OPTIONAL] You may overwrite (faster) your maze world, but if you want, you may also reset it like this:
ms.IntMatrixReset(Maze)
B4X:
'You MUST dispose the maze world once you don't need it anymore
'If you're solving mazes in a loop, dispose the maze world outside (after) the loop.
ms.Dispose(Maze)

Remember: Do NOT create several maze worlds, recycle instead. You may dispose the maze on Activity_Pause or LG_Dispose (LibGDX).
Source Code:
Included as the source code example for my Native Library Generator.

Written in C++ (Visual Studio Enterprise 2015) and compiled into a B4A library with Native Library Generator.
 

Attachments

  • MazeSolver 1.51.zip
    483.9 KB · Views: 516
Last edited:

Informatix

Expert
Licensed User
Longtime User
As you saw, this algorithm does not find the optimal way. It is just very quick to find a way among all possibilities. Depending on the game, a better algorithm has to be used (like A* in my Dark Continent game or my new game Daedalo Monstro) for smarter moves.
 

Informatix

Expert
Licensed User
Longtime 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
Longtime 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
Longtime 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
Longtime 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
Longtime 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
Longtime User
Last edited:

wonder

Expert
Licensed User
Longtime 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