grid_pathfinding 0.3.0

Pathfinding using jump point search (JPS) and connected components on a 2D grid.
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

/// Fuzzes pathfinding system by checking for many random grids that a path is always found if the goal is reachable
/// by being part of the same connected component. All system settings (diagonals, improved pruning) are tested.
use grid_pathfinding::*;
use grid_util::*;
use rand::prelude::*;

fn random_grid(n: usize, rng: &mut StdRng, diagonal: bool, improved_pruning: bool) -> PathingGrid {
    let mut pathing_grid: PathingGrid = PathingGrid::new(n, n, false);
    pathing_grid.allow_diagonal_move = diagonal;
    pathing_grid.improved_pruning = improved_pruning;
    for x in 0..pathing_grid.width() as i32 {
        for y in 0..pathing_grid.height() as i32 {
            pathing_grid.set(x, y, rng.gen_bool(0.4))
        }
    }
    pathing_grid.generate_components();
    pathing_grid
}

fn visualize_grid(grid: &PathingGrid, start: &Point, end: &Point) {
    let grid = &grid.grid;
    for y in (0..grid.height as i32).rev() {
        for x in 0..grid.width as i32 {
            let p = Point::new(x, y);
            if *start == p {
                print!("S");
            } else if *end == p {
                print!("G");
            } else if grid.get(x, y) {
                print!("#");
            } else {
                print!(".");
            }
        }
        println!();
    }
}

#[test]
fn fuzz() {
    const N: usize = 10;
    const N_GRIDS: usize = 10000;
    let mut rng = StdRng::seed_from_u64(0);
    for (diagonal, improved_pruning) in [(false, false), (true, false), (true, true)] {
        let mut random_grids: Vec<PathingGrid> = Vec::new();
        for _ in 0..N_GRIDS {
            random_grids.push(random_grid(N, &mut rng, diagonal, improved_pruning))
        }

        let start = Point::new(0, 0);
        let end = Point::new(N as i32 - 1, N as i32 - 1);
        for mut random_grid in random_grids {
            random_grid.set_point(start, false);
            random_grid.set_point(end, false);
            let reachable = random_grid.reachable(&start, &end);
            let path = random_grid.get_path_single_goal(start, end, false);
            // Show the grid if a path is not found
            if path.is_some() != reachable {
                visualize_grid(&random_grid, &start, &end);
            }
            assert!(path.is_some() == reachable);
        }
    }
}