# B4A LibraryMazeSolver - 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]

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

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: 400
Last edited:

Longtime User

#### Attachments

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

#### Informatix

##### Expert
Longtime User
There's an error in the example. The first line of MazeTest should be:
Maze = ms.SolveMazeInitialize(40, 20)

#### sorex

##### Expert
Longtime User
How fast was it in the original B4A version?

#### Informatix

##### Expert
Longtime User
How fast was it in the original B4A version?
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.

#### wonder

##### Expert
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
---
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.

#### Informatix

##### Expert
Longtime User
By running many times your code on various mazes, with various start and end positions, I encounter a lot of crashes for a grid 20x20. In my loop, I reuse the matrix by calling the reset function. Initialize and Dispose are outside the loop.

#### wonder

##### Expert
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:

Longtime User

#### Informatix

##### Expert
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
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
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.

#### Informatix

##### Expert
Longtime User
Is this the algorithm that you use in Diktatour?
Not exactly because I used optimizations specific to the game, but it is very close. I did not use a single dimensional array for convenience.

#### wonder

##### Expert
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
Longtime User
No crashes (stack overflow) so far. It appears to be stable enough for such world size.
That depends strongly on the device used. I will test your code if I find some time today. It would be interesting to compare its speed to the speed of the Java version.

#### Informatix

##### Expert
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
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..``````

B4A Library Native SHA-512
Replies
4
Views
3K
Replies
95
Views
29K
Android Tutorial Optimization with B4A
Replies
11
Views
5K