Shortest path maze solver algorithm

[benbalach]

Hi guys! I'm working on a maze solving program. So far I got the program to solve a maze using the recursive backtracking algorithm. I represent the maze as vector<vector<Square>> where Square is an enum that contains the kind of square (empty, wall, etc.). I use a class Point that contains 2 ints which are used for subscripting the vector of vectors. I have a Point begin and Point end. Now I want the program to solve the maze using the shortest path. I can either use the A* algorithm, Dijkstra's algorithm, or the breadth first search algorithm. I looked them up, but I'm have a hard time understanding how they work and I have no idea how to port them to my code. I looked online for their pseudo code, but it confused me even more. Can anyone give me a detailed pseudo code of any of these 3 algorithms so I can port it to my code? Thanks in advance!

[LB]

What attempts have you made at porting it yourself so far?

[Smac89]

breadth first search (BFS) might be the easiest one to understand because the only data structure it requires is a queue. But BFS is only useful if you know what node you are looking for which is why BFS tries to visit as many nodes that are closest to the current point before visiting any that are further away. So for example if you have a maze that looks like a circle and you are in the middle but your destination is at one of the outer edges, BFS will first search the inner most circle of nodes then the move like that until it has searched the outer most circle

https://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode
(Comments in bold are mine)

  procedure BFS(G,v) is // G is the graph, v is the start node
      create a queue Q
      create a vector set V
      enqueue v onto Q // put v into the queue
      add v to V // add v to the set of used nodes
      while Q is not empty loop
         t ← Q.dequeue() // remove the first element from the queue
         if t is what we are looking for then
            return t
        end if
        for all edges e in G.adjacentEdges(t) loop
           u ← G.adjacentVertex(t,e)
           if u is not in V then
               add u to V // all nodes connected the current node are
               enqueue u onto Q // added to the queue and to the set of used nodes
           end if
        end loop
     end loop
     return none
 end BFS

Dijkstra's algorithm and A* algorithm will make use of a priority queue in order to find the shortest distance from the start point to the exit point (goal). The priority queue is a heap data structure which makes sure that only the best node with the smallest distance to the current node is at the top of the list.

Since your program is all about finding shortest distance from a start node to the goal node, there is no need to use A* which is used more for game trees and also requires calculating a heuristic that is used to determine the best node to choose.

So in that case, Dijkstra's is the way to go. If you wish to do backtracking after you find the shortest path from your start node to the goal node, you can decide to simply put the all found nodes into a stack as you find them and in the end simply pop all nodes from the stack to see the path. This works because Dijkstra's guarantees that each node found is the shortest path from itself to the start node

https://en.wikipedia.org/wiki/Dijkstra's_algorithm#Using_a_priority_queue
(Comments in bold are mine)

function Dijkstra(Graph, source):
      dist := []
      previous := []
      dist[source] := 0    // Initializations
      for each vertex v in Graph:           
          if v ≠ source
              dist[v] := infinity    // Unknown distance from source to v
              previous[v] := undefined    // Predecessor of v
          end if
          PQ.add_with_priority(v,dist[v])
      end for 


     while PQ is not empty:                 // The main loop
         u := PQ.extract_min()              // Remove and return best vertex
         for each neighbor v of u:          // where v has not yet been removed from PQ.
             alt = dist[u] + length(u, v)   // distance from u to node v
             if alt < dist[v]               // if the new distance is smaller than 
                                            // the distance to node v
                 dist[v] := alt             // change distance to node v
                 previous[v] := u           // set u as the best node connected to v
                 PQ.decrease_priority(v,alt)    // reorder v in the priority queue 
                                                // by calling decrease_priority
             end if
         end for
     end while
     return previous[]

In short:

