Привет, Хабр! Сегодня у нас задачка из мира природы: представьте, что маленький воробушек потерялся в городе. Ему нужно срочно найти путь домой, а дороги кишат кошками, людьми и прочими препятствиями. Разумеется, вручную искать маршрут — не вариант. Нам нужен алгоритм, а лучше параллельный, чтобы воробушек не ждал вечность.

Какой алгоритм взять? Конечно же, A*. Он и кратчайший путь найдёт, и с умом его построит. Но в одиночку он справляется медленно. Поэтому подключаем Rayon — библиотеку для многопоточных вычислений в Rust.

Как работает A

Итак, представим карту города как сетку:

  • Воробушек стартует с точки S.

  • Домик — это точка G.

  • Между ними — опасные кошки (стены) и всякие препятствия.

A* ищет путь, оценивая клетки по функции:

f(n)=g(n)+h(n)f(n) = g(n) + h(n)

Где:

  • g(n)— реальная стоимость пути от старта до текущей клетки.

  • h(n)— эвристическая оценка оставшегося расстояния (например, Манхэттенская дистанция).

Алгоритм держит приоритетную очередь клеток, которые он хочет проверить. На каждом шаге:

  1. Берёт самую «дешёвую» клетку (по f(n)).

  2. Проверяет соседей.

  3. Добавляет их в очередь и повторяет шаг 1, пока не дойдёт до цели.

Но есть проблема: всё это работает последовательно. Каждый шаг занимает время, а если карта большая — воробушек может умереть от старости, пока найдёт путь. Это нужно ускорить.

Где можно распараллелить?

  1. Обход соседей — можно параллельно проверять все доступные направления.

  2. Вычисление эвристики — если есть миллион клеток, считаем их эвристику не по одной, а пачками.

  3. Обновление структуры данных — очередь узлов должна быть потокобезопасной.

Реализация 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(&current, 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. Возможности и компромиссы»
    Посмотрим на возможности языка, позволяющие писать обобщённый код и разберёмся со способами компиляции и выполнения полиморфного кода. Записаться