DFS Maze Solver

Question

I am new to Rust Programming so I decided to implement a Maze Solver using DFS. I was wondering if there is any way to optimize this code further

use std::collections::{HashMap, HashSet, VecDeque};

// Load maze from a given file name and return an array of strings
// fn load_maze(filename: &str) -> Vec<String> {
//     let mut maze = Vec::new();
//     let file = File::open(filename).unwrap();
//     let reader = BufReader::new(file);
//     for line in reader.lines() {
//         // if line is not empty
//         if !line.as_ref().unwrap().is_empty() {
//             maze.push(line.unwrap());
//         }
//     }
//     maze
// }

// Use include_str! to load the maze from a file
fn include_maze() -> Vec<String> {
    let mut maze = Vec::new();
    // Get the file contents as a string using include_str! macro
    let file_contents = include_str!("/path/to/maze.txt");
    // Split the string into lines
    for line in file_contents.lines() {
        // if line is not empty
        if !line.is_empty() {
            maze.push(line.to_string());
        }
    }
    maze
}

// Parse the maze and return an array of arrays of characters removing any whitespace
fn parse_maze(maze: &Vec<String>) -> Vec<Vec<bool>> {
    let mut parsed_maze = Vec::new();
    for line in maze {
        let mut parsed_line = Vec::new();
        for c in line.chars() {
            // switch statement
            match c {
                // if c is a wall (#) return false
                '#' => parsed_line.push(false),
                // if c is a path (-) return true
                '-' => parsed_line.push(true),
                _ => (),
            }
        }
        parsed_maze.push(parsed_line);
    }
    parsed_maze
}

fn dfs(
    matrix: &Vec<Vec<bool>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Option<Vec<(usize, usize)>> {
    // Create a stack
    let mut stack = VecDeque::new();
    stack.push_back(start);

    // Create a set to store the visited nodes
    let mut visited = HashSet::new();

    // Create a dictionary to store the parent of each node
    let mut parent = HashMap::new();

    // While the stack is not empty
    while let Some(node) = stack.pop_back() {
        // If the node is the end, we have found a path
        if node == end {
            // Create a list to store the path
            let mut path = vec![];
            let mut current = node;

            // While the node is not the start
            while current != start {
                // Add the node to the path
                path.push(current);
                // Set the node to its parent
                current = parent[&current];
            }

            // Add the start node to the path
            path.push(start);
            // Reverse the path
            path.reverse();
            // Return the path
            return Some(path);
        }

        // If the node has not been visited
        if !visited.contains(&node) {
            // Add the node to the visited set
            visited.insert(node);
            // Get the row and column of the node
            let (row, col) = node;
            // Get the possible moves
            let moves = get_moves(matrix, row, col);
            // For each move
            for m in moves {
                // If the move has not been visited
                if !visited.contains(&m) {
                    // Add the move to the parent dictionary
                    parent.insert(m, node);
                    // Push the move onto the stack
                    stack.push_back(m);
                }
            }
        }
    }

    // If we have not found a path, return None
    None
}

fn get_moves(matrix: &Vec<Vec<bool>>, row: usize, col: usize) -> Vec<(usize, usize)> {
    // \# is a wall and - is a path
    // Get the possible moves
    let mut moves = vec![];

    // Check the left move
    if col > 0 && matrix[row][col - 1] {
        moves.push((row, col - 1));
    }

    // Check the right move
    if col < matrix[0].len() - 1 && matrix[row][col + 1] {
        moves.push((row, col + 1));
    }

    // Check the up move
    if row > 0 && matrix[row - 1][col] {
        moves.push((row - 1, col));
    }

    // Check the down move
    if row < matrix.len() - 1 && matrix[row + 1][col] {
        moves.push((row + 1, col));
    }

    // Return the moves
    moves
}

fn main() {
    // let maze = load_maze("/home/cms/fun/dfs/mazes/maze-Easy.txt");
    let maze = include_maze();
    let parsed_maze = parse_maze(&maze);
    let start = (0, 1);
    let end = (parsed_maze.len() - 1, parsed_maze[0].len() - 2);
    let path = dfs(&parsed_maze, start, end).unwrap();
    println!("Path: {:?}", path)
}

An example maze file:

# - # # # # # # # # # # # # # # # # # # 
# - - - - - - - - - - - - - - - - - # # 
# # # # # - # # - # # - # # # - # - - #
# - # # # - # - - # # - # # - - # - # # 
# - # - - - # # # # # # # # # - # - - # 
# - - - # - - - - # - # # - # - # # # #
# - # # # # - # - - - - - - - - - - - #
# - # # - - - # # # # # # # # # # - # #
# - - - - # - - # # - - - - - - - - - #
# # # # # # # # # # # # # # # # # # - # 

This is a very small maze, but this program should solve as long as the end is in the bottom right corner. Here is a large maze

So far, the best optimization I have made is by using include_str! which has decreased execution time by 200ms. I have tried to use threading to speed it up, but that only seemed to make it slower (I think I was making too many threads)

Any help is appreciated! :)

