pathfinding 4.15.0

Pathfinding, flow, and graph algorithms
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
150
151
152
153
154
155

//! This example demonstrates the BFS bidirectional algorithm,
//! and compares it with the regular BFS algorithm.

use pathfinding::prelude::{bfs, bfs_bidirectional};
use std::ops::Add;
use std::time::Instant;

const SIZE: isize = 64;
const BOTTOM_LEFT: P = P(0, 0);
const TOP_RIGHT: P = P(SIZE, SIZE);
const CENTER: P = P(SIZE / 2, SIZE / 2);

#[derive(Debug, Clone, Eq, Hash, Ord, PartialEq, PartialOrd)]
struct P(isize, isize);

impl Add for P {
    type Output = Self;

    fn add(self, other: Self) -> Self {
        P(self.0 + other.0, self.1 + other.1)
    }
}

fn successors(p: &P) -> Vec<P> {
    [P(0, 1), P(0, -1), P(1, 0), P(-1, 0)]
        .into_iter()
        .map(|delta| p.clone() + delta)
        .filter(|p| p.0 >= 0 && p.0 <= SIZE && p.1 >= 0 && p.1 <= SIZE)
        .collect()
}

fn main() {
    run_corner_to_corner();
    run_center_to_corner();
}

/// Corner to corner:
/// =================
///
/// In this case both algorithms will perform similarly.
/// In fact, regular BFS will perform slightly better, since the algorithm is slightly simpler.
///
/// We can understand this in terms of the number of points that need to be searched in order to reach
/// the goal. In the below diagrams this corresponds to the area covered in the final snapshot.
///
/// In both cases every point gets searched - the entire area is filled. For this reason we can intuitively see that
/// regular BFS and bidirectional BFS will perform similarly.
///
/// Regular BFS:
/// ============
///
/// $---------$         $---------$         $---------$         $---------$               $---------$         $---------$
/// |        G|         |        G|         |        G|         |        G|               |FFFFFFF G|         |FFFFFFFFG|
/// |         |         |         |         |         |         |         |               |FFFFFFFF |         |FFFFFFFFF|
/// |         |         |         |         |         |         |         |               |FFFFFFFFF|         |FFFFFFFFF|
/// |         |         |         |         |         |         |         |               |FFFFFFFFF|         |FFFFFFFFF|
/// |         |    =>   |         |    =>   |         |    =>   |         |   => ... =>   |FFFFFFFFF|    =>   |FFFFFFFFF|
/// |         |         |         |         |         |         |F        |               |FFFFFFFFF|         |FFFFFFFFF|
/// |         |         |         |         |F        |         |FF       |               |FFFFFFFFF|         |FFFFFFFFF|
/// |         |         |F        |         |FF       |         |FFF      |               |FFFFFFFFF|         |FFFFFFFFF|
/// |S        |         |SF       |         |SFF      |         |SFFF     |               |SFFFFFFFF|         |SFFFFFFFF|
/// $---------$         $---------$         $---------$         $---------$               $---------$         $---------$
///
/// Bidirectional BFS:
/// ==================
///
/// $---------$         $---------$         $---------$         $---------$               $---------$         $---------$
/// |        G|         |       BG|         |      BBG|         |     BBBG|               | BBBBBBBG|         |FBBBBBBBG|
/// |         |         |        B|         |       BB|         |      BBB|               |F BBBBBBB|         |FFBBBBBBB|
/// |         |         |         |         |        B|         |       BB|               |FF BBBBBB|         |FFFBBBBBB|
/// |         |         |         |         |         |         |        B|               |FFF BBBBB|         |FFFFBBBBB|
/// |         |    =>   |         |    =>   |         |    =>   |         |   => ... =>   |FFFF BBBB|    =>   |FFFFFBBBB|
/// |         |         |         |         |         |         |F        |               |FFFFF BBB|         |FFFFFFBBB|
/// |         |         |         |         |F        |         |FF       |               |FFFFFF BB|         |FFFFFFFBB|
/// |         |         |F        |         |FF       |         |FFF      |               |FFFFFFF B|         |FFFFFFFFB|
/// |S        |         |SF       |         |SFF      |         |SFFF     |               |SFFFFFFF |         |SFFFFFFFF|
/// $---------$         $---------$         $---------$         $---------$               $---------$         $---------$
fn run_corner_to_corner() {
    let instant = Instant::now();
    bfs(&BOTTOM_LEFT, &successors, |p| *p == TOP_RIGHT);
    let duration_bfs = instant.elapsed();

    let instant = Instant::now();
    bfs_bidirectional(&BOTTOM_LEFT, &TOP_RIGHT, successors, successors);
    let duration_bfs_bidirectional = instant.elapsed();

    print!(
        "
Corner to Corner
================
BFS took {duration_bfs:?}
Bidirectional BFS took {duration_bfs_bidirectional:?}
"
    );
}

