Paths in a grid

Consider the problem of having a two-dimensional grid and a set of questions to answer: what's the shortest path between a given origin position and a target position in the grid? How many paths there are between those two positions?

In this article we will develop some solutions to these questions while building up a way to think about these kinds of problems. The algorithms developed here can be used in interesting applications like robotics and motion planning.

A grid representation with an origin, a target, a path and blocked positions.

Paths in a grid, problem space

Let's first start by breaking the problem down and coming up with a model. * Given a two-dimensional grid

This statement is loaded with information, let's dig that information up.

First, we can represent a two-dimensional grid with a matrix where each position is defined by a row-index (i) and a column-index (j). The matrix is represented by a two-dimensional collection (like arrays, vectors or lists depending on the language you choose). In this article we choose python to help us express the problem:

# example grid
grid = [
    [1, 0, 1, 1],
    [1, 1, 1, 1],
    [0, 1, 1, 1],
    [0, 0, 1, 9],
]

# gives us the information stored for position row i, column j
grid[i][j] 

We will be asking information about paths in the grid, so we choose to store information that affects the path passing through that position. We convention the following:

# means position is blocked and no paths can pass through it
grid[i][j] == 0 

# means position is open and paths can pass through it
grid[i][j] == 1 

We will also need someway to encode a target position meaning where ours paths end. We can arbitrarily choose a value to represent the target.

# this is the target position
gridi[i][j] == 9 

• what's the shortest path

Let's be more precise about what we mean by path.
A path is a sequential order of positions in a grid and each position can only appear once in a path to prevent loops. The shortest path is the sequence with the least number of positions in it from origin to target.

We further define that the path starting in a given position can only go to a neighboring position. A neighbor position to (i, j) is defined as a position that shares and edge with (i, j) or that seats in one of (i, j) diagonals. The neighbors of a given position are completed defined by the position (i, j) and the grid size (width, height). We can have a function that gives us neighboring positions: neighbors(i, j, width, height)

Neighbors in a grid illustration

• between a given origin position and a target position

We previously defined a position to be a pair row, column (i, j). And we defined the target position to be the position in the grid that stores the value 9. We can consider to know what's the origin position.

• how many paths there are between them

The number of paths between two positions will be the set size of all possible paths starting in the origin and ending in the target position.

Neighbors in a grid

Let's start to write some code for the problem space definition:

def neighbors(i, j, width, height):
  "Returns all possible neighbors of position (i, j)."
  neighborhood = []
  for row_offset in range(-1, 2):
    for col_offset in range(-1, 2):
      if row_offset == 0 and col_offset == 0:
        continue

      neighbor_i = i + row_offset
      neighbor_j = j + col_offset

      if (0 <= neighbor_i < height) and ( 0 <= neighbor_j < width):
        neighborhood.append((neighbor_i, neighbor_j))
  return neighborhood

Dealing with blocked positions

def is_open(grid, i, j):
    return grid[i][j] > 0

def open_positions(grid, positions):
    return [
        (i, j) for (i, j) in positions
        if is_open(grid, i, j)
    ]

Shortest path in a grid (not knowing the target position)

Now that we have a model for the problem space and have a way to get neighbors for a position, let's start asking the interesting questions. How do we find the shortest path between two positions? We don't know in which row and column the target is located, we only know that it holds the 9 value as described earlier.

A first thought could be: if we generate all paths and then get the path with the least number of positions in it we will get answer. And that is correct. But intuitively that seems like a lot of work. And we will explore that later. Let's try to come up with other ideas. For example, can we transfer knowledge from other domains into our problem?

Searching in a grid based on graphs

What if instead of generating all paths, we search for the shortest path in a smaller search space? Let's think about search in a graph and see if we can translate that into grids.

Breadth-first search

Breadth-first search is an algorithm for traversing or searching tree or graph data structures.
In a graph it's guaranteed to find the shortest path.

Can you prove or somewhat build an intuition to why this is true?
Make sure you're subscribed to our newsletter - we publish solutions to challenges in the following posts.

Here's an implementation of BFS applied to a graph represented as an adjacency-list:

from collections import deque

def shortest_path(graph, start, target):
    seen = {start}
    queue = deque([(start, [start])])
    while queue:
        v, path = queue.popleft()
        if v == target:
            return path
        for u in graph[v]:
            if u not in seen:
                queue.append((u, path+[u]))
                seen.add(u)
    return None

Can you adapt this shortest path algorithm that applies to graphs represented as adjacency lists to work on grids represented as matrices?

Shortest path in a grid (knowing the target position)

What if we are given the row and column of the origin and target positions? Is there a better way to compute the shortest path between those two positions than BFS?

BFS, as shown previously, will look through all positions starting from the origin and will only stop once it finds itself in the, previously unknown, target position. If we employ BFS to solve this problem as we did previously it seems we're not using all information available to us. Specifically, we're not using the information about the location of the target position.

Searching heuristics

There must be some kind of heuristic we could use to try to improve our approach.
At any point in the shortest path search we can compute how far we are from the target position because, well, we know that position beforehand. Maybe we could use that to inform our path search. Instead of going through all positions until we find the target, we could somehow favor the positions that seem to get us closer to the target.

Let's try to loosen the constraints:

1. Let's assume we know the origin and target positions, and all positions are open. Intuitively the shortest path is just "go in the target direction". Or more formerly, choose the next position as the position that gets us closer to the target.
2. Now if we consider that some positions might be blocked. We can't just follow the target direction because it might be blocked. On the other hand, blockers might only change the solution locally and even if we find a blocked position in the target direction, the shortest path may be close.

One idea is to favor neighbors that brings us closer to the target, if they are available. This heuristic is, in fact, the basis of the A* search algorithm.

Can you take these ideas and implement an algorithm that will, at any point in the shortest path search, consider how far we are from the target position?

Want some hints?

How many paths in a grid?

Ok, let's say we now know how to compute shortest paths when we know the target location and when we don't know the target location. Let's go back to our first idea: to compute all paths and get the shortest. We intuited that there were a lot of paths.

Well, how many exactly? How do we compute that?

Finding paths with recursion

At firsthand we don't know how many positions there are between the origin position and the target position but one thing we do know: * for every possible path, the last hop in the path to the target position must come from one of its neighbors; that's by our earlier definition of the path.

Let's explore that idea:

We know that every possible path must pass through one of the target's neighbors. Also every possible path that passes through a certain neighbor of the target, let's call it A; must come from one of A's neighbors.
To solve for the target we must first solve its neighbors. And to solve for the neighbors we first must to solve for their neighbors and so on.
But then what? If we magically solve for every neighbor recursively what do we do with that information?
Well, if we know the number of paths to each of the targets neighbors, we can conclude that the number of paths to the target is the sum of the number of paths to its neighbors.

In code we can write:

# Let's say the target is at position (i_target, j_target)
n_of_paths[(i_target, j_target)] = sum(
    n_of_paths[(i, j)] 
    for (i, j) in neighbors(i_target, j_target, width, height)
)
# Where neighbors is our previously defined function.

Can you take this definition and use to compute the number of paths from an origin to a target in a grid?

Paths in a grid challenge

Let's recap the questions we asked through out the post:

1. Can you prove or somewhat build an intuition to why BFS is guaranteed to find the shortest path?
2. Can you adapt the BFS algorithm presented to work on grids?
3. Can you come with an algorithm to compute the shortest path knowing the target location and using that information to improve the path search?
4. Can you implement an algorithm to compute the number of paths from origin to target using the definition we proposed?

Here are some hints. And here is a bootstrapped repl.it so you don't have to start from scratch.