soukoban 0.1.5

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

use crate::{FxHashMap, FxHashSet, Vector2, direction::Direction};

/// A biconnected component graph.
pub(crate) struct BccGraph {
    /// Maps an undirected edge to its block ID.
    edge_blocks: FxHashMap<[Vector2<i32>; 2], usize>,
    /// The set of cut vertices (articulation points) in the graph.
    cut_vertices: FxHashSet<Vector2<i32>>,
}

impl BccGraph {
    /// Creates a new `BccGraph`.
    pub(crate) fn new(start: Vector2<i32>, is_walkable: impl Fn(Vector2<i32>) -> bool) -> Self {
        let mut edge_blocks = FxHashMap::default();
        let mut cut_vertices = FxHashSet::default();
        let mut depth = FxHashMap::default();
        let mut low = FxHashMap::default();
        let mut edge_stack = Vec::new();
        let mut block_count = 0;
        let mut time = 0;
        let mut root_children = 0;

        let mut stack = Vec::new();

        time += 1;
        depth.insert(start, time);
        low.insert(start, time);
        stack.push((start, None::<Vector2<i32>>, 0));

        let directions = Direction::iter().collect::<Vec<_>>();
        while let Some((u, p, direction_idx)) = stack.pop() {
            let mut next_direction_idx = direction_idx;
            let mut pushed_child = false;

            while next_direction_idx < directions.len() {
                let direction = directions[next_direction_idx];
                next_direction_idx += 1;

                let v = u + &direction.into();
                if !is_walkable(v) {
                    continue;
                }
                if Some(v) == p {
                    continue;
                }

                if let Some(&v_depth) = depth.get(&v) {
                    let u_depth = depth[&u];
                    if v_depth < u_depth {
                        // Back edge
                        edge_stack.push(canonicalize_edge(u, v));
                        let low_u = low.get_mut(&u).unwrap();
                        *low_u = (*low_u).min(v_depth);
                    }
                } else {
                    if p.is_none() {
                        root_children += 1;
                    }

                    time += 1;
                    depth.insert(v, time);
                    low.insert(v, time);
                    edge_stack.push(canonicalize_edge(u, v));

                    stack.push((u, p, next_direction_idx));
                    stack.push((v, Some(u), 0));
                    pushed_child = true;
                    break;
                }
            }

            if pushed_child {
                continue;
            }

            if let Some(parent) = p {
                let low_u = low[&u];
                let low_p = low.get_mut(&parent).unwrap();
                *low_p = (*low_p).min(low_u);

                if low_u >= depth[&parent] {
                    if parent != start {
                        cut_vertices.insert(parent);
                    }
                    block_count += 1;
                    let target_edge = canonicalize_edge(parent, u);
                    while let Some(edge) = edge_stack.pop() {
                        edge_blocks.insert(edge, block_count);
                        if edge == target_edge {
                            break;
                        }
                    }
                }
            }
        }

        if root_children > 1 {
            cut_vertices.insert(start);
        }

        Self {
            edge_blocks,
            cut_vertices,
        }
    }

    /// Checks if a path exists from `from` to `to` without passing through the
    /// given `obstacle`.
    ///
    /// # Panics
    ///
    /// Panics if `from` and `to` are not adjacent to the `obstacle`, or are
    /// outside the movable area.
    pub(crate) fn is_reachable(
        &self,
        from: Vector2<i32>,
        to: Vector2<i32>,
        obstacle: Vector2<i32>,
    ) -> bool {
        debug_assert_eq!((from - obstacle).abs().sum(), 1);
        debug_assert_eq!((to - obstacle).abs().sum(), 1);

        // If the obstacle is not located at a cut vertex, it indicates that the entire
        // graph remains connected
        if !self.cut_vertices.contains(&obstacle) {
            return true;
        }

        let (edge1, edge2) = (
            canonicalize_edge(from, obstacle),
            canonicalize_edge(to, obstacle),
        );
        let (block1, block2) = (
            self.edge_blocks.get(&edge1).unwrap(),
            self.edge_blocks.get(&edge2).unwrap(),
        );

        block1 == block2
    }
}

/// Normalizes an undirected edge between two nodes.
fn canonicalize_edge(a: Vector2<i32>, b: Vector2<i32>) -> [Vector2<i32>; 2] {
    if (a.y, a.x) < (b.y, b.x) {
        [a, b]
    } else {
        [b, a]
    }
}