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:

Spoiler: Expand

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

'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

'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.

'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)

'Solves the maze in Optimized Plus mode.
ms.SolvePlus(Maze, startX, startY, destX, destY, recursionLimit)

'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)

'[OPTIONAL] You may overwrite (faster) your maze world, but if you want, you may also reset it like this:
ms.IntMatrixReset(Maze)

'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.

 

[wonder]

::: Example Project [Updated 2018-11-12] :::

Actual screenshot

Note: NanoTime library required for benchmarking: https://www.b4x.com/android/forum/threads/nanotime.50104/

 

[Informatix]

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

 

[sorex]

How fast was it in the original B4A version?

 

[Informatix]

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]

There's an error in the example.

Corrected. Thanks.

How fast was it in the original B4A version?

These are the B4A timings:

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.

 

[Informatix]

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]

@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:

If ms.IntMatrixGetElement(Maze, sX, sY) = 0 And ms.IntMatrixGetElement(Maze, dX, dY) = 0 Then _                    
Log("Solution: " & ms.SolveMaze(Maze, sX, sY, dX, dY))

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?

 

[wonder]

Confirmed Stack Overflow for a 200x200 maze matrix.
http://s7.postimg.org/fseta8wnv/Capture.png

@Informatix
1) Do you also encounter this issue (stack overflow) in your B4A version for larger/more complex mazes?
2) Is there an iterative version of your algorithm?

 

[Informatix]

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.

 

[wonder]

I know that you have limited time, but if possible, would you be willing to write an iterative version of your SDA algorithm?

 

[Informatix]

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]

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]

Thanks, I'll look into it!!
Is this the algorithm that you use in Diktatour?

 

[Informatix]

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]

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.

 

[Informatix]

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]

I get very strange results sometimes. For example (SS = start, DD = destination):

......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]

Another example:

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

 

[wonder]

Library updated. Bugs corrected. Video added.
Everything should be working now.