Как найти кратчайший путь в лабиринте?

Question

[Григорий Каляшов]

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

Есть 2 вектора:

//карта с 0 и 1, 1 - стена
vector<vector<int>> map;
//карта с ценами путей
vector<vector<int>> tempMap;

В конечной ячейке:
map[finishX][finishY] = 19;

int startX=0; 
int startY=6; 
int finishX=12; 
int finishY=6;

Сам алгоритм:

void FindPath(int startX,int startY,int finishX,int finishY,int upper) 
{ 
   if( upper>20 )
	   return; 
   //если в стартовой ячейке что-то есть
   if(tempMap[startX][startY]<=upper && tempMap[startX][startY] > 0)
	   return; 
   //конец пути
   if( startX == finishX && startY == finishY)
   {
	   tempMap[startX][startY]=upper;
	   return;
   } 
   //если в стартовой ячейке что-то есть
   if(map[startX][startY]>0)
	   return; 
   //увеличиваем стартовую ячейку на 1
   tempMap[startX][startY] = upper; 
    //верхние ячейки
   if(startY > 0)
	   FindPath(startX, startY - 1, finishX, finishY, upper+1); 
   //влево
   if(startX > 0)
	   FindPath(startX - 1, startY, finishX, finishY, upper+1); 
   //влево и вверх
   if(startX > 0 && startY > 0)
	   FindPath(startX-1,startY-1, finishX, finishY, upper+1); 
   //вправо
   if(startX < col)
	   FindPath(startX + 1, startY, finishX, finishY, upper+1); 
   //вниз
   if(startY < col)
	   FindPath(startX,startY + 1, finishX, finishY, upper+1); 
   //вправо и вниз
   if(startY < col && startX < col)
	   FindPath(startX+1,startY+1, finishX, finishY, upper+1); 
};

После прохода волнового алгоритма лабиринт выглядит так:
0 0 0 0 0 0 0 0 0 0 0 0 0
0 7 8 9 10 11 12 13 14 15 16 17 0
0 6 7 8 9 10 11 12 13 14 15 16 0
0 5 6 7 8 9 10 11 12 13 14 15 0
0 4 5 6 7 8 9 10 11 12 13 14 0
2 3 4 5 6 7 8 9 10 11 12 0 15
1 0 4 5 6 7 8 9 10 11 0 13 14
2 0 5 5 6 7 8 9 10 11 0 14 14
0 0 6 6 6 7 8 9 10 11 0 15 0
0 0 7 7 7 7 8 9 10 11 0 15 0
0 0 8 8 8 8 8 9 10 11 0 14 0
0 0 9 9 9 9 9 9 10 11 12 13 0
0 0 0 0 0 0 0 0 0 0 0 0 0

0 - стена

Подскажите, как найти кратчайший путь?

Answer 1

[Сергей Мельников]

qiao.github.io/PathFinding.js/visual

Answer 2

[ManWithBear]

Начинаете с конца и идете по уменьшению цифр пока не дойдете до начала.

Comments

[Григорий Каляшов]

ManWithBear так и делал, но путь не всегда самый короткий и решение не оптимальное.

[ManWithBear]

Григорий Каляшов: если путь не самый короткий, значит у вас не правильно реализован волновой алгоритм.

Answer 3

[CodeInside]

Я бы посоветовал почитать какую-то книгу о теории графов. Помню учили по этому предмету алгоритмы поиска пути. Но это очень давно было. Так что вводив поисковик "книга теория графов". Предмет не сложен, так что можешь сразу искать нужную тебе главу. Думаю понять будет не тяжело.

Answer 4

[Кирилл Пензин]

У тебя есть уже матрица графа используй Алгоритм Дейкстры

Comments

[Григорий Каляшов]

Кирилл Пензин нужен именно волновой алгоритм)

[Кирилл Пензин]

Григорий Каляшов: Тогда всё просто, берёшь свою матрицу, выбираешь некую произвольную начальную точку со значением 0, потом ищешь соседа со значением большим на 1, единицу соответственно, потом у 1 ищешь соседнюю 2 и т.д. При этом полезно было бы отмечать все уже пройденные вершины, чтобы не попасть в одну и ту же точку дважды. Причём, даже так лучше. Точка считается пройденной, если все её соседи, большие на 1 ведут в тупик.

[Кирилл Пензин]

Григорий Каляшов: Если нашёл путь, то отмечай его иным образом(любой другой флаг добавь). Потом просто сравни значения конечных точек полученных путей. Наименьшая конечная точка даст один из кратчайших путей в лабиринте.

Answer 5

[Mrrl]

Заведите ещё один массив и кладите в него направление, откуда пришли в данную клетку. Проще всего это направление передать параметром в FindPath. Потом пройдите по этим направлениям от финиша до старта.
Другой вариант - на обратном проходе искать соседнюю клетку со значением tempMap на 1 меньшим, чем в данной клетке, и идти в неё. Это дольше писать и оно чуть медленнее работает, но требует меньше памяти.
Лабиринт действительно на сетке из шестиугольников?

Comments

[Григорий Каляшов]

Mrrl в смысле? какая сетка из шестиугольников?

[Mrrl]

Григорий Каляшов: В коде проверяется 6 направлений. Для сетки из квадратов проверялось бы только 4.