Android Question Quiz "Is there a path ?"

Informatix · Aug 12, 2015

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

B4X:

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 · Aug 15, 2015

cimperia said:
I was expecting some performance gain with the walled array, but there were not.

What you gain by avoiding unnecessary checks on the bounds is probably lost by creating your array with a shifted index.

cimperia said:

When you see a difference after the second decimal (0.0575 vs 0.0598), it is not significant and you can ignore it. Run the same algorithm twice on the same maze and you'll see differences after this second decimal that can be as important as the result above. There are a few things running on your phone, including the garbage collector, that alter the timing. That's why the benchmark in my project repeats at least 100 times the same search to minimize the influence of external factors. What's important is to see if an algorithm beats the other algorithms in almost all cases, like your SDA algo does.

sorex · Aug 16, 2015

I didn't see this post till now.

Is this only path searching for the given example grid in post 1?

RandomCoder · Aug 16, 2015

sorex said:
I didn't see this post till now.

Is this only path searching for the given example grid in post 1?

No, if you download the file or preferably the second example that informatix posted you will see that it is a randomly created 20x20 grid. Solving the puzzle from start to finish points is pretty straight forward, and sometimes there is no possible route. Doing it fast is proving tricky.

sorex · Aug 16, 2015

ok, I'll give it some thinkering.

I have one question tho...

What is the point of the division by loop count R here?

B4X:

        Dim Result As Double = (Nano.NanoTime - t) / R / 1000000

RandomCoder · Aug 16, 2015

It repeats the same maze 100 times to average the result which is in ms. This gives a more repeatable estimate of the time it takes to perform the task due to moments where the phone may have other background tasks such as garbage collector running.

sorex · Aug 16, 2015

it's indeed quite annoying to correctly meassure something on Android, a routine that is 2-4 times faster is on some runs suddenly 2 times slower than the other one.
this happends on real hardware and genymotion.

RandomCoder · Aug 16, 2015

I've finally got my algorithm to work. But as expected, its pig slow by comparison to the bog standard DFS

I've tied myself in knots several times trying to get this to work but at least now I seem to have something I can try to optimise. Here's a peek at some of the mazes its solved....

B4X:

** Activity (main) Create, isFirst = true **
** Activity (main) Resume **
-----
Avg. time for DFS=0.05126954 ms
    0   0   0   1   0   0  .0  .0  .0  .0  .0  .0  .0  .0  .0   1  .0  .0   0   0
    1   0   0   1   0   1  .0   1  .0   1  .0  .0   1  .0  .0  .0  .0  .0  .0   0
    0   1   0  .0  .0   0  .0  .0   1   0  .0  .0   1  .0  .0  .0   1   1  .0   0
    0   1   1  .0  .0   0   1  .0   1   1  .0   1  .0  .0  .0   1   0   0  .0   1
    1   1   0  .0  .0   1   1  .0   1   0   1  .0  .0  .0  .0   0   0   .D  .0  .0
    0   1   S  .0  .0  .0  .0  .0   0   1   0   1  .0  .0   1   0   0   1  .0  .0
    1  .0  .0  .0   1   1  .0  .0   1   1   1   0   1   1   0   0   0   1  .0  .0
   .0  .0  .0   1   1  .0  .0   1   0   0   1   1   1   0   1   1   1   1  .0  .0
   .0   1  .0  .0  .0   1   1   1   1   0   1  .0   1   0   0   1   0   0   1  .0
   .0  .0   1  .0   1   1   1   1   0   1  .0  .0  .0   1   1   0   1   1  .0  .0
   .0   1  .0  .0  .0  .0   1  .0   1  .0   1  .0  .0  .0  .0   1   0   1   1  .0
   .0   1  .0  .0  .0   1   1  .0  .0  .0  .0  .0  .0  .0  .0  .0   1   1   1   1
    1   1  .0  .0  .0  .0  .0   1  .0  .0   1   1  .0  .0  .0  .0  .0  .0  .0  .0
    0   1   1  .0  .0   1  .0  .0  .0  .0  .0  .0  .0   1  .0   1   1  .0   1   1
    1   1  .0  .0   1  .0  .0   1  .0  .0   1  .0  .0  .0   1  .0  .0   1   0   0
   .0  .0  .0   1  .0  .0  .0  .0   1   1  .0  .0   1  .0  .0  .0  .0  .0   1   1
   .0  .0  .0  .0   1   1  .0   1  .0  .0  .0   1  .0  .0  .0  .0  .0  .0  .0  .0
   .0  .0  .0  .0  .0   1   1  .0   1  .0  .0  .0  .0   1  .0  .0   1   1   1  .0
   .0   1   1   1  .0   1   1  .0  .0  .0  .0  .0  .0   1  .0  .0   1   0   0   1
   .0  .0   1   0   1  .0  .0  .0  .0   1  .0   1  .0   1   1   1   1   1   0   0
Visited=210
-
Avg. time for your algo=0.67474364 ms
   0   0   0   1   0   0  .0  .0  .0  .0  .0  .0  .0  .0  .0   1   0   0   0   0
   1   0   0   1   0   1  .0   1   0   1   0   0   1   0  .0  .0   0   0   0   0
   0   1   0   0   0   0  .0  .0   1   0   0   0   1   0  .0  .0   1   1   0   0
   0   1   1   0   0   0   1  .0   1   1   0   1   0   0  .0   1   0   0   0   1
   1   1   0   0   0   1   1  .0   1   0   1   0   0   0  .0  .0  .0  .D   0   0
   0   1  .S  .0  .0  .0  .0  .0  .0   1   0   1   0   0   1   0   0   1   0   0
   1   0   0   0   1   1   0   0   1   1   1   0   1   1   0   0   0   1   0   0
   0   0   0   1   1   0   0   1   0   0   1   1   1   0   1   1   1   1   0   0
   0   1   0   0   0   1   1   1   1   0   1   0   1   0   0   1   0   0   1   0
   0   0   1   0   1   1   1   1   0   1   0   0   0   1   1   0   1   1   0   0
   0   1   0   0   0   0   1   0   1   0   1   0   0   0   0   1   0   1   1   0
   0   1   0   0   0   1   1   0   0   0   0   0   0   0   0   0   1   1   1   1
   1   1   0   0   0   0   0   1   0   0   1   1   0   0   0   0   0   0   0   0
   0   1   1   0   0   1   0   0   0   0   0   0   0   1   0   1   1   0   1   1
   1   1   0   0   1   0   0   1   0   0   1   0   0   0   1   0   0   1   0   0
   0   0   0   1   0   0   0   0   1   1   0   0   1   0   0   0   0   0   1   1
   0   0   0   0   1   1   0   1   0   0   0   1   0   0   0   0   0   0   0   0
   0   0   0   0   0   1   1   0   1   0   0   0   0   1   0   0   1   1   1   0
   0   1   1   1   0   1   1   0   0   0   0   0   0   1   0   0   1   0   0   1
   0   0   1   0   1   0   0   0   0   1   0   1   0   1   1   1   1   1   0   0
..
Visited=30
-
-----
Avg. time for DFS=0.039978019999999996 ms
    1  .0  .0  .0  .0   1   0   0   1   0   1   1   0   0   1   1   0   1   0   0
   .0  .0  .0   1  .0  .0   1   0   0   0   0   1   0   0   0   0   1   0   0   0
    1  .0  .0   0   1  .0   1   1   0   1   0   1   0   1   0   0   0   1   1   0
    1  .0  .0   0   1  .0  .0   0   1   0   0   0   0   0   0   0   0   1   0   0
    1  .0  .0   0   1   1  .0   1   0   0   1   0   1   0   1   1   0   0   1   0
   .0  .0   S   0   1   1  .0   1   1   1   0   0  .0  .0   1   0   1   0   1   0
   .0  .0   1   0   0   0  .0   1  .0   1   1   0  .0  .0   0   1   0   0   0   1
   .0  .0   1   1   1   1  .0  .0  .0  .0  .0  .0  .0  .0  .0   1   1   1   1   0
   .0  .0  .0  .0  .0   1   1  .0  .0  .0  .0  .0  .0   1  .0  .0  .0   1   0   1
    1   1  .0   1  .0  .0  .0  .0   1  .0   1   1   1   1  .0  .0  .0   0   0   1
   .0  .0   1  .0  .0  .0  .0  .0  .0   1   0   0   0   1  .0  .0  .0   0   1   0
   .0  .0  .0  .0   1  .0   1   1   1   0   0   1   0   1  .0  .0   .D   0   0   0
   .0  .0  .0  .0  .0  .0  .0  .0  .0   1   1   1   1  .0  .0  .0   0   0   0   0
   .0   1  .0  .0  .0   1   1  .0  .0  .0   1   0   1  .0  .0  .0   1   1   1   1
    1   1  .0   1  .0  .0   1   1   1   1  .0   1  .0  .0  .0  .0   0   0   0   0
   .0  .0   1   1  .0   1  .0  .0  .0  .0  .0  .0  .0  .0  .0   1   0   1   0   0
    1  .0  .0  .0   1  .0  .0  .0   1  .0   1  .0   1   1   1   0   0   0   0   0
   .0   1  .0  .0  .0  .0  .0  .0  .0  .0  .0   1   0   0   0   0   0   0   1   1
   .0  .0  .0   1   1  .0  .0  .0  .0  .0   1   0   1   0   0   0   1   0   1   1
   .0  .0   1  .0  .0  .0  .0  .0  .0   1   1   0   0   1   0   0   0   1   0   0
Visited=160
-
Avg. time for your algo=0.58135987 ms
   1   0   0   0   0   1   0   0   1   0   1   1   0   0   1   1   0   1   0   0
   0   0   0   1   0   0   1   0   0   0   0   1   0   0   0   0   1   0   0   0
   1   0   0   0   1   0   1   1   0   1   0   1   0   1   0   0   0   1   1   0
   1   0   0   0   1   0   0   0   1   0   0   0   0   0   0   0   0   1   0   0
   1   0   0   0   1   1   0   1   0   0   1   0   1   0   1   1   0   0   1   0
   0   0  .S  .0   1   1   0   1   1   1   0   0   0   0   1   0   1   0   1   0
   0   0   1  .0  .0  .0  .0   1   0   1   1   0   0   0   0   1   0   0   0   1
   0   0   1   1   1   1  .0  .0  .0  .0  .0  .0  .0  .0  .0   1   1   1   1   0
   0   0   0   0   0   1   1   0   0   0   0   0   0   1  .0   0   0   1   0   1
   1   1   0   1   0   0   0   0   1   0   1   1   1   1  .0  .0   0   0   0   1
   0   0   1   0   0   0   0   0   0   1   0   0   0   1   0  .0  .0   0   1   0
   0   0   0   0   1   0   1   1   1   0   0   1   0   1   0   0  .D   0   0   0
   0   0   0   0   0   0   0   0   0   1   1   1   1   0   0   0   0   0   0   0
   0   1   0   0   0   1   1   0   0   0   1   0   1   0   0   0   1   1   1   1
   1   1   0   1   0   0   1   1   1   1   0   1   0   0   0   0   0   0   0   0
   0   0   1   1   0   1   0   0   0   0   0   0   0   0   0   1   0   1   0   0
   1   0   0   0   1   0   0   0   1   0   1   0   1   1   1   0   0   0   0   0
   0   1   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0   1   1
   0   0   0   1   1   0   0   0   0   0   1   0   1   0   0   0   1   0   1   1
   0   0   1   0   0   0   0   0   0   1   1   0   0   1   0   0   0   1   0   0
