How to find the shortest path in a maze?

Question

Programming

To find the shortest path in the maze, I use the wave algorithm, I did it, but the shortest path cannot be restored.
There are 2 vectors:

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

In the end cell:
map[finishX][finishY] = 19;

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

The algorithm itself:

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); 
};

After passing through the wave algorithm , the
maze
looks like this : 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 - wall
Tell me how to find the shortest path?

Answer 1

qiao.github.io/PathFinding.js/visual

Answer 2

Start from the end and go down the numbers until you reach the beginning.

Answer 3

I would suggest reading some book about graph theory. I remember teaching pathfinding algorithms on this subject. But that was a very long time ago. So entering the search engine "graph theory book". The subject is not difficult, so you can immediately search for the chapter you need. I don't think it will be hard to understand.

Answer 4

You already have a graph matrix, use Dijkstra's Algorithm

Answer 5

Get another array and put in it the direction from where you came to this cell. The easiest way is to pass this direction as a parameter to FindPath. Then follow these directions from the finish to the start.
Another option is to look for a neighboring cell with a tempMap value that is 1 less than in the given cell on the reverse pass, and go to it. It takes longer to write and is slightly slower, but requires less memory.
Is the maze really on a grid of hexagons?