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:

wonder

Expert
Licensed User
Longtime User

Attachments

  • demo.zip
    9.4 KB · Views: 367
Last edited:

wonder

Expert
Licensed User
Longtime User
There's an error in the example.
Corrected. Thanks. :)

How fast was it in the original B4A version?
These are the B4A timings:
Informatix said:
Moto G (KitKat):
SolveMaze_FLMAlgo_MDA = 10.097 ms / Worst = 0.149 ms
SolveMaze_FLMAlgo_SDA = 8.365 ms / Worst = 0.089 ms
---
Kindle Fire HD (FireOS based on ICS):
SolveMaze_FLMAlgo_MDA = 8.965 ms / Worst = 0.096 ms
SolveMaze_FLMAlgo_SDA = 7.643 ms / Worst = 0.094 ms
---
Huawei Honor (Gingerbread):
SolveMaze_FLMAlgo_MDA = 11.197 ms / Worst = 0.172 ms
SolveMaze_FLMAlgo_SDA = 9.889 ms / Worst = 0.134 ms
---
Nexus 7 (Lollypop):
SolveMaze_FLMAlgo_MDA = 7.393 ms / Worst = 0.078 ms
SolveMaze_FLMAlgo_SDA = 5.968 ms / Worst = 0.064 ms

They cannot be compared currently because this C version stores the complete path, which is not done by the Java version, and does not reset it when you call SolveMaze again so this function cannot be put in the loop of the benchmark used for the Java version.
I can add an option to the initializer so that it won't store the path.
Reseting is entire optional, I added it as an extra.

I'll add the C++ source to the first post.
 

wonder

Expert
Licensed User
Longtime User
@Informatix - Ok, I found the issue! See the video below.

If you start or finish in a solid block (a "1" in the maze matrix), it will indeed crash. The current workaround is adding any of these lines:
B4X:
If ms.IntMatrixGetElement(Maze, sX, sY) = 0 And ms.IntMatrixGetElement(Maze, dX, dY) = 0 Then _                    
Log("Solution: " & ms.SolveMaze(Maze, sX, sY, dX, dY))
B4X:
If ms.IntMatrixGetElement(Maze, sX, sY) = 1 Or ms.IntMatrixGetElement(Maze, dX, dY) = 1 Then Continue
Log("Solution: " & ms.SolveMaze(Maze, sX, sY, dX, dY) & " - " & ((nt.NanoTime - ts) / 1000000) & " millisecs.")

Note: The solution is almost always true because the map has minimal complexity.

The code is still running as I'm writting this post. No crashes. :)
I'll make sure to add this verification to the original C++ code.

EDIT: There is still a crash here an there, every so often, might be stack overflow on more complex maps.
Is there a way to avoid it?
 
Last edited:

wonder

Expert
Licensed User
Longtime User

Informatix

Expert
Licensed User
Longtime User
EDIT: There is still a crash here an there, every so often, might be stack overflow on more complex maps.
Is there a way to avoid it?
The only ways to avoid a StackOverflow are to avoid recursive functions or to reduce a lot their memory consumption. If your routine is very fast, maybe you can afford to write it as an iterative function, not a recursive one.
 

Informatix

Expert
Licensed User
Longtime User
I know that you have limited time, but if possible, would you be willing to write an iterative version of your SDA algorithm?
I'm currently writing the tutorial explaining how I solved a few technical problems in Diktatour and I prefer, indeed, to focus on that task for now. Doing an iterative version is not very complicated. You just have to manage the stack yourself. For help, look here. I'd use the stack class of DataCollection.
 

Informatix

Expert
Licensed User
Longtime User
1) Do you also encounter this issue (stack overflow) in your B4A version for larger/more complex mazes?
Yes, of course. It is due to the stack size limitation of Java. It is low under Android but a grid 20x20 with a moderate number of obstacles is not a problem on most devices.
2) Is there an iterative version of your algorithm?
I wrote one but the code is lost. It was of no interest in Java.
 

wonder

Expert
Licensed User
Longtime User
The library was just updated and so was both the zip file and source code provided in the first post.

I've done some corrections/changes to my logic, but the original Recursive SDA algorithm remains untouched.
For the past 3 hours, I've been running a B4A test, generating random mazes with random starting and finishing positions on a 20x20 matrix.
No crashes (stack overflow) so far. It appears to be stable enough for such world size.
 
Last edited:

Informatix

Expert
Licensed User
Longtime User
I get very strange results sometimes. For example (SS = start, DD = destination):
B4X:
......XX....XXXXXX....XX....XX..........
....XX..XX..............XX....[]..XX....
....XX..XX..........XX..XXDDXX[]XXXXXX..
..XX....XX............XX..XX..[][][][]..
XX..XXXX......XXXX..XX[]....XX....XX[][]
............XXXX..[][][]..XXXX....XXXX[]
..XXXX....XX....XX[]XX..[]XXXXXXXXXX..[]
XX..XX........[][][]..[]......XX..XXXX[]
........[][][][]XX..[][][]XXXX[][][][][]
......[][]XX..XX..[][][]..XXXX[]....XX..
XX....[]XX..............[][][][]XX......
....XX[]XXXX....XX......XX......XX......
......[]....XXXX..XXXX....XX..XX........
......[]XXXX..XX........XX............XX
XXXX..[][][]XX..XX..........XXXX..XX....
....XX..XX[]......XXXX......XX....XX..XX
....XX....[]..XX....XX......XX..........
..XXXXXX..SS....XX....XXXX..XX..XXXX..XX
..........XX..XX..[]XX[][][]XX..XXXX....
........XXXXXX........XX....XXXXXX......

Could you provide a working example inside a loop?
 

Informatix

Expert
Licensed User
Longtime User
Another example:
B4X:
........XXXXXX..XXXX....................
..............XX....XX..XX..XXXXXXXX....
........XXXX..........XX..XXXX..XX....XX
..XXXX........XX......XX..XX....XX......
........XX..XX..XX........XX..........XX
....XXXX....XXXX..XXXX..XXXX....XX..XXXX
XX....XX..XXXX..XXXX..XX....XX....xD....
..XX..XX........XX........XX......[]....
XX..XX....XX..XXXX........XXXXXX..[]..XX
........XX....XX..XX......XX..XXXX[]XX..
....XX..XX..............XXXXXX....[]XX..
..........XXXX......XX..XX....XXXX[]....
....XX....XX......XX..XX....XX..XX[]....
XX......XX[][][][]XX[]..XXXX....XX[]XXXX
XX..SS[][][]XX..[][][][][][]..XXXX[][]..
..XX..XX......XX............[][]..XX[]XX
XX..XX....XX..............XXXX..[][][]..
......XX..XXXX..............XX..........
..XX..XX..XX..XX..XX..[]....[]XX[]..XX..
..XXXX....XX......XXXXXX..XX........XX..
 
Top