Android Tutorial Optimization with B4A

OPTIMIZATION WITH B4A​

A case where optimization is required:
One of the most time-consuming task in a RTS game is to compute paths for all units because of the number of units and the many computations and memory accesses needed to find a path. If you want to run your game at a fast pace, and thus stay under 16ms past in the Render event of libGDX, you have only 16/100 = 0.16 ms to compute each path for 100 units. In a real situation where you have to check collisions, select targets, animate the moves and shootings, react to user actions, etc., you have in fact less than 0.1 ms left for your path computations (and my current game can have up to 200 units on screen...). Choosing the proper pathfinding algorithm and writing it as optimized as possible becomes very important. Fortunately, many developers and researchers worked on this problem and published their algorithms or source codes on Internet. So it's very easy to find a good implementation of A* for Java, for example, and not very difficult to find better algorithms than A* for specific cases. But the interest and performance of all this material for your case is not always easy to evaluate, and you can read articles claiming a 50% improvement over a well-known algorithm while your implementation of their pseudocode tends to prove the contrary. Unless you ask for code to the authors, you have no idea of the chosen implementation of both algorithms and that can lead to wrong conclusions (including on the authors side). It's very common to see only pseudocode in research works because most researchers are convinced that an unoptimized good algorithm will always beat an optimized bad algorithm and that the implementation in a given language is not the most important. That's only partially true as an american team proved it. The difference between the various implementations in C of the same pseudocode can be huge (up to 20x faster in some cases). Is it the same in Java? That gave me an idea for a quiz that I submitted to the fellow members of this forum. Now here's the tutorial explaining my solution and how I proceeded to optimize the code. I added a few general tips about optimization and faster variants of a few math functions at the end.

An unit blocked in a maze:
Let's consider an unit moving along a pre-computed path. At a time, it will be blocked by other units sharing the same path or by temporary obstacles like closed gates or open bridges. You have two solutions: either the blocked unit stops moving and waits until the path is clear or the unit tries to find another way. For the latter, you're in trouble if re-computing a new path is too costly (e.g. the fastest implementation of the A* algorithm is too slow for a RTS game with 100 units under Android) but blocking the unit can lead easily to a deadlock situation or create stupid behaviors so it's better to find a solution to keep moving. Many solutions to this problem exist, but I'll present only the one that I used in my game because it is simple and does not require multithreading operations.
The idea is to consider only the area where the unit is blocked and try to bypass this area. Typically, a path is made of waypoints. The unit moves from a waypoint to another by computing intermediate moves with a given speed and angle (this is done by the Steering Behaviors library in my game). In other words, my problem is to find an alternate path from the current location of the unit to the waypoint located after the blocking point and, as the other units and obstacles create a kind of maze, it can be resumed to a maze solving in a small grid, with only one ending (the waypoint to reach) and multiple paths.

The DFS algorithm:
This maze has peculiarities that prevent from using some maze solving algorithms or make them highly inefficient: the starting and ending positions are not on the edges, there are 0 to n paths, loops are possible. The Trémaux's algorithm can solve it anyway under its modern form: the Depth-First Search algorithm. Here's this algorithm in its DFS recursive variant, converted from the Java code published on Wikipedia:

Dim Visited(SizeX, SizeY) As Boolean
Dim CorrectPath(SizeX, SizeY) As Boolean 'The solution to the maze

Sub SolveMaze As Boolean
    'Initializes the arrays
    For X = 0 To SizeX - 1
        For Y = 0 To SizeY - 1
            Visited(X, Y) = False
            CorrectPath(X, Y) = False
        Next
    Next

    'Solves the maze (the True values in CorrectPath indicate the path to the end)
    Return Recursive_DFS(StartX, StartY)
End Sub

Sub Recursive_DFS(X As Int, Y As Int) As Boolean
    'If you reached the end
    If X = DestX AND Y = DestY Then
        Visited(X, Y) = True
        Return True
    End If

    'If you are on a wall or already were here
    If Blocked(X, Y) OR Visited(X, Y) Then Return False

    'Marks as visited
    Visited(X, Y) = True

    If X <> 0 Then 'Checks if not on left edge
        If Recursive_DFS(X - 1, Y) Then 'Recalls function one to the left
            CorrectPath(X, Y) = True 'Sets that path value to True
            Return True
        End If
    End If
    If X <> SizeX - 1 Then 'Checks if not on right edge
        If Recursive_DFS(X + 1, Y) Then 'Recalls function one to the right
            CorrectPath(X, Y) = True
            Return True
        End If
    End If
    If Y <> 0 Then 'Checks if not on bottom edge
        If Recursive_DFS(X, Y - 1) Then 'Recalls function one up
            CorrectPath(X, Y) = True
            Return True
        End If
    End If
    If Y <> SizeY - 1 Then 'Checks if not on top edge
        If Recursive_DFS(X, Y + 1) Then 'Recalls function one down
            CorrectPath(X, Y) = True
            Return True
        End If
    End If
    Return False
End Sub

The Blocked array contains the maze. Its boolean values are set to True when an obstacle blocks the way.
StartX, StartY and DestX, DestY define the starting point and the destination.

