2
\$\begingroup\$

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

\$\endgroup\$

1 Answer 1

Reset to default
2
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.