-> Set the distance from the source to source to 0
-> Set the distance from all nodes (except from source) to the source to a very large value (infinite)
-> Put all nodes in the graph into the min priority queue
-> prev_node is null
-> while the priority queue is not empty:
----> remove the node u with the smallest priority from the queue
----> set prev_node as the previous node to this node
----> prev_node is u
----> for all nodes v having an edge to this node:
-------> if distance to u plus distance from u to v is smaller than current distance stored at v
-----------> update v's distance
-----------> and set v's previous node as prev_node
-----------> reorder v in the priority queue

So the algorithm is easy straightforward to implement, what you might have trouble with is implementing the graph data structure.

[Stewbond]

Has any used the Ant Colony Optimization algorithm? It uses the model of ants who leave behind traces of pheromones behind them while they search for, and return with, food. The stronger the pheremone scent, the more likely the next ant will follow that path. As more ants travel, they converge on the shortest path.

[benbalach]

@ Smac89

I find Dijkstra's algorithm the easiest to understand. How do I go about implementing the graph and node (considering how I represent the maze in the program)? I don't want to break my code or have to rewrite anything.

[Smac89]

You should post the code you have so far then we can go from there

[ac517]

This doesn't do exactly what you want, but demonstrates BFS.

Reads a text file all lower case with a rectangular maze of x's and o's where x is a wall and o is an open space. The cell with "s" is the start and "e" is the end.

Like this:

oooooooxooooooooooooxoooooooooo
oooeoooxooooooooooooxoooooooooo
oooooooxooxxxxxxxxxxxxxxxxxxxoo
ooxxxxxxooooooooooooxoooooooooo
ooooooooooxxxxxxxxxxxoxoooooooo
ooooooooooxoooosooooxoxoooooooo
ooooooooooxoooooooooxoxoooooooo
ooooooooooxoooooooooxoxoooooooo
ooooooooooxoooooooooooxoooooooo
ooooooooooxxxxxxxxxxxoooooooooo
ooooooooooooooooooooxoooooooooo
ooooooooooooooooooooxoooooooooo
ooooooooooooooooooooxoooooooooo
ooooooooooooooooooooxoooooooooo
ooooooooooooooooooooxoooooooooo
ooooooooooooooooooxxooooooooooo
ooooooooooooooooooxoooooooooooo

Prints out the shortest distance from the source cell to all other cells, -1 is a wall. Also prints out the distance to the end cell.

The idea is that we initialize a grid of integers such that the source is zero, walls are -1, and all open cells are a large value like 2^30 i used. Then we add the source cell to the queue and start. While Q isn't empty we pop off the queue and for all non-walls in the 8 surrounding cells (we can move diagonally in my example) the current cell value is the min of either its current value or its neighbor's value+1 because it costs one step to move from the neighbor. Add neighbor to the Q if we haven't been there yet. Keep a set of visited cells so we don't just keep revisiting the same ones over and over again.

Here is the output for the above maze, as you see the source is 0, walls are -1, and all the rest are the fewest number of moves required to get there.

Even though you're probably looking for the actual shortest path, I just figured it'd help to see something other than pseudo-code and somewhat cryptic wikipedia articles.