..
Visited=21
-
-----
Avg. time for DFS=0.01281738 ms
    0   1   1   1   0   0   1   0   0   1   0   1   1   0   1   0   0   0   0   0
    0   0   1   0   1   1   1   0   0   0   0   0   1   0   0   0   0   0   0   1
    0   0   1   0   0   0   0   1   0   0   0   1   1   0   0   0   0   1   0   0
    0   0   0   0   1   0   1   0   0   0   0   0   0   1   0   1   1   1   0   1
    0   1   0   0   0   0   0   0   0   0   0   1   0   0   0   0   1   0   0   1
    1   1   0   0   0   0   1   0   0   1   0   0   1   0   0   0   1   0   1   1
    1   1   0   0   0   0   0   1   1   0   1   1   1   0   1   0   0   1   1   1
    1   0   1   1   0   1   0   0   1   1   1   0   1   0   0   1   0   0   0   0
    0   0   0   0   0   0   0   0   0   0   0   1   0   0   1   1   0   0   0   1
    1   1   1   0   0   1   1   1   1   1   0   1   0   1   1   1   0   1   1   0
    0   0   0   1   1  .0   1   0   0   0   0   0   1   0   0   1   0   0   1   0
    1   1   1  .0  .0  .0  .0   1   0   1   1   0   1   0   1   D   1   0   0   0
   .0   1  .0   1  .0  .0   1   0   0   0   0   0   0   0   0   1   1   0   0   0
   .0  .0   S  .0  .0   1   0   1   0   0   1   0   0   1   1   0   0   0   0   1
   .0   1  .0  .0  .0  .0   1   0   1   1   0   0   0   0   0   1   0   0   0   0
   .0  .0   1   1  .0  .0   1   0   0   0   1   0   0   0   0   1   0   1   0   0
   .0  .0   1  .0   1  .0   1   0   0   0   0   1   0   1   0   0   1   1   1   0
   .0   1   1  .0  .0   1   0   0   0   0   0   0   1   0   0   1   0   1   0   0
   .0  .0  .0  .0  .0  .0   1   0   1   1   0   0   0   1   1   0   0   0   0   0
   .0  .0  .0   1   1   1   1   0   0   1   1   0   1   0   0   1   0   1   0   0
Visited=39
-
   0   1   1   1   0   0   1   0   0   1   0   1   1   0   1   0   0   0   0   0
   0   0   1   0   1   1   1   0   0   0   0   0   1   0   0   0   0   0   0   1
   0   0   1   0   0   0   0   1   0   0   0   1   1   0   0   0   0   1   0   0
   0   0   0   0   1   0   1   0   0   0   0   0   0   1   0   1   1   1   0   1
   0   1   0   0   0   0   0   0   0   0   0   1   0   0   0   0   1   0   0   1
   1   1   0   0   0   0   1   0   0   1   0   0   1   0   0   0   1   0   1   1
   1   1   0   0   0   0   0   1   1   0   1   1   1   0   1   0   0   1   1   1
   1   0   1   1   0   1   0   0   1   1   1   0   1   0   0   1   0   0   0   0
   0   0   0   0   0   0   0   0   0   0   0   1   0   0   1   1   0   0   0   1
   1   1   1   0   0   1   1   1   1   1   0   1   0   1   1   1   0   1   1   0
   0   0   0   1   1  .0   1   0   0   0   0   0   1   0   0   1   0   0   1   0
   1   1   1  .0  .0  .0  .0   1   0   1   1   0   1   0   1  D   1   0   0   0
  .0   1  .0   1  .0  .0   1   0   0   0   0   0   0   0   0   1   1   0   0   0
  .0  .0  .S  .0  .0   1   0   1   0   0   1   0   0   1   1   0   0   0   0   1
  .0   1  .0  .0  .0  .0   1   0   1   1   0   0   0   0   0   1   0   0   0   0
  .0  .0   1   1  .0  .0   1   0   0   0   1   0   0   0   0   1   0   1   0   0
  .0  .0   1  .0   1  .0   1   0   0   0   0   1   0   1   0   0   1   1   1   0
  .0   1   1  .0  .0   1   0   0   0   0   0   0   1   0   0   1   0   1   0   0
  .0  .0  .0  .0  .0  .0   1   0   1   1   0   0   0   1   1   0   0   0   0   0
  .0  .0  .0   1   1   1   1   0   0   1   1   0   1   0   0   1   0   1   0   0
..
Visited=39
-
-----
Avg. time for DFS=0.02655029 ms
    1   0   0   1  .0   1   1  .0   1  .0   1   1   0   0   0   0   0   0   0   0
    1   0   0   1  .0  .0   1  .0  .0  .0  .0  .0   1   1   1   0   1   0   0   0
    0   1   0   1  .0  .0  .0  .0  .0   1  .0   1   0   1   1   0   0   0   1   0
    1  .0  .0  .0  .0  .0  .0  .0  .0  .0   1   1   0   1   0   0   0   1   0   1
    1  .0  .0  .0  .0   1   1  .0   1  .0  .0   0   0   1   0   0   0   0   1   0
    0  .0  .0   1  .0  .0   1  .0  .0  .0  .0   1   0   0   1   0   1   1   1   0
    1  .0   1   1  .0   1   1  .0   1   1  .0  .0   1   0   0   0   0   1   1   0
    1  .0  .0  .0  .0   1   1  .0  .0  .0   1  .0  .0   1   1   1   1  .0  .0   1
    1  .0   S  .0  .0   1   1  .0   1  .0   1   1  .0   0   .D  .0  .0  .0   1   0
   .0  .0  .0   1  .0  .0   1   1   1   1   0   0  .0  .0  .0  .0   1  .0   0   0
   .0  .0   1   0   1   1   0   0   0   0   0   0   1  .0  .0  .0  .0  .0   0   0
    1   1   1   0   0   0   1   0   1   1   0   0   0   1  .0  .0  .0  .0   1   0
    0   0   0   0   0   0   1   0   0   1   0   1   1   0  .0  .0  .0  .0   1   0
    1   0   0   0   1   1   0   1   0   0   0   0   0   0  .0   1   1  .0   1   0
    1   0   0   0   1   0   0   0   0   1   1   0   1   0  .0  .0  .0  .0   0   0
    1   1   1   0   0   0   0   1   1   0   0   0   0   0  .0  .0   1   1   1   1
    1   0   0   1   0   0   0   0   0   1   0   0   0   0   1   1   1   0   0   1
    1   0   0   0   0   0   1   0   0   1   0   0   0   0   0   1   1   1   0   1
    0   0   1   1   1   0   0   0   1   0   1   1   0   0   0   0   0   0   0   0
    1   1   0   1   0   0   1   0   0   1   1   0   0   0   1   0   0   0   1   0
Visited=100
-
Avg. time for your algo=1.48559572 ms
   1   0   0   1   0   1   1   0   1   0   1   1  .0  .0  .0  .0  .0  .0  .0  .0
   1   0   0   1   0   0   1   0   0   0   0   0   1   1   1  .0   1  .0  .0  .0
   0   1   0   1   0   0   0   0   0   1   0   1  .0   1   1  .0  .0  .0   1  .0
   1   0   0   0  .0  .0  .0  .0  .0  .0   1   1  .0   1  .0  .0  .0   1   0   1
   1   0   0   0  .0   1   1   0   1  .0  .0  .0  .0   1  .0  .0  .0  .0   1   0
   0   0   0   1  .0  .0   1   0   0   0  .0   1  .0  .0   1  .0   1   1   1   0
   1   0   1   1  .0   1   1   0   1   1  .0  .0   1  .0  .0  .0  .0   1   1   0
   1   0   0   0  .0   1   1   0   0   0   1  .0  .0   1   1   1   1   0   0   1
   1   0  .S  .0  .0   1   1   0   1   0   1   1  .0  .0  .D   0   0   0   1   0
   0   0   0   1   0   0   1   1   1   1   0   0   0   0   0   0   1   0   0   0
   0   0   1   0   1   1   0   0   0   0   0   0   1   0   0   0   0   0   0   0
   1   1   1   0   0   0   1   0   1   1   0   0   0   1   0   0   0   0   1   0
   0   0   0   0   0   0   1   0   0   1   0   1   1   0   0   0   0   0   1   0
   1   0   0   0   1   1   0   1   0   0   0   0   0   0   0   1   1   0   1   0
   1   0   0   0   1   0   0   0   0   1   1   0   1   0   0   0   0   0   0   0
   1   1   1   0   0   0   0   1   1   0   0   0   0   0   0   0   1   1   1   1
   1   0   0   1   0   0   0   0   0   1   0   0   0   0   1   1   1   0   0   1
   1   0   0   0   0   0   1   0   0   1   0   0   0   0   0   1   1   1   0   1
   0   0   1   1   1   0   0   0   1   0   1   1   0   0   0   0   0   0   0   0
   1   1   0   1   0   0   1   0   0   1   1   0   0   0   1   0   0   0   1   0
..
Visited=58
-
-----
Avg. time for DFS=0.03173828 ms
   .0  .0   1  .0  .0  .0   1   1   0   0   0   0   0   0   0   0   1   0   0   0
   .0  .0  .0  .0   1  .0   1  .0   1   1   1   0   1   0   0   0   1   0   0   0
    1   1   1  .0   1  .0   1  .0  .0   1   0   0   0   1   0   1   0   1   0   0
    0   0   1  .0   1  .0  .0  .0  .0   1   0   0   0   0   0   0   0   1   0   0
    1   0   1  .0   1   1  .0  .0   1   0   1   1   0   1   0   0   0   1   0   0
    0   1  .0   1  .0  .0  .0  .0   1   0   0   1   0   D   1   0   0   0   1   1
    1  .0  .0  .0   1  .0  .0   1   0   1   0   1   0   0   0   0   0   1   0   0
    1   1  .0  .0  .0  .0   1   1   1   0   0   1   1   0   1   0   0   0   1   1
   .0   1  .0   1  .0  .0   1   1   1   1   1   1  .0   1   0   0   0   0   1   0
   .0  .0  .0  .0  .0   1   1  .0  .0   1  .0  .0  .0  .0   1   0   1   1   0   0
    1  .0  .0  .0   1   0   1  .0  .0  .0  .0  .0  .0   1   0   0   0   0   0   0
    1  .0   1  .0   1   1   1  .0  .0  .0  .0  .0  .0   1   0   1   1   0   0   0
    1  .0  .0   1  .0  .0   1  .0  .0   1  .0  .0   1   0   0   1   0   0   0   0
   .0   1  .0  .0  .0  .0  .0  .0  .0  .0  .0   1   0   0   0   1   0   1   1   1
   .0  .0   S   1   1   1   1  .0   1  .0  .0   1   0   0   1   0   0   0   0   0
   .0   1  .0  .0  .0  .0  .0  .0   1   1   1   0   0   0   1   0   1   1   0   0
    1   1  .0  .0   1  .0   1  .0   1   1   1   0   0   1   0   1   0   0   0   0
   .0  .0  .0  .0  .0  .0   1  .0  .0   1   0   0   1   0   0   0   1   0   1   0
   .0  .0  .0  .0   1   1   1   1   1   1   1   1   0   0   0   1   1   1   0   0
   .0  .0  .0   1   1   0   0   0   0   0   1   0   1   0   1   0   0   1   0   0
