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.

 

[Informatix]

Good job.
As the stack size is much bigger in C, the mazes can be a lot larger than in Java. Great improvement.
I will benchmark the lib today to compare it with the Java version and measure the performance improvement.

 

[Informatix]

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]

I tested the lib with many different settings and the performance improvement over the Java version is very good: around +65%

 

[sorex]

improvement over the Java version is very good: around +65%

nice job, wonder.

 

[wonder]

Thank you so much!! I'm really glad to see such good results!
Like I mentioned in the first post, it's Fred's algorithm! None of this would have been possible without his code!

 

[Informatix]

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

 

[wonder]

Library updated to v1.30
- Internal math simplified (faster code)
- New solving mode (SolveMazePlus)
- More accurate path optimization algorithm
- Example code and apk updated

 

[Informatix]

I tried the version v1.3 and saw no speed improvement over the previous version with my benchmark.

 

[Informatix]

In your doc in first thread, you should correct the error:
ms.SolveMazeInitialize(20, 20)
It's:
Maze = ms.SolveMazeInitialize(20, 20)

 

[Informatix]

The bi-directional search (SolveMazePlus) seems bugged. The results are wrong and the computation time is very long.

 

[Informatix]

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]

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]

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]

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]

All results are wrong.

Issues corrected for the next version.

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.

Very well, I'll change my benchmark code to match yours.

 

[wonder]

Library updated to v1.32
- Minor code refactoring
- SolveMazePlus() bugs corrected

Example code and apk will be updated soon.

 

[wonder]

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.

 

[wonder]

Library updated to v1.51
- Fixed a memory leak bug on the Dispose method.