Introduction to graphs - BFS algorithm

Imagine we have a game in which the characters can move in a 2D grid, just like the image below:

Now, let's say our character needs to reach the marked square. More importantly, he needs to reach the destination in the shortest path possible, considering that the character can only move one square horizontally or vertically at a time.

How can we solve this problem and find the shortest path? The answer lies on graphs.

Changing the perspective: seeing the grid as a graph

The image above depicts a graph - a visual representation of data or information that consists of nodes (or vertices) connected by edges. Each node represents an entity, while the edges represent relationships or connections between these entities. Graphs can be used to model a wide range of complex systems, such as social networks, transportation networks, computer networks, and more. They are a fundamental data structure in mathematics and computer science, enabling the analysis, visualization, and problem-solving of various real-world scenarios and relationships.

In our problem, a graph is useful to model the grid - a set of coordinated points representing all possible positions of our character. As we are talking about a movement that can only be horizontal or vertical, each square has adjacent squares that the character can move to, provided they meet the condition of being horizontally or vertically adjacent.

Therefore, the grid below

Can be represented by the following graph, in which we can see the nodes and the edges connecting them:

This shift of perspective is the first step to solve our problem; the second step is to write an algorithm to "walk the graph"

Pathfinding algorithms

Finding the shortest path in a graph is a very common problem encountered in various real-life scenarios - think about GPS navigation systems, for example.

