Страница строит учебный RRT (быстро исследующее случайное дерево) на той же сетке стен 40×28, что и engineering/astar-dijkstra-grid, но с непрерывными координатами узлов в «клеточных» единицах — путь может срезать углы между узлами решётки. На каждой итерации берётся случайная свободная точка (с смещением выборки к цели), ищется ближайший узел дерева, делается шаг ограниченной длины вдоль хорды, и рёбро принимается только если плотная проверка отрезка не пересекает клетки-стены. Новая вершина внутри радиуса захвата цели вокруг центра G завершает поиск; жёлтая линия — обратный проход по родителям к S. RRT вероятностно полон, но не оптимален: длина пути часто больше, чем у дискретного **A* с манхэттенской эвристикой на тех же стенах; кнопка Compare A* запускает такой A* (4-соседство, дорогие клетки ×5, если они есть в сетке). Настройте шаг, bias и итерации за кадр**, чтобы увидеть компромисс между зондированием пространства и проходом в узких коридорах.
Для кого: Студенты, уже поигравшиеся с A* на сетке и желающие увидеть сэмплинговое планирование до RRT*, PRM и кинодинамических версий.
Ключевые понятия
RRT
Сэмплинговое планирование
Ближайший сосед
Функция шага (steer)
Проверка столкновений
Вероятностная полнота
Смещение к цели
Препятствия на сетке
Как это работает
RRT: случайная точка → ближайший узел дерева → шаг к ней с проверкой стен сетки; bias к цели ускоряет конец; A* на той же карте — дискретный ориентир стоимости и числа раскрытий.
Часто задаваемые вопросы
Почему RRT иногда не находит путь там, где A* находит?
Узкие коридоры требуют, чтобы случайная точка попала внутрь щели до того, как дерево «войдёт»; при малом бюджете итераций или большом шаге вероятность мала. Уменьшите шаг, увеличьте max nodes или bias к цели, когда дерево уже близко — та же «узкая проходная» проблема, из-за которой придумали RRT* и Informed RRT.
Оптимален ли жёлтый путь RRT?
Нет — базовый RRT возвращает любой допустимый геометрический путь. A* на решётке оптимален для этой дискретной модели, но не может свободно резать клетки, поэтому стоимости напрямую не сравнимы.
Как устроена проверка столкновений?
Отрезок дискретизуется с шагом меньше клетки; каждая точка отображается в клетку по floor; попадание в стену отклоняет ребро. Это быстрый учебный тест, а не движок с «раздутыми» препятствиями.
Обновляется ли A* при переносе S/G?
Кнопка считает текущее состояние карты и концов. После перемещения маркеров нажмите Compare A* снова.