Prog blog
Inventory

Find a path in 2d array maze

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 myLines gamethis 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 labyrinthmapas 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 thePlace.

#[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 fromstart_placetostop_place.

In addition, a new structure is needed.

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

PathPlacestores 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 thestop_place(using theget_pathfunction). Thestepfield is not used in the algorithm, but it remains because it is useful for debugging.

At the beginning of thefind_path_2dfunction creates an identical sized secondary array ofmap_of_pathsforPathPlaceusingfill_map_of_paths. Then create our firstpath_placefrom thestart_placestructure and add it tomap_of_pathsand to the places array for checkingpath_places_to_search. The algorithm then falls into a loop until thepath_places_to_searchis empty. In the body of the loop, the first element is pulled one by one from thepath_places_places_to_searcharray. It is compared with thestop_place. If it is equal, we return the path with theget_pathfunction based onmap_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 themaptable and hasn't already been visited inmap_of_paths. If the conditions are met, a new place is added tomap_of_pathsandpath_places_to_search.

example find path result - lines game

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
}