While I was working on a toy project in Rust, where i was developing a real-word simulation, at some point i needed to work with 2D representations of streets, something similar to google maps but with the possibility to try different combinations and scenarios quickly. So I had an idea: i will generate those paths as 2D matrix, with the possibility to test different combinations with different complexity quickly.
A* algorithm for pathfinding 🔗
As you can understand from the title I used A*, an algorithm whose purpose is to find the best path given a starting point, a goal, and some obstacles. But how does it work ?
Starting from a specific node, it computes the cost of every edge (least distance travelled, shortest time etc.) and keeps track of a tree of paths. At each iteration of its main loop, it needs to determine which path to extend based on two elements:
- the cost of the already visited nodes.
- the estimated cost which is required to extend the path all the way to the goal.
A* selects the path that minimises the sum of the cost of the path from the start node and a heuristic function, which estimates the cost of the cheapest path to the goal.
If you’re looking for a detailed tutorial on how to implement it, you can find tons of them with a quick search. Since I was developing in Rust, I used the pathfinding crate which includes many useful algorithms, and this is how I used it to generate random paths.
use pathfinding::prelude::astar;
use rand::{thread_rng, Rng};
use rand_distr::{Distribution, Normal};
fn create_grid(
size: (usize, usize),
start: (usize, usize),
end: (usize, usize),
obstacle_ratio: f64,
) -> Vec<Vec<i32>> {
let mut grid = vec![vec![0; size.1]; size.0];
let mut rng = rand::thread_rng();
let num_obstacles = (obstacle_ratio * (size.0 * size.1) as f64) as usize;
for _ in 0..num_obstacles {
let x = rng.gen_range(0..size.0);
let y = rng.gen_range(0..size.1);
if (x == start.0 && y == start.1) || (x == end.0 && y == end.1) {
continue;
}
grid[x][y] = 1;
}
grid
}
fn find_path(
grid: &[Vec<i32>],
start: (usize, usize),
goal: (usize, usize),
) -> Option<Vec<(usize, usize)>> {
let successors = |&(x, y): &(usize, usize)| -> Vec<((usize, usize), usize)> {
let mut neighbors = Vec::new();
let directions = vec![(0, 1), (1, 0), (0, -1), (-1, 0)]; // Right, Down, Left, Up
for &(dx, dy) in &directions {
let new_x = x as isize + dx;
let new_y = y as isize + dy;
if new_x >= 0 && new_y >= 0 {
let new_x = new_x as usize;
let new_y = new_y as usize;
if new_x < grid.len() && new_y < grid[0].len() && grid[new_x][new_y] == 0 {
neighbors.push(((new_x, new_y), 1));
}
}
}
neighbors
};
astar(
&start,
successors,
|&(x, y)| {
let h = (x as isize - goal.0 as isize).abs() + (y as isize - goal.1 as isize).abs();
let normal_dist = Normal::new(1000.0, 500.0).unwrap();
let mut rng = thread_rng();
let gaussian_noise: f32 = normal_dist.sample(&mut rng);
let delta = if gaussian_noise < 0.0 {
0.0
} else {
gaussian_noise
};
(h + delta as isize) as usize
},
|&p| p == goal,
)
.map(|(path, _)| path)
}
fn generate_random_points(width: usize, height: usize) -> ((usize, usize), (usize, usize)) {
let mut rng = rand::thread_rng();
let side1 = rng.gen_range(0..4);
let mut side2 = rng.gen_range(0..4);
while side2 == side1 {
side2 = rng.gen_range(0..4);
}
let point1 = generate_point_on_side(side1, width, height, &mut rng);
let point2 = generate_point_on_side(side2, width, height, &mut rng);
(point1, point2)
}
fn generate_point_on_side(
side: usize,
width: usize,
height: usize,
rng: &mut impl Rng,
) -> (usize, usize) {
match side {
0 => (rng.gen_range(0..width), 0), // Top side
1 => (width - 1, rng.gen_range(0..height)), // Right side
2 => (rng.gen_range(0..width), height - 1), // Bottom side
3 => (0, rng.gen_range(0..height)), // Left side
_ => unreachable!(),
}
}
pub fn generate_paths(
grid_x: usize,
grid_y: usize,
obstacle_ratio: f64,
number_of_paths: usize,
) -> Vec<Vec<(usize, usize)>> {
let grid_size = (grid_x, grid_y);
let mut paths = Vec::new();
for _ in 0..number_of_paths {
let (start, end) = generate_random_points(grid_x, grid_y);
let grid = create_grid(grid_size, start, end, obstacle_ratio);
if let Some(path) = find_path(&grid, start, end) {
paths.push(path);
} else {
println!("No path found.");
}
}
paths
}
Gaussian noise 🔗
To avoid the ugly effect where the random generation is too evident, I added some Gaussian noise. Thanks to this little trick, which add a pattern that follows the normal distribution, where most of the noise values are close to a central point (the mean), it gives a cool “smooth” effect to our paths!