Shortest Path Algorithm - with Java examples - feature image

Shortest Path Algorithm (With Java Examples)

by Sven Woltmann – November 11, 2020

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:

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.

FatCat - Shortest path problem with "cat and mouse" game on the HP85
“FatCat” on an HP85 emulator (“GamesPac2” cartridge)

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:

FatCat: Beaming to a random target position
Beaming to a random target position

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.

Maze as a boolean array
boolean array “lab”

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.

boolean array "discovered" with cat position marked
boolean array “discovered” with cat position marked

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”):

Pathfinding queue with the cat's position as the first element
Pathfinding queue with the cat’s position as the first element

(You can read all about the general functionality of a queue in this article.)

Step 1

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

Pathfinding queue: first element removed
Pathfinding queue: first element removed

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:

Pathfinding: fields reachable in the first step
Pathfinding queue: fields reachable in the first step
Pathfinding queue: fields reachable in the first step

These fields are also marked as “discovered”:

boolean array "discovered" with fields reachable in the next step
boolean array “discovered” with fields reachable in the next step

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:

Pathfinding queue: removed field (15,6)
Pathfinding queue: removed field (15,6)

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

Pathfinding: fields reachable in the second step
Pathfinding: fields reachable by the cat in the second step

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”:

boolean array "discovered" with the newly discovered field (15,5)
boolean array “discovered” with the newly discovered field (15,5)
Pathfinding queue with the added field (15,5)
Pathfinding queue with the added field (15,5)

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:

Pathfinding: discovering the reachable fields
Pathfinding: discovering the reachable fields

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):

Pathfinding queue: the element removed last indicates the direction to go
Pathfinding queue: the element removed last indicates the direction to go

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

Maze algorithm: termination condition reached - shortest path found
Termination condition reached – shortest path found

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;
  }
}

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;
  }
}

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:

Pathfinding in a maze: test output of the Java program
Pathfinding in a maze: test output of the Java program

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.

AlgorithmTime for 100,000 path calculations
CatAlgorithmFrom1990530 ms
CatAlgorithmFrom2020662 ms

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:

FatCat - only every second waypoint is a node of the graph.
Only every second waypoint is a node of the graph.

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));
    }
  }
}

And here is the result of another performance comparison:

AlgorithmTime for 100,000 path calculations
CatAlgorithmFrom1990540 ms
CatAlgorithmFrom2020687 ms
CatAlgorithmFrom2020Opt433 ms

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 subscribe to my 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.

  •  
  •  
  •  
  •  
  •  
  •  

About the author

I'm a freelance software developer with more than two decades of experience in scalable Java enterprise applications. My focus is on optimizing complex algorithms and on advanced topics such as concurrency, the Java memory model, and garbage collection. Here on HappyCoders.eu, I want to help you become a better Java programmer. Read more about me here.

Leave a Comment

Your email address will not be published. Required fields are marked *

{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}