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
_.-*-._.-*-._.-*-._.-*-._.-*-._.-*-._.-*-._.-*-.__.-*-._.-*-._.-*-._.-*-._.-*-._.-*-._.-*-._.-*-._
Fast Path Finding Algorithm
[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.
- 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
Last edited: