An efficient way to get and store the shortest paths

Question

When I say efficient I mean code that isn't cpu intensive.

The Problem: I have a field of blocks. Like in the following image:

Every single one of these blocks represents an instance of a self-made Block class. This block class has a List<Block> neighBours, where the neighbours of the block are stored. So every single block in the image knows which blocks are next to it.

What I want to do is to pick any block from this image, and compute how many "steps" away this block is. For example if I pick the block in the top left, I want to have a Map<Block, Integer> representing how many "steps" away each block is from the picked block. Like this:

Now before you say "Just store it's position X and Y in the block class and calculate the difference X + difference Y", that wouldn't work because the field can have gaps(represented by red color) between them like the following image:

And as you might notice, the block next to the gap that was first 4 steps away, is now 6 steps away. Thus the best way(I presume) to get how many steps away the other blocks are is by using a recursive algorith that makes use of the neighbour info. I couldn't make an efficient one myself and I was hoping someone might know something that works well.

Several problems I came across are the fact that because all blocks know their neighbours, the recursive algorithm would go indefinately back and forth between the first and second block. Or the fact that when using the algorithm on a 11x11 field, there were 3284 method calls, which seems waaay too high for an 11x11 field.

Question: So the question I have is: What is an efficient way, using the knowledge of what neighbours each block has, to get how many steps away each block is.

Code: This is the current code that I have incase anyone wants to see it.

public class Block
{
    List<Block> neighBours;
    public Block(List<Block> neighBours)
    {
        this.neighBours = neighBours;
    }
    public Map<Block, Integer> getStepsAway()
    {
        Map<Block, Integer> path = new HashMap<Block, Integer>();
        getPaths(path, 0, 100);
        return path;
    }
    public void getPaths(Map<Block, Integer> path, int pathNumber, int maxPathNumber)
    {           
        if(pathNumber <= maxPathNumber)
        {
            for(Block block : neighBours)
            {
                Integer thePathNumber = path.get(block);
                if(thePathNumber != null)
                {
                    if(pathNumber < thePathNumber)
                    {
                        path.put(block, pathNumber);
                        block.getPaths(path, pathNumber + 1, maxPathNumber);
                    }
                }
                else
                {
                    path.put(block, pathNumber);
                    block.getPaths(path, pathNumber + 1, maxPathNumber);
                }
            }
        }
    }
}

Answer 1

Recursive algorithms are doomed to fail on a large grid. Java is not designed for deep recursions and can only withstand a few thousands recursive calls before failing with a StackOverflowException. Only iterative solutions are a reasonible approach for large pathfinding problems in Java.

Of course you can always use a classic pathfinding algorithm such as A*, but you would have to apply it for each cell, which would be extremely expensive.

Indeed, your problem is a bit particular in the sense you want to calculate the minimum distance to all cells and not only just one. Therefore, you can do it in a more clever way.

One property of your problem is that given A and B, if the minimal path from A to B contains C then this path is also minimal from A to C and from C to B. That's what my intuition tells me, but it would need to be proven before implementing my suggestion.

The algorithm I propose is efficient, uses O(n) memory and has O(n^2) runtime complexity (cannot be faster since you need to set this many cells in the array):

• start with your first point and set the distance of all its valid neighbours to 1. Doing so, you will record the border, which is all the cells at distance 1 from the first cell.
• then, you iterate over the border and take all their neighbours which have not already been assigned a distance and assign them distance 2. All cells of distance 2 become your new border.
• iterate until the border is empty

Below is a full working solution. The code may be improved in various ways using more convenience methods for initializing and printing matrices of objects and primitive integers, but you get the idea:

public class Solution {
    public enum Cell { FREE, BLOCKED }

