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

Question

[PopeyetheSailor]

Несколько раз на хабре проскакивали статьи о реализации алгоритмов поиска пути. Мне стало интересно, решил немного прокачаться в js и наваять что-нибудь (делаю все на html/js на div-ах, с js знаком, но больше на уровне jQuery). Но вот проблема — в процессе реализации понимаю, что не знаю как лучше сделать. Было 2 идеи — загонять поле поиска в двумерный массив, а потом проходиться по нему, создавая html вывод, затем поиск/перемещение делать в массиве, изменения опять же отображать в html — получается двойная работа.

Или второй вариант — сразу выводить html блоки со вспомогательной информацией (координаты) и весь поиск сразу производить в html — как-то криво, на мой взгляд.

Подскажите, в какое принять решение, а также буду рад, если посоветуете еще какие-нибудь идеи для практических занятий js.

Спасибо.

Answer 1

[Eugene Obrezkov]

Вот здесь очень хорошо показан принцип работы поиска путей визуально. И его же можно использовать для поиска путей. В нем уже реализованы такие алгоритмы, как А* и другие.

Comments

[PopeyetheSailor]

Отлично, спасибо. Прямо в точку — выглядит именно так, как я хотел реализовать и как раз на A-star.

[PopeyetheSailor]

Оу, все-таки это далеко не мой уровень, расковырять этот код кажется нереальным.

[Eugene Obrezkov]

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

var matrix = [
    [0, 0, 0, 1, 0],
    [1, 0, 0, 0, 1],
    [0, 0, 1, 0, 0],
];
var grid = new PF.Grid(5, 3, matrix);

Затем создаем объект поиска путей по алгоритму А*

var finder = new PF.AStarFinder();

Говорим ему найти путь от (1,2) к (4,2):

var path = finder.findPath(1, 2, 4, 2, grid);

В результате с вышеописанной матрицей будет такой вывод:

[ [ 1, 2 ], [ 1, 1 ], [ 2, 1 ], [ 3, 1 ], [ 3, 2 ], [ 4, 2 ] ]

[PopeyetheSailor]

Нет-нет, это я понимаю. Я о том, что сам код очень непрост и самому повторить такую реализацию для меня нереально. Мне ведь конкретно поиск пути сам по себе не нужен. Хочется именно реализовать самому решение, скилл прокачать.

[sapphiriq]

Вчера на dailyjs писали: Easystar.js, может быть там попроще

Answer 2

[Андрей Апанасик]

Я в своё время реализовывал на js волновой алгоритм. Посмотрите, может пригодится. Визуально можно посмотреть как волны строятся. Сам обход в целом являет собой одну рекурсивную функцию.

Comments

[Sild]

Так же реализоввывал волновой алгоритм с визуализацией, правда в виде консольной псевдографики на джаве. Алгоритм вроде не сложный и интуитивно-понятный. Для начала самое то.

Answer 3

[overmes]

Если английский у вас хороший могу накидать ссылок из онлайн курса ИИ университета в Беркли. Очень классно рассказывают, есть A* по шагам:
www.youtube.com/watch?feature=player_embedded&v=g0MJRpquEOk