Visited=120
-
  .0  .0   1  .0  .0  .0   1   1   0   0   0   0   0   0   0   0   1   0   0   0
  .0  .0  .0  .0   1  .0   1  .0   1   1   1   0   1   0   0   0   1   0   0   0
   1   1   1  .0   1  .0   1  .0  .0   1   0   0   0   1   0   1   0   1   0   0
   0   0   1  .0   1  .0  .0  .0  .0   1   0   0   0   0   0   0   0   1   0   0
   1   0   1  .0   1   1  .0  .0   1   0   1   1   0   1   0   0   0   1   0   0
   0   1  .0   1  .0  .0  .0  .0   1   0   0   1   0  D   1   0   0   0   1   1
   1  .0  .0  .0   1  .0  .0   1   0   1   0   1   0   0   0   0   0   1   0   0
   1   1  .0  .0  .0  .0   1   1   1   0   0   1   1   0   1   0   0   0   1   1
  .0   1  .0   1  .0  .0   1   1   1   1   1   1  .0   1   0   0   0   0   1   0
  .0  .0  .0  .0  .0   1   1  .0  .0   1  .0  .0  .0  .0   1   0   1   1   0   0
   1  .0  .0  .0   1   0   1  .0  .0  .0  .0  .0  .0   1   0   0   0   0   0   0
   1  .0   1  .0   1   1   1  .0  .0  .0  .0  .0  .0   1   0   1   1   0   0   0
   1  .0  .0   1  .0  .0   1  .0  .0   1  .0  .0   1   0   0   1   0   0   0   0
  .0   1  .0  .0  .0  .0  .0  .0  .0  .0  .0   1   0   0   0   1   0   1   1   1
  .0  .0  .S   1   1   1   1  .0   1  .0  .0   1   0   0   1   0   0   0   0   0
  .0   1  .0  .0  .0  .0  .0  .0   1   1   1   0   0   0   1   0   1   1   0   0
   1   1  .0  .0   1  .0   1  .0   1   1   1   0   0   1   0   1   0   0   0   0
  .0  .0  .0  .0  .0  .0   1  .0  .0   1   0   0   1   0   0   0   1   0   1   0
  .0  .0  .0  .0   1   1   1   1   1   1   1   1   0   0   0   1   1   1   0   0
  .0  .0  .0   1   1   0   0   0   0   0   1   0   1   0   1   0   0   1   0   0
..
Visited=120
-
-----
Avg. time for DFS=0.04211426 ms
    0   0   0   0   1   0   0   1   0   0   0   0   0   1   0   1   0   0   0   1
    0   0   0   1   1   0   1   0   0   0   0   0   0   0   0   1   0   0   0   0
    1   1   1   0   0   0   0   0   0   1   1   0   1   1   0   0   0   1   0   0
    1   1   0   0   1   0   1   0   1   1   1   1   1   0   0   0   1   0   0   1
    0   1   1   1   0   0   1   0   0   1   1  .0   .D   0   0   0   0   0   1   1
    0   0   0   1   1   0   0   0   0   1   0  .0   1   1   1   0   1   0   1   0
    0   0   1   0   0   1   1   0   0   0   1  .0   0   1  .0   1   1  .0  .0   1
    1   0   S   1   0   0   0   1   0   0   0  .0  .0  .0  .0  .0  .0  .0  .0   1
    0   1  .0  .0   0   1   1   1   0   0   0  .0  .0   1  .0  .0  .0  .0  .0   0
    0   0   1  .0   0   1   0   1   1   1   1  .0  .0   1  .0  .0   1  .0  .0   1
    0   1   0  .0   1   0   1   0   0   0   1  .0   1   0   1  .0   1   1  .0   0
    1   1  .0  .0   1   1   0   0   1   1   0   1   0   0   1   1   1  .0  .0   1
    0   1  .0   1  .0  .0   1   0   1   0   1  .0   1   0  .0  .0  .0  .0  .0   1
    1   1  .0  .0  .0  .0   0   0   1   1   0  .0  .0   0  .0   1  .0   1   1   0
    1   0   1  .0  .0  .0   0   0   1   1   0  .0  .0   0  .0  .0  .0  .0  .0   1
    0   0   1   1   1  .0  .0   1   0   0   0  .0  .0   0  .0  .0  .0  .0  .0  .0
    0   0   1   0   1   1  .0  .0   1   1   1  .0  .0   0  .0   1  .0  .0   1  .0
    1   1   1   1  .0  .0  .0  .0  .0  .0  .0  .0  .0  .0  .0   1  .0  .0   1  .0
    1   0   0   0   1  .0  .0  .0  .0  .0  .0  .0   1  .0  .0  .0  .0  .0  .0   1
    0   0   0   0   1  .0  .0   1  .0  .0  .0   1   0  .0  .0   1  .0  .0  .0  .0
Visited=123
-
   0   0   0   0   1   0   0   1   0   0   0   0   0   1   0   1   0   0   0   1
   0   0   0   1   1   0   1   0   0   0   0   0   0   0   0   1   0   0   0   0
   1   1   1   0   0   0   0   0   0   1   1   0   1   1   0   0   0   1   0   0
   1   1   0   0   1   0   1   0   1   1   1   1   1   0   0   0   1   0   0   1
   0   1   1   1   0   0   1   0   0   1   1   0  .D  .0  .0  .0  .0  .0   1   1
   0   0   0   1   1   0   0   0   0   1   0   0   1   1   1   0   1  .0   1   0
   0   0   1  .0  .0   1   1   0   0   0   1   0   0   1   0   1   1  .0  .0   1
   1   0  .S   1  .0  .0  .0   1   0   0   0   0   0   0   0   0   0   0  .0   1
   0   1  .0  .0  .0   1   1   1   0   0   0   0   0   1   0   0   0   0  .0   0
   0   0   1  .0  .0   1   0   1   1   1   1   0   0   1   0   0   1   0  .0   1
   0   1  .0  .0   1   0   1  .0  .0  .0   1   0   1  .0   1   0   1   1  .0   0
   1   1  .0  .0   1   1  .0  .0   1   1   0   1  .0  .0   1   1   1  .0  .0   1
   0   1  .0   1   0   0   1  .0   1   0   1  .0   1  .0  .0  .0  .0  .0   0   1
   1   1  .0  .0  .0  .0  .0  .0   1   1  .0  .0  .0  .0  .0   1  .0   1   1   0
   1   0   1   0   0   0  .0  .0   1   1  .0  .0  .0  .0  .0  .0  .0   0   0   1
   0   0   1   1   1   0  .0   1  .0  .0  .0  .0  .0  .0  .0  .0   0   0   0   0
   0   0   1   0   1   1  .0  .0   1   1   1  .0  .0  .0  .0   1   0   0   1   0
   1   1   1   1   0   0   0  .0  .0  .0  .0  .0  .0  .0  .0   1   0   0   1   0
   1   0   0   0   1   0   0   0   0   0   0   0   1  .0  .0   0   0   0   0   1
   0   0   0   0   1   0   0   1   0   0   0   1  .0  .0  .0   1   0   0   0   0
..
Visited=95
-
-----
Avg. time for DFS=0.030822759999999998 ms
    1   0   0   0   0   0   0   1   0   1   1  .0  .0   1   0   0   0   0   0   0
    1   1   1   0   0   0   0   0   0  .0  .0  .0  .0  .0   1   0   1   0   1   1
    0   0   0   0   0   0   1   1   0  .0  .0   1  .0  .0   1   1   0   0   1   0
    0   0   1   0   1   0   1   1   1  .0   1   0  .0  .0  .0  .0  .0   0   0   1
    0   1   1   0   1   0  .0  .0   0  .0   0   0  .0  .0  .0  .0  .0  .0   0   0
    1   1   1   1   0   1  .0  .0  .0  .0   0   0   1   1  .0  .0   1  .0  .0   0
    0  .0  .0   1   0   0  .0   1  .0  .0   1   .D  .0   1   1   1   1   1  .0   0
    0  .0   S   0   0   0  .0   0  .0  .0   0   0  .0   0   1   1   1  .0  .0  .0
    0  .0   1   0   0   0  .0   0  .0  .0   0   0  .0   1   1  .0   1  .0   1  .0
    0  .0   1   0   0   0  .0   1   1   1   0   1  .0   0  .0  .0  .0  .0  .0  .0
    1  .0   1   1   0   1  .0   0   0   0   0   1  .0  .0  .0  .0  .0  .0  .0   1
    0  .0   0   0   1   1  .0   1   1   1   0   0  .0  .0   1  .0  .0  .0  .0   1
    0  .0   0   1  .0  .0  .0   0   0   0   0   0   1   1   0   1  .0   1   1   0
    0  .0   1   1  .0  .0  .0   1   1   0   0   0   1  .0   1   1  .0  .0   1   0
    1  .0  .0  .0  .0  .0  .0   1   0   1   0   0   1  .0  .0  .0  .0  .0   1   0
    1  .0  .0  .0  .0  .0   1   1   1   0   0   0   0   1   1  .0   1   1   0   0
    0  .0  .0  .0  .0   1   1   0   1   1   0   0   0   1   1  .0   1   1   0   0
    0   1   1   1   1   0   0   0   0   0   0   0   1   0   0   1   0   0   1   0
    1   0   0   0   1   1   0   1   0   0   1   1   1   0   0   0   0   0   0   0
    0   1   1   0   0   0   0   0   0   0   0   0   1   1   0   1   1   1   0   0
Visited=119
-
   1   0   0   0   0   0   0   1   0   1   1   0   0   1   0   0   0   0   0   0
   1   1   1   0   0   0   0   0   0   0   0   0   0   0   1   0   1   0   1   1
   0   0   0   0   0   0   1   1   0   0   0   1   0   0   1   1   0   0   1   0
   0   0   1   0   1   0   1   1   1   0   1   0   0   0   0   0   0   0   0   1
   0   1   1   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
   1   1   1   1   0   1   0   0   0   0   0   0   1   1   0   0   1   0   0   0
   0   0   0   1   0   0   0   1   0   0   1  .D   0   1   1   1   1   1   0   0
   0   0  .S  .0  .0  .0  .0  .0  .0  .0  .0  .0   0   0   1   1   1   0   0   0
   0   0   1   0   0   0   0   0   0   0   0   0   0   1   1   0   1   0   1   0
   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   0   0   0   0
   1   0   1   1   0   1   0   0   0   0   0   1   0   0   0   0   0   0   0   1
   0   0   0   0   1   1   0   1   1   1   0   0   0   0   1   0   0   0   0   1
   0   0   0   1   0   0   0   0   0   0   0   0   1   1   0   1   0   1   1   0
   0   0   1   1   0   0   0   1   1   0   0   0   1   0   1   1   0   0   1   0
   1   0   0   0   0   0   0   1   0   1   0   0   1   0   0   0   0   0   1   0
   1   0   0   0   0   0   1   1   1   0   0   0   0   1   1   0   1   1   0   0
   0   0   0   0   0   1   1   0   1   1   0   0   0   1   1   0   1   1   0   0
   0   1   1   1   1   0   0   0   0   0   0   0   1   0   0   1   0   0   1   0
   1   0   0   0   1   1   0   1   0   0   1   1   1   0   0   0   0   0   0   0
   0   1   1   0   0   0   0   0   0   0   0   0   1   1   0   1   1   1   0   0
