(C++) GetNonDeadEnds

 

GetNonDeadEnds is a maze code snippet to obtain all the non-dead-ends (that is, spots with at least two adjacent free spots) in a maze, for example the mazes created by CreateMaze/CreateSloppyMaze.

 

 

 

 

 

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> //From http://www.richelbilderbeek.nl/CppGetNonDeadEnds.htm std::vector<std::pair<int,int> > GetNonDeadEnds(const std::vector<std::vector<int> >& maze) std::vector<std::pair<int,int> > GetNonDeadEnds(const std::vector<std::vector<int> >& maze) {   const int size = maze.size();   std::vector<std::pair<int,int> > nonDeadEnds;   for (int y=1; y!=size-1; ++y)   {     for (int x=1; x!=size-1; ++x)     {       if (maze[y][x] != 0) continue; //Continue if here is a wall       const int nWalls         = (maze[y+1][x ] == 1 ? 1 : 0)         + (maze[y-1][x ] == 1 ? 1 : 0)         + (maze[y ][x+1] == 1 ? 1 : 0)         + (maze[y ][x-1] == 1 ? 1 : 0);       if (nWalls < 3) nonDeadEnds.push_back(std::make_pair(x,y));     }   }   return nonDeadEnds; }