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............

 

[LucaMs]

Damn, I love quizzes, but today I'm very bad.

I have not read it well.

Can you use the Spoiler, please?

Thank you

 

[EnriqueGonzalez]

do you have a Deadline?

 

[Informatix]

Damn, I love quizzes, but today I'm very bad.

I have not read it well.

Can you use the Spoiler, please?

Thank you

To explain more simply: the first goal is to say if starting from a cell I can reach another cell (my destination) by moving only horizontally and vertically. Blocked cells cannot be crossed. This goal is very easy to achieve. The second goal is to beat my own algorithm. The difficulty lies here.
At start, I wanted to include this into a tutorial but I thought that would be more interesting to see whether people have better solution than mine.

 

[Informatix]

do you have a Deadline?

No. That can last weeks if needed. I'm on vacation in a few days so...

 

[LucaMs]

To explain more simply: the first goal is to say if starting from a cell I can reach another cell (my destination) by moving only horizontally and vertically. Blocked cells cannot be crossed. This goal is very easy to achieve. The second goal is to beat my own algorithm. The difficulty lies here.
At start, I wanted to include this into a tutorial but I thought that would be more interesting to see whether people have better solution than mine.

Thank you for further explanation, @Informatix (I had read only the first part only, then I had to leave).

Now I feel better (painkiller).

Too bad that you have not even prepared a layout

However, it is obvious that my code will take less time than yours

(Even I do not believe in what I say/write, and not also this time )

 

[RandomCoder]

To explain more simply: the first goal is to say if starting from a cell I can reach another cell (my destination) by moving only horizontally and vertically. Blocked cells cannot be crossed. This goal is very easy to achieve. The second goal is to beat my own algorithm. The difficulty lies here.
At start, I wanted to include this into a tutorial but I thought that would be more interesting to see whether people have better solution than mine.

I have no idea how I'm going to approach the problem yet but I intend to give it some thought.

The first question... is the vertical direction limited to only moving forward as shown in your example, or, if the only clear path requires it to travel past the row containing the destination then move across and back down to reach the destination is this to be considered?

 

[EnriqueGonzalez]

I have no idea how I'm going to approach the problem yet but I intend to give it some thought.

The first question... is the vertical direction limited to only moving forward as shown in your example, or, if the only clear path requires it to travel past the row containing the destination then move across and back down to reach the destination is this to be considered?

i also was going for the up-forward approach as Y in start is fixed and is always desty > starty, but because the map is randomly created, it is not posible, if the very first up neighbord is blocked, you will need to go down, not even that, you could reach a cave after several attempts by going up.

or am i wrong?

 

[RandomCoder]

My initial thought was to slide each section across (think bit shift left until a clear path was found or shifted all 20 possibilities and no route available)...

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............

But having searched Google as @Informatix suggested I reckon he's probably thinking of an algorithm based solution like A* maybe. This will find any possible route having the least resistance. I don't fully understand yet and its getting late but I plan to have another look tomorrow.

 

[EnriqueGonzalez]

I made a research too and it seems that In order to be faster than him is not by using A* but a better algorithm: Orthogonal JSP with Manhattan Heuristics. But it is easier said than done.

 

[RandomCoder]

I made a research too and it seems that In order to be faster than him is not by using A* but a better algorithm: Orthogonal JSP with Manhattan Heuristics. But it is easier said than done.

The challenge is not only beating @Informatix but also trying to interpret the mathematics involved

 

[Informatix]

I have no idea how I'm going to approach the problem yet but I intend to give it some thought.

The first question... is the vertical direction limited to only moving forward as shown in your example, or, if the only clear path requires it to travel past the row containing the destination then move across and back down to reach the destination is this to be considered?

No, you can move in all directions, one cell at a time, and turn around the destination if it's a possible path. And your code must be able to solve the same problem with any location of the starting and ending cells. My own benchmark rotates the maze to test the code when going from left to right.

 

[Informatix]

i also was going for the up-forward approach as Y in start is fixed and is always desty > starty, but because the map is randomly created, it is not posible, if the very first up neighbord is blocked, you will need to go down, not even that, you could reach a cave after several attempts by going up.

or am i wrong?

No, you're right. And avoiding the bias of promoting the upwards move is recommended.

This problem is the typical problem that you have to solve in many games when something blocks the path of your sprite. You have to find another route in a very short span of time. If there's a route, it moves. If there's none, it waits until there's one.

 

[Informatix]

ut having searched Google as @Informatix suggested I reckon he's probably thinking of an algorithm based solution like A* maybe. This will find any possible route having the least resistance. I don't fully understand yet and its getting late but I plan to have another look tomorrow.

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.

 

[Troberg]

OK, I don't have time to do it at the moment, but my algoritm would basically be a recursive flood fill.

In pseudocode:

CheckCell(StartCell)

Sub CheckCell(Cell)
  Fill Cell
  For each neighboring cell
    If neighboring cell is DestinationCell then PathExist
    If neighboring cell is empty and not filled then CheckCell(NeighboringCell)
  Next
End Sub

A nice side effect is that, with very little modification, you will also get the length of the shortest path, simply by counting recursion depth.

 

[Informatix]

OK, I don't have time to do it at the moment, but my algoritm would basically be a recursive flood fill.

In pseudocode:

CheckCell(StartCell)

Sub CheckCell(Cell)
  Fill Cell
  For each neighboring cell
    If neighboring cell is DestinationCell then PathExist
    If neighboring cell is empty and not filled then CheckCell(NeighboringCell)
  Next
End Sub

A nice side effect is that, with very little modification, you will also get the length of the shortest path, simply by counting recursion depth.

Yes, it's a good idea. This algorithm is called "Depth-First Search" (Flood-Fill is a bit different and serves a different purpose). You won't get the length of the shortest path by counting the recursion depth but only the length of your path.
Now, you have to write your DFS in B4A. Even properly written, you will be still far from the performance of my algo, but it's a solid basis.

 

[Informatix]

The DFS algo compared to my algo in a complex maze:

DFS
Avg. time for rDFS=0.6752383839999999 ms
 [][][]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....

My algo:
Avg. time for AlgoFLM=0.078296147 ms
 ......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....

 

[Troberg]

You won't get the length of the shortest path by counting the recursion depth but only the length of your path.

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

Edit: Scratch that. I was tired. If I made it tail recursive, my comment would be true, but, as it stands, it's not.

Now, you have to write your DFS in B4A. Even properly written, you will be still far from the performance of my algo, but it's a solid basis.

It will be slow, and, more importantly, being recursive, will probably break the stack on larger maps. Still, it's probably the simplest solution to write and understand.

 

[JordiCP]

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)

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

 

[Informatix]

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.