First optimization:
I can remove the CorrectPath array as I don't need to store the path. Why? Because I need an answer only to these two questions: is there an alternate path? If no, the unit is really blocked. If yes, what's the next move to engage the unit on this path? As the obstacles position can change after each computation, it's useless to store a path. Only the first move has some interest and there's a trick to know where to do this first step without ambiguity: taking the destination as the starting point. The DFS algorithm stops as soon as it reaches the end so there's only one path reaching the end, i.e. the current location of the unit as the search direction is reversed.
I can also write differently the first lines because my destination is not supposed to be blocked (it's where my unit comes from).
My new code:

Dim Visited(SizeX, SizeY) As Boolean

Sub SolveMaze2 As Boolean
    'Initializes the Visited array
    For X = 0 To SizeX - 1
        For Y = 0 To SizeY - 1
            Visited(X, Y) = False
        Next
    Next

    'Is there a path to the end ?
    Return Recursive_SolveMaze2(StartX, StartY)
End Sub

Sub Recursive_SolveMaze2(X As Int, Y As Int) As Boolean
    'If you are on a wall or already were here
    If Blocked(X, Y) OR Visited(X, Y) Then Return False

    'Marks as visited
    Visited(X, Y) = True

    'If you reached the end
    If X = DestX AND Y = DestY Then Return True

    'Checks if not on left edge
    If X <> 0 Then
        If Recursive_SolveMaze2(X - 1, Y) Then 'Recalls function one to the left
            Return True
        End If
    End If

    'Checks if not on right edge
    If X <> SizeX - 1 Then
        If Recursive_SolveMaze2(X + 1, Y) Then 'Recalls function one to the right
            Return True
        End If
    End If

    'Checks if not on bottom edge
    If Y <> 0 Then
        If Recursive_SolveMaze2(X, Y - 1) Then 'Recalls function one up
            Return True
        End If
    End If

    'Checks if not on top edge
    If Y <> SizeY - 1 Then
        If Recursive_SolveMaze2(X, Y + 1) Then 'Recalls function one down
            Return True
        End If
    End If
    Return False
End Sub

This code is my reference as it is the basic form of the algorithm adapted to my case.
Using the benchmark provided in the quiz thread, I get (the first number is the sum of all timings):

SolveMaze = 28.75 ms / Worst = 0.214 ms
SolveMaze2 = 22.787 ms / Worst = 0.175 ms​

The removal of CorrectPath improved the performance, which is not surprising.
The worst timing is very important to consider as it says how much time has been spent in the worst case. If I multiply this value by the number of units, I have an idea of the maximum number of milliseconds required in my Render event to compute all path changes. That being said, it is very unlikely that all units are blocked at the same time so this value can probably be halved.

Second optimization:
An idea to improve my code is to check whether the iterative version is faster than the recursive one. You can read often that iterative variants are faster because of the memory allocations and deallocations implied by the recursive calls (each function is saved onto the stack with its data). In B4A, unless you use my DataCollection library, you have only the List object at your disposal to store the extra data required by the iterative version. Anyway, it's not the main reason of the very bad results that I get. I am so far from the performance of the recursive variant that I really doubt that the iterative version could be used even after a heavy optimization. Moreover it is less readable than the recursive code so I abandon completely the idea.
That being said, the iterative variant is your only option if you want to get rid of the StackOverflow error which is the main drawback of recursive functions. In my game, the grid is too small to raise the error on most devices and I set a limit in the final code to stop after a certain recursion depth so I'm not concerned.

Third optimization:
At the language level, it is interesting to see if avoiding nested IF by combining them on a single line (thanks to the short-circuit evaluation) could bring an improvement. So I just replace lines like:

If X <> 0 Then
    If Recursive_SolveMaze2(X - 1, Y) Then 'Recalls function one to the left

by:

If X <> 0 AND Recursive_SolveMaze3(X - 1, Y) Then

Result:

SolveMaze2 = 22.787 ms / Worst = 0.175 ms
SolveMaze3 = 22.774 ms / Worst = 0.17 ms​

The slight difference is not significant at all.

Fourth optimization:
Another idea is to move the first condition to avoid a recursive call for nothing when the next cell to visit contains an obstacle or has already been visited. I am expecting a lot from this change. I remove:

'If you are on a wall or already were here
If Blocked(X, Y) OR Visited(X, Y) Then Return False

and I change all other conditions to test the Blocked and Visited arrays. Example:

If X <> 0 AND Not(Blocked(X - 1, Y) OR Visited(X - 1, Y)) AND Recursive_SolveMaze4(X - 1, Y) Then

In the above case, Recursive_SolveMaze4 is only called when I am sure that I can visit this cell.
The result is very surprising:

SolveMaze2 = 22.787 ms / Worst = 0.175 ms
SolveMaze4 = 28.409 ms / Worst = 0.196 ms​

It's a lot slower !
In fact, and I thank Cimperia to have drawn it to my attention, using the NOT operator is a big mistake as it is very slow.
So I change all NOT:

If X <> 0 AND Blocked(X - 1, Y) = False AND Visited(X - 1, Y) = False AND Recursive_SolveMaze5(X - 1, Y) Then

The performance improvement is impressive and can be reproduced on all devices at my disposal:

SolveMaze2 = 22.787 ms / Worst = 0.175 ms
SolveMaze4 = 28.409 ms / Worst = 0.196 ms
SolveMaze5 = 15.593 ms / Worst = 0.137 ms​

Fifth optimization:
As you can notice, computations of the new X and Y are repeated three times by condition, so I create a variable to store the computation result:

Sub Recursive_SolveMaze6(X As Int, Y As Int) As Boolean
    'Marks as visited
    Visited(X, Y) = True

    'If you reached the end
    If X = DestX AND Y = DestY Then Return True

    'Checks if not on left edge and not blocked or already were here
    If X <> 0 Then
        Dim NewX As Int = X - 1
        If Blocked(NewX, Y) = False AND Visited(NewX, Y) = False AND Recursive_SolveMaze6(NewX, Y) Then
            Return True
        End If
    End If

    'Checks if not on right edge and not blocked or already were here
    If X <> SizeX - 1 Then
        Dim NewX As Int = X + 1
        If Blocked(NewX, Y) = False AND Visited(NewX, Y) = False AND Recursive_SolveMaze6(NewX, Y) Then
            Return True
        End If
    End If

    'Checks if not on bottom edge and not blocked or already were here
    If Y <> 0 Then
        Dim NewY As Int = Y - 1
        If Blocked(X, NewY) = False AND Visited(X, NewY) = False AND Recursive_SolveMaze6(X, NewY) Then
            Return True
        End If
    End If

    'Checks if not on top edge and not blocked or already were here
    If Y <> SizeY - 1 Then
        Dim NewY As Int = Y + 1
        If Blocked(X, NewY) = False AND Visited(X, NewY) = False AND Recursive_SolveMaze6(X, NewY) Then
            Return True
        End If
    End If
    Return False
End Sub

Result:

SolveMaze5 = 15.593 ms / Worst = 0.137 ms
SolveMaze6 = 15.308 ms / Worst = 0.131 ms​

Not very significant. Adding 1 or subtracting 1 is so fast that there's no real advantage to store the computation. However, I favor this way of writing code as it minimizes the risk of error so I keep it.
Since NewX and NewY are temporary variables (they are not used after a recursive call), it is safe to make them globals but local variables are known to be faster. A quick test confirms it:

SolveMaze6 = 15.308 ms / Worst = 0.131 ms
SolveMaze7 = 16.163 ms / Worst = 0.146 ms​

At this point, I run out of ideas to improve the code at the language level. It looks like I created the fastest variant of the DFS algorithm in B4A. Really ?

...

 

[Informatix]

Using another algorithm ?
Until now, I used the DFS algorithm but I could use the Breadth-First Search or the Iterative Deepening DFS algorithms instead. Both have the advantage over DFS to find the shortest path. This is not a requirement in my case and the result of my final algorithm shows that 90% of paths found are the shortest ones, but that could deserve a try. In fact, there's no chance for these algorithms to beat my DFS version: the main difference between the BFS and DFS algorithms is the use of a queue instead of a stack; that prevents from writing BFS in a recursive way and we already saw than using a List is too costly so it's not worth trying. The IDDFS algorithm is a variant of the DFS algorithm where the recursion depth is increased by a loop each time that the current maximum depth returns no result. It is more suited for trees than mazes as it can go multiple times through the same paths. If you try to implement it, you will have to reinitialize the Visited array for each new maximum depth so you can easily imagine the huge penalty on the performance for medium and long paths.

DFS is far from perfect:
So we keep the DFS algorithm. But is there a mean to improve it? Look at how it proceeds: it starts by exploring the cell on the left of the starting position. It continues to the left until it meets the edge of the maze or a wall (a blocking cell). If blocked, it goes back and explores the cell on the right of the current position. It's where we come from so checking Visited will always return True. That seems to be a stupid move. So why do we start always to the left? And why do we go right if blocked? Because the DFS algorithm is not specifically designed for a maze and is far from perfect in this case. The sequence of search directions is arbitrary. In a tree, there's no mean to decide which branch to check first because there's not a predictable topology, just a succession of parent/child. In the navigation grid of a 2D game, you know right from the start the relative position of the goal (it can be on the left, on the right, above, etc.) and the distance between two cells not directly connected. Indeed, you can compute easily the distance between the starting cell and the destination, which is impossible in a tree. This can be used to orient the search. If the starting position is on the left of the goal, then moving right first is smarter than moving left. That can be wrong as the path can turn around the starting location before reaching the destination, but it has a higher probability to succeed. So I'm going to add some code to my DFS to select the appropriate sequence of search directions being given the relative positions at start. This code, that speeds up the algorithm by taking adaptative and approximate decisions based on probabilities, is called a heuristic.

A very simple heuristic:
Currently, the sequence is Left-Right-Top-Bottom. A better sequence would be Left-Top-Bottom-Right. I create a recursive function for this sequence (I take the current recursive function and I move the condition checking the right cell at the end) and I add three other functions for the following sequences: Right-Top-Bottom-Left, Top-Left-Right-Bottom and Bottom-Left-Right-Top. It's not ideal; in Left-Top-Bottom-Right, we have Bottom after Top while the contrary could be better, so the vertical choice is completely arbitrary, but it's a very simple approach, easy to implement. The sequence selection is based on the horizontal and vertical distances and is done by this code:

Sub SolveMaze8 As Boolean
    'Initializes the Visited array
    For X = 0 To SizeX - 1
        For Y = 0 To SizeY - 1
            Visited(X, Y) = False
        Next
    Next

    'Selects the axis to follow
    Dim DifX As Int = StartX - DestX
    Dim DifY As Int = StartY - DestY
    Dim Horizontal As Boolean = Abs(DifX) > Abs(DifY)

    'Selects a sequence for the chosen axis
    If Horizontal Then
        If DifX > 0 Then
            Return Recursive_SolveMaze_Left(StartX, StartY)
        Else
            Return Recursive_SolveMaze_Right(StartX, StartY)
        End If
    Else If DifY > 0 Then
        Return Recursive_SolveMaze_Bottom(StartX, StartY)
    Else
        Return Recursive_SolveMaze_Top(StartX, StartY)
    End If
End Sub

I run the benchmark a few times to be sure that the randomness of the maze creation does not favor a certain direction.
Results:

SolveMaze6 = 15.308 ms / Worst = 0.131 ms
SolveMaze8 = 13.407 ms / Worst = 0.132 ms
---
SolveMaze6 = 15.411 ms / Worst = 0.092 ms
SolveMaze8 = 13.506 ms / Worst = 0.088 ms
---
SolveMaze6 = 12.69 ms / Worst = 0.071 ms
SolveMaze8 = 11.262 ms / Worst = 0.073 ms
---
SolveMaze6 = 14.944 ms / Worst = 0.122 ms
SolveMaze8 = 13.516 ms / Worst = 0.122 ms​

It's better in all cases but not very impressive.

Optimization of the heuristic:
In SolveMaze8, I use the Abs function which is known to be slow in many languages. I replace it by:

Dim Horizontal As Boolean
If DifX > 0 Then
    If DifY > 0 Then
        Horizontal = DifX > DifY
    Else
        Horizontal = DifX > -DifY
    End If
Else
    If DifY > 0 Then
        Horizontal = -DifX > DifY
    Else
        Horizontal = -DifX > -DifY
    End If
End If

As this code is called only once, the change should not have a significant effect. However, on all runs, I can see a very slight improvement.
Another optimization could be to re-compute the distance after each exploration to select the best sequence once again, but that would make the code too complex. It's better to rewrite everything with the same heuristic.

Optimization comes to a limit:
My DFS variant with four different sequences runs 2x faster than my original DFS implementation and 1.6x faster than my reference (SolveMaze2). The worst time is very good (close to 0.1 ms most of the time) so this is really usable in a game. I don't think that trying to improve again the DFS implementation is really necessary in most cases. And is it possible? B4A is not a language where you have many ways to write something and the algorithm is fairly simple.
However, a significant improvement could be achieved by using an array of bytes combining the values of the Blocked and Visited arrays to access the memory only once (it's what I did in my game) but the Blocked array initialization was always done until now outside the timing frame so I prefer to keep the two boolean arrays for the tutorial.
Another optimization could be to replace Visited by a single-dimensional array, but as this optimization can be applied to all algorithms of this tutorial and makes the code more complex and less readable, I will try it later.
The current version is good enough for many cases but not for my game where 200 units can be on screen at the same time. I want a smooth execution on all kind of devices so the fastest is the best. A new algorithm integrating the heuristic to minimize the number of visited cells is the next step in my search of the fastest solution. We saw above that starting in a chosen direction was a good idea, but the algorithm was unable to select the closest cell to the goal once blocked so the benefit was small. The purpose of the new algorithm is to select as often as possible the search direction with the highest probability of success.

My new algorithm:

Sub SolveMaze_FLMAlgo As Boolean
   'Sets the initial state of the elements of the Visited array
   For X = 0 To SizeX - 1
     For Y = 0 To SizeY - 1
       Visited(X, Y) = False
     Next
   Next

   'Runs the recursive algo
   Return Recursive_Algo(StartX, StartY)
End Sub

Sub Recursive_Algo(X As Int, Y As Int) As Boolean
   'Marks as visited
   Visited(X, Y) = True

   'If the goal is reached...
   If X = DestX AND Y = DestY Then Return True

   'Computes the horizontal and vertical distances
   Dim DistX As Int = DestX - X
   Dim DistY As Int = DestY - Y

   'Selects the axis to follow
   Dim Horizontal As Boolean
   If DistX > 0 Then
     If DistY > 0 Then
       Horizontal = DistX > DistY
     Else
       Horizontal = DistX > -DistY
     End If
   Else
     If DistY > 0 Then
       Horizontal = -DistX > DistY
     Else
       Horizontal = -DistX > -DistY
     End If
   End If

   'Selects the next cell to visit
   If Horizontal Then
     'The horizontal axis is explored first
     If DistX > 0 Then 'On the left -> to the right
       Dim Xright As Int = X + 1
       If Xright < SizeX AND Blocked(Xright, Y) = False AND Visited(Xright, Y) = False _
         AND Recursive_Algo(Xright, Y) Then Return True
     Else 'On the right -> to the left
       Dim Xleft As Int = X - 1
       If Xleft >= 0 AND Blocked(Xleft, Y) = False AND Visited(Xleft, Y) = False _
         AND Recursive_Algo(Xleft, Y) Then Return True
     End If
     'Vertical axis
     If DistY > 0 Then 'Too low -> to the top
       Dim Ytop As Int = Y + 1
       If Ytop < SizeY AND Blocked(X, Ytop) = False AND Visited(X, Ytop) = False _
         AND Recursive_Algo(X, Ytop) Then Return True
       Dim Ybottom As Int = Y - 1
       If Ybottom >= 0 AND Blocked(X, Ybottom) = False AND Visited(X, Ybottom) = False _
         AND Recursive_Algo(X, Ybottom) Then Return True
     Else 'Too high -> to the bottom
       Dim Ybottom As Int = Y - 1
       If Ybottom >= 0 AND Blocked(X, Ybottom) = False AND Visited(X, Ybottom) = False _
         AND Recursive_Algo(X, Ybottom) Then Return True
       Dim Ytop As Int = Y + 1
       If Ytop < SizeY AND Blocked(X, Ytop) = False AND Visited(X, Ytop) = False _
         AND Recursive_Algo(X, Ytop) Then Return True
     End If
     'Last possible direction
     If DistX > 0 Then
       Dim Xleft As Int = X - 1
       If Xleft >= 0 AND Blocked(Xleft, Y) = False AND Visited(Xleft, Y) = False _
         AND Recursive_Algo(Xleft, Y) Then Return True
     Else
       Dim Xright As Int = X + 1
       If Xright < SizeX AND Blocked(Xright, Y) = False AND Visited(Xright, Y) = False _
         AND Recursive_Algo(Xright, Y) Then Return True
     End If
   Else
     'The vertical axis is explored first
     If DistY > 0 Then 'Too low -> to the top
       Dim Ytop As Int = Y + 1
       If Ytop < SizeY AND Blocked(X, Ytop) = False AND Visited(X, Ytop) = False _
         AND Recursive_Algo(X, Ytop) Then Return True
     Else 'Too high -> to the bottom
       Dim Ybottom As Int = Y - 1
       If Ybottom >= 0 AND Blocked(X, Ybottom) = False AND Visited(X, Ybottom) = False _
         AND Recursive_Algo(X, Ybottom) Then Return True
     End If
     'Horizontal axis
     If DistX > 0 Then 'On the left -> to the right
       Dim Xright As Int = X + 1
       If Xright < SizeX AND Blocked(Xright, Y) = False AND Visited(Xright, Y) = False _
         AND Recursive_Algo(Xright, Y) Then Return True
       Dim Xleft As Int = X - 1
       If Xleft >= 0 AND Blocked(Xleft, Y) = False AND Visited(Xleft, Y) = False _
         AND Recursive_Algo(Xleft, Y) Then Return True
     Else 'On the right -> to the left
       Dim Xleft As Int = X - 1
       If Xleft >= 0 AND Blocked(Xleft, Y) = False AND Visited(Xleft, Y) = False _
         AND Recursive_Algo(Xleft, Y) Then Return True
       Dim Xright As Int = X + 1
       If Xright < SizeX AND Blocked(Xright, Y) = False AND Visited(Xright, Y) = False _
         AND Recursive_Algo(Xright, Y) Then Return True
     End If
     'Last possible direction
     If DistY > 0 Then
       Dim Ybottom As Int = Y - 1
       If Ybottom >= 0 AND Blocked(X, Ybottom) = False AND Visited(X, Ybottom) = False _
         AND Recursive_Algo(X, Ybottom) Then Return True
     Else
       Dim Ytop As Int = Y + 1
       If Ytop < SizeY AND Blocked(X, Ytop) = False AND Visited(X, Ytop) = False _
         AND Recursive_Algo(X, Ytop) Then Return True
     End If
   End If
   Return False
End Sub

The algorithm seems a bit complex but it is not. It's just a mix between the DFS algorithm and my heuristic. What does it do? It tries to detect which cell around the current cell is the closest to the goal. It goes to this cell, detects which cell is the closest to the goal, and continues until the destination is reached.
My code can generate 8 different sequences: Left-Top-Bottom-Right, Left-Bottom-Top-Right, Top-Left-Right-Bottom, Top-Right-Left-Bottom, Right-Top-Bottom-Left, etc., and can select a new sequence for each recursive call.
To fully understand it, let's take an example. If the horizontal distance between DestX (column of the destination) and X (column of the current cell) is -10, that means that X is bigger than DestX and thus is located on the right of the destination. If DestY - Y = 8, then the starting cell is located below the destination. Moving to the left and to the top should reduce the distance to the goal and be the smartest move. But, as diagonal moves are not allowed, the algorithm has to order these two moves. To decide which will be first, it compares the absolute values of distances. 10 is greater than 8, so there are more cells to cross on the horizontal axis than on the vertical axis. The horizontal axis is selected. Why? A particular case helps to understand: if DestY - Y = 0 then the current cell is on the same row as the destination. X - DestX cannot be equal to 0 at the same time or the goal is reached and we exit the recursive function. So the only axis to follow is the horizontal one, the one with the biggest delta. This rule can be applied to all situations.
Let's continue. On the horizontal axis, the difference is negative so the algorithm checks the left cell first. If this is a dead end, it goes back and explores the top cell (8 > 0). If it's also a dead end, it explores the remaining cells: the bottom one, then the right. Let's suppose that the bottom cell is not visited and not blocked so the function is called recursively to explore this cell. New distances are computed and the biggest absolute distance defines the prefered axis, then the sign of the distance indicates the direction to follow on the axis. A new sequence is started. If it leads nowhere, we return where we were before going to the bottom and we explore the last cell, on the right.
The benchmark result for this new algorithm speaks by itself:

SolveMaze2 = 22.787 ms / Worst = 0.175 ms
SolveMaze9 = 13.29 ms / Worst = 0.137 ms
SolveMaze_FLMAlgo = 10.097 ms / Worst = 0.149 ms
---
SolveMaze2 = 23.041 ms / Worst = 0.138 ms
SolveMaze9 = 13.418 ms / Worst = 0.088 ms
SolveMaze_FLMAlgo = 10.277 ms / Worst = 0.12 ms
---
SolveMaze2 = 19.107 ms / Worst = 0.125 ms
SolveMaze9 = 11.261 ms / Worst = 0.073 ms
SolveMaze_FLMAlgo = 8.965 ms / Worst = 0.096 ms​

With a single-dimensional array:
The drawback of multidimensional arrays is that they require an internal computation to locate the data in memory with the given indices, while a single-dimensional array uses directly the given index. To do the computation, it is necessary to get the length of dimensions, which is not a free operation. Moreover, you have to pass multiple arguments to functions and store multiple indices so there should be an obvious benefit to convert all multidimensional arrays to single-dimensional ones. Let's check whether it's true.
I convert Visited to a single-dimensional array. Two consequences: I have to initialize it linearly with a single loop, which is an advantage, but I have to add a few computations because DestX, DestY, StartX, StartY and the Blocked array are not suited for this change:

Sub SolveMaze_FLMAlgo_SDA As Boolean
   'Sets the initial state of the elements of the Visited array
   For Index = 0 To VisitedSDA.Length - 1
     VisitedSDA(Index) = False
   Next

   'Runs the recursive SDA algo
   DestIndex = DestX + (DestY * SizeX)
   InvSizeX = 1 / SizeX
   Return Recursive_FLMAlgo_SDA(StartX + (StartY * SizeX))
End Sub

Sub Recursive_FLMAlgo_SDA(Index As Int) As Boolean
   'Marks as visited
   VisitedSDA(Index) = True

   'If the goal is reached...
   If Index = DestIndex Then Return True

   'Computes the horizontal and vertical distances
   Dim Y As Int = Index * InvSizeX
   Dim X As Int = Index - (Y * SizeX)
   Dim DistX As Int = DestX - X
   Dim DistY As Int = DestY - Y

   'Selects the axis to follow
   Dim Horizontal As Boolean
   If DistX > 0 Then
     If DistY > 0 Then
       Horizontal = DistX > DistY
     Else
       Horizontal = DistX > -DistY
     End If
   Else
     If DistY > 0 Then
       Horizontal = -DistX > DistY
     Else
       Horizontal = -DistX > -DistY
     End If
   End If

   'Selects the next cell to visit
   Dim NewIndex As Int
   If Horizontal Then
     'The horizontal axis is explored first
     If DistX > 0 Then 'On the left -> to the right
       If X <> SizeX - 1 AND Blocked(X + 1, Y) = False Then
         NewIndex = Index + 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else 'On the right -> to the left
       If X <> 0 AND Blocked(X - 1, Y) = False Then
         NewIndex = Index - 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
     'Vertical axis
     If DistY > 0 Then 'Too low -> to the top
       If Y <> SizeY - 1 AND Blocked(X, Y + 1) = False Then
         NewIndex = Index + SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
       If Y <> 0 AND Blocked(X, Y - 1) = False Then
         NewIndex = Index - SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else 'Too high -> to the bottom
       If Y <> 0 AND Blocked(X, Y - 1) = False Then
         NewIndex = Index - SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
       If Y <> SizeY - 1 AND Blocked(X, Y + 1) = False Then
         NewIndex = Index + SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
     'Last possible direction
     If DistX > 0 Then
       If X <> 0 AND Blocked(X - 1, Y) = False Then
         NewIndex = Index - 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else
       If X <> SizeX - 1 AND Blocked(X + 1, Y) = False Then
         NewIndex = Index + 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
   Else
     'The vertical axis is explored first
     If DistY > 0 Then 'Too low -> to the top
       If Y <> SizeY - 1 AND Blocked(X, Y + 1) = False Then
         NewIndex = Index + SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else 'Too high -> to the bottom
       If Y <> 0 AND Blocked(X, Y - 1) = False Then
         NewIndex = Index - SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
     'Horizontal axis
     If DistX > 0 Then 'On the left -> to the right
       If X <> SizeX - 1 AND Blocked(X + 1, Y) = False Then
         NewIndex = Index + 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
       If X <> 0 AND Blocked(X - 1, Y) = False Then
         NewIndex = Index - 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else 'On the right -> to the left
       If X <> 0 AND Blocked(X - 1, Y) = False Then
         NewIndex = Index - 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
       If X <> SizeX - 1 AND Blocked(X + 1, Y) = False Then
         NewIndex = Index + 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
     'Last possible direction
     If DistY > 0 Then
       If Y <> 0 AND Blocked(X, Y - 1) = False Then
         NewIndex = Index - SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else
       If Y <> SizeY - 1 AND Blocked(X, Y + 1) = False Then
         NewIndex = Index + SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
   End If
   Return False
End Sub

This code introduces a new optimization: instead of dividing Index by SizeX to get Y, I multiply it by the pre-computed result of 1/SizeX because on many CPU multiplications of floats are faster than divisions. Depending on the computation and on the CPU, the difference can go over 100%. In other cases, the difference is next to none, so it's a safe optimization.
The big question with this code is: does the overhead of the added computations remove the benefit of using a single-dimensional array? Let's see the results on different devices with different Android versions:

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​

Let's see if I get the same improvement with a previous solution with no heuristic, for example SolveMaze6:

SolveMaze6_MDA = 15.308 ms / Worst = 0.131 ms
SolveMaze6_SDA = 14.368 ms / Worst = 0.089 ms​

The use of a SDA proves to be faster and I do appreciate the reduction in the worst time in all cases.
Now, the needs of my game are satisfied and I can stop there. I have no other idea anyway and I'm quite sure that all other optimizations will be very marginal. A gain of 1% or 2% does not really interest me, especially if I have to spend a few hours to get it.

In brief:
Between the Wikipedia version of the DFS algorithm converted to B4A and the final code using a SDA, there were many changes that increased the performance by more than 3. At the algorithm level, I removed what's useless for my case, moved the check of the Blocked and Visited arrays before the recursive call and added a heuristic. At the language level, I avoided two pitfalls: the Not operator and the Abs function, I replaced a division by a multiplication and I converted the Visited array to a SDA. Without these changes at the language level, my new algorithm would not have been very interesting. Look at the numbers with and without these optimizations:

SolveMaze_FLMAlgo Optimized(SDA) = 9.206 ms / Worst = 0.111 ms
SolveMaze_FLMAlgo Unoptimized(MDA,Not,Abs) = 21.602 ms / Worst = 0.297 ms​

So a good algorithm is not enough for performance, a good implementation is also very important.

General tips:
Optimization is a vast subject and it needs more than a tutorial (and more than a book) to be fully covered. So here are just a few general tips:

• Optimizing is not the thing to do last, to improve the existing code, as so many people think. It's something to consider at all steps of your development. Replacing an algorithm or a data structure at the end, for example, can be rather complicated, with a few unexpected consequences.
• Optimizing is not mandatory. From an user point of view, a function that runs in 60ms and a function that runs in 30ms provide exactly the same experience. You should feel concerned by optimization only when the level of performance is not acceptable enough on the slowest device that you target or when you face problems, e.g. an OutOfMemory error.
• Optimizing means testing (a lot). Never trust what you read and even what you think. Try. Something that is true in most cases can be totally wrong in your specific case.
• To help you make choices during the development, and to be able to evaluate a change in your code, it is important to have tools or functions to profile the speed of your code or the speed of your database queries, to know how much memory or battery is used, to simulate some scenarios (do I have enough memory when the worst case occurs? is the speed acceptable when all units are on screen?), etc.
• These libraries will help you profile your functions, implement a cache (an optimization mean overlooked by many developers) or know the memory available to your application: Cache, StrictMode, NanoTime.
• When you profile the speed of your code, don't forget that many things in the background can alter the execution duration of your code, e.g. the antivirus application or the garbage collector, so repeat the same test many times to get an average time.
• Give an explicit type to all variables and functions that return a value. Declaring MyNumber, for example, with "Dim MyNumber" or "Dim MyNumber = 8" is the best way to definitely kill the performance of your application.

Faster code:
The little project at the end of this tutorial shows how to replace the Not operator and a few math functions (Abs, Atan2, Division, Floor, Round, Max, Power) by faster variants. Note that there's no faster alternative for the Sqrt function but, as this function is commonly used to compute a distance, you don't need to apply it when you compare two distances.

 

[wonder]

Your tutorials are pure gold! Thank you so much, Fred!! Your knowledge and expertise is really appreciated!

 

[Informatix]

There was a bias in my benchmark so I retested everything with the new benchmark and updated the results. I also revised many things in the second post. There's still an unfinished final section (General tips) that I will do later.
I'd like to thank the people that contributed to the quiz, especially Cimperia that warned me about the Not operator.

 

[Informatix]

I just finished my tutorial. I added a little project at the end to show how to code faster variants of a few common math functions.

Note that NOT is slow in B4A because it is not converted to ! in Java (! in Java is as fast as "== false") and calls a Not() function. Maybe Erel will improve that some day.

 

[wonder]

Note that NOT is slow in B4A because it is not converted to ! in Java (! in Java is as fast as "== false") and calls a Not() function. Maybe Erel will improve that some day.

Looks like I have 108 "NOT" occurrences to restructure...

 

[wonder]

Hello Fred,

Regarding the final version of your code (seen below), could you provide us an implementation example?
I'm a little bit confused. Given the function return value (True|False), how would a game character move?

Sub SolveMaze_FLMAlgo_SDA As Boolean
   'Sets the initial state of the elements of the Visited array
   For Index = 0 To VisitedSDA.Length - 1
     VisitedSDA(Index) = False
   Next

   'Runs the recursive SDA algo
   DestIndex = DestX + (DestY * SizeX)
   InvSizeX = 1 / SizeX
   Return Recursive_FLMAlgo_SDA(StartX + (StartY * SizeX))
End Sub

Sub Recursive_FLMAlgo_SDA(Index As Int) As Boolean
   'Marks as visited
   VisitedSDA(Index) = True

   'If the goal is reached...
   If Index = DestIndex Then Return True

   'Computes the horizontal and vertical distances
   Dim Y As Int = Index * InvSizeX
   Dim X As Int = Index - (Y * SizeX)
   Dim DistX As Int = DestX - X
   Dim DistY As Int = DestY - Y

   'Selects the axis to follow
   Dim Horizontal As Boolean
   If DistX > 0 Then
     If DistY > 0 Then
       Horizontal = DistX > DistY
     Else
       Horizontal = DistX > -DistY
     End If
   Else
     If DistY > 0 Then
       Horizontal = -DistX > DistY
     Else
       Horizontal = -DistX > -DistY
     End If
   End If

   'Selects the next cell to visit
   Dim NewIndex As Int
   If Horizontal Then
     'The horizontal axis is explored first
     If DistX > 0 Then 'On the left -> to the right
       If X <> SizeX - 1 AND Blocked(X + 1, Y) = False Then
         NewIndex = Index + 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else 'On the right -> to the left
       If X <> 0 AND Blocked(X - 1, Y) = False Then
         NewIndex = Index - 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
     'Vertical axis
     If DistY > 0 Then 'Too low -> to the top
       If Y <> SizeY - 1 AND Blocked(X, Y + 1) = False Then
         NewIndex = Index + SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
       If Y <> 0 AND Blocked(X, Y - 1) = False Then
         NewIndex = Index - SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else 'Too high -> to the bottom
       If Y <> 0 AND Blocked(X, Y - 1) = False Then
         NewIndex = Index - SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
       If Y <> SizeY - 1 AND Blocked(X, Y + 1) = False Then
         NewIndex = Index + SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
     'Last possible direction
     If DistX > 0 Then
       If X <> 0 AND Blocked(X - 1, Y) = False Then
         NewIndex = Index - 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else
       If X <> SizeX - 1 AND Blocked(X + 1, Y) = False Then
         NewIndex = Index + 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
   Else
     'The vertical axis is explored first
     If DistY > 0 Then 'Too low -> to the top
       If Y <> SizeY - 1 AND Blocked(X, Y + 1) = False Then
         NewIndex = Index + SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else 'Too high -> to the bottom
       If Y <> 0 AND Blocked(X, Y - 1) = False Then
         NewIndex = Index - SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
     'Horizontal axis
     If DistX > 0 Then 'On the left -> to the right
       If X <> SizeX - 1 AND Blocked(X + 1, Y) = False Then
         NewIndex = Index + 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
       If X <> 0 AND Blocked(X - 1, Y) = False Then
         NewIndex = Index - 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else 'On the right -> to the left
       If X <> 0 AND Blocked(X - 1, Y) = False Then
         NewIndex = Index - 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
       If X <> SizeX - 1 AND Blocked(X + 1, Y) = False Then
         NewIndex = Index + 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
     'Last possible direction
     If DistY > 0 Then
       If Y <> 0 AND Blocked(X, Y - 1) = False Then
         NewIndex = Index - SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else
       If Y <> SizeY - 1 AND Blocked(X, Y + 1) = False Then
         NewIndex = Index + SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
   End If
   Return False
End Sub

 

[Informatix]

Hello Fred,

Regarding the final version of your code (seen below), could you provide us an implementation example?
I'm a little bit confused. Given the function return value (True|False), how would a game character move?

Sub SolveMaze_FLMAlgo_SDA As Boolean
   'Sets the initial state of the elements of the Visited array
   For Index = 0 To VisitedSDA.Length - 1
     VisitedSDA(Index) = False
   Next

   'Runs the recursive SDA algo
   DestIndex = DestX + (DestY * SizeX)
   InvSizeX = 1 / SizeX
   Return Recursive_FLMAlgo_SDA(StartX + (StartY * SizeX))
End Sub

Sub Recursive_FLMAlgo_SDA(Index As Int) As Boolean
   'Marks as visited
   VisitedSDA(Index) = True

   'If the goal is reached...
   If Index = DestIndex Then Return True

   'Computes the horizontal and vertical distances
   Dim Y As Int = Index * InvSizeX
   Dim X As Int = Index - (Y * SizeX)
   Dim DistX As Int = DestX - X
   Dim DistY As Int = DestY - Y

   'Selects the axis to follow
   Dim Horizontal As Boolean
   If DistX > 0 Then
     If DistY > 0 Then
       Horizontal = DistX > DistY
     Else
       Horizontal = DistX > -DistY
     End If
   Else
     If DistY > 0 Then
       Horizontal = -DistX > DistY
     Else
       Horizontal = -DistX > -DistY
     End If
   End If

   'Selects the next cell to visit
   Dim NewIndex As Int
   If Horizontal Then
     'The horizontal axis is explored first
     If DistX > 0 Then 'On the left -> to the right
       If X <> SizeX - 1 AND Blocked(X + 1, Y) = False Then
         NewIndex = Index + 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else 'On the right -> to the left
       If X <> 0 AND Blocked(X - 1, Y) = False Then
         NewIndex = Index - 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
     'Vertical axis
     If DistY > 0 Then 'Too low -> to the top
       If Y <> SizeY - 1 AND Blocked(X, Y + 1) = False Then
         NewIndex = Index + SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
       If Y <> 0 AND Blocked(X, Y - 1) = False Then
         NewIndex = Index - SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else 'Too high -> to the bottom
       If Y <> 0 AND Blocked(X, Y - 1) = False Then
         NewIndex = Index - SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
       If Y <> SizeY - 1 AND Blocked(X, Y + 1) = False Then
         NewIndex = Index + SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
     'Last possible direction
     If DistX > 0 Then
       If X <> 0 AND Blocked(X - 1, Y) = False Then
         NewIndex = Index - 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else
       If X <> SizeX - 1 AND Blocked(X + 1, Y) = False Then
         NewIndex = Index + 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
   Else
     'The vertical axis is explored first
     If DistY > 0 Then 'Too low -> to the top
       If Y <> SizeY - 1 AND Blocked(X, Y + 1) = False Then
         NewIndex = Index + SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else 'Too high -> to the bottom
       If Y <> 0 AND Blocked(X, Y - 1) = False Then
         NewIndex = Index - SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
     'Horizontal axis
     If DistX > 0 Then 'On the left -> to the right
       If X <> SizeX - 1 AND Blocked(X + 1, Y) = False Then
         NewIndex = Index + 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
       If X <> 0 AND Blocked(X - 1, Y) = False Then
         NewIndex = Index - 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else 'On the right -> to the left
       If X <> 0 AND Blocked(X - 1, Y) = False Then
         NewIndex = Index - 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
       If X <> SizeX - 1 AND Blocked(X + 1, Y) = False Then
         NewIndex = Index + 1
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
     'Last possible direction
     If DistY > 0 Then
       If Y <> 0 AND Blocked(X, Y - 1) = False Then
         NewIndex = Index - SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     Else
       If Y <> SizeY - 1 AND Blocked(X, Y + 1) = False Then
         NewIndex = Index + SizeX
         If VisitedSDA(NewIndex) = False AND Recursive_FLMAlgo_SDA(NewIndex) Then
           Return True
         End If
       End If
     End If
   End If
   Return False
End Sub

It's explained in the tutorial:

I can remove the CorrectPath array as I don't need to store the path. Why? Because I need an answer only to these two questions: is there an alternate path? If no, the unit is really blocked. If yes, what's the next move to engage the unit on this path? As the obstacles position can change after each computation, it's useless to store a path. Only the first move has some interest and there's a trick to know where to do this first step without ambiguity: taking the destination as the starting point. The DFS algorithm stops as soon as it reaches the end so there's only one path reaching the end, i.e. the current location of the unit as the search direction is reversed.

Around your starting position, VisitedSDA can have only one value set to True. It's where to move.

Happy new year 2016 !

 

[Jose57]

Really a very good article. One of the finest viewed in the forum.
I have always appreciated your work. Thanks for sharing

 

[wonder]

Using Visual Studio 2015, with Informatix's permission, I rewrote the the SDA_Algo in C++.
100 000 mazes solved in 20 seconds (Core i7)!!
Fred, you're the best!!!!


Here it is, compiled as a B4A library:
https://www.b4x.com/android/forum/threads/mazesolver-c-path-finding-algorithm.61998/

 

[wonder]

That being said, the iterative variant is your only option if you want to get rid of the StackOverflow error which is the main drawback of recursive functions. In my game, the grid is too small to raise the error on most devices and I set a limit in the final code to stop after a certain recursion depth so I'm not concerned.

So, if you reach maximum recursion depth, what happens to the game character's behavior? Will he just stand still?
What's the maximum recursion depth you're using and how did you find such value?

Many thanks in advance, as always!

 

[Informatix]

So, if you reach maximum recursion depth, what happens to the game character's behavior? Will he just stand still?
What's the maximum recursion depth you're using and how did you find such value?

Many thanks in advance, as always!

The character does not move indeed and waits until a straighter path is available.
In Diktatour, I did no set a maximum recursion depth but a maximum number of visited cells. I had to put this limit as my grids can be of variable size. I found the maximum value (70) by testing on all my devices. The value found was around 80, but I preferred to lower it to be safe.