/// Center to corner:
/// =================
///
/// In this case bidirectional BFS will outperform regular BFS.
///
/// We can understand this in terms of the number of points that need to be searched in order to reach
/// the goal. In the below diagrams this corresponds to the area covered in the final snapshot.
///
/// In this case for the regular BFS every point still needs to be searched - again, the entire area is filled.
/// However, for the bidirectional BFS some points remain unsearched - the entire area is not filled. For this
/// reason we can intuitively see that bidirectional BFS will outperform regular BFS here.
///
/// Regular BFS:
/// ============
///
/// $---------$         $---------$         $---------$               $---------$          $---------$
/// |        G|         |        G|         |        G|               | FFFFFFFG|          |FFFFFFFFG|
/// |         |         |         |         |         |               |FFFFFFFFF|          |FFFFFFFFF|
/// |         |         |    F    |         |    F    |               |FFFFFFFFF|          |FFFFFFFFF|
/// |         |         |   FFF   |         |   FFF   |               |FFFFFFFFF|          |FFFFFFFFF|
/// |    S    |    =>   |  FFSFF  |    =>   |  FFSFF  |   => ... =>   |FFFFSFFFF|    =>    |FFFFSFFFF|
/// |         |         |   FFF   |         |   FFF   |               |FFFFFFFFF|          |FFFFFFFFF|
/// |         |         |    F    |         |    F    |               |FFFFFFFFF|          |FFFFFFFFF|
/// |         |         |         |         |         |               |FFFFFFFFF|          |FFFFFFFFF|
/// |         |         |         |         |         |               | FFFFFFF |          |FFFFFFFFF|
/// $---------$         $---------$         $---------$               $---------$          $---------$
///
/// Bidirectional BFS:
/// ==================
///
/// $---------$         $---------$         $---------$         $---------$         $---------$
/// |        G|         |       BG|         |      BBG|         |     BBBG|         |    FBBBG|
/// |         |         |        B|         |       BB|         |    F BBB|         |   FFFBBB|
/// |         |         |         |         |    F    |         |   FFF  B|         |  FFFFFBB|
/// |         |         |    F    |         |   FFF   |         |  FFFFF  |         | FFFFFFFB|
/// |    S    |    =>   |   FSF   |    =>   |  FFSFF  |    =>   | FFFSFFF |    =>   |FFFFSFFFF|
/// |         |         |    F    |         |   FFF   |         |  FFFFF  |         | FFFFFFF |
/// |         |         |         |         |    F    |         |   FFF   |         |  FFFFF  |
/// |         |         |         |         |         |         |    F    |         |   FFF   |
/// |         |         |         |         |         |         |         |         |    F    |
/// $---------$         $---------$         $---------$         $---------$         $---------$
fn run_center_to_corner() {
    let instant = Instant::now();
    bfs(&CENTER, &successors, |p| *p == TOP_RIGHT);
    let duration_bfs = instant.elapsed();

    let instant = Instant::now();
    bfs_bidirectional(&CENTER, &TOP_RIGHT, successors, successors);
    let duration_bfs_bidirectional = instant.elapsed();

    print!(
        "
Center to Corner
================
BFS took {duration_bfs:?}
Bidirectional BFS took {duration_bfs_bidirectional:?}
"
    );
}