..
Visited=11
-
-----
Avg. time for DFS=0.03936768 ms
    1   1   1   0   1   0   0   0   1   0   1   0   1   0   0   0   1   0   1   0
    0   1   0   0   0   1   0   1   0   1   0   0   0   1   0   0   0   0   0   0
    0   1   0   0   0   0   1   0   0   1   1   1   0   1   0   0   0   1   0   0
    0   0   0   1   0   0   0   1   0   1   0   0   0   0   1   1   1  .0   1   1
    0   0   0   1   0   1   1   0   0   1   0   1   1   1  .0  .0  .0  .0  .0  .0
    0   1   0  .0  .0   1   1   0   1  .0  .0   0   1  .0   1  .0   1   1  .0  .0
    0   1   0  .0  .0  .0  .0   1  .0  .0  .0   1   1  .0  .0  .0  .0  .0  .0   1
    0   1   0  .0  .0  .0  .0  .0  .0   1  .0   1   0   1  .0  .0  .0  .0  .0   1
    0   1   0  .0  .0   1  .0  .0   1   1  .0  .0   1  .0  .0  .0  .0  .0  .0  .0
    1   1   0  .0  .0   1  .0   1   1   0   1  .0  .0  .0  .0   1  .0  .0  .0  .0
    1   0   1  .0   1   1   1   0   0  .0  .0  .0  .0   1   1   1  .0  .0  .0  .0
    1   1   1  .0   1   1   0   1  .0  .0  .0  .0  .0  .0  .0   1   1  .0   1  .0
    0   0   S  .0   0   0   0   0  .0   1  .0  .0  .0  .0  .0  .0  .0   1  .0  .0
    0   0   1  .0   1   0   1   0  .0   0   1   1  .0   1  .0   1  .0  .0  .0  .0
    0   0   0   1  .0   1  .0   .D  .0   0   0   0   1  .0  .0  .0   1  .0  .0  .0
    1   1   1  .0  .0   1  .0   1  .0   0   0   0   0   1  .0  .0   1   1  .0  .0
    1  .0  .0  .0  .0  .0  .0   1  .0   1   1   0   0   1   1  .0   1  .0   1  .0
    1  .0   1  .0  .0   1   1   1  .0   0   0   0   0   1   0   1  .0  .0  .0  .0
   .0  .0  .0   1  .0  .0   1  .0  .0   0   0   0   1   0   0   0   1  .0   1  .0
   .0  .0  .0  .0  .0  .0  .0  .0  .0   1   0   0   1   0   0   0   0   1  .0  .0
Visited=159
-
Avg. time for your algo=0.20019531 ms
   1   1   1   0   1   0   0   0   1   0   1   0   1   0   0   0   1   0   1   0
   0   1   0   0   0   1   0   1   0   1   0   0   0   1   0   0   0   0   0   0
   0   1   0   0   0   0   1   0   0   1   1   1   0   1   0   0   0   1   0   0
   0   0   0   1   0   0   0   1   0   1   0   0   0   0   1   1   1   0   1   1
   0   0   0   1   0   1   1   0   0   1   0   1   1   1   0   0   0   0   0   0
   0   1   0   0   0   1   1   0   1   0   0   0   1   0   1   0   1   1   0   0
   0   1   0   0   0   0   0   1   0   0   0   1   1   0   0   0   0   0   0   1
   0   1   0   0   0   0   0   0   0   1   0   1   0   1   0   0   0   0   0   1
   0   1   0   0   0   1   0   0   1   1   0   0   1   0   0   0   0   0   0   0
   1   1   0   0   0   1   0   1   1   0   1   0   0   0   0   1   0   0   0   0
   1   0   1   0   1   1   1   0   0   0   0   0   0   1   1   1   0   0   0   0
   1   1   1   0   1   1   0   1   0   0   0   0   0   0   0   1   1   0   1   0
   0   0  .S  .0  .0  .0  .0  .0   0   1   0   0   0   0   0   0   0   1   0   0
   0   0   1   0   1   0   1  .0   0   0   1   1   0   1   0   1   0   0   0   0
   0   0   0   1   0   1   0  .D   0   0   0   0   1   0   0   0   1   0   0   0
   1   1   1   0   0   1   0   1   0   0   0   0   0   1   0   0   1   1   0   0
   1   0   0   0   0   0   0   1   0   1   1   0   0   1   1   0   1   0   1   0
   1   0   1   0   0   1   1   1   0   0   0   0   0   1   0   1   0   0   0   0
   0   0   0   1   0   0   1   0   0   0   0   0   1   0   0   0   1   0   1   0
   0   0   0   0   0   0   0   0   0   1   0   0   1   0   0   0   0   1   0   0
..
Visited=8
-
-----
Avg. time for DFS=0.03234863 ms
    1   0   0   0   0   0   0   0   1   0   1   0   0   1   0   0   1   0   1   0
    0   0   0   1   0   1   1   1   0   1   0   0   0   0   0   0   1   1   0   0
    0   1   0   0   0   0   0   0   0   1   0   0   0   0   0   1   1   0   0   0
    0   1   0   0   0   0   1   0   1   0   0   0   1   0   0   0   0   0   0   0
    0   0   1   1   1   0   1   1  .0   1   0   1   0   1   1   0   0   1   0   0
    0   0   1   0   0   1   1  .0  .0  .0  .0  .0   1   0   1   0   0   0   0   0
    0   1   0   0   0   0   1  .0  .0  .0  .0  .0   0   0   0   0   0   0   0   0
    1   0   S   1   0   1   1   1  .0  .0  .0  .0   0   0   1   1   0   0   1   1
    0   0  .0   0   0   0   .D  .0  .0  .0   1  .0   1   0   1   0   1   0   1   0
    0   0  .0   0   1   0   0  .0  .0  .0   1  .0   1   0   0   0   1   0   0   0
    0   0  .0  .0   0   0   0  .0  .0   1   0  .0   0   0   0   0   0   0   0   0
    0   0   1  .0   1   0   1   1  .0   1   1  .0   1   0   0   1   1   0   0   1
    0   1   0  .0   0   0   0   1  .0  .0  .0  .0   0   0   0   1   0   1   0   1
    1   1   0  .0   1   0   0  .0  .0  .0  .0  .0   0   0   0   0   0   0   0   0
    1   0   0  .0   0   1   0  .0  .0  .0  .0  .0   0   0   0   0   0   0   0   0
    0   0   0  .0   0   1   1  .0   1   1  .0  .0   1   0   0   0   1   1   0   0
    1   1   0  .0  .0  .0  .0  .0   0   1  .0  .0   0   1   1   1   1   0   0   0
    0   0   0   1  .0  .0  .0  .0   1   0  .0  .0   1   1  .0   1   1   0   1   0
    1   0   0   1  .0   1   1   1  .0   1  .0   1  .0  .0  .0  .0   1   0   1   0
    0   0   1  .0  .0   1  .0  .0  .0  .0  .0  .0  .0  .0   1   1   0   0   0   1
Visited=87
-
Avg. time for your algo=0.15594482999999998 ms
   1   0   0   0   0   0   0   0   1   0   1   0   0   1   0   0   1   0   1   0
   0   0   0   1   0   1   1   1   0   1   0   0   0   0   0   0   1   1   0   0
   0   1   0   0   0   0   0   0   0   1   0   0   0   0   0   1   1   0   0   0
   0   1   0   0   0   0   1   0   1   0   0   0   1   0   0   0   0   0   0   0
   0   0   1   1   1   0   1   1   0   1   0   1   0   1   1   0   0   1   0   0
   0   0   1   0   0   1   1   0   0   0   0   0   1   0   1   0   0   0   0   0
   0   1   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0
   1   0  .S   1   0   1   1   1   0   0   0   0   0   0   1   1   0   0   1   1
   0   0  .0  .0  .0  .0  .D   0   0   0   1   0   1   0   1   0   1   0   1   0
   0   0   0   0   1   0   0   0   0   0   1   0   1   0   0   0   1   0   0   0
   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0
   0   0   1   0   1   0   1   1   0   1   1   0   1   0   0   1   1   0   0   1
   0   1   0   0   0   0   0   1   0   0   0   0   0   0   0   1   0   1   0   1
   1   1   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
   1   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   1   1   0   1   1   0   0   1   0   0   0   1   1   0   0
   1   1   0   0   0   0   0   0   0   1   0   0   0   1   1   1   1   0   0   0
   0   0   0   1   0   0   0   0   1   0   0   0   1   1   0   1   1   0   1   0
   1   0   0   1   0   1   1   1   0   1   0   1   0   0   0   0   1   0   1   0
   0   0   1   0   0   1   0   0   0   0   0   0   0   0   1   1   0   0   0   1
..
Visited=6
-
-----
Avg. time for DFS=0.0076294 ms
   .0   1  .0  .0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1
   .0  .0  .0   1   1   0   1   1   0   0   0   0   0   0   0   0   1   0   1   0
   .0  .0   1   0   0   1   0   0   0   0   1   0   1   1   1   1   0   0   0   0
    1  .0   1   0   0   0   1   1   1   1   0   0   1   0   1   1   0   1   0   1
   .0  .0   S   1   0   1   0   1   1   0   1   1   1   0   0   1   0   0   0   1
   .0   1  .0   1   1   1   0   1   0   0   1   0   1   0   1   0   0   0   1   1
   .0   1  .0   1   0   0   0   0   0   0   1   1   0   0   0   0   1   0   0   1
   .0  .0   1   0   D   0   0   1   1   1   0   0   0   0   1   1   0   0   0   0
   .0   1   0   0   0   1   0   1   0   0   0   1   1   1   0   0   0   1   1   0
    1   0   0   0   1   0   1   0   1   1   1   1   0   1   0   1   0   0   1   1
    0   0   0   0   1   0   1   0   0   0   0   0   0   1   0   0   0   1   0   0
    1   1   0   1   0   0   0   1   0   0   1   0   1   0   1   0   0   0   0   0
    1   1   1   1   0   1   0   1   0   0   1   1   1   0   0   1   0   0   1   0
    1   0   1   1   0   1   1   0   0   0   0   0   1   1   1   0   0   0   0   0
    1   0   0   1   0   0   0   0   0   1   1   0   0   0   0   0   1   0   0   0
    1   0   1   0   0   0   0   0   1   1   1   0   0   0   0   0   0   0   0   1
    1   1   1   0   0   0   1   0   0   1   0   1   0   0   1   0   0   1   1   0
    0   0   0   0   1   1   1   0   0   1   1   1   0   1   0   1   0   1   0   0
    1   1   0   1   0   0   1   1   0   1   0   0   0   1   0   0   1   1   1   0
    0   0   0   1   0   0   0   0   1   1   0   0   0   0   0   0   1   0   0   0
Visited=19
-
Avg. time for your algo=0.5285644399999999 ms
  .0   1  .0  .0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1
  .0  .0  .0   1   1   0   1   1   0   0   0   0   0   0   0   0   1   0   1   0
  .0  .0   1   0   0   1   0   0   0   0   1   0   1   1   1   1   0   0   0   0
   1  .0   1   0   0   0   1   1   1   1   0   0   1   0   1   1   0   1   0   1
  .0  .0  .S   1   0   1   0   1   1   0   1   1   1   0   0   1   0   0   0   1
  .0   1  .0   1   1   1   0   1   0   0   1   0   1   0   1   0   0   0   1   1
  .0   1  .0   1   0   0   0   0   0   0   1   1   0   0   0   0   1   0   0   1
  .0  .0   1   0  D   0   0   1   1   1   0   0   0   0   1   1   0   0   0   0
  .0   1   0   0   0   1   0   1   0   0   0   1   1   1   0   0   0   1   1   0
   1   0   0   0   1   0   1   0   1   1   1   1   0   1   0   1   0   0   1   1
   0   0   0   0   1   0   1   0   0   0   0   0   0   1   0   0   0   1   0   0
   1   1   0   1   0   0   0   1   0   0   1   0   1   0   1   0   0   0   0   0
   1   1   1   1   0   1   0   1   0   0   1   1   1   0   0   1   0   0   1   0
   1   0   1   1   0   1   1   0   0   0   0   0   1   1   1   0   0   0   0   0
   1   0   0   1   0   0   0   0   0   1   1   0   0   0   0   0   1   0   0   0
   1   0   1   0   0   0   0   0   1   1   1   0   0   0   0   0   0   0   0   1
   1   1   1   0   0   0   1   0   0   1   0   1   0   0   1   0   0   1   1   0
   0   0   0   0   1   1   1   0   0   1   1   1   0   1   0   1   0   1   0   0
   1   1   0   1   0   0   1   1   0   1   0   0   0   1   0   0   1   1   1   0
   0   0   0   1   0   0   0   0   1   1   0   0   0   0   0   0   1   0   0   0
..
Visited=19
-
-----
Avg. time for DFS=0.052490230000000006 ms
    1  .0   1  .0  .0  .0  .0   1   0   0   0   1   0   0   0   1   0   0   0   0
   .0  .0  .0  .0  .0   1  .0  .0   1   1   1   0   0   0   0   1   1   0   0   0
    1  .0  .0  .0  .0  .0  .0  .0  .0  .0   1   0   1   0   0   1   0   0   0   1
   .0  .0   1  .0  .0  .0  .0   1   1  .0  .0   1   0   0   1   0   0   0   0   1
   .0   1   S  .0  .0  .0   1   0   0   1  .0  .0   1   0   0   1   0   1   0   0
    1   0  .0   1  .0  .0  .0   1   0   1   1   1   0   0   1   0   0   0   0   0
    0   0  .0   .D   1  .0   1   1   1  .0  .0  .0   1   1   0   1   0   0   0   1
    0   0  .0  .0  .0  .0  .0  .0   1  .0  .0  .0   1  .0   1  .0   1   0   0   1
    0   0  .0  .0  .0  .0  .0  .0  .0   1  .0  .0  .0  .0   1  .0  .0   1   1  .0
    0   0  .0  .0   1  .0  .0  .0   1  .0   1  .0   1  .0  .0  .0  .0  .0   1  .0
    1   0  .0  .0  .0  .0   1   1   1  .0   1  .0   1   1   1  .0  .0  .0  .0  .0
    1   1  .0  .0  .0  .0  .0  .0  .0  .0  .0  .0  .0   1  .0  .0  .0  .0  .0  .0
   .0  .0  .0  .0  .0   1  .0  .0   1  .0  .0  .0  .0   1  .0  .0  .0  .0  .0  .0
    1  .0  .0  .0   1   0   1  .0  .0  .0  .0   1   1   1  .0  .0   1  .0  .0   1
    1  .0   1  .0  .0   0   1   1   1  .0   1   1   1  .0  .0   1   1  .0  .0  .0
   .0  .0  .0   1  .0  .0   1   0   0  .0  .0  .0  .0   1  .0  .0  .0   1  .0  .0
   .0  .0  .0  .0   1  .0  .0  .0   0  .0  .0   1  .0  .0  .0  .0   1  .0  .0  .0
   .0  .0  .0   1  .0  .0   1  .0  .0  .0  .0  .0  .0  .0   1   1   1  .0  .0  .0
    1  .0  .0  .0  .0  .0   1   1  .0  .0  .0  .0   1   1   0   0   0   1  .0   1
    1   1  .0  .0  .0  .0   1  .0  .0   1  .0  .0  .0   1   0   0   0   0   1   0
Visited=213
-
   1   0   1   0   0   0   0   1   0   0   0   1   0   0   0   1   0   0   0   0
   0   0   0   0   0   1   0   0   1   1   1   0   0   0   0   1   1   0   0   0
   1   0   0   0   0   0   0   0   0   0   1   0   1   0   0   1   0   0   0   1
   0   0   1   0   0   0   0   1   1   0   0   1   0   0   1   0   0   0   0   1
   0   1  .S   0   0   0   1   0   0   1   0   0   1   0   0   1   0   1   0   0
   1   0  .0   1   0   0   0   1   0   1   1   1   0   0   1   0   0   0   0   0
   0   0  .0  .D   1   0   1   1   1   0   0   0   1   1   0   1   0   0   0   1
   0   0   0   0   0   0   0   0   1   0   0   0   1   0   1   0   1   0   0   1
   0   0   0   0   0   0   0   0   0   1   0   0   0   0   1   0   0   1   1   0
   0   0   0   0   1   0   0   0   1   0   1   0   1   0   0   0   0   0   1   0
   1   0   0   0   0   0   1   1   1   0   1   0   1   1   1   0   0   0   0   0
   1   1   0   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0
   0   0   0   0   0   1   0   0   1   0   0   0   0   1   0   0   0   0   0   0
   1   0   0   0   1   0   1   0   0   0   0   1   1   1   0   0   1   0   0   1
   1   0   1   0   0   0   1   1   1   0   1   1   1   0   0   1   1   0   0   0
   0   0   0   1   0   0   1   0   0   0   0   0   0   1   0   0   0   1   0   0
   0   0   0   0   1   0   0   0   0   0   0   1   0   0   0   0   1   0   0   0
   0   0   0   1   0   0   1   0   0   0   0   0   0   0   1   1   1   0   0   0
   1   0   0   0   0   0   1   1   0   0   0   0   1   1   0   0   0   1   0   1
   1   1   0   0   0   0   1   0   0   1   0   0   0   1   0   0   0   0   1   0
..
Visited=4
-

For some reason it doesn't always log the time taken to complete my algo, I don't know why and occasionally it fails to place new Log statements on the next line. Now I've just got to try and neaten up my code (which I can barely follow

) and try to optimise it rather a lot!

cimperia · Aug 16, 2015

I had some time to get back to this.

I have coded a new method (shown as ZoomIn in the results) which tries to get nearer to the Target on every call, instead of filling the grid and hitting the Destination by blind luck.

It shows interesting results compared to DFS, the basic algorithm posted by @Informatix and used to baseline, and DFS_SDA which is in essence DFS but with an optimized data structure (Single Dimensional Array) which outperforms DFS quite consistently.

ZoomIn will often enough find one the shortest routes to reach the Target.By short I mean that there is no backtracking and that the number of recursive calls is equal to the number of visited cells.

ZoomIn will often outperform DFS* in these circumstances and sometimes by a factor 5 or 6. The first grid in the run I posted (1000 iterations for each grid) is a perfect example of this.

The more moves it takes for ZoomIn to reach the target, the less gain there will be, and DFS* will then often outperform ZoomIn. It's pretty much the case when NO path is found, as often the number of moves to determine that there's no path will be pretty much the same in both algorithms.

The reason it that it takes longer to determine which move to take for ZoomIn than for DFS*. The "intelligent" behaviour comes to a price and I'll see if I can tweak the performance further and maybe improve on the "intelligence" bit as some the grids posted in the log show that there's room for improvement.

Here's the log of a typical run (1000 iterations for each grid). I have left grids where I think it was adding something useful.

EDIT: Just realised that there's a bug in ZoomIn: it sometimes reports NO path found when one exists

B4X:

Start: 1000 iterations
--------------------------------------------------------------------------------------
  Start Cell: 5:2
  End  Cell: 8:17
------------------------------------------------
Avg. time For DFS  = 0.113 ms. Path Found in 160 Recursive Calls. Visited Cells=160
---
Avg. time For DFS_SDA= 0.104 ms. Path Found in 160 Recursive Calls. Visited Cells=160
---
Avg. time For ZoomIn = 0.017 ms. Path Found in 21 Recursive Calls. Visited Cells=21
---
..........XXXX..XX....XXXXXX..XX....XX..
XX........XX..........XX......XX......XX
................DD[]XX......XXXX..XX..XX
XX..XX..XXXX......[]XX....XX..XX..XXXXXX
XX..XX....XXXX..XX[]..XX....XX..XX......
..XX..........XX[][]..XX......XX......XX
XX....XX....XX[][]..XX..XX..XXXX..XXXX..
XX..........XX[]......XX..........XX....
..........XXXX[]......XX..XXXX......XX..
XX..XX......XX[]....XX....XXXXXX..XX..XX
......XXXX....[]..XXXX......XX..........
..XXXX..XX..XX[]XXXXXX..XXXX......XXXX..
XXXX..........[]XX..XX..XX..............
............XX[]XXXX..XX....XXXX....XX..
......XX....XX[]....XX..................
..XXXXXXXXXX[][]..XX..XXXX..XX..........
........XXXX[]XX......XXXX..XX..XXXX....
..........SS[]..........................
........................XXXX..XX..XX..XX
....XX..XX....XXXXXX......XX..XX........
--------------------------------------------------------------------------------------
  Start Cell: 13:2
  End  Cell: 9:16
------------------------------------------------
Avg. time For DFS  = 0.177 ms. Path Found in 229 Recursive Calls. Visited Cells=229
---
Avg. time For DFS_SDA= 0.164 ms. Path Found in 229 Recursive Calls. Visited Cells=229
---
Avg. time For ZoomIn = 0.162 ms. Path Found in 135 Recursive Calls. Visited Cells=135
---
............XXXXXX................XX..XX
XX..XX..........XX....XXXX............XX
XX........XX......[][][][][]XXXX........
XX........XXXX..XXDDXX..XX[]XXXXXXXX....
XXXX..XX....XX....XX[][]XX[]XX......XX..
XX....XX..XX..XXXX..XX[][][]............
..XX....XXXXXX[][]XXXX[][]..XX....XX....
XXXXXX..XX[][]XX[][]XXXX[]..XX..XX..XX..
XX[]XX[][]XX[][][][][]XX[]XX........XX..
XX[][][][][][]XX[][]XX..[][]XXXX..XXXX..
..[][][]XX[][]XXXX[][]XXXX[]XX..XXXXXXXX
XX[][][][]XX[][]XX[][]....[][]XX........
[][]XXXX[]XX[][]XX[][]XX....[]....XX....
[]XX[][][][][][][][][]XX..XX[]....XX..XX
[][][][][][][][]XX[]XXXXXXXX[]..XXXXXXXX
[][][]XXXXXXXXXX[]XX[][][][][]......XXXX
[][][][][][]XXXX[][]XX[]XX[][]XX........
XX[][][][][][][][][]XX[]XXSSXX..XXXX....
[][]XX[]XXXX[][][][][][]..XXXX....XX..XX
XXXXXX[][][]XX[][][][]XX..XXXX..XX......
--------------------------------------------------------------------------------------
  Start Cell: 6:2
  End  Cell: 8:15
------------------------------------------------
Avg. time For DFS  = 0.098 ms. Path Found in 119 Recursive Calls. Visited Cells=119
---
Avg. time For DFS_SDA= 0.067 ms. Path Found in 119 Recursive Calls. Visited Cells=119
---
Avg. time For ZoomIn = 0.035 ms. Path Found in 27 Recursive Calls. Visited Cells=27
---
..XX......XXXX..XXXXXX......XX....XXXX..
XX........XX......XX..XXXX..XX..........
XX........XXXXXX............XX..XX....XX
....XX..........XX..XX....XX........XX..
..XX......XX..[]DDXXXX....XX......XXXX..
........XX..[][]........XX........XX..XX
..XXXX....[][]....XX....................
XX....XX[][]..........XX..........XX....
..XXXXXX[]......XX....XX......XXXX......
..XXXX..[]XX....XX..XX......XX..XX..XX..
....XX..[]..XX........................XX
XXXX....[]XXXX..XXXX..XX..XX........XXXX
....XXXX[][][]XX[]XX........XX..XX..XX..
..XX....XX..[][][][]........XX..........
......XX........XX[]..XX....XX..XXXXXX..
XXXX............XX[]..XXXX......XXXX....
..XXXX......XXXX[][]....XXXX........XX..
......XXXX..SS[][]XX..XX..XXXXXX....XXXX
......XX..XX..XXXX..XXXXXX........XXXX..
XX..........XXXXXX....XX..XX..XX..XX....
--------------------------------------------------------------------------------------
  Start Cell: 14:2
  End  Cell: 5:14
------------------------------------------------
Avg. time For DFS  = 0.149 ms. Path Found in 142 Recursive Calls. Visited Cells=142
---
Avg. time For DFS_SDA= 0.106 ms. Path Found in 142 Recursive Calls. Visited Cells=142
---
Avg. time For ZoomIn = 0.126 ms. Path Found in 108 Recursive Calls. Visited Cells=108
--------------------------------------------------------------------------------------
  Start Cell: 6:2
  End  Cell: 8:13
------------------------------------------------
Avg. time For DFS  = 0.039 ms. Path NOT Found in 49 Recursive Calls. Visited Cells=49
---
Avg. time For DFS_SDA= 0.036 ms. Path NOT Found in 49 Recursive Calls. Visited Cells=49
---
Avg. time For ZoomIn = 0.063 ms. Path NOT Found in 48 Recursive Calls. Visited Cells=48
--------------------------------------------------------------------------------------
  Start Cell: 13:2
  End  Cell: 7:12
------------------------------------------------
Avg. time For DFS  = 0.039 ms. Path Found in 52 Recursive Calls. Visited Cells=52
---
Avg. time For DFS_SDA= 0.024 ms. Path Found in 52 Recursive Calls. Visited Cells=52
---
Avg. time For ZoomIn = 0.014 ms. Path Found in 17 Recursive Calls. Visited Cells=17
---
XX....XX........XX......XX......XX....XX
........XX..XX........XX..XX..XX..XX....
XXXX....XX....XX....XX..............XX..
..XX......XX......XXXXXXXX....XX........
..XX....XXXXXX..........XX........XX....
............XX............XX....XX......
..XXXXXX....XX..XX..XX....XX......XX....
........XX....DD[]..XXXXXX..XX..XX......
....XXXX........[][]XXXX............XXXX
................XX[]....XX..........XX..
......XXXX....XX..[]..XX..XX........XXXX
..XX......XX......[]XXXXXX......XX..XXXX
....XXXX......XXXX[][][]XXXXXX..........
XX....XXXX..XXXX..XXXX[][][]..XX....XX..
..XXXX................XXXX[]XX....XXXX..
......XX..XXXX......XXXX..[]..XXXX....XX
............XXXXXX........[]XXXXXXXX....
......XX..XX..........XX..SS......XX..XX
XX..XXXX....XX................XX..XXXX..
..XX..XX....XXXX..........XXXXXX........
--------------------------------------------------------------------------------------
  Start Cell: 13:2
  End  Cell: 7:11
------------------------------------------------
Avg. time For DFS  = 0.066 ms. Path NOT Found in 98 Recursive Calls. Visited Cells=98
---
Avg. time For DFS_SDA= 0.063 ms. Path NOT Found in 98 Recursive Calls. Visited Cells=98
---
Avg. time For ZoomIn = 0.107 ms. Path NOT Found in 98 Recursive Calls. Visited Cells=98
-------------------------------------------
  Start Cell: 11:2
  End  Cell: 7:10
------------------------------------------------
Avg. time For DFS  = 0.152 ms. Path Found in 235 Recursive Calls. Visited Cells=235
---
Avg. time For DFS_SDA= 0.132 ms. Path Found in 235 Recursive Calls. Visited Cells=235
---
Avg. time For ZoomIn = 0.183 ms. Path NOT Found in 158 Recursive Calls. Visited Cells=158
---
--------------------------------------------------------------------------------------
  Start Cell: 4:2
  End  Cell: 4:9
------------------------------------------------
Avg. time For DFS  = 0.03 ms. Path Found in 28 Recursive Calls. Visited Cells=28
---
Avg. time For DFS_SDA= 0.019 ms. Path Found in 28 Recursive Calls. Visited Cells=28
---
Avg. time For ZoomIn = 0.021 ms. Path NOT Found in 11 Recursive Calls. Visited Cells=11
--------------------------------------------------------------------------------------
  Start Cell: 10:2
  End  Cell: 6:8
------------------------------------------------
Avg. time For DFS  = 0.123 ms. Path Found in 175 Recursive Calls. Visited Cells=175
---
Avg. time For DFS_SDA= 0.105 ms. Path Found in 175 Recursive Calls. Visited Cells=175
---
Avg. time For ZoomIn = 0.013 ms. Path Found in 11 Recursive Calls. Visited Cells=11
--------------------------------------------------------------------------------------
  Start Cell: 14:2
  End  Cell: 10:7
------------------------------------------------
Avg. time For DFS  = 0.033 ms. Path Found in 41 Recursive Calls. Visited Cells=41
---
Avg. time For DFS_SDA= 0.02 ms. Path Found in 41 Recursive Calls. Visited Cells=41
---
Avg. time For ZoomIn = 0.017 ms. Path Found in 17 Recursive Calls. Visited Cells=17
--------------------------------------------------------------------------------------
  Start Cell: 15:2
  End  Cell: 14:6
------------------------------------------------
Avg. time For DFS  = 0.009 ms. Path NOT Found in 4 Recursive Calls. Visited Cells=4
---
Avg. time For DFS_SDA= 0.007 ms. Path NOT Found in 4 Recursive Calls. Visited Cells=4
---
Avg. time For ZoomIn = 0.012 ms. Path NOT Found in 4 Recursive Calls. Visited Cells=4
--------------------------------------------------------------------------------------
  Start Cell: 9:2
  End  Cell: 7:5
------------------------------------------------
Avg. time For DFS  = 0.021 ms. Path Found in 24 Recursive Calls. Visited Cells=24
---
Avg. time For DFS_SDA= 0.017 ms. Path Found in 24 Recursive Calls. Visited Cells=24
---
Avg. time For ZoomIn = 0.01 ms. Path Found in 6 Recursive Calls. Visited Cells=6
--------------------------------------------------------------------------------------
  Start Cell: 8:2
  End  Cell: 14:4
------------------------------------------------
Avg. time For DFS  = 0.16 ms. Path Found in 230 Recursive Calls. Visited Cells=230
---
Avg. time For DFS_SDA= 0.161 ms. Path Found in 230 Recursive Calls. Visited Cells=230
---
Avg. time For ZoomIn = 0.012 ms. Path Found in 9 Recursive Calls. Visited Cells=9
--------------------------------------------------------------------------------------
  Start Cell: 13:2
  End  Cell: 5:3
------------------------------------------------
Avg. time For DFS  = 0.154 ms. Path NOT Found in 219 Recursive Calls. Visited Cells=219
---
Avg. time For DFS_SDA= 0.147 ms. Path NOT Found in 219 Recursive Calls. Visited Cells=219
---
Avg. time For ZoomIn = 0.336 ms. Path NOT Found in 198 Recursive Calls. Visited Cells=198
---
XXXX[][][][]XX[][][]XXXX..XX........XX..
XX..XX[][]XXXX[][]XXXX..XX..XX....XX..XX
XXXXXX[][][]XX[][][][]XX..XXXXXX..XX..XX
[][]XX[][]XXXXXX[][]XXXXXXXXXXXX....XX[]
[][]XX[][]XXXXXX[][][][]XX[]XX....XX[][]
[][][]XX[]XX..XX[][]XX[]XX[]XX[][][][][]
XX[][][][]XX..XXXXXX[][]XX[][][][][][][]
XX[]XXXX[]XX......XXXX[][][]XXXX[][][][]
..XXXX[][][]XXXXXXXX[][][][][][]XX[][][]
XX[]XX[][][]XX....XX[][]XXXX[][][]XXXX[]
XX[][][]XX[][]XX[][][]XXXX[]XX[]XXXX[][]
[][]XX[]..[][][][][][][]XX[][][]XX[][]XX
XXXXXX[]XX[]XX[][][][][][][]XX[][][][][]
[][][][]XX[][][][][]XXXX[][][][][][][][]
XXXXXX[]XXXXXX[][]XX[]XX[][][]XXXX[][][]
XX....XXXX....XX[][][][][]XX[][]XX[][][]
XXXXXX....xD....XX[][][][][][][][][][][]
..........XX..XX..XX..XX[]SS[][][][]XX[]
..XX............XX....XXXX..XX[][]XX[][]
..XXXXXX....XX....XX......XX[][][]XX[][]
--------------------------------------------------------------------------------------
  Start Cell: 6:2
  End  Cell: 7:2
------------------------------------------------
Avg. time For DFS  = 0.008 ms. Path Found in 2 Recursive Calls. Visited Cells=2
---
Avg. time For DFS_SDA= 0.005 ms. Path Found in 2 Recursive Calls. Visited Cells=2
---
Avg. time For ZoomIn = 0.01 ms. Path Found in 2 Recursive Calls. Visited Cells=2
---

End

RandomCoder · Aug 16, 2015

cimperia said:
....EDIT: Just realised that there's a bug in ZoomIn: it sometimes reports NO path found when one exists

Welcome to my world

I've been ironing out bugs most of the day.

cimperia · Aug 17, 2015

@RandomCoder : bye bye

Fixed the bug and increased speed, especially when a Path is NOT found, ZoomIn does not lag too far behind DFS.
It's usually (much) quicker than DFS when a path is Found.

B4X:

Start: 1000 iterations
--------------------------------------------------------------------------------------
  Start Cell: 4:2
  End  Cell: 9:17
------------------------------------------------
Avg. time For DFS  = 0.082 ms. Path Found in 242 Recursive Calls. Visited Cells=85
---
Avg. time For ZoomIn = 0.018 ms. Path Found in 28 Recursive Calls. Visited Cells=27
---
--------------------------------------------------------------------------------------
  Start Cell: 4:2
  End  Cell: 15:16
