Android Question Quiz "Is there a path ?"

[Informatix]

Hello,

I'd like to submit a quiz to the fellow members of this forum:
In a grid of 20x20, that you can see as a graph where each cell is connected to the four adjacent cells (no diagonals), there's a certain amount of blocked cells that creates a maze (or an empty crosswords grid). Your algorithm has to determine if there's a path between 2 cells of this grid (2 nodes of this graph).
The goal is to write the fastest algorithm and to beat mine. It's more a quiz about optimization with B4A than a quiz about algorithms (you should quickly find with Google a suitable algorithm for this). And the path has not to be the shortest one nor stored for a later use (only the answer to the question matters).

I'll give an answer of course and I'll explain my own code if there are participants to this quiz. Note that's not complicated at all and if you write more than 100 lines of code, you're probably doing something too complex and too slow. Simplicity is the key. No external library is allowed.

I join to this post a B4A project that you can use to create the maze and benchmark your attempts. It uses the NanoTime library to time your code (because DateTime.now is not accurate enough; 1 millisecond is too much ).
I will compare all submitted algo to my own algo ASAP.

Example of solution found in 0.09 ms on a Moto G (SS is the starting cell and DD the destination):

XX..XX............XXXX....XX......XX..XX
XXXXXX....XX......XX........XX......XX..
XX....XX..XXXXXX........DDXX....XXXX....
..XX....XXXX....XX......[][]XX..XX......
XX..XXXX....XXXX....XXXX..[]..XXXXXXXX..
..XX..XX..XX..XXXX..XX..XX[]XXXX........
....XX......XX......XXXX[][]..XX..XX..XX
......XX............XX[][]......XX......
..XXXX..XXXXXX....XX[][]..XXXX..XX......
XX..XX........XXXX[][]XX..........XX..XX
................[][]....XXXX..XX........
XX..XXXXXXXX....[]..XX..XX......XXXXXX..
..XX............[]XX......XX..XXXX......
XXXXXXXXXXXXXXXX[][]XXXXXXXX..XX..XX....
......XX..........[]..........XXXX..XXXX
XXXXXX..XX..XX....[]XX..XX..XX..........
XX......XX........[]XXXX........XXXX....
..XX........XXXXXXSSXXXX..XX....XXXX....
..XX....XX..XXXX......XXXX..XX....XX....
XX........XX......XX..XX..XX............

 

[Informatix]

Yep, it will, as it will fill all paths equally fast, so the destination is found with the shortest path.

Absolutely not or you're thinking to another algorithm that the one you posted. Here's what a DFS can return:

Recursion depth when destination found=26:
..............XX....XXXX[][]XXXXXX[][][]
........XX......XXXX..XX[][][]XX[]XX[][]
....XX....XXXX....XXXX[]XX[]XXXX[][][][]
..XXXX....XX....XX..XX[][][][]XXXX[][][]
..XX....XX......XXXX[][]XX[][][]XX[][][]
XX....XXXXXXXXXX[][][]XX[][][]XXXX[][][]
..............XX[][][][]XX[][][]XX[][][]
......XX....XX[][][]XX[][][][]XX[][]XX[]
....XX....XXXXXXXX[]XXXX[][][][][][][][]
..........XXXXXX[][][][]XX[]XX[][][][]XX
......XXXX....XX[][][]XX[]XX[]XX[][][]XX
......XX..XXXX[][]XX[][][]XX[][][][]XX..
XX......XX[][][]XX..XX[][][]XXXX[][]XX..
....XX..XXXXXX[][]XXXX[][][][]XX[][][]XX
..XXXX..XX....[][][][]XXXXXX[]XX[]XXXX..
..XXXX......XX[][][][]XX..XX[][][][]XX..
..........XXXX[][][][][]DDXX[][][][][]XX
....XX..XX..SS[][][][][]XX[][]XX[][][][]
XXXXXX....XX[][][][][]XX[][][][]XX[]XXXX
..XX........XXXX[]XX[][]XX[][][][][]XX..

