Привет, Хабр! Сегодня у нас задачка из мира природы: представьте, что маленький воробушек потерялся в городе. Ему нужно срочно найти путь домой, а дороги кишат кошками, людьми и прочими препятствиями. Разумеется, вручную искать маршрут — не вариант. Нам нужен алгоритм, а лучше параллельный, чтобы воробушек не ждал вечность.
Какой алгоритм взять? Конечно же, A*. Он и кратчайший путь найдёт, и с умом его построит. Но в одиночку он справляется медленно. Поэтому подключаем Rayon — библиотеку для многопоточных вычислений в Rust.
Как работает A
Итак, представим карту города как сетку:
Воробушек стартует с точки S.
Домик — это точка G.
Между ними — опасные кошки (стены) и всякие препятствия.
A* ищет путь, оценивая клетки по функции:
Где:
— реальная стоимость пути от старта до текущей клетки.
— эвристическая оценка оставшегося расстояния (например, Манхэттенская дистанция).
Алгоритм держит приоритетную очередь клеток, которые он хочет проверить. На каждом шаге:
Берёт самую «дешёвую» клетку (по f(n)).
Проверяет соседей.
Добавляет их в очередь и повторяет шаг 1, пока не дойдёт до цели.
Но есть проблема: всё это работает последовательно. Каждый шаг занимает время, а если карта большая — воробушек может умереть от старости, пока найдёт путь. Это нужно ускорить.
Где можно распараллелить?
Обход соседей — можно параллельно проверять все доступные направления.
Вычисление эвристики — если есть миллион клеток, считаем их эвристику не по одной, а пачками.
Обновление структуры данных — очередь узлов должна быть потокобезопасной.
Реализация A с параллельной обработкой на Rust*
Определяем узлы
Для начала создадим структуру для узлов, которые будут представлять клетки сетки:
use std::collections::{BinaryHeap, HashMap};
use std::cmp::Ordering;
use rayon::prelude::*;
#[derive(Debug, Clone, Eq, PartialEq)]
struct Node {
position: (i32, i32),
g: f32,
h: f32,
}
impl Node {
fn new(position: (i32, i32), g: f32, h: f32) -> Self {
Node { position, g, h }
}
fn f(&self) -> f32 {
self.g + self.h
}
}
impl Ord for Node {
fn cmp(&self, other: &Self) -> Ordering {
other.f().partial_cmp(&self.f()).unwrap()
}
}
impl PartialOrd for Node {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}Что тут происходит:
Node — узел сетки, в котором живёт воробушек.
f(n) = g + h — чем меньше, тем лучше.
Приоритетная очередь использует
Ord, чтобы сортировать узлы поf(n).
Пишем эвристику
Манхэттенское расстояние — быстро, просто, но не всегда эффективно. Можно ускорить его расчёт с Rayon:
fn heuristic(a: (i32, i32), b: (i32, i32)) -> f32 {
let dx = (a.0 - b.0).abs() as f32;
let dy = (a.1 - b.1).abs() as f32;
dx + dy
}
fn batch_heuristic(nodes: &[(i32, i32)], goal: (i32, i32)) -> Vec<f32> {
nodes.par_iter()
.map(|&node| heuristic(node, goal))
.collect()
}Если у нас 1000 узлов, то с par_iter() все 1000 эвристик считаются в несколько потоков, а не по одной.
Параллельный обход соседей
Теперь нужно, чтобы воробушек выбирал новые клетки одновременно.
fn get_neighbors(position: (i32, i32)) -> Vec<(i32, i32)> {
vec![
(position.0 - 1, position.1),
(position.0 + 1, position.1),
(position.0, position.1 - 1),
(position.0, position.1 + 1),
]
}
fn process_neighbors(
current: &Node,
goal: (i32, i32),
open_set: &mut BinaryHeap<Node>,
came_from: &mut HashMap<(i32, i32), (i32, i32)>,
cost_so_far: &mut HashMap<(i32, i32), f32>
) {
let neighbors = get_neighbors(current.position);
let new_nodes: Vec<_> = neighbors.par_iter()
.filter(|&&neighbor| !cost_so_far.contains_key(&neighbor))
.map(|&neighbor| {
let new_g = current.g + 1.0;
let new_h = heuristic(neighbor, goal);
Node::new(neighbor, new_g, new_h)
})
.collect();
for node in new_nodes {
open_set.push(node.clone());
cost_so_far.insert(node.position, node.g);
came_from.insert(node.position, current.position);
}
}Теперь соседние клетки обрабатываются одновременно.
Собираем A*
fn a_star(start: (i32, i32), goal: (i32, i32)) -> Vec<(i32, i32)> {
let mut open_set = BinaryHeap::new();
let mut came_from = HashMap::new();
let mut cost_so_far = HashMap::new();
open_set.push(Node::new(start, 0.0, heuristic(start, goal)));
cost_so_far.insert(start, 0.0);
while let Some(current) = open_set.pop() {
if current.position == goal {
let mut path = vec![goal];
let mut pos = goal;
while let Some(&prev) = came_from.get(&pos) {
path.push(prev);
pos = prev;
}
path.reverse();
return path;
}
process_neighbors(¤t, goal, &mut open_set, &mut came_from, &mut cost_so_far);
}
vec![]
}Что в итоге? Проверяем параллельный A* в деле
Теперь проверим, как работает наша реализация на конкретном примере. Допустим, есть сетка 10×10, и воробушку нужно добраться из (0, 0) в (9, 9), минуя препятствия.
Вот код, который запустит алгоритм и выведет путь:
fn main() {
let start = (0, 0);
let goal = (9, 9);
let path = a_star(start, goal);
if path.is_empty() {
println!("Путь не найден!");
} else {
println!("Найден путь ({} шагов):", path.len() - 1);
for step in &path {
println!("{:?}", step);
}
}
}Если путь найден, получим что‑то вроде этого:
Найден путь (18 шагов):
(0, 0)
(1, 0)
(2, 0)
(3, 0)
(4, 1)
(5, 2)
(6, 3)
(7, 4)
(8, 5)
(9, 6)
(9, 7)
(9, 8)
(9, 9)Если путь заблокирован (например, всё завалено кошками), то вывод будет:
Путь не найден!Теперь воробушек летит домой в несколько потоков. А как вы применяете A* в своих проектах?
В завершение всем Rust-разработчикам рекомендую к посещению открытые уроки, которые пройдут в Otus бесплатно в феврале:
11 февраля — «Разбираем анатомию парсера на Rust»
Рассмотрим, какие особенности языка делают код надёжным и производительным, а также изучим архитектурные решения, лежащие в основе многих современных Rust-проектов. Записаться18 февраля — «Полиморфизм в Rust. Возможности и компромиссы»
Посмотрим на возможности языка, позволяющие писать обобщённый код и разберёмся со способами компиляции и выполнения полиморфного кода. Записаться