**MazeSolver 1.51**

Fast Path Finding Algorithm

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

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

Written in C++ (Visual Studio Enterprise 2015) and compiled into a B4A library with

**Native Library Generator**.#### Attachments

Last edited: