Shortest Path Algorithm (With Java Examples)

How does a sat-nav system find the shortest path from start to destination? How do bot opponents orient themselves in first-person shooters? This series of articles on shortest path algorithms (and more generally: pathfinding algorithms) will address these questions.

This first article covers the following topics:

• What is the difference between "Shortest Path" and "Pathfinding"?
• Which shortest path algorithms exist?
• How to find the shortest path between two points in a maze?

You can find the source code for the article in my GitHub repository.

Shortest Path or Pathfinding?

A shortest path algorithm solves the problem of finding the shortest path between two points in a graph (e.g., on a road map). The term "short" does not necessarily mean physical distance. It can also be time (freeways are preferred) or cost (toll roads are avoided), or a combination of multiple factors.

Graphs can be very complex and contain millions of nodes and edges (for example, in a video game world where hundreds or thousands of characters can move around freely), so finding the optimal path would be very time-consuming.

For certain applications, it is sufficient to find a reasonably short (or even any) way. That is then generally referred to as pathfinding.

Shortest Path Algorithms

The best known shortest path algorithms are:

• Dijkstra's algorithm
• the A* search algorithm (pronounced "A Star")
• the Bellman-Ford algorithm
• the Floyd-Warshall algorithm

On two-dimensional, tile-based maps, such as those used in early computer games, we can also use a form of breadth-first search known as the Lee algorithm.

In the remaining part of this article, I explain an optimized version of the Lee algorithm using an example with animations and Java source code.

Maze Algorithm: How to Find the Shortest Path in a Labyrinth?

My favorite example for solving the shortest path problem is the game "FatCat" on the HP-85, a computer from the 1980s. My uncle let me experiment with this computer as a child.

The mission was (like in Pac-Man) to let a mouse eat all the cheese pieces in a maze – without being eaten by the cat. The difficult part was (apart from the control with only two buttons to turn the mouse left and right) that the cat (unlike the ghosts in Pac-Man) always took the shortest path to the mouse.

Only through a mouse hole, connecting the left and right edge, one could evade the cat. Besides, the mouse could be beamed to a different location once per lifetime – which was incredibly helpful in dead ends:

At that time (I was about ten years old), I was already interested in programming and wanted to reprogram the game on my C64. I had quickly implemented the display of the mazes and the control of the mouse. But calculating the shortest path between cat and mouse caused me headaches for months.

In the end, I solved it – as I was to find out years later in my computer science studies – with a variant of the Lee algorithm. Without knowledge of this algorithm, I had developed an optimized variant of it, which I will present step by step in the following chapters.

Optimized Lee Algorithm

The Lee algorithm has the disadvantage that in the end, you have to go back all the way ("backtrace") to find out which direction the cat has to take.

Furthermore, the algorithm does not specify how to find the "neighbors of points marked with i". It would be quite slow to search the whole labyrinth at every step. At this point, I use a queue known from the breadth-first search to store the fields to process in the next step.

The following images and animations use the labyrinth shown above with the cat at position (15,7) and the mouse at position (11,5). The coordinate system starts at the upper left corner of the labyrinth with (0,0).

Preparation

The maze is stored in a two-dimensional boolean array called lab. Walls are identified by the value true. Keeping the outer wall in this array simplifies the code, which does not need separate checks for reaching the edges.

To avoid running in circles, we create another two-dimensional boolean array named discovered, in which those fields are marked, which we have already discovered during the search. The current position of the cat is initially set to true.

I have colored the labyrinth walls; the position of the cat is marked red, and the position of the mouse yellow. The discovered array does not contain this information. It is shown below for easier understanding.

Furthermore, we create the queue for the fields to be visited next. We insert the current position of the cat (15,7) into the queue without a direction (therefore "zero"):

(Learn all about queues in the HappyCoders Queue Tutorial.)

Step 1

We remove the element just put into the queue (the start position of the cat):

Then we write all fields, which can be reached by the cat in one step, into the queue – with their X and Y coordinates and the respective direction relative to the starting point:

These fields are also marked as "discovered":

Steps 2 to n

As long as the queue is not empty, we now take one position element each and write all fields reachable from this position into the queue – unless they are already marked as "discovered".

This time, we don't save the direction taken in this step. Instead, we copy the direction from the removed element. After all, we want to know which direction the cat must take from its starting position.

The first element in the queue is the position (15,6) above the cat:

From this position, we can reach the fields above (15,5) and below (15,7):

The lower field (15,7) is already marked as "discovered" (that is where we came from), and it will be ignored. We write the upper field (15,5) into the queue and also mark it as "discovered":

We will now repeat this process until we "discover" the position of the mouse. The following animation shows how the discovered array fills up step by step:

Termination Condition

As soon as we reach the position of the mouse, the algorithm is finished. The queue entry removed last indicates the direction in which the cat has to go. In the example, that is (11,4)/LEFT (the field above the mouse):

Thus the shortest path from cat to mouse leads to the left. In the following image, I have highlighted the path in yellow:

The path can no longer be inferred from the data at this point. It is irrelevant because the cat has to do only one step, and after that, the shortest path is calculated again (because the mouse is moving too, and the shortest path could lead in a different direction in the next step).

If the queue is empty without the mouse being found, there is no path between cat and mouse. This case cannot occur in the FatCat game but should be handled for other applications.

Shortest Path Java Code

Source Code From 1990

Unfortunately, I do not have the C64 code anymore. A few years later, I reimplemented the game on a 286 in Turbo Pascal, and I managed to find this code again. You can find it - reduced to the relevant parts - here: KATZE.PAS

The Pascal code is a little bit outdated and hard to read for untrained people. Therefore I translated the source code – without changing the algorithms and data structures – into Java. You can find the Java adaption here: CatAlgorithmFrom1990.java

The following code implements the algorithm with modern language features and data structures like the ArrayDeque as a queue. You can find it in the GitHub repository in the CatAlgorithmFrom2020 class.

You will find the code of the Direction enum at the end.

/**
 * Finds the shortest path from cat to mouse in the given labyrinth.
 *
 * @param lab the labyrinth's matrix with walls indicated by {@code true}
 * @param cx the cat's X coordinate
 * @param cy the cat's Y coordinate
 * @param mx the mouse's X coordinate
 * @param my the mouse's Y coordinate
 * @return the direction of the shortest path
 */
private Direction findShortestPathToMouse
    (boolean[][] lab, int cx, int cy, int mx, int my) {
  // Create a queue for all nodes we will process in breadth-first order.
  // Each node is a data structure containing the cat's position and the
  // initial direction it took to reach this point.
  Queue<Node> queue = new ArrayDeque<>();

  // Matrix for "discovered" fields
  // (I know we're wasting a few bytes here as the cat and mouse can never
  // reach the outer border, but it will make the code easier to read. Another
  // solution would be to not store the outer border at all - neither here nor
  // in the labyrinth. But then we'd need additional checks in the code
  // whether the outer border is reached.)
  boolean[][] discovered = new boolean[23][31];

  // "Discover" and enqueue the cat's start position
  discovered[cy][cx] = true;
  queue.add(new Node(cx, cy, null));

  while (!queue.isEmpty()) {
    Node node = queue.poll();

    // Go breath-first into each direction
    for (Direction dir : Direction.values()) {
      int newX = node.x + dir.getDx();
      int newY = node.y + dir.getDy();
      Direction newDir = node.initialDir == null ? dir : node.initialDir;

      // Mouse found?
      if (newX == mx && newY == my) {
        return newDir;
      }

      // Is there a path in the direction (= is it a free field in the labyrinth)?
      // And has that field not yet been discovered?
      if (!lab[newY][newX] && !discovered[newY][newX]) {
        // "Discover" and enqueue that field
        discovered[newY][newX] = true;
        queue.add(new Node(newX, newY, newDir));
      }
    }
  }

  throw new IllegalStateException("No path found");
}