Answer 1

Use a Heuristic Search Algorithm

If you’re serious about getting better performance from this, don’t just try the cardinal directions in the same order. At least try to move toward the exit before you try moving away from it. It would be simple to tweak get_moves to return those directions first, rather than in a fixed order. The most common algorithm for this (as you probably know) is A*-search.

Mark Visited Spaces on the Map

Since the list of visited spaces should not be restored when you backtrack, you could just mark the visited coordinates off on the map of the maze. Allow each space on the grid to have three values: visited, unvisited or wall. If you are making this multi-threaded, slap a mutex lock on it.

Build the Path as You Go Along

It’s code that only runs once, but right now, you’re keeping a parent HashMap to store the predecessor of each move. It would be far simpler to push moves on a stack and pop them when you backtrack (more on which later). Then the stack is your path. When you reach the end, this queue is the list of moves on your path.

An alternative to keeping a list of all moves so far is to use a recursive implementation and return either Some list of nodes leading from end to start, or None. You would then build the list in reverse order by passing a list of moves, with each caller adding its current location to the end, back up the stack.

Backtrack with Either Recursion or a Trampoline

If you keep a stack (either a trampoline data structure or the program stack of recursive calls) whose elements are the current location and a list of child open paths from here, you can depth-first search until you reach the end, or backtrack until you hit a dead end and then follow the previous path not taken on the stack. This doesn’t require the queue to be double-ended or other costly data structures. In this case, you probably want to store the moves in a fixed-length array rather than dynamically allocate from the heap, since (if you start on an edge) there are at most three valid moves from any square.

A trampoline data structure, however, has the advantage that it can be shared between threads, with each thread atomically removing the next path to search. A mechanism using recursive function calls could still partition the search space before making the top-level call, but that would not work well here because we do not know in advance which branches of the search will terminate quickly.

Your Map Should be a Flat Vector

Since every row is the same width, that is, a rectangular array it has rows*cols elements, and element (i,j) of a M × N array has index M*i + j. (The three-dimensional version would be M*(N*i + j) + k, and so on for higher dimensions.) Use this formula to look up coordinates in the flat array of data. Using a vector of vectors destroys your locality of reference and forces the program to dereference multiple pointers just to access a single element.

In fact, you (practically) never want to use a vector of vectors as your data structure. You almost always want a vector of fixed-width arrays, or a flat vector that knows its own dimensions and maps the coordinates it is given to an index. If in fact you are storing a sparse matrix and want to save memory by omitting the empty trailing elements of each row, you more likely want a format such as Compressed Sparse Row.

You Can Optimize Parsing the Maze Data

Currently, you repeatedly push each value into the representation of the map in memory. If you iterate over the input, you can map a transformation function over it and collect the results.