------------------------------------------------
Avg. time For DFS  = 0.056 ms. Path Found in 175 Recursive Calls. Visited Cells=56
---
Avg. time For ZoomIn = 0.034 ms. Path Found in 40 Recursive Calls. Visited Cells=33
---
--------------------------------------------------------------------------------------
  Start Cell: 12:2
  End  Cell: 11:15
------------------------------------------------
Avg. time For DFS  = 0.042 ms. Path Found in 149 Recursive Calls. Visited Cells=55
---
Avg. time For ZoomIn = 0.015 ms. Path Found in 20 Recursive Calls. Visited Cells=19
---
--------------------------------------------------------------------------------------
  Start Cell: 7:2
  End  Cell: 7:14
------------------------------------------------
Avg. time For DFS  = 0.151 ms. Path Found in 486 Recursive Calls. Visited Cells=183
---
Avg. time For ZoomIn = 0.026 ms. Path Found in 30 Recursive Calls. Visited Cells=25
---
--------------------------------------------------------------------------------------
  Start Cell: 9:2
  End  Cell: 11:13
------------------------------------------------
Avg. time For DFS  = 0.119 ms. Path NOT Found in 397 Recursive Calls. Visited Cells=161
---
Avg. time For ZoomIn = 0.19 ms. Path NOT Found in 397 Recursive Calls. Visited Cells=161
---
--------------------------------------------------------------------------------------
  Start Cell: 12:2
  End  Cell: 11:12
------------------------------------------------
Avg. time For DFS  = 0.109 ms. Path Found in 443 Recursive Calls. Visited Cells=154
---
Avg. time For ZoomIn = 0.017 ms. Path Found in 12 Recursive Calls. Visited Cells=12
---
--------------------------------------------------------------------------------------
  Start Cell: 4:2
  End  Cell: 13:11
------------------------------------------------
Avg. time For DFS  = 0.014 ms. Path NOT Found in 23 Recursive Calls. Visited Cells=10
---
Avg. time For ZoomIn = 0.023 ms. Path NOT Found in 23 Recursive Calls. Visited Cells=10
---
--------------------------------------------------------------------------------------
  Start Cell: 9:2
  End  Cell: 12:10
------------------------------------------------
Avg. time For DFS  = 0.161 ms. Path Found in 591 Recursive Calls. Visited Cells=213
---
Avg. time For ZoomIn = 0.012 ms. Path Found in 12 Recursive Calls. Visited Cells=12
---
--------------------------------------------------------------------------------------
  Start Cell: 15:2
  End  Cell: 4:9
------------------------------------------------
Avg. time For DFS  = 0.088 ms. Path Found in 276 Recursive Calls. Visited Cells=95
---
Avg. time For ZoomIn = 0.027 ms. Path Found in 51 Recursive Calls. Visited Cells=33
---
--------------------------------------------------------------------------------------
  Start Cell: 10:2
  End  Cell: 6:8
------------------------------------------------
Avg. time For DFS  = 0.038 ms. Path Found in 126 Recursive Calls. Visited Cells=45
---
Avg. time For ZoomIn = 0.016 ms. Path Found in 11 Recursive Calls. Visited Cells=11
---
--------------------------------------------------------------------------------------
  Start Cell: 7:2
  End  Cell: 10:7
------------------------------------------------
Avg. time For DFS  = 0.043 ms. Path Found in 72 Recursive Calls. Visited Cells=27
---
Avg. time For ZoomIn = 0.014 ms. Path Found in 9 Recursive Calls. Visited Cells=9
---
--------------------------------------------------------------------------------------
  Start Cell: 8:2
  End  Cell: 14:6
------------------------------------------------
Avg. time For DFS  = 0.045 ms. Path Found in 140 Recursive Calls. Visited Cells=54
---
Avg. time For ZoomIn = 0.013 ms. Path Found in 15 Recursive Calls. Visited Cells=13
---
--------------------------------------------------------------------------------------
  Start Cell: 9:2
  End  Cell: 8:5
------------------------------------------------
Avg. time For DFS  = 0.026 ms. Path Found in 80 Recursive Calls. Visited Cells=28
---
Avg. time For ZoomIn = 0.01 ms. Path Found in 5 Recursive Calls. Visited Cells=5
---
 ......XXXX........................XX....
 ..XXXX....XX..XXXXXX........XX....XXXX..
 XX..........XX....XX..XX........XXXX....
 ........XXXXXX..XXXX............XX..XX..
 XXXXXX..XXXX......XXXX..XX..XX..XX..XXXX
 ..XX......XXXX..XX....XX....XXXXXX......
 ..........XX..............XX........XX..
 ..XXXX......XX....XXXX..........XXXX....
 ....XXXX......XX......XX....XX......XX..
 ..XX..XX......XXXXXXXX..XX........XX....
 ....XX....XX....XXXX....XX..XX..........
 XXXX....XX....XX......XX..XX....XX....XX
 ......XX..XX..........XX............XX..
 ..XX..XXXX......XX..XX......XXXXXX..XXXX
 ......XX..XX..XXDD[]......XX..XX..XXXX..
 ..XXXXXX........XX[]..............XX....
 XXXX........XXXX..[]......XXXXXXXX......
 XX..XX..XX....XX..SS......XXXXXX....XX..
 ....XXXX....XX....XX........XXXXXX..XX..
 ..............XX..XX..XX....XX......XX..
--------------------------------------------------------------------------------------
  Start Cell: 11:2
  End  Cell: 4:4
------------------------------------------------
Avg. time For DFS  = 0.098 ms. Path Found in 374 Recursive Calls. Visited Cells=138
---
Avg. time For ZoomIn = 0.068 ms. Path Found in 150 Recursive Calls. Visited Cells=80
---
--------------------------------------------------------------------------------------
  Start Cell: 13:2
  End  Cell: 7:3
------------------------------------------------
Avg. time For DFS  = 0.097 ms. Path Found in 351 Recursive Calls. Visited Cells=141
---
Avg. time For ZoomIn = 0.074 ms. Path Found in 152 Recursive Calls. Visited Cells=85
---
--------------------------------------------------------------------------------------
  Start Cell: 8:2
  End  Cell: 15:2
------------------------------------------------
Avg. time For DFS  = 0.056 ms. Path Found in 207 Recursive Calls. Visited Cells=77
---
Avg. time For ZoomIn = 0.018 ms. Path Found in 27 Recursive Calls. Visited Cells=18
---
 XXXX..XXXXXX......XXXXXX....XXXX........
 ..XX....XX..XX....XX......XX..XXXXXX....
 XX....XX......XXXX....XXXX......XX......
 XX..XXXX..XXXX........XX......XX..XXXX..
 XXXXXX..XX........XXXX..XX....XX..XX..XX
 ......XX..XXXXXX..........XXXX......XX..
 ..XX..XX........XXXX..........XX....XXXX
 XX..XX..............XX..XX......XX......
 ....XX..XXXX..............XX....XX..XX..
 ..XXXX..........XXXX........XX....XX....
 ..XX..XX......XX......XX..XXXXXX..XX....
 ........XX..XXXX......XX..XXXX......XXXX
 ......XX..XX....XX..XX......XX..XX..XXXX
 ............XXXX......XX....XX..XX..XXXX
 XX..XX........XX........XX....XX....XX..
 ..XX..XX..XX....[][][][]XX..XXXX..XX..XX
 ..XX......XX..XX[]XX..[][]XX......XX....
 ........XXXX..XXSSXX....[][][]DD....XX..
 XX..XX....XXXX[][][]XX....XX........XX..
 ......XX..XX..XX[][][]XXXX..........XX..
End

cimperia · Aug 17, 2015

I was intrigued by the path followed by @Informatix 's AlgoFLM in this post as it looks to me that two paths were explored and one dropped when nearing towards the Destination square, though both would have led to Destination?

The enhancement in speed (relative to DFS that is, as absolute values cannot be sensibly compared) is stunning: nearly 9 times faster.

I have therefore decided to test that very same maze on my device to pit it against my own algorithm: ZoomIn.

The results are not as spectacular as ZoomIn only outperforms DFS by a factor 5. Not bad but still much slower than AlgoFLM. The only consolation is that the path followed, if not optimal, was still pretty efficient.

@Informatix, how on earth do you manage to get such speed gain?

Informatix said:
I promise a very surprising ending to this quiz.

I am looking forward to the answer.

B4X:

Avg. time For DFS  = 0.091 ms. Path Found in 316 Recursive Calls. Visited Cells=112
---
Avg. time For ZoomIn = 0.018 ms. Path Found in 31 Recursive Calls. Visited Cells=28
---
......XX....XX....XX................XX..
..........XX..XXXX......XX..XXXXXX......
XXXX......XX....DD....XXXXXXXX......XX..
XX....XX......XX[]XXXX..XX..XX..XX......
................[]XX[][][]..XX..XX......
....XX..XX....XX[][][]XX[][]..XX....XX..
..XXXX..XXXX......XX....XX[]XX..XX..XXXX
XX......XX......XX........[][]XXXXXXXX..
............XX..XX..XX......[]..........
XXXXXX........XX............[]..XXXX....
XX..XX..XXXXXX....XXXXXX..XX[]....XXXX..
XX..............XX..........[]XXXX......
XX....XX....................[][]..XXXX..
....XX....XX..........XX....XX[]XXXXXXXX
....XX......XX......XX..XXXX[][]XX......
..XXXX..XX........XX..XX[][][]........XX
....XX......XXXX......XX[]............XX
....XXXX..XXXXXXXX..XX..SS..XX....XX....
............XX....XX..XX..XX..........XX
..XX........XX....XX..XX......XX..XX....

RandomCoder · Aug 17, 2015

cimperia said:
I was intrigued by the path followed by @Informatix 's AlgoFLM in this post as it looks to me that two paths were explored and one dropped when nearing towards the Destination square, though both would have led to Destination?

I disagree, I think that only one route was chosen but that it tailed back onto itself. It then had to choose alternative paths and back filled until it found the correct path that led to the destination. This is where it could be optimised as when choosing an alternative path it would have (on this occasion) been preferable to choose a location closest to the destination, but of course this could have taken longer than just testing the route(s)! I've numbered the route I think that the Algo took, its the same route I would expect that my method would take. Albeit a dam site slower

B4X:

My algo:
Avg. time for AlgoFLM=0.078296147 ms
......XX....XX....XX................XX..
..........XX..XXXX......XX..XXXXXX......
XXXX......XX....DD....XXXXXXXX......XX..
XX....XX......XX16XXXX12XX11XX..XX......
................15XX 3 4 5 6XX..XX......
....XX..XX....XX1413 2XX 8 7 10XX....XX..
..XXXX..XXXX......XX 1XX 9XX..XX..XXXX
XX......XX......XX....[][][]..XXXXXXXX..
............XX..XX..XX....[][]..........
XXXXXX........XX............[]..XXXX....
XX..XX..XXXXXX....XXXXXX..XX[]....XXXX..
XX..............XX..........[]XXXX......
XX....XX....................[][]..XXXX..
....XX....XX..........XX....XX[]XXXXXXXX
....XX......XX......XX..XXXX[][]XX......
..XXXX..XX........XX..XX[][][]........XX
....XX......XXXX......XX[]............XX
....XXXX..XXXXXXXX..XX..SS..XX....XX....
............XX....XX..XX..XX..........XX
..XX........XX....XX..XX......XX..XX....

