Я искал алгоритм/псевдокод A*, следовал ему и закодировал. Я использовал манхэттенское расстояние для h(n). ( f(n) = g(n) + h(n) ) И это результат,
Это всегда происходит, когда нет стен, преграждающих путь, но когда я ставлю много стен, кажется, что он выбирает кратчайший путь. Это самый короткий путь? Я имею в виду, почему это не так, как ниже?
Этот тоже A* Manhattan, и они имеют одинаковый размер (19x19). Это из http://qiao.github.com/PathFinding.js/visual/
Оба пути имеют одинаковое манхэттенское расстояние. Следовательно, выбор пути зависит от реализации. Чтобы понять, почему была выбрана именно эта часть, нам нужно взглянуть на код этой конкретной реализации A*.
Подсказка: каждый путь от исходной к целевой ячейке, который использует только район фон Неймана (т. е. не идет по диагонали) и не делает шаг в «неправильном» направлении (т. е. никогда не идет вверх или влево в вашем примере) имеет такое же манхэттенское расстояние. Так что, если вы находитесь в Нью-Йорке, не имеет значения, какой перекресток вы выберете, чтобы добраться до определенного места на Манхэттене :)
При манхэттенском расстоянии первый путь является кратчайшим. Он просто подсчитывает количество сделанных горизонтальных и вертикальных шагов. Если вам нужно что-то, что больше похоже на кратчайший путь на евклидовом расстоянии, вы можете попробовать изменить свой алгоритм так, чтобы, когда у него есть выбор двигаться по горизонтали или вертикали в одной точке, он выбирал горизонтальный путь, если расстояние по горизонтали больше, чем по вертикали. один и наоборот.
Вам нужно провести линию взгляда (пифагорейскую/евклидову) от начальной точки до каждой точки (результата Манхэттена/A*) до финиша. Если бросок лески в определенную точку заблокирован/скрыт препятствием, вы используете предыдущую брошенную точку и начинаете бросать другую леску из этой заблокированной точки, а затем вперед до конца. Заблокированная точка — это когда точка скрыта линией прямой видимости начальной точки сегмента/линии. Так это как:
Первая строка: Старт--------->S+N(до заблокированной точки)
Вторая/Средняя линия/с:Заблокированная точка---------->S+N(перед другой заблокированной точкой) повторить еще раз(новая линия/сегмент), пока не установится линия прямой видимости к цели.
Последняя строка:Заблокированная точка------------->Цель
Соедините все линии, и у вас будет гораздо более короткий кратчайший путь. Вы можете выполнить еще раз, но в обратном порядке, чтобы добавить еще одну точность, чтобы линия прицеливания начиналась с цели до начала.