private static class Node {
  final int x;
  final int y;
  final Direction initialDir;

  public Node(int x, int y, Direction initialDir) {
    this.x = x;
    this.y = y;
    this.initialDir = initialDir;
  }
}Code language: Java (java)

And the Direction class:

public enum Direction {
  UP(0, -1),
  RIGHT(1, 0),
  DOWN(0, 1),
  LEFT(-1, 0);

  private final int dx;
  private final int dy;

  Direction(int dx, int dy) {
    this.dx = dx;
    this.dy = dy;
  }

  public int getDx() {
    return dx;
  }

  public int getDy() {
    return dy;
  }
}Code language: Java (java)

You can test the code with the CatAlgorithmsTest class. This class creates a maze, places cat and mouse at random positions, and lets the cat move to the mouse on the shortest path.

The demo program visualizes the maze with ASCII blocks. The individual steps are printed one below the other for simplicity (the pathfinding algorithm is in focus here, not the visualization). The following animation shows the printed steps in animated form:

Algorithm Performance

The CatAlgorithmsBenchmark tool allows you to compare the performance of the old and new implementation. The following table shows the median of the measurements from 20 test iterations, each with 100,000 calculations of the shortest path. Ten warmup iterations preceded the test.

At first glance, the algorithm I wrote as a 15-year-old is faster than my new algorithm. How is this possible?

Optimization for FatCat Mazes

Another look into the old code shows that the pathfinding algorithm examines only every second waypoint. That makes sense in so far as the specific structure of the labyrinths means that the cat can only change its direction after every second step:

I have optimized the Java code once more. Only the part inside the loop changes. It is essential not to ignore the cat's intermediate steps completely – the mouse could sit there.

You will find the optimized code in the following listing and the CatAlgorithmFrom2020Opt class in the GitHub repository.

while (!queue.isEmpty()) {
  Node node = queue.poll();

  // Go *two* steps breath-first into each direction
  for (Direction dir : Direction.values()) {
    // First step
    int newX = node.x + dir.getDx();
    int newY = node.y + dir.getDy();
    Direction newDir = node.initialDir == null ? dir : node.initialDir;

    // Mouse found after first step?
    if (newX == mx && newY == my) {
      return newDir;
    }

    // Is there a path in the direction (= is it a free field in the labyrinth)?
    // No -> continue to next direction
    if (lab[newY][newX]) continue;

    // Second step
    newX += dir.getDx();
    newY += dir.getDy();

    // Mouse found after second step?
    if (newX == mx && newY == my) {
      return newDir;
    }

    // Target field has not yet been discovered?
    if (!discovered[newY][newX]) {
      // "Discover" and enqueue that field
      discovered[newY][newX] = true;
      queue.add(new Node(newX, newY, newDir));
    }
  }
}Code language: Java (java)

And here is the result of another performance comparison:

The new code is now about 25% faster than the code from 1990.

If you have looked into the code from 1990: The reason is that I did not use a queue back then, but two separate data structures for the starting and ending points of each pathfinding step. After each step, all discovered ending points were copied back into the starting points' data structure.

May I be forgiven for not thinking about using a queue (which I couldn't have simply pulled out of the toolbox at that time anyway) when I was 15 ;-)

Summary and Outlook

This article described the "shortest path problem" and used the "FatCat" game (by the way, we called it "cat and mouse") as an example to show how to solve the problem with a pathfinding algorithm in Java.

The algorithm presented here can only be applied to tile-based maps or to graphs that represent tile-based maps.

I will introduce general shortest path algorithms like Dijkstra's algorithm and the A* search algorithm in the following parts of the series.

If you liked the article, feel free to sign up for the HappyCoders newsletter (you'll be informed right away when I publish more parts of this series), and also feel free to share the article using one of the share buttons at the end.