@x5reunion

Здравствуйте знаю что подобных тем сотни, но я никак не могу разобраться в двух вещах.

Я пытаюсь реализовать ортогональную логику нахождения пути, движение по диагонали мне не нужно.

Допустим у нас есть массив. Стартовая ячейка [ 0 , 0 ] , а наша цель [ 3 , 0 ].

[ 0 , 0 ] = 1; [ 0 , 1 ] = 1; [ 0 , 2 ] = 1; [ 0 , 3 ] = 1;

[ 1 , 0 ] = 1; [ 1 , 1 ] = 255; [ 1 , 2 ] = 255; [ 1 , 3 ] = 1;

[ 2 , 0 ] = 255; [ 2 , 1 ] = 255; [ 2 , 2 ] = 255; [ 2 , 3 ] = 1;

[ 3 , 0 ] = 1; [ 3 , 1 ] = 1; [ 3 , 2 ] = 1; [ 3 , 3 ] = 1;

1 можно пройти 255 непроходима. 10 единиц я взял за базовую стоимость. По логике алгоритма мы берем две соседние ячейки которые расположены ортогонально.

Это [ 1 , 0 ] = 1; [ 1 , 0 ] = 1; Стоимость при передвижении к ним будет равна 10. Далее вычисляем их примерную стоимость до достижения цели.

У ячейки [ 1 , 0 ] она будет самая низкая равна 20 + 10 = 30;
А у ячейки [ 0 , 1 ] она будет равна 40 + 10 = 50;

Естественно мы берем ячейку [ 1 , 0 ] помещаем ее в закрытый список, а ячейку [ 1 , 0 ] оставляем в открытом.

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

Вопрос в случае подобной неудачи мы просто возвращаемся к открытому списку и выбираем ячейку с самой низкой базовой стоимостью? И повторяем наш путь по новой?

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

( но я просматривал таблицы стоимости ячеек на разных сайтах и не всегда ячейка, которая находится в открытом списке с самой низкой базовой стоимостью будет вести по правильному пути, если мы зашли в тупик )


Далее мы посчитали стоимость всех ячеек до цели выйдет что то типо.

[ 0 , 0 ] = 0; [ 0 , 1 ] = 10 + 40; [ 0 , 2 ] = 20 + 50; [ 0 , 3 ] = 30 + 60;

[ 1 , 0 ] = 30; [ 1 , 1 ] = 255; [ 1 , 2 ] = 255; [ 1 , 3 ] = 40 + 50;

[ 2 , 0 ] = 255; [ 2 , 1 ] = 255; [ 2 , 2 ] = 255; [ 2 , 3 ] = 50 + 40;

[ 3 , 0 ] = 1; [ 3 , 1 ] = 80 + 10; [ 3 , 2 ] = 70 + 20; [ 3 , 3 ] = 60 + 30;

И все мы дошли до цели.

В закрытом списке у нас будут ячейки

[ 0 , 0 ]
[ 0 , 1 ]
[ 0 , 2 ]
[ 0 , 3 ]
[ 1 , 3 ]
[ 2 , 3 ]
[ 3 , 3 ]
[ 3 , 2 ]
[ 3 , 1 ]

и тупиковая ячейка [ 1 , 0 ].

Вопрос во всех гайдах по алгоритму пишут что надо идти от конечной ячейки до стартовой просто перебирая все в обратном порядке, я никак не могу понять по какой логике отсеиваются тупиковые ячейки? Их может быть и 2 и 3 и сотня и их стоимость ниже других, но они ведут в тупик.
Я никак не могу понять как их исключать, как восстановить полученный путь

0

raxp

A Star. Пространство и алгоритм поиска пути. - ПРОграммист, 2011, №16.

0

@x5reunion

Благодарю за ссылку на журнал, правда он практически мне ни чем не помог, но я почти решил задачу.

0

raxp

...прочитав опыт других ко всем приходит понимание.

0