PS. don't forget that some of your time differences could be due to the difference in your device and that which Informatix is using.

Informatix · Aug 17, 2015

RandomCoder said:
I disagree, I think that only one route was chosen but that it tailed back onto itself. It then had to choose alternative paths and back filled until it found the correct path that led to the destination.

Exact.

RandomCoder said:
PS. don't forget that some of your time differences could be due to the difference in your device and that which Informatix is using.

Absolutely.
On my Moto G, my best algorithm is 2x faster than the basic DFS. On a different device, this factor can be higher or lower. On a device emulated with Genymotion, the difference is a bit disappointing but always in favor of my algorithm. Among the reasons, you have the CPU, the memory chips quality, the memory size (when small, the GC is frequently called)... You can easily see one of these differences due to the CPU by comparing a division with the corresponding multiplication on different devices, e.g. on my MotoG, "myfloat / 5" is 3 x slower than "myfloat * 0.2", but on another device I see almost no difference.
If you want to compare your algo to mine, post your code and I'll run it on my Moto G.

Informatix · Aug 17, 2015

I created a complete benchmark for the algorithms of this quiz. The number of obstacles varies, the orientation varies, the distance between the two points varies, etc., and all results are summed. With this benchmark, I can see that one of my algorithms performs better in an open space (where DFS is very bad) than in a very crowded grid, but it still outperforms the DFS overall.
Example of result on my Moto G:
----- TOTAL -----
Sum algo DFS = 17.673 ms / Worst = 0.22 ms
Sum algo FLM (simple) = 10.526 ms / Worst = 0.09 ms
Sum algo FLM (advanced) = 9.931 ms / Worst = 0.18 ms

cimperia · Aug 17, 2015

OK, I've just realised that to replicate the FLM path for that specific maze, all I had to do was to modify my algo as to privilege moving the X axis, instead of Y when dx = dy.

I ran it and here's the result:

B4X:

Avg. time For DFS  = 0.118 ms. Path Found in 316 Recursive Calls. Visited Cells=112
---
Avg. time For ZoomIn = 0.023 ms. Path Found in 50 Recursive Calls. Visited Cells=36
---
 ......XX....XX....XX................XX..
 ..........XX..XXXX......XX..XXXXXX......
 XXXX......XX....DD....XXXXXXXX......XX..
 XX....XX......XX[]XXXX[]XX[]XX..XX......
 ................[]XX[][][][]XX..XX......
 ....XX..XX....XX[][][]XX[][][]XX....XX..
 ..XXXX..XXXX......XX[][]XX[]XX..XX..XXXX
 XX......XX......XX....[][][]..XXXXXXXX..
 ............XX..XX..XX....[][]..........
 XXXXXX........XX............[]..XXXX....
 XX..XX..XXXXXX....XXXXXX..XX[]....XXXX..
 XX..............XX..........[]XXXX......
 XX....XX....................[][]..XXXX..
 ....XX....XX..........XX....XX[]XXXXXXXX
 ....XX......XX......XX..XXXX[][]XX......
 ..XXXX..XX........XX..XX[][][]........XX
 ....XX......XXXX......XX[]............XX
 ....XXXX..XXXXXXXX..XX..SS..XX....XX....
 ............XX....XX..XX..XX..........XX
 ..XX........XX....XX..XX......XX..XX....

Informatix · Aug 17, 2015

cimperia said:
OK, I've just realised that to replicate the FLM path for that specific maze, all I had to do was to modify my algo as to privilege moving the X axis, instead of Y when dx = dy.

You probably have the same algorithm as mine now. The difference is how it's written with B4A and that can make a big difference.

cimperia · Aug 17, 2015

Informatix said:
You probably have the same algorithm as mine now. The difference is how it's written with B4A and that can make a big difference.

Very possibly we have the same logic (simple really) and I agree that the BA4 coding will make the difference.

As I have been using a walled array of 22 X 22 instead of the 20 x 20, I'll modify the algo accordingly before posting it tomorrow (though it's going to make it look even uglier) so that you can run it on your Motorola without change to your data structures.

I'll run your benchmark later on my phone.

RandomCoder · Aug 17, 2015

I have a really, really embarrassing confession to make

, so embarrassing that maybe I shouldn't share it, but I'm hopeful that it's happened to even the best of you out there.
All this time I've been struggling to achieve times even close to the standard DFS routine which Informatics posted, and frequently I'm a factor of 10 out even though I've achieved the destination in significantly less moves

. I also had the problem, as mentioned earlier, that quite often the time taken to solve the maze didn't display. Strange I thought but nothing to get worried about. I wish I'd looked into it further!
Just about to give up thinking that there was no way I could even get marginally close to your times, even having gone to the drastic measure of making all my variables Global just in case the declarations inside of my routine were adding extra overhead, I came across the culprit!
On the next to last line of my routine, just before the Loop statement I had this...

B4X:

Log("")

I seem to recall that I only added it to place a breakpoint at the end of the loop whilst debugging

You can imagine my frustration

Oh well, at least I now have a reasonably quick solution to share. It's not pretty though

cimperia · Aug 17, 2015

Here are the results of the benchmark. I am not sure that I understand what they mean though. I'll have to read the benchmark code.

Alcatel POP'C5 (Don't laugh

)

B4X:

Sum algo DFS  = 17.828 ms / Worst = 0.33 ms
Sum algo ZoomIn = 8.898 ms / Worst = 0.336 ms

cimperia · Aug 17, 2015

OK, I have cleaned up the Algo. It looks pretty ugly and repetitive but I have found out that it was the only way to extract the max speed out of it. I used to populate an array with values (EAST, WEST ...) according to the decisions made and later on iterate it but it was taking too long.

B4X:

Sub Globals
   '....
   'My Algo Variables
   Dim dx, dxa, dy, dya As Short
End Sub

Sub ZoomIn (x As Int, y As Int) As Boolean  
'     counter = counter + 1

     'Accept Case - we found the Destination
     If x = DestX And y = DestY Then
       Visited(x, y) = True
       Return True
     End If
  
     'Reject Case - we hit a block|wall Or our path
     If Blocked(x, y) Or Visited(x, y) Then Return False
     '
     Visited(x, y) = True

     dx = DestX - x
     dy = DestY - y

     If dx < 0 Then dxa = -dx Else dxa = dx
     If dy < 0 Then dya = -dy Else dya = dy
  
     If (dxa > dya) Then ' Move along the X axis
       If dx > 0 Then     ' Try East first
'         Order(0) = EAST
         If x < SizeX -1 And Not(Blocked(x+1, y)) Then
           If ZoomIn(x+1, y) Then Return True
         End If      
         If dy > 0 Then
'           Order(1) = SOUTH
           If y < SizeY - 1 And Not(Blocked(x, y+1)) Then
             If ZoomIn(x, y+1) Then Return True
           End If
'           Order(2) = NORTH
           If y > 0 And Not(Blocked(x, y-1)) Then
             If ZoomIn(x, y-1) Then Return True
           End If            
         Else
'           Order(1) = NORTH
           If Y > 0 And Not(Blocked(x, y-1)) Then
             If ZoomIn(x, y-1) Then Return True
           End If
'           Order(2) = SOUTH  
           If y < SizeY - 1 And Not(Blocked(x, y+1)) Then
             If ZoomIn(x, y+1) Then Return True
           End If
         End If
'         Order(3) = WEST
         If x > 0 And Not(Blocked(x-1, y)) Then
           If ZoomIn(x-1, y) Then Return True
         End If
       Else                ' Try West first
'         Order(0) = WEST
         If x > 0 And Not(Blocked(x-1, y)) Then
           If ZoomIn(x-1, y) Then Return True
         End If        
         If dy > 0 Then
'           Order(1) = SOUTH
           If y < SizeY - 1 And Not(Blocked(x, y+1)) Then
             If ZoomIn(x, y+1) Then Return True
           End If
'           Order(2) = NORTH
           If Y > 0 And Not(Blocked(x, y-1)) Then
             If ZoomIn(x, y-1) Then Return True
           End If            
         Else
'           Order(1) = NORTH
           If Y > 0 And Not(Blocked(x, y-1)) Then
             If ZoomIn(x, y-1) Then Return True
           End If
'           Order(2) = SOUTH  
           If y < SizeY - 1 And Not(Blocked(x, y+1)) Then
             If ZoomIn(x, y+1) Then Return True
           End If
         End If
'         Order(3) = EAST
         If x < SizeX -1 And Not(Blocked(x+1, y)) Then
           If ZoomIn(x+1, y) Then Return True
         End If      
       End If  
     Else                ' Move along the Y axis
       If dy > 0 Then     ' Try South first
'         Order(0) = SOUTH
         If y < SizeY - 1 And Not(Blocked(x, y+1)) Then
           If ZoomIn(x, y+1) Then Return True
         End If
         If dx < 0 Then
'           Order(1) = WEST
           If X > 0 And Not(Blocked(x-1, y)) Then
             If ZoomIn(x-1, y) Then Return True
           End If
'           Order(2) = EAST
           If x < SizeX -1 And Not(Blocked(x+1, y)) Then
             If ZoomIn(x+1, y) Then Return True
           End If
         Else
'           Order(1) = EAST
           If x < SizeX -1 And Not(Blocked(x+1, y)) Then
             If ZoomIn(x+1, y) Then Return True
           End If
'           Order(2) = WEST    
           If X > 0 And Not(Blocked(x-1, y)) Then
             If ZoomIn(x-1, y) Then Return True
           End If
         End If
'         Order(3) = NORTH
         If Y > 0 And Not(Blocked(x, y-1)) Then
           If ZoomIn(x, y-1) Then Return True
         End If    
       Else  ' Try North first
'         Order(0) = NORTH
         If Y > 0 And Not(Blocked(x, y-1)) Then
           If ZoomIn(x, y-1) Then Return True
         End If      
         If dx < 0 Then
'           Order(1) = WEST
           If X > 0 And Not(Blocked(x-1, y)) Then
             If ZoomIn(x-1, y) Then Return True
           End If
'           Order(2) = EAST
           If x < SizeX -1 And Not(Blocked(x+1, y)) Then
             If ZoomIn(x+1, y) Then Return True
           End If
         Else
'           Order(1) = EAST
           If x < SizeX -1 And Not(Blocked(x+1, y)) Then
             If ZoomIn(x+1, y) Then Return True
           End If
'           Order(2) = WEST    
           If X > 0 And Not(Blocked(x-1, y)) Then
             If ZoomIn(x-1, y) Then Return True
           End If
         End If
'         Order(3) = SOUTH  
         If y < SizeY - 1 And Not(Blocked(x, y+1)) Then
           If ZoomIn(x, y+1) Then Return True
         End If  
       End If
     End If
  
     'Deadend - this location can't be part of path
     Return False
End Sub

Android Question Quiz "Is there a path ?"

Expert

Attachments

Expert

Expert

Well-Known Member

Expert

Well-Known Member

Expert

Well-Known Member

Active Member

Well-Known Member

Active Member

Active Member

Well-Known Member

Expert

Expert

Attachments

Active Member

Expert

Active Member

Well-Known Member

Active Member

Active Member

Similar Threads