soukoban 0.1.4

A library provides the implementation of some algorithms and data structures related to Sokoban
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

use std::{
    collections::HashSet,
    hash::{DefaultHasher, Hash, Hasher},
};

use nalgebra::Vector2;

use crate::{
    Map, Tiles,
    path_finding::{compute_area_anchor, compute_reachable_area},
    solver::Strategy,
};

#[derive(Clone, Eq, PartialEq, Debug)]
pub struct State {
    pub player_position: Vector2<i32>,
    pub box_positions: HashSet<Vector2<i32>>,
}

impl State {
    /// Computes the hash of the canonicalized state.
    pub fn canonicalized_hash(&self, strategy: Strategy, map: &Map) -> u64 {
        let mut hasher = DefaultHasher::new();
        match strategy {
            Strategy::Fast | Strategy::OptimalPush => {
                let mut canonicalized_state = self.clone();
                canonicalized_state.canonicalize_player(map);
                canonicalized_state.hash(&mut hasher);
                hasher.finish()
            }
            Strategy::OptimalMove => {
                self.hash(&mut hasher);
                hasher.finish()
            }
        }
    }

    /// Canonicalizes the position of the player.
    fn canonicalize_player(&mut self, map: &Map) {
        let player_reachable_area = compute_reachable_area(self.player_position, |position| {
            !(map[position].intersects(Tiles::Wall) || self.box_positions.contains(&position))
        });
        self.player_position = compute_area_anchor(&player_reachable_area).unwrap();
    }
}

impl Hash for State {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.player_position.hash(state);
        let mut sorted_boxes: Vec<_> = self.box_positions.iter().collect();
        sorted_boxes.sort_by_key(|position| (position.x, position.y));
        for box_position in sorted_boxes {
            box_position.hash(state);
        }
    }
}