For this reason, this type of algorithm has been studied for a long time, and nowadays there are multiple ways to solve the problem of "finding the shortest path." The simplest algorithms are Breadth-First Search (which we'll see in this post) and Depth-First Search. There are also more advanced (and effective) ones such as Dijkstra and A*.

How Breadth-First Search works?

Think about it for a minute: what is the first step to find the shortest path in a maze?

One possible answer is to first map all the possible paths. After all, to find the shortest path, we first need to know which paths are possible, taking into account the character's movement restrictions.

We can narrow down the problem scope by asking, "Which squares can my character move to from the current position, denoted as X?"
This is necessary given that, particularly at the edges of the grid, the character may not be able to move further vertically or horizontally. Furthermore, there could be scenarios where the character's movement should be limited by certain conditions, similar to this Advent of Code problem.

Therefore, let's write a simple function that decides the "available neighbors" (adjacent positions which we can move to), given we are working with coordinates, represented by cartesian points like below:

pub struct Coord {
    x: usize,
    y: usize,
}

pub fn neighbors(grid: &Grid, curr_coord: &Coord) -> Vec<Coord> {
    let deltas: [(isize, isize); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];

    let neighbors: Vec<Coord> = deltas
        .into_iter()
        .filter_map(|(dx, dy)| {
            let coord_x = curr_coord.x.checked_add_signed(dx)?;
            let coord_y = curr_coord.y.checked_add_signed(dy)?;

            let neighb_coord = Coord {
                x: coord_x,
                y: coord_y,
            };
            if !grid.in_bounds(&neighb_coord) {
                return None;
            }
            Some(neighb_coord)
        })
        .collect();

    neighbors
}

This function receives the grid as a parameter. The grid is a struct that contains all the points and info such as height and width:

pub struct Grid {
    width: usize,
    height: usize,
    data: Vec<Coord>,
    start_coord: Coord,
    end_coord: Coord,
}

Then, we are going to check all possible four coordinates that are adjacent to the current coordinate. In the code, this is represented by [(-1, 0), (1, 0), (0, -1), (0, 1)], which are the numbers we are going to sum with x and y to verify squares vertically and horizontally adjacent.
Rust provides a method checked_add_signed, which is used here to verify if the sum returns a positive number. For example, if we add 0 + (-1), we would get -1, but here Rust returns None to this operation - which excludes negative (and therefore invalid) coordinates from the neighbors returned by this function.
After excluding possibly negative coordinates, the grid.in_bounds() method checks if the neighbor coordinates are out of grid bounds:

pub fn in_bounds(&self, coord: &Coord) -> bool {
        coord.x < self.width && coord.y < self.height
}

In sum, the general idea in this step is to get the adjacent coordinates from a grid square and return only the valid ones.

However, mapping the available positions for each square is not enough: how do we move from square to square?

Enqueueing the nodes

Walking the graph involves:
1 - Moving to a square
2 - Mapping the available positions from that square
3 - Moving to the next available square

In code, this can be translated to: put the available nodes in a queue, visit each node mapping its neighbors (and putting them in the queue), store the visited nodes and repeat this sequence until the queue is empty.

Visually, we can demonstrate it like this (images from GeeksforGeeks):

We start with an empty queue and an empty array of visited nodes. Once we map the available nodes from that starting point, we populate the queue and mark the start coordinate as visited:

While the queue is not empty, we get the first element from it (that becomes our current node), map their neighbors and add it to the visited array.

    while queue.len() != 0 {
        let curr_node = queue.pop_front().expect("queue is empty");
        let curr_node_neighbors = neighbors(grid, &curr_node, part);
        for neighbor in curr_node_neighbors {
            if !visited.contains(&neighbor) {
                queue.push_back(neighbor);
                visited.push(neighbor);
            }
        }

Once the queue is empty, we know all possible paths have been checked.

All roads lead to Rome

Finding all possible paths our character can walk does not tell us anything about the shortest path to point X. However, we are halfway there.

Since we guarantee that nodes in visited vec are not visited again, no node is visited more than once. This constraint guarantees we don't repeat ourselves checking again paths that lead to nowhere. Additionally, BFS employs a queue data structure to keep track of nodes to visit - which means nodes are enqueued in the order they are discovered, and dequeued in the same order. This "first-in, first-out" (FIFO) behavior ensures that nodes closer to the source are explored before nodes farther away.

Therefore, once BFS reaches the node we are searching for (the destination node), it has essentially found the shortest path in terms of the number of edges.

Finally, to find the shortest path, we can start from the destination node and follow its parent backward through the graph until we reach the source node.

To do so, we keep track of the parent node of each node visited, so that we can reconstruct the path. We can do this using a hashmap, for example, to store coordinates and their respective parents.

let mut coord_parents: HashMap<Option<Coord>, Option<Coord>> = HashMap::new();

And finally, we can add the following logic to recreate the path that leads to the destination node:

if curr_node == end {
    let mut current = Some(end);
    while let Some(current_coord) = current {
        path.push(current_coord);
        current = *coord_parents.get(&current).expect("coord not found");
    }
}

Basically, what this code does is populate a Vec named path, which stores the Coords that correspond to the path from the initial node to the final node. As you can see, this Vec is constructed based on the information of the parent of each node.

Our code becomes roughly like this:

pub fn find_path(grid: &Grid) -> Vec<Coord> {
    let mut queue: VecDeque<Coord> = VecDeque::new();
    let mut visited: Vec<Coord> = Vec::new();
    let mut path: Vec<Coord> = Vec::new();

    let mut coord_parents: HashMap<Option<Coord>, Option<Coord>> = HashMap::new();

    // Populate the initial info
    let start = grid.start_coord;
    let end = grid.end_coord;
    coord_parents.insert(Some(start), None);
    queue.push_back(start);
    visited.push(start);

    while queue.len() != 0 {
        let curr_node = queue.pop_front().expect("queue is empty");
        if curr_node == end {
            // We reached the end node, now we reconstruct the path
            let mut current = Some(end);
            while let Some(current_coord) = current {
                path.push(current_coord);
                current = *coord_parents.get(&current).expect("coord not found");
            }
        }
        let curr_node_neighbors = neighbors(grid, &curr_node);
        for neighbor in curr_node_neighbors {
            if !visited.contains(&neighbor) {
                queue.push_back(neighbor);
                visited.push(neighbor);
                coord_parents.insert(Some(neighbor), Some(curr_node));
            }
        }
    }
    path
}

BFS definitely is not the standard for pathfinding nowadays, since it is a lot less efficient than more advanced algorithms, such as A*. However, understanding how BFS works provide us with very useful insights about the importance of graphs and how they can be applied in Computer Science.