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;

}

Go back to Richel Bilderbeek's C++ page.

Go back to Richel Bilderbeek's homepage.

(C++) GetNonDeadEnds

Project and source code