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: Optimized: Optimized Plus :Note:
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 .
Native Library Generator 