Этот вопрос закрыт для ответов, так как повторяет вопрос Как осуществить поиск кратчайшего пути на javascript?
@Banan44
Full Stack

Как реализовать алгоритм поиска пути на Js?

Задача такая, у меня есть поле 10х10
Каждая ячейка ( .cell ) представлена в div'е и имеет атрибуты PosX и PosY.
Есть зеленая стартовая точка ( .start ) и красная конечная ( .end ).
Так же присутствуют синие стены ( .wall ).
Нужно проложить кратчайший маршрут из start в end , для обозначения маршрута есть оранжевые точки ( .route ). Нужно что бы это работало даже с рандомной генерацией стен, стартовой точки и конечной.
Подскажите как можно реализовать, если не сложно то часть кода к моему коду дайте, что бы я примерно понял. Я перечитал не одну статью и в книге Грокаем Алгоритмы смотрел и все равно не понятно как реализовать, например здесь говорится о какой-то "стоимости", а не знаю как ее определить.
Мой код в CodePen
  • Вопрос задан
  • 1849 просмотров
Решения вопроса 1
@Banan44 Автор вопроса
Full Stack
Почитал про волновой алгоритм и друг помог, его можно реализовать в 2 циклах, 1 цикл устанавливает положительные индексы пустым ячейкам, проверяет является ли ячейка в матрице положительным числом или стартовой позицией, если да то соседям выдается индекс: индекс текущей клетки +1 либо 1 и так пока не дойдем до конечной точки. А 2 цикл строит кратчайший путь из конечной точки в стартовую, просто переходим в соседнюю ячейку где индекс: индекс текущей клетки - 1 , а прошлой ячейке присваиваем например -4 это будет кратчайший маршрут. Ну и таким образом мы получим матрицу с готовым кратчайшим путём.
Ответ написан
Ответы на вопрос 2
@SkibaAnton
Frontend-Developer
Да господи... возьми любой алгоритм с препятствиями, алгоритмы типа a* с весами тебе не нужны, самый простой:

выставь приоритеты направлений, то есть 4 переменных с разными значениями,
сделай шаг в приоритетном направлении,
если стена иди в следующее по приоритету, если нет иди в том же направлении,
и... итерация повторяется.

ты главное не с интерфейса начинай, а напиши например массив из 0 и 1 своего лабиринта
и итерируй по нему значения не вложенными циклами, а отдельно по высоте и ширине.

приоритеты можно посчитать как гипотетическая длина между клетками, чем короче, тем больше приоритет
Ответ написан
@krka92
В статье, которую Вы указали есть готовая реализация
https://github.com/newpdv/pathfinder/blob/master/f...
Ответ написан
Ваш ответ на вопрос

Вопрос закрыт для ответов и комментариев

Потому что уже есть похожий вопрос.
Похожие вопросы