Shortest path=7:
..............XX....XXXX....XXXXXX......
........XX......XXXX..XX......XX..XX....
....XX....XXXX....XXXX..XX..XXXX........
..XXXX....XX....XX..XX........XXXX......
..XX....XX......XXXX....XX......XX......
XX....XXXXXXXXXX......XX......XXXX......
..............XX........XX......XX......
......XX....XX......XX........XX....XX..
....XX....XXXXXXXX..XXXX................
..........XXXXXX........XX..XX........XX
......XXXX....XX......XX..XX..XX......XX
......XX..XXXX....XX......XX........XX..
XX......XX......XX..XX......XXXX....XX..
....XX..XXXXXX....XXXX........XX......XX
..XXXX..XX............XXXXXX..XX..XXXX..
..XXXX......XX........XX..XX........XX..
..........XXXX........[]DDXX..........XX
....XX..XX..SS[][][][][]XX....XX........
XXXXXX....XX..........XX........XX..XXXX
..XX........XXXX..XX....XX..........XX..

The DFS algo is not known to return the shortest path. A* or JPS are better alternatives for this.

 

[Informatix]

more importantly, being recursive, will probably break the stack on larger maps.

Yes, that's why I limited the grid to 20x20 in my first post. That should not raise a Stack Overflow with a well-written recursive routine.

Still, it's probably the simplest solution to write and understand.

This DFS algorithm is at the heart of mine. Simple and fast. But can be a lot faster with a heuristic to keep the search oriented to the goal. And even faster by writing it in a proper way.

 

[Troberg]

Absolutely not or you're thinking to another algorithm that the one you posted.

Correct. I was tired and didn't Think it through. If I made it tail recursive, my comment would be true, but, as it stands, it's not.

 

[Informatix]

I think it is quite optimal for such "crowded" arrays. Not sure what would happen if there is a higher obstacle density

I wrote the algorithm for a real game where the space is very crowded, with only a few cells left to move.

 

[RandomCoder]

You have plenty of algorithms to find the shortest path, but the length of the path is not a requirement here. You can do simpler things. The drawback of many algorithms is their preparation time (creating a graph that allows the main function to run very quickly). So "simplicity is the key". My code is easy to read and does not require any particular mathematical knowledge.

Knowing that the problem is not purely a mathematical one has inspired me. I'll have to try some basic logic tonight then see if I can then tune it to home in on the destination.

 

[cimperia]

It seems that your algo priorizes the search towards the direction which is nearest to the vector between the current point and DD (in other words, the direction which minimizes the highest dx,dy component of the distance vector)

Exact. I use a heuristic to orient the search.

I might give it a try this WE - but building on this idea, I was thinking of adding a one step look-ahead so that instead of applying the rule above rigidly (choosing to reduce the Y or X distance depending on which is the highest), the algo would choose the cell which has the highest onwards (towards the target) moves, i.e the cell which has the highest free nodes.

 

[JordiCP]

I might give it a try this WE - but building on this idea, I was thinking of adding a one step look-ahead so that instead of applying the rule above rigidly (choosing to reduce the Y or X distance depending on which is the highest), the algo would choose the cell which has the highest onwards (towards the target) moves, i.e the cell which has the highest free nodes.

I think that all variants which converge in a reduction of dx,dy components will behave quite similarly. Of course there will always be specific random scenarios which will be better for one and worse for the other.

Perhaps the performance differences between them can be found in the mean number of checks that are to be done on each step. The lesser, the faster (assuming the same "optimality" in their implementations)

 

[Troberg]

One also has to remember that determining the smartest way to test the path can sometimes be more costly, time wise, than simply going with the simple solution and test in all directions.