    // assuming cells is a rectangular array with non-empty columns
    public static int[][] distances(Cell[][] cells, ArrayCoordinate startingPoint) {
        int[][] distances = new int[cells.length][cells[0].length];
        // -1 will mean that the cell is unreachable from the startingPoint
        for (int i = 0; i < cells.length; i++) {
            for (int j = 0; j < cells[0].length; j++) {
                distances[i][j] = -1;
            }
        }
        distances[startingPoint.i][startingPoint.j] = 0;

        Set<ArrayCoordinate> border = startingPoint.validNeighbours(cells);
        for (int currentDistance = 1; !border.isEmpty(); currentDistance++) {
            Set<ArrayCoordinate> newBorder = new HashSet<>();
            for (ArrayCoordinate coord : border) {
                distances[coord.i][coord.j] = currentDistance;

                for (ArrayCoordinate neighbour : coord.validNeighbours(cells)) {
                    if (distances[neighbour.i][neighbour.j] < 0) {
                        newBorder.add(neighbour);
                    }
                }
            }
            border = newBorder;
        }

        return distances;
    }

    private static class ArrayCoordinate {
        public ArrayCoordinate(int i, int j) {
            if (i < 0 || j < 0) throw new IllegalArgumentException("Array coordinates must be positive");
            this.i = i;
            this.j = j;
        }

        public final int i, j;

        public Set<ArrayCoordinate> validNeighbours(Cell[][] cells) {
            Set<ArrayCoordinate> neighbours = new HashSet<>();

            // inlining for not doing extra work in a loop iterating over (-1, 1) x (-1, 1). If diagonals are allowed
            // then switch for using a loop
            addIfValid(cells, neighbours,  1,  0);
            addIfValid(cells, neighbours, -1,  0);
            addIfValid(cells, neighbours,  0,  1);
            addIfValid(cells, neighbours,  0, -1);

            return neighbours;
        }

        private void addIfValid(Cell[][] cells, Set<ArrayCoordinate> neighbours, int dx, int dy) {
            int x = i + dx, y = j + dy;
            if (0 <= x && 0 <= y && x < cells.length && y < cells[0].length && cells[x][y] == Cell.FREE) {
                neighbours.add(new ArrayCoordinate(i + dx, j + dy));
            }
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            ArrayCoordinate point = (ArrayCoordinate) o;

            if (i != point.i) return false;
            if (j != point.j) return false;

            return true;
        }

        @Override
        public int hashCode() {
            int result = i;
            result = 31 * result + j;
            return result;
        }
    }

    public static void main(String[] args) {
        int n = 11, m = 5;

        Cell[][] cells = new Cell[n][m];
        cells[1][1] = Cell.BLOCKED;
        cells[1][2] = Cell.BLOCKED;
        cells[2][1] = Cell.BLOCKED;

        ArrayCoordinate startingPoint = new ArrayCoordinate(5, 2);

        System.out.println("Initial matrix:");
        for (int i = 0; i < cells.length; i++) {
            for (int j = 0; j < cells[0].length; j++) {
                if (cells[i][j] == null) {
                    cells[i][j] = Cell.FREE;
                }
                if (startingPoint.i == i && startingPoint.j == j) {
                    System.out.print("S ");
                } else {
                    System.out.print(cells[i][j] == Cell.FREE ? ". " : "X ");
                }
            }
            System.out.println();
        }

        int[][] distances = distances(cells, startingPoint);
        System.out.println("\nDistances from starting point:");
        for (int i = 0; i < distances.length; i++) {
            for (int j = 0; j < distances[0].length; j++) {
                System.out.print((distances[i][j] < 0 ? "X" : distances[i][j]) + " ");
            }
            System.out.println();
        }
    }
}

Output:

Initial matrix:
. . . . . 
. X X . . 
. X . . . 
. . . . . 
. . . . . 
. . S . . 
. . . . . 
. . . . . 
. . . . . 
. . . . . 
. . . . . 

Distances from starting point:
7 8 7 6 7 
6 X X 5 6 
5 X 3 4 5 
4 3 2 3 4 
3 2 1 2 3 
2 1 0 1 2 
3 2 1 2 3 
4 3 2 3 4 
5 4 3 4 5 
6 5 4 5 6 
7 6 5 6 7 

Bonus

