// Returns a list of tile positions,
// showing the path to the closest adjacent point to the goal.
Returns a list of tile positions,
showing the path to the closest adjacent point to the goal.
Returns a list of tile positions showing the path to the closest adjacent point to the goal .
fn simple_a_star(
  start: HashablePos,
  goal: HashablePos,
  blocked_tiles: HashSet<HashablePos>,
  map_dim: (u32, u32),
) -> Option<Vec<HashablePos>> {
  let mut open_tiles: HashMap<HashablePos, PathfindingNode> = HashMap::new();
  open_tiles.insert(
    start,
    PathfindingNode {
      pos: start,
      last_pos: start,
      from_start: 0,
      to_goal: get_tile_distance(start, goal),
      visited: true,
    },
  );
  let mut cur = start;
  'outer: loop {
    let new_positions: Vec<PathfindingNode> = [cur.up(), cur.down(), cur.left(), cur.right()]
      .iter()
      .filter(|pos| pos.is_on_map(map_dim))
      .filter(|pos| !blocked_tiles.contains(pos))
      .map(|pos| PathfindingNode {
        pos: pos.to_owned(),
        last_pos: cur.clone(),
        from_start: get_tile_distance(*pos, start),
        to_goal: get_tile_distance(*pos, goal),
        visited: false,
      })
      .collect();
    for mut node in new_positions.into_iter() {
      let node_pos = node.pos;
      if node.to_goal == 1 {
        open_tiles.insert(node_pos, node);
        cur = node_pos;
        break 'outer;
      }
      if let Some(old_node) = open_tiles.get(&node_pos) {
        if node.weight() < old_node.weight()
          || node.weight() == old_node.weight() && node.to_goal < old_node.to_goal
        {
          if old_node.visited {
            node.visited = true;
          }
          open_tiles.insert(node_pos, node);
        }
      } else {
        open_tiles.insert(node_pos.clone(), node);
      }
    }
    let mut best: Option<PathfindingNode> = None;
    for (_, node) in open_tiles.iter() {
      if !node.visited {
        if let Some(cur_best) = best.as_ref() {
          if node.weight() < cur_best.weight() {
            best = Some(node.clone());
          }
        } else {
          best = Some(node.clone());
        }
      }
    }
    if let Some(new_cur) = best {
      cur = new_cur.pos;
      open_tiles.get_mut(&cur).unwrap().visited = true;
    } else {
      // There are no spaces that haven't been visited
      // so no path can be found.
      return None;
    }
  }
  let mut steps: Vec<HashablePos> = vec![];
  let mut last = cur;
  while last != start {
    let previous_node = open_tiles.get(&last).unwrap();
    steps.push(previous_node.pos);
    last = previous_node.last_pos;
  }
  steps.reverse();
  Some(steps)
}
fn simple_a_star ( start : HashablePos , goal : HashablePos , blocked_tiles : HashSet < HashablePos > , map_dim : ( u32 , u32 ) , ) -> Option < Vec < HashablePos > > { let mut open_tiles : HashMap < HashablePos , PathfindingNode > = HashMap :: new ( ) ; open_tiles . insert ( start , PathfindingNode { pos : start , last_pos : start , from_start : 0 , to_goal : get_tile_distance ( start , goal ) , visited : true , } , ) ; let mut cur = start ; ' outer : loop { let new_positions : Vec < PathfindingNode > = [ cur . up ( ) , cur . down ( ) , cur . left ( ) , cur . right ( ) ] . iter ( ) . filter ( | pos | pos . is_on_map ( map_dim ) ) . filter ( | pos | ! blocked_tiles . contains ( pos ) ) . map ( | pos | PathfindingNode { pos : pos . to_owned ( ) , last_pos : cur . clone ( ) , from_start : get_tile_distance ( * pos , start ) , to_goal : get_tile_distance ( * pos , goal ) , visited : false , } ) . collect ( ) ; for mut node in new_positions . into_iter ( ) { let node_pos = node . pos ; if node . to_goal == 1 { open_tiles . insert ( node_pos , node ) ; cur = node_pos ; break ' outer ; } if let Some ( old_node ) = open_tiles . get ( & node_pos ) { if node . weight ( ) < old_node . weight ( ) || node . weight ( ) == old_node . weight ( ) && node . to_goal < old_node . to_goal { if old_node . visited { node . visited = true ; } open_tiles . insert ( node_pos , node ) ; } } else { open_tiles . insert ( node_pos . clone ( ) , node ) ; } } let mut best : Option < PathfindingNode > = None ; for ( _ , node ) in open_tiles . iter ( ) { if ! node . visited { if let Some ( cur_best ) = best . as_ref ( ) { if node . weight ( ) < cur_best . weight ( ) { best = Some ( node . clone ( ) ) ; } } else { best = Some ( node . clone ( ) ) ; } } } if let Some ( new_cur ) = best { cur = new_cur . pos ; open_tiles . get_mut ( & cur ) . unwrap ( ) . visited = true ; } else { // There are no spaces that haven't been visited // so no path can be found. return None ; } } let mut steps : Vec < HashablePos > = vec ! [ ] ; let mut last = cur ; while last != start { let previous_node = open_tiles . get ( & last ) . unwrap ( ) ; steps . push ( previous_node . pos ) ; last = previous_node . last_pos ; } steps . reverse ( ) ; Some ( steps ) }
Returns a list of tile positions,
showing the path to the closest adjacent point to the goal.
Returns a list of tile positions showing the path to the closest adjacent point to the goal .
start
HashablePos
goal
HashablePos
blocked_tiles
HashSet<HashablePos>
map_dim
(u32, u32)