I'm not saying that it's like this here (haven't tested it), but, as testing if a square is passable or not is an extremely "cheap" operation, any optimization similarly has to be even "cheaper" in order to give a net gain. Sometimes the logic behind "smart" optimizations is so heavy that there is a net loss of performance.

Just something to watch out for.

 

[cimperia]

@Informatix

I had a quick look at the BA4 QuizProject.

I need some clarification:

1. The comments within the code seem to preclude the use of a recursive solution as it is not possible to code a function outside the loop, am I right?
2. Are we constrained to use the double dimensional arrays of booleans?

 

[Informatix]

The comments within the code seem to preclude the use of a recursive solution as it is not possible to code a function outside the loop, am I right?

You can call as many functions as you want. It's just that you have to call them from inside the loop.

Are we constrained to use the double dimensional arrays of booleans?

Yes, but you can create another data structure, more convenient for your algorithm, inside the loop. As you can notice, I create two sections inside the loop: one for the creation of a grid/graph and another for the algorithm that uses this grid/graph.

 

[RandomCoder]

Thought it kind of relevant

 

[RandomCoder]

So far I have succeeded in creating a fast algorithm that doesn't work! Unless of course I've been really unlucky and the dozen times I've tested it have actually been on grids that are impassable. Oh well, maybe tomorrow will yield a better result after some shut eye?

 

[Informatix]

To help you starting with a working code, I added to the quiz project an implementation of the DFS algorithm, with a function to create a visual representation of the result (won't be very useful with B4A v5 because of the font used for the log).

EDIT: after testing on a long series of various grids, I saw that my algo is "only" 2x faster than the basic DFS (it's an average, sometimes it is 10 times faster). I'm quite sure it can be beaten and I'll be glad if that happens.

EDIT2: it is possible to implement the DFS without any recursion but it's a lot slower (contrary to what the litterature says on the subject) and requires a specialized data structure, e.g. the ArrayDeque only available in my DataCollection library, which is considered as the best choice for this.

 

[cimperia]

Thanks Informatix.

This is nearly identical to my implementation, no wonder there. The only difference is that my grid is walled up, ie the original array is surrounded by a wall of blocked cells (True). This makes the array 2 rows higher and 2 columns wider. The advantage, from a programming point of view, is that the limits/edges checks are not required as going beyond the edge of the original array hits a wall.

It simplifies the implementation:

Sub Move (x As Int, y As Int) As Boolean 
     counter = counter + 1
 
     'Accept Case - we found the Exit
     If x = DestXX And y = DestYY Then Return True
 
     'Reject Case - we hit a wall Or our path
     If maze2(x, y) Then Return False
 
     ' Backtracking Move  
     ' Mark this location As part of our path
     maze2(x, y) = True
 
     'Try To go South
     If Move(x, y+1) Then Return True     
     
     'Try To go East
     If Move(x+1, y) Then Return True
         
     'Try To go West
     If Move(x-1, y) Then Return True
     
     'Try To go North
     If Move(x, y-1) Then Return True
         
     'Deadend - this location can't be part of the solution
 
     'Unmark this location
     maze2(x, y) = False
 
     'Go back
     Return False
End Sub

I'll compare with your "default" implementation to see whether there's any performance again or whether it's just syntactic sugar.
I also keep track of how many moves are required.

 

[RandomCoder]

@Informatics
That is some tight code

If you copy and paste the Log into notepad it displays perfectly thanks to the fixed pitch font. Due to the difficulties I've been having I had already created my own print routine...

Sub Print()
    Dim str, bln As String
    For X = 0 To SizeX - 1
        For Y = 0 To SizeY - 1
            If X = StartX And Y = StartY Then
                bln = "S"
            Else If X = DestX And Y = DestY Then
                bln = "D"
            Else
                If Grid(X, Y) = True Then
                    If Blocked(X, Y) = False Then
                        bln = ".0"
                    Else
                        bln = " 1"
                    End If
                Else
                    bln = " 0"
                End If
            End If
            str = str & "  " & bln
        Next
        str = str & CRLF
    Next
    Log(str & CRLF & ".." & CRLF)
End Sub

The Grid array is similar to your Visited array, although it also contains a copy of the blocked cells because I use it within my algorithm. The actual path is being stored in a list to be recalled later. I think that maybe I will change this now. And here's where my algo' manages to reach (displays better in the Log window)...

IMPASSABLE
Result...
0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0
0 0 0 1 0 1 0 1 0 1 1 0 0 0 0 0 1 1 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 1 1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 1 1
0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1
1 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 0
1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 1 1 0
0 0 D 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1
1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1
0 1 .0 .0 .0 1 0 1 0 1 1 1 1 1 1 0 0 0 0 0
0 1 .0 .0 .0 1 1 1 0 1 0 1 1 0 0 0 0 1 0 1
0 1 .0 1 0 0 0 0 1 1 0 1 0 0 1 1 0 1 0 0
0 .0 .0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1
1 .0 S 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0
0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 1 0 1 1 1 1 0 1 1 0 0 0
0 0 1 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 0 1
1 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0
0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 1
..
Avg. time for Algo=7.71911621 ms
** Activity (main) Pause, UserClosed = true **

Now I'm going to have to step it through and identify where the problem is then try to optimise it without breaking it again

 

[Informatix]

The only difference is that my grid is walled up, ie the original array is surrounded by a wall of blocked cells (True). This makes the array 2 rows higher and 2 columns wider. The advantage, from a programming point of view, is that the limits/edges checks are not required as going beyond the edge of the original array hits a wall.

I didn't think doing this so it may be an interesting lead.

 

[Informatix]

The actual path is being stored in a list to be recalled later.

It's probably an important cause of slowdown. It's not required for the quiz (nor for a real implementation in a game. In most cases, the path will be re-computed every move to take into account all grid modifications: other sprites moving, doors opening or closing, walls destroyed, etc., so storing this path in a dynamic environment is useless).
Little trick with a search oriented by a heuristic to know where to move after a path is found: start the search from the destination. If the starting cell is not visited = no path; if it is visited, the visited cell around it, which is single, indicates where to move. This trick does not work with the basic DFS.

 

[RandomCoder]

It's probably an important cause of slowdown. It's not required for the quiz (nor for a real implementation in a game. In most cases, the path will be re-computed every move to take into account all grid modifications: other sprites moving, doors opening or closing, walls destroyed, etc., so storing this path in a dynamic environment is useless).
Little trick with a search oriented by a heuristic to know where to move after a path is found: start the search from the destination. If the starting cell is not visited = no path; if it is visited, the visited cell around it, which is single, indicates where to move. This trick does not work with the basic DFS.

I can pretty much guarantee that any solution I come up with won't be the fastest, but it's an interesting problem to solve and I like little puzzles like this. I've got my algorithm working now but it needs smartening up a lot. I'm checking all 4 cells around the point at which the current position exists and moving into the next cell which is potentially closest to the destination, I also store the location if other options were possible (although I do not navigate these yet). I continue this loop until a dead end is found. I then select that last location that had alternative routes and try that instead and so on etc.
I currently have two issues to resolve...

1. It sometimes chooses to go in the opposite direction because I use Abs(distance) to determine how far away and make a decision which is the shortest route. But it's not very smart to head away from the destination
2. Instead of selecting the last route with alternative paths it would be better to look at each alternative and choose the one that was again closest to the destination, otherwise its just back filling a dead end that had several other dead ends from it. (if that makes sense)

Anyway you know all this, I'm just thinking out loud. Got some jobs to do now but I'll have another crack at it later. I'm pretty happy that I appear to have a working solution. I've also found a problem with the Rapid debugger in that it fails to compile my App, yet it will happily compile in Release or Legacy Debug mode? It's probably something I'm doing wrong and I'll make a new post once I submit my solution.

PS. Nice quiz idea, we could do with more of these to spur interest in B4A, and to help share different coding methods. I don't expect to find the fastest solution but I do expect that I will learn a lot!

 

[Informatix]

I can pretty much guarantee that any solution I come up with won't be the fastest, but it's an interesting problem to solve and I like little puzzles like this. I've got my algorithm working now but it needs smartening up a lot. I'm checking all 4 cells around the point at which the current position exists and moving into the next cell which is potentially closest to the destination, I also store the location if other options were possible (although I do not navigate these yet). I continue this loop until a dead end is found. I then select that last location that had alternative routes and try that instead and so on etc.

Many researchers did that before us and that's why there's plenty of algorithms available (Best-First, IDA*, BFS, DFS, DFS Br.&Bd., IDDFS, A*, JPS, HPA*, etc.). But most of the time there's no source code provided with their academic paper, only pseudo-code, and coding in a specific language is not really taken into account (they consider, and that's usually true, that optimizing at the algorithm level is better than doing it at the code/language level) while that can make a huge difference; I will prove this point later. I promise a very surprising ending to this quiz.

I use Abs(distance)

I didn't check whether Abs performs quickly in Java, but in other languages, it's often better to use a branching (if a > b then c = a - b else c = b - a) than Abs when you need performance.

PS. Nice quiz idea, we could do with more of these to spur interest in B4A, and to help share different coding methods. I don't expect to find the fastest solution but I do expect that I will learn a lot!

Yes , I'd like to see more too.
Thanks for participating to this one. The goal is not to prove any superiority (any developer with years of experience in IA would succeed in beating my algo for sure), it is a way to teach/learn something interesting. If I described my algo right from the start, people wouldn't search something different that could be better.

 

[cimperia]

I have done some work on the data structure to see whether it was possible to gain some time just on that score, and it seems it's possible.

Here's an excerpt of the log generated while running the app. I just show the 2 first results as they are representative of the results I usually get.

Two Start and End cells have been tested. 4 algorithms are run for the same conditions.
1. DFS Which is the basic DFS algorithm to baseline the results.
2. DFSW but using an array walled up by blocked cells. The array can conceptually be seen as an inner array (Blocked(,) if you want) and an outer array, ie the wall.
3. My Algo, an implementation of DFS with a walled array (as in 2)
4. AlgoSDA, AN implementation of DFS with a single dimensional array

It can be seen that it's the same algorithm as the number of visited cells are identical in each case.
I was expecting some performance gain with the walled array, but there were not. However the implementation with a Single Dimensional Array seems to genuinely enhance the processing speed.

NOW, I need to move from the blind DFS implementation to a heuristic based search.

EDIT - I have posted the whole log as it is not that big.

Start: 1000 iterations
--------------------------------------------------------------------------------------
  Start Cell: 8:2
  End  Cell: 11:17
------------------------------------------------
Avg. time for DFS=  0.116035847 ms
Path NOT Found in 445 Recursive Calls
Visited=183
-
---
Avg. time for DFSW=  0.115073693 ms
Path NOT Found in 445 Recursive Calls
Visited=183
-
---
Avg. time for My Algo=0.119594616 ms
Path NOT Found in 445 Recursive Calls
Visited=183
-
---
Avg. time for AlgoSDA=0.108019307 ms
Path NOT Found in 445 Recursive Calls
Visited=183
-
--------------------------------------------------------------------------------------
  Start Cell: 11:2
  End  Cell: 4:16
------------------------------------------------
Avg. time for DFS=  0.082568077 ms
Path Found in : 346 Recursive Calls
Visited=127
-
---
Avg. time for DFSW=  0.08384907700000001 ms
Path Found in : 346 Recursive Calls
Visited=127
-
---
Avg. time for My Algo=0.069210615 ms
Path Found in : 264 Recursive Calls
Visited=127
-
---
Avg. time for AlgoSDA=0.060480384 ms
Path Found in : 264 Recursive Calls
Visited=127
-
--------------------------------------------------------------------------------------
  Start Cell: 8:2
  End  Cell: 14:15
------------------------------------------------
Avg. time for DFS=  0.127867231 ms
Path Found in : 549 Recursive Calls
Visited=209
-
---
Avg. time for DFSW=  0.129814154 ms
Path Found in : 549 Recursive Calls
Visited=209
-
---
Avg. time for My Algo=0.119580538 ms
Path Found in : 470 Recursive Calls
Visited=209
-
---
Avg. time for AlgoSDA=0.10685338400000001 ms
Path Found in : 470 Recursive Calls
Visited=209
-
--------------------------------------------------------------------------------------
  Start Cell: 8:2
  End  Cell: 14:14
------------------------------------------------
Avg. time for DFS=  0.029954616000000003 ms
Path Found in : 115 Recursive Calls
Visited=41
-
---
Avg. time for DFSW=  0.031240462 ms
Path Found in : 115 Recursive Calls
Visited=41
-
---
Avg. time for My Algo=0.020940308 ms
Path Found in : 57 Recursive Calls
Visited=41
-
---
Avg. time for AlgoSDA=0.016404846 ms
Path Found in : 57 Recursive Calls
Visited=41
-
--------------------------------------------------------------------------------------
  Start Cell: 8:2
  End  Cell: 14:13
------------------------------------------------
Avg. time for DFS=  0.144274462 ms
Path NOT Found in 593 Recursive Calls
Visited=225
-
---
Avg. time for DFSW=  0.143915538 ms
Path NOT Found in 593 Recursive Calls
Visited=225
-
---
Avg. time for My Algo=0.147871538 ms
Path NOT Found in 593 Recursive Calls
Visited=225
-
---
Avg. time for AlgoSDA=0.132483846 ms
Path NOT Found in 593 Recursive Calls
Visited=225
-
--------------------------------------------------------------------------------------
  Start Cell: 11:2
  End  Cell: 6:12
------------------------------------------------
Avg. time for DFS=  0.08467930800000001 ms
Path Found in : 360 Recursive Calls
Visited=134
-
---
Avg. time for DFSW=  0.08680338400000001 ms
Path Found in : 360 Recursive Calls
Visited=134
-
---
Avg. time for My Algo=0.069544307 ms
Path Found in : 263 Recursive Calls
Visited=134
-
---
Avg. time for AlgoSDA=0.060774 ms
Path Found in : 263 Recursive Calls
Visited=134
-
--------------------------------------------------------------------------------------
  Start Cell: 8:2
  End  Cell: 14:11
------------------------------------------------
Avg. time for DFS=  0.052570692 ms
Path Found in : 223 Recursive Calls
Visited=78
-
---
Avg. time for DFSW=  0.053792846 ms
Path Found in : 223 Recursive Calls
Visited=78
-
---
Avg. time for My Algo=0.043947769 ms
Path Found in : 161 Recursive Calls
Visited=78
-
---
Avg. time for AlgoSDA=0.038236538 ms
Path Found in : 161 Recursive Calls
Visited=78
-
--------------------------------------------------------------------------------------
  Start Cell: 4:2
  End  Cell: 8:10
------------------------------------------------
Avg. time for DFS=  0.071398615 ms
Path Found in : 314 Recursive Calls
Visited=110
-
---
Avg. time for DFSW=  0.07200815399999999 ms
Path Found in : 314 Recursive Calls
Visited=110
-
---
Avg. time for My Algo=0.052668614999999995 ms
Path Found in : 196 Recursive Calls
Visited=110
-
---
Avg. time for AlgoSDA=0.044520461000000004 ms
Path Found in : 196 Recursive Calls
Visited=110
-
--------------------------------------------------------------------------------------
  Start Cell: 9:2
  End  Cell: 12:9
------------------------------------------------
Avg. time for DFS=  0.108300923 ms
Path Found in : 489 Recursive Calls
Visited=172
-
---
Avg. time for DFSW=  0.109949769 ms
Path Found in : 489 Recursive Calls
Visited=172
-
---
Avg. time for My Algo=0.08841884600000001 ms
Path Found in : 350 Recursive Calls
Visited=172
-
---
Avg. time for AlgoSDA=0.07753846099999999 ms
Path Found in : 350 Recursive Calls
Visited=172
-
--------------------------------------------------------------------------------------
  Start Cell: 15:2
  End  Cell: 11:8
------------------------------------------------
Avg. time for DFS=  0.054842769 ms
Path NOT Found in 203 Recursive Calls
Visited=81
-
---
Avg. time for DFSW=  0.056564692 ms
Path NOT Found in 203 Recursive Calls
Visited=81
-
---
Avg. time for My Algo=0.057898307 ms
Path NOT Found in 203 Recursive Calls
Visited=81
-
---
Avg. time for AlgoSDA=0.050103154000000004 ms
Path NOT Found in 203 Recursive Calls
Visited=81
-
--------------------------------------------------------------------------------------
  Start Cell: 7:2
  End  Cell: 13:7
------------------------------------------------
Avg. time for DFS=  0.057521231 ms
Path Found in : 246 Recursive Calls
Visited=87
-
---
Avg. time for DFSW=  0.059841693 ms
Path Found in : 246 Recursive Calls
Visited=87
-
---
Avg. time for My Algo=0.051194538 ms
Path Found in : 187 Recursive Calls
Visited=87
-
---
Avg. time for AlgoSDA=0.043531307 ms
Path Found in : 187 Recursive Calls
Visited=87
-
--------------------------------------------------------------------------------------
  Start Cell: 5:2
  End  Cell: 6:6
------------------------------------------------
Avg. time for DFS=  0.018907539 ms
Path Found in : 53 Recursive Calls
Visited=23
-
---
Avg. time for DFSW=  0.020014923 ms
Path Found in : 53 Recursive Calls
Visited=23
-
---
Avg. time for My Algo=0.019745077 ms
Path Found in : 36 Recursive Calls
Visited=23
-
---
Avg. time for AlgoSDA=0.012935923 ms
Path Found in : 36 Recursive Calls
Visited=23
-
--------------------------------------------------------------------------------------
  Start Cell: 4:2
  End  Cell: 8:5
------------------------------------------------
Avg. time for DFS=  0.14150515400000002 ms
Path Found in : 638 Recursive Calls
Visited=232
-
---
Avg. time for DFSW=  0.144274615 ms
Path Found in : 638 Recursive Calls
Visited=232
-
---
Avg. time for My Algo=0.118593615 ms
Path Found in : 482 Recursive Calls
Visited=232
-
---
Avg. time for AlgoSDA=0.10537476900000001 ms
Path Found in : 482 Recursive Calls
Visited=232
-
--------------------------------------------------------------------------------------
  Start Cell: 5:2
  End  Cell: 12:4
------------------------------------------------
Avg. time for DFS=  0.11937584600000001 ms
Path Found in : 509 Recursive Calls
Visited=189
-
---
Avg. time for DFSW=  0.120386154 ms
Path Found in : 509 Recursive Calls
Visited=189
-
---
Avg. time for My Algo=0.111638308 ms
Path Found in : 438 Recursive Calls
Visited=189
-
---
Avg. time for AlgoSDA=0.09947330800000001 ms
Path Found in : 438 Recursive Calls
Visited=189
-
--------------------------------------------------------------------------------------
  Start Cell: 5:2
  End  Cell: 6:3
------------------------------------------------
Avg. time for DFS=  0.12777192299999998 ms
Path Found in : 541 Recursive Calls
Visited=205
-
---
Avg. time for DFSW=  0.129224231 ms
Path Found in : 541 Recursive Calls
Visited=205
-
---
Avg. time for My Algo=0.12222546199999999 ms
Path Found in : 486 Recursive Calls
Visited=205
-
---
Avg. time for AlgoSDA=0.109155231 ms
Path Found in : 486 Recursive Calls
Visited=205
-
--------------------------------------------------------------------------------------
  Start Cell: 13:2
  End  Cell: 7:2
------------------------------------------------
Avg. time for DFS=  0.024930692 ms
Path Found in : 88 Recursive Calls
Visited=33
-
---
Avg. time for DFSW=  0.026801615 ms
Path Found in : 88 Recursive Calls
Visited=33
-
---
Avg. time for My Algo=0.020829 ms
Path Found in : 58 Recursive Calls
Visited=33
-
---
Avg. time for AlgoSDA=0.016760615000000003 ms
Path Found in : 58 Recursive Calls
Visited=33
-
End