Go back to Richel Bilderbeek's homepage.

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

 

 

 

 

 

(C++) GetDeadEnds

 

GetDeadEnds is a maze code snippet to obtain all the dead ends 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:

 

 

 

 

 

#include <vector>

//From http://www.richelbilderbeek.nl/CppGetDeadEnds.htm
std::vector<std::pair<int,int> > GetDeadEnds(const std::vector<std::vector<int> >& maze)
std::vector<std::pair<int,int> > GetDeadEnds(const std::vector<std::vector<int> >& maze)
{
  const int size = maze.size();

  std::vector<std::pair<int,int> > deadEnds;

  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) deadEnds.push_back(std::make_pair(x,y));

    }
  }
  return deadEnds;
}

 

 

 

 

 

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

Go back to Richel Bilderbeek's homepage.

 

Valid XHTML 1.0 Strict