Find a path in 2d array maze

The post was created with the thought that someday someone will search for an algorithm to find the path in the 2D maze. In my Lines game this algorithm is used when moving the ball on the board to a selected empty field.

The function returns the path option, if it finds a way, it returns an array of places that the key has to visit before it reaches the destination, or returns None which is considered as the ball cannot reach the set destination.

fn find_path_2d<T>(map: &[Vec<Option<T>>], start_place: Place, stop_place: Place) -> Option<Path>

The function takes the labyrinth map as a 2d table. For the function it is sufficient for the array to contain information (Option). Whether there is something (Some) or nothing (None). So we can assign a generic T type there, which can be anything. Additionally, we need the structure of the Place.

#[derive(Default, Serialize, Copy, Clone)]
pub struct Place {
  pub row_index: usize,
  pub column_index: usize
}

It contains the row and column indexes for the other function arguments (start_place, stop_place). The final result of the function will be a path option (Path)

pub type Path = Vec<Place>;

It is an ordinary vector of places to visit from start_place to stop_place.

In addition, a new structure is needed.

#[derive(Default, Clone)]
struct PathPlace {
  place: Place,
  place_before: Option<Place>,
  step: usize
}

PathPlace stores information about the place visited by the algorithm. In addition, it stores the place you came from (place_before) so you can easily pull the path when you reach the stop_place (using the get_path function). The step field is not used in the algorithm, but it remains because it is useful for debugging.

At the beginning of the find_path_2d function creates an identical sized secondary array of map_of_paths for PathPlace using fill_map_of_paths. Then create our first path_place from the start_place structure and add it to map_of_paths and to the places array for checking path_places_to_search. The algorithm then falls into a loop until the path_places_to_search is empty. In the body of the loop, the first element is pulled one by one from the path_places_places_to_search array. It is compared with the stop_place. If it is equal, we return the path with the get_path function based on map_of_paths. If it is not, then the algorithm checks the undiscovered places. It makes sure that we don't go outside the array, and additionally, that the place is empty in the map table and hasn't already been visited in map_of_paths. If the conditions are met, a new place is added to map_of_paths and path_places_to_search.

Here's the whole algorithm code.

#[derive(Default, Serialize, Copy, Clone)]
pub struct Place {
  pub row_index: usize,
  pub column_index: usize
}

pub type Path = Vec<Place>;

#[derive(Default, Clone)]
struct PathPlace {
  place: Place,
  place_before: Option<Place>,
  step: usize
}

fn find_path_2d<T>(map: &[Vec<Option<T>>], start_place: Place, stop_place: Place) -> Option<Path> {
  let mut map_of_paths: Vec<Vec<Option<PathPlace>>> = fill_map_of_paths(&map);
  let path_place = PathPlace {
    place: start_place,
    place_before: None,
    step: 0
  };
  let Place { row_index, column_index } = start_place;
  let mut path_places_to_search: Vec<PathPlace> = vec![path_place.clone()];
  map_of_paths[row_index][column_index] = Some(path_place);
  while !path_places_to_search.is_empty() {
    let PathPlace { place, step, .. } = path_places_to_search.remove(0);
    if equal_place(place, stop_place) {
      return Some(get_path(stop_place, &map_of_paths));
    }
    let mut places_to_check = vec![];
    if place.row_index > 0 {
      places_to_check.push(Place { row_index: place.row_index - 1, column_index: place.column_index });
    }
    if place.row_index + 1 < map.len() {
      places_to_check.push(Place { row_index: place.row_index + 1, column_index: place.column_index });
    }
    if place.column_index > 0 {
      places_to_check.push(Place { row_index: place.row_index, column_index: place.column_index - 1 });
    }
    if place.column_index + 1 < map[place.row_index].len(){
      places_to_check.push(Place { row_index: place.row_index, column_index: place.column_index + 1 });
    }
    for place_to_check in places_to_check {
      let row_index = place_to_check.row_index;
      let column_index = place_to_check.column_index;

      if is_unchecked_place(&map, &map_of_paths, place_to_check) {
        let path_place = PathPlace {
          place: place_to_check,
          place_before: Some(place),
          step: step + 1
        };
        map_of_paths[row_index][column_index] = Some(path_place.clone());
        path_places_to_search.push(path_place);
      }
    }
  }
  None
}

fn fill_map_of_paths<T>(map: &[Vec<Option<T>>]) -> Vec<Vec<Option<PathPlace>>>{
  let mut map_of_paths: Vec<Vec<Option<PathPlace>>> = vec![];
  for row_item in map.iter() {
    let mut row_item_vec = vec![];
    for _item in row_item.iter() {
      row_item_vec.push(None);
    }
    map_of_paths.push(row_item_vec);
  }
  map_of_paths
}

fn get_path(place: Place, map_of_paths: &[Vec<Option<PathPlace>>]) -> Path {
  let mut path = vec![];
  let mut maybe_path_place = map_of_paths[place.row_index][place.column_index].clone();
  while let Some(path_place) = maybe_path_place {
    path.push(path_place.place);
    match path_place.place_before {
      Some(place) => {
        maybe_path_place = map_of_paths[place.row_index][place.column_index].clone();
      }
      None => {
        maybe_path_place = None
      }
    }
  }
  path.reverse();
  path
}

fn is_unchecked_place<T>(map: &[Vec<Option<T>>], map_of_paths: &[Vec<Option<PathPlace>>], place: Place) -> bool {
  if map[place.row_index][place.column_index].is_some() {
    return false;
  }
  if map_of_paths[place.row_index][place.column_index].is_some() {
    return false;
  }
  true
}

How to throttle in rust stwdeb

When I was writing the Lines game, I wanted to limit the number of calls to drawing the game. In Rust it's not that easy to write, but you can do it quickly wi...