(C++) GetMazeDistances

 

GetMazeDistances is a maze code snippet to calculate the distances of all squares to the exit of a maze (for example one created with CreateMaze/CreateSloppyMaze) Walls are given the highest possible value. If the algorithm below is too confusing, For a perhaps more straightforward, though slower algorithm, view GetMazeDistancesSlow.

 

 

 

 

 

Project and source code

 

Operating system: Ubuntu 10.04 LTS Lucid Lynx

IDE: Qt Creator 2.0.0

Project type: Qt4 GUI Application

Compiler: G++ 4.4.1

Libraries used:

• Qt: version 4.7.0 (32 bit)
• STL: from GCC, shipped with Qt Creator 2.0.0

 

 

 

 

 

---

#include <vector> #include <assert> //From http://www.richelbilderbeek.nl/GetMazeDistances.htm std::vector<std::vector<int> > GetMazeDistances(   const std::vector<std::vector<int> >& maze,   const int x,   const int y) {   //Assume maze is square   assert(maze[0].size() == maze.size());   assert(maze[y][x] == 0); //Assume starting point is no wall   const int size = maze.size();   const int area = size * size;   const int maxDistance = area;   std::vector<std::vector<int> > distances(size, std::vector<int>(size,maxDistance));   std::vector<std::vector<int> > distances(size, std::vector<int>(size,maxDistance));   {     //Calculate the distances     int distance = 0;     distances[y][x] = 0; //Set final point     std::vector< std::pair<int,int> > found;     found.push_back(std::make_pair(x,y));     while(found.empty() == false)     {       ++distance;       std::vector< std::pair<int,int> > newFound;       const std::vector< std::pair<int,int> >::iterator j = found.end();       for (std::vector< std::pair<int,int> >::iterator i = found.begin(); i!=j; ++i)       for (std::vector< std::pair<int,int> >::iterator i = found.begin(); i!=j; ++i)       {         const int x = (*i).first;         const int y = (*i).second;         if ( maze[y-1][x] == 0 //No wall           && distances[y-1][x] == maxDistance) //Not already in solution         {           distances[y-1][x] = distance;           newFound.push_back(std::make_pair(x,y-1));         }         if ( maze[y+1][x] == 0 //No wall           && distances[y+1][x] == maxDistance) //Not already in solution         {           distances[y+1][x] = distance;           newFound.push_back(std::make_pair(x,y+1));         }         if ( maze[y][x+1] == 0 //No wall           && distances[y][x+1] == maxDistance) //Not already in solution         {           distances[y][x+1] = distance;           newFound.push_back(std::make_pair(x+1,y));         }         if ( maze[y][x-1] == 0 //No wall           && distances[y][x-1] == maxDistance) //Not already in solution         {           distances[y][x-1] = distance;           newFound.push_back(std::make_pair(x-1,y));         }       }       found = newFound;     }   }   return distances; }