34	34	34	34	34	35	36	-1	32	32	32	32	33	34	35	36	37	38	39	40	-1	22	21	20	19	18	17	16	16	16	16	
33	33	33	33	34	35	36	-1	31	31	31	32	33	34	35	36	37	38	39	40	-1	22	21	20	19	18	17	16	15	15	15	
32	32	32	33	34	35	36	-1	30	30	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	14	15	
32	31	-1	-1	-1	-1	-1	-1	29	29	29	30	31	32	33	34	35	36	37	38	-1	10	10	11	12	13	13	13	13	14	15	
32	31	30	29	28	28	28	28	28	28	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	9	-1	11	12	12	12	12	13	14	15	
32	31	30	29	28	27	27	27	27	27	-1	4	3	2	1	0	1	2	3	4	-1	8	-1	11	11	11	11	12	13	14	15	
32	31	30	29	28	27	26	26	26	26	-1	4	3	2	1	1	1	2	3	4	-1	7	-1	10	10	10	11	12	13	14	15	
32	31	30	29	28	27	26	25	25	25	-1	4	3	2	2	2	2	2	3	4	-1	6	-1	9	9	10	11	12	13	14	15	
32	31	30	29	28	27	26	25	24	24	-1	4	3	3	3	3	3	3	3	4	5	6	-1	8	9	10	11	12	13	14	15	
32	31	30	29	28	27	26	25	24	23	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	6	7	8	9	10	11	12	13	14	15	
32	31	30	29	28	27	26	25	24	23	22	21	20	19	18	17	17	17	17	17	-1	7	7	8	9	10	11	12	13	14	15	
32	31	30	29	28	27	26	25	24	23	22	21	20	19	18	17	16	16	16	16	-1	8	8	8	9	10	11	12	13	14	15	
32	31	30	29	28	27	26	25	24	23	22	21	20	19	18	17	16	15	15	15	-1	9	9	9	9	10	11	12	13	14	15	
32	31	30	29	28	27	26	25	24	23	22	21	20	19	18	17	16	15	14	14	-1	10	10	10	10	10	11	12	13	14	15	
32	31	30	29	28	27	26	25	24	23	22	21	20	19	18	17	16	15	14	13	-1	11	11	11	11	11	11	12	13	14	15	
32	31	30	29	28	27	26	25	24	23	22	21	20	19	18	17	16	15	-1	-1	12	12	12	12	12	12	12	12	13	14	15	
32	31	30	29	28	27	26	25	24	23	22	21	20	19	18	17	16	16	-1	13	13	13	13	13	13	13	13	13	13	14	15

#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#include <iostream>
#include <fstream>
#include <set>

using namespace std;

void print2D(vector<vector<int>> arr)
{
   for(int i=0;i<arr.size();++i)
   {
      for(int j=0;j<arr[0].size();++j)
      {
         cout << (arr[i][j]==(1<<30)?-9:arr[i][j]) << "   ";
      }
      cout << endl;
   }
}

void solve(vector<vector<int>>& maze, int si, int sj, int ei, int ej)
{
   queue<pair<int,int>> Q;
   set<pair<int,int>> S;
   int M=maze.size(),N=maze[0].size();
   S.insert(make_pair(si,sj));
   Q.push(make_pair(si,sj));
   
   while(!Q.empty())
   {
      pair<int,int> p = Q.front();
      Q.pop();
      for(int x : {-1,0,1})
      {
         for(int y : {-1,0,1})
         {
            if(x==0 && y==0) continue;
            int i = p.first+x;
            int j = p.second+y;
            if(i<0 || i>=M || j<0 || j>=N || maze[i][j]==-1) continue;
            maze[i][j]=min(maze[i][j],maze[p.first][p.second]+1);
            if(S.find(make_pair(i,j))==S.end())
            {
               S.insert(make_pair(i,j));
               Q.push(make_pair(i,j));
            }
         }
      }
   } 
}

int main(int argc, char** argv)
{
   ++argv;
   ifstream infile(*argv);
   string s;
   int v=0,si=0,sj=0,ei=0,ej=0;
   vector<vector<int>> maze;
   int i=0;
   while(infile >> s)
   {
      vector<int> row;
      for(int j=0;j<s.size();++j)
      {
         if(s[j]=='s')
         {
            si=i;
            sj=j;
            row.push_back(0);
         }
         else if(s[j]=='e')
         {
            ei=i;
            ej=j;
            row.push_back((1<<30));
         }
         else 
         {
            row.push_back((s[j]=='x'?-1:(1<<30)));
         }
      }
      maze.push_back(row);
      ++i;
   }
   
   solve(maze,si,sj,ei,ej);
   print2D(maze);
   cout << "Shortest distance to end: " << maze[ei][ej] << endl;
   return 0;
}

You'll need to compile with -std=c++0x or -std=c++11