I almost cried when I saw all this boilerplate in my Java solution, so I wrote a shorter (perhaps slightly less efficient) version in Scala:

object ScalaSolution {
  sealed abstract  class Cell
  object Free    extends Cell
  object Blocked extends Cell

  // assuming cells is a rectangular array with non-empty columns
  def distances(cells: Array[Array[Cell]], startingPoint: (Int, Int)) = {
    // -1 will mean that the cell is unreachable from the startingPoint
    val distances = Array.fill[Int](cells.length, cells(0).length)(-1)
    distances(startingPoint._1)(startingPoint._2) = 0

    var (currentDistance, border) = (1, validNeighbours(cells, startingPoint))
    while (border.nonEmpty) {
      border.foreach { case (i, j) => distances(i)(j) = currentDistance }
      border = border.flatMap(validNeighbours(cells, _)).filter { case (i, j) => distances(i)(j) < 0 }
      currentDistance += 1
    }

    distances
  }

  private def validNeighbours(cells: Array[Array[Cell]], startingPoint: (Int, Int)) = {
    // inlining for not doing extra work in a for yield iterating over (-1, 1) x (-1, 1). If diagonals are allowed
    // then switch for using a for yield
    Set(neighbourIfValid(cells, startingPoint, ( 1,  0)),
        neighbourIfValid(cells, startingPoint, (-1,  0)),
        neighbourIfValid(cells, startingPoint, ( 0,  1)),
        neighbourIfValid(cells, startingPoint, ( 0, -1)))
      .flatten
  }

  private def neighbourIfValid(cells: Array[Array[Cell]], origin: (Int, Int), delta: (Int, Int)) = {
    val (x, y) = (origin._1 + delta._1, origin._2 + delta._2)
    if (0 <= x && 0 <= y && x < cells.length && y < cells(0).length && cells(x)(y) == Free) {
      Some(x, y)
    } else None
  }

  def main (args: Array[String]): Unit = {
    val (n, m) = (11, 5)

    val cells: Array[Array[Cell]] = Array.fill(n, m)(Free)
    cells(1)(1) = Blocked
    cells(1)(2) = Blocked
    cells(2)(1) = Blocked

    val startingPoint = (5, 2)
    println("Initial matrix:")
    printMatrix(cells)((i, j, value) => if ((i, j) == startingPoint) "S" else if (value == Free) "." else "X")

    val distancesMatrix = distances(cells, startingPoint)
    println("\nDistances from starting point:")
    printMatrix(distancesMatrix)((i, j, value) => if (value < 0) "X" else value.toString)
  }

  private def printMatrix[T](matrix: Array[Array[T]])(formatter: (Int, Int, T) => String) = {
    for (i <- 0 until matrix.length) {
      for (j <- 0 until matrix(0).length) {
        print(formatter(i, j, matrix(i)(j)) + " ")
      }
      println()
    }
  }
}

Answer 2

I believe there is a DP (dynamic programming) solution to this problem, looking at this, code below. I realize this is for finding all possible paths to a cell but it can give insight on your condition about 'blanks' or 'walls'

#include <iostream>
using namespace std;

// Returns count of possible paths to reach cell at row number m and column
// number n from the topmost leftmost cell (cell at 1, 1)
int numberOfPaths(int m, int n)
{
    // Create a 2D table to store results of subproblems
    int count[m][n];

    // Count of paths to reach any cell in first column is 1
    for (int i = 0; i < m; i++)
        count[i][0] = 1;

    // Count of paths to reach any cell in first column is 1
    for (int j = 0; j < n; j++)
        count[0][j] = 1;

    // Calculate count of paths for other cells in bottom-up manner using
    // the recursive solution
    for (int i = 1; i < m; i++)
    {
        for (int j = 1; j < n; j++)

            // By uncommenting the last part the code calculatest he total
            // possible paths if the diagonal Movements are allowed
            count[i][j] = count[i-1][j] + count[i][j-1]; //+ count[i-1][j-1];

    }
    return count[m-1][n-1];
}