Dijkstra or A* on 10x10 Grid with obstacles which are random, starting point on 0,0 end on 9,9?

Question

I have a 2D Array which has

1 0 1 1 1 1 1 1 1 1 
1 1 0 0 1 1 1 1 1 1 
1 1 1 0 1 1 1 1 1 0 
1 1 1 1 1 1 1 1 1 0 
1 0 1 1 1 0 1 0 1 1 
1 1 0 1 0 1 0 0 1 1 
1 1 0 1 1 0 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 0 1 1 1 1 
1 1 1 1 1 1 0 1 1 1 

1 represent open 0 represent close

The 0's can be random and user get to choose the start point and end point.

I understand how to get all open cell by 2 nested for loop, and store them into Arraylist of points.

Now I need to find the shortest path, but A* or Djakstra are confusing

Say for example my starting point is 0,0 and my end point is 9,9, how do I get the shortest path?

I come up with this so far to get open cell:

//Check empty cells in the grid  and color them in YELLOW
for (int i = 0; i < MyMatrix.length; i++) {
    for (int j = 0; j < MyMatrix.length; j++) {
        if (MyMatrix[j][i]) {
            StdDraw.setPenColor(StdDraw.YELLOW);
            StdDraw.filledSquare(i, N - j - 1, .1);

        }
    }

}

//add all empty coordinates to array list of points
for (int i = 0; i < MyMatrix.length; i++) {
    for (int j = 0; j < MyMatrix.length; j++) {
        if (MyMatrix[i][j]) {
            coordinates.add(new Point(i, j));

        }
    }
}

But then how do I check the shortest path?

Answer 1

You can use A*, Dijkstra or BFS to find the shortest path. That involves transforming your matrix into a graph, such that any adjacent cells in the matrix are adjacent in the graph. It's not hard, but I can understand why you might find it a little confusing.

However, if you are looking for a simpler solution, I'll suggest Lee's algorithm. Lee's algorithm is based on BFS, but I find it somewhat simpler to understand. It's a lot like flood fill.

The algorithm looks something like this :

Consider matrix A of size n by m, and another matrix D of the same size.
Pick starting point S.
Set D[S.y][S.x] to 1.
Add S into a queue Q.
while Q isn't empty:
      get point from top of the queue, call it T, pop the queue
      for all adjacent cells P of T:
              if cell P is visitable:
                     D[P.y][P.x]=D[T.y][T.x]+1
                     push P into queue
The minimum distance from the starting point to any other point P will be found in D[P.y][P.x].
If P can't be reached, then D[p.y][p.x]=0.
To find the actual path, you need to backtrack from the end point to the starting point, by going through the cells of D in a descending order.