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

Question

[Banan44]

Задача такая, у меня есть поле 10х10
Каждая ячейка ( .cell ) представлена в div'е и имеет атрибуты PosX и PosY.
Есть зеленая стартовая точка ( .start ) и красная конечная ( .end ).
Так же присутствуют синие стены ( .wall ).
Нужно проложить кратчайший маршрут из start в end , для обозначения маршрута есть оранжевые точки ( .route ). Нужно что бы это работало даже с рандомной генерацией стен, стартовой точки и конечной.
Подскажите как можно реализовать, если не сложно то часть кода к моему коду дайте, что бы я примерно понял. Я перечитал не одну статью и в книге Грокаем Алгоритмы смотрел и все равно не понятно как реализовать, например здесь говорится о какой-то "стоимости", а не знаю как ее определить.
Мой код в CodePen

Comments

[Сергей Соколов]

от клеточки можно «пойти» только вверх-вниз-вправо-влево или по диагонали допустимо?

В статье по ссылке объясняют же, что такое «стоимость» в их варианте решения.

[Banan44]

Сергей Соколов, по дигонали нельзя, только направо , налево, вверх и вниз

[Banan44]

Сергей Соколов, ссылка с реализацией нахождения стоимости в той статье недоступна

Answer 1

[Banan44]

Почитал про волновой алгоритм и друг помог, его можно реализовать в 2 циклах, 1 цикл устанавливает положительные индексы пустым ячейкам, проверяет является ли ячейка в матрице положительным числом или стартовой позицией, если да то соседям выдается индекс: индекс текущей клетки +1 либо 1 и так пока не дойдем до конечной точки. А 2 цикл строит кратчайший путь из конечной точки в стартовую, просто переходим в соседнюю ячейку где индекс: индекс текущей клетки - 1 , а прошлой ячейке присваиваем например -4 это будет кратчайший маршрут. Ну и таким образом мы получим матрицу с готовым кратчайшим путём.

Answer 2

[Антон Скиба]

Да господи... возьми любой алгоритм с препятствиями, алгоритмы типа a* с весами тебе не нужны, самый простой:

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

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

приоритеты можно посчитать как гипотетическая длина между клетками, чем короче, тем больше приоритет

Answer 3

[krka92]

В статье, которую Вы указали есть готовая реализация
https://github.com/newpdv/pathfinder/blob/master/f...

Comments

[Banan44]

огромный код без обьяснений, ничего не понятно