Android Java shortest path from two indexes on gridview

Question

If I have two points gather from onClick and they come as indexes or positions on the grid, how can I calculate weather to go up, down, left and right, diagonals are not allowed for the shortest route to the other point? So if i have pointA and pointB and point B is trying to get to pointA in the shortest path and I would recalculate this after every movement because pointA will move after movment from point B. What I have started to write is to find the adjacent positions around pointB without diagonals so points that are on edge will have less options obviously but how do I determine right movement with choices of neighboring squares? Should pointB go up,down,left and down preferably using indexes? I'm indexing from zero and its 11 by 11 grid so 11 columns. Something I just thought of is deal with choices that have the same distance, to select at random between them.

0  1   2  3  4 ...
11 12 13 14 15 ...
22 23 24 25 16 ...
33 34 35 36 37 ...
etc...

I find array of indexes that I now can try to pick for the shortest path

Integer[] getAdjacentPositions(int position) 
{ 
   /*This will return integer array of positions that adjacent to position that is
    pass through that are not diagonal.*/ 

    Integer[] columnRow = new Integer[8];
    int columns = 11;
    int column = (position % columns);
    int row = (position / columns);
    int numberedges = 0;

    Log.d(TAG, "position inside of isedgeitem is " + position );
    Log.d(TAG, "row is " + row );
    Log.d(TAG, "column is " + column );

    for (int rowOffset = -1; rowOffset <= 1; rowOffset++) 
    {
        final int actRow = row + rowOffset;

        for (int columnOffset = -1; columnOffset <= 1; columnOffset++) 
        {
            final int actColumn = column + columnOffset;

            if (actRow >= 0 && actRow < 11 && actColumn >= 0 && actColumn < 11) 
                {
                    if (!isOneOfDiagonals(position, (actColumn + actRow * columns)))
                        {
                            columnRow[numberedges]= actColumn + actRow * columns; 
                            numberedges++;
                        }
                    Log.d(TAG, " actColumn" + actColumn );
                    Log.d(TAG, " actRow" + actRow );

                }

        }
    }

    return columnRow;


}

Now what to do with this array of Int Indexes to find the shortest path

shortestnextposition(Integer[] positions, int pointA )
    {

    return int position;


    }

Answer 1

If I understand correctly the problem:

• Difference between X positions of A and B : dX = Math.abs(ax - bx)
• Difference between Y positions of A and B : dY = Math.abs(ay - by)
• The shortest distance is : dX + dY

The problem with the shortest path is you can have different ways which uses the number of moves shortest distance. But you can code a preference in this move, for example, if you have to go from 0 to 24, the shortest distance is 3 and you have 3 shortest possible ways:

• [0,11,22,23]
• [0,1,12,23]
• [0,11,12,23]

I suppose you want to use the third possibility?

For that, compare dX and dY and move in the greater dimension, if dX > dY, move X, if dY > dX, moveY

---

Update : try this

public static int[] shortestPath(int x, int a, int b) {
    int ax = a % x, ay = a / x, bx = b % x, by = b / x;
    int[] path = new int[Math.abs(ax - bx) + Math.abs(ay - by) + 1];
    for (int i = 0; i < path.length; i++)
        path[i] = a = i == 0 ? a : getAdjacentInDirectionOf(x, a, b);
    return path;
}

public static int getAdjacentInDirectionOf(int x, int a, int b) {
    int ax = a % x, ay = a / x, bx = b % x, by = b / x;
    int dx = Math.abs(ax - bx), dy = Math.abs(ay - by);
    if (dx >= dy) return (int) (ax + Math.signum(bx - ax) + ay * x);
    else return (int) (ax + (ay + Math.signum(by - ay)) * x);
}

---

Update : replace shortestPath() method from previous by this one to avoid first case

public static int[] shortestPath(int x, int a, int b) {
    int ax = a % x, ay = a / x, bx = b % x, by = b / x;
    int[] path = new int[Math.abs(ax - bx) + Math.abs(ay - by)];
    for (int i = 0; i < path.length; i++)
        path[i] = a = getAdjacentInDirectionOf(x, a, b);
    return path;
}