Coordinate.cpp

#include "Coordinate.h"

Coordinate::Coordinate(){
  set( 0, 0 );
}
Coordinate::Coordinate( int x, int y ){
  set( x, y );
}
Coordinate::~Coordinate(){}
void Coordinate::setX( int x ){
  this->x = x;
}
void Coordinate::setY( int y ){
  this->y = y;
}
void Coordinate::set( int x, int y ){
  this->x = x;
  this->y = y;
}
Coordinate Coordinate::add( Coordinate coord ){
  return Coordinate( this->x + coord.x, this->y + coord.y );
}

Coordinate.h

#ifndef Coordinate_H
#define Coordinate_H

struct Coordinate {
  public:
    Coordinate();
    Coordinate( int x, int y );
    ~Coordinate();
    int x, y;
    void setX( int x );
    void setY( int y );
    void set( int x, int y );
    Coordinate add( Coordinate coord );
};

#endif

main.cpp

#include <iostream>
#include <vector>
#include <string>

#include "Coordinate.h"
#include "Maze.h"

using std::vector;

int main(){

  std::cout << "program begin" << std::endl << std::endl;
  
  int w = 21, h = 21;

  Maze maze( w, h );


  vector<vector<char>> map;
  maze.fillPrintMap( map );

  for( int i = 0; i < w; ++i ){
    for( int j = 0; j < h; ++j ){
      std::cout << map[j][i];
    }
    std::cout << std::endl;
  }

  std::cout << std::endl << "program end" << std::endl;

  return 0;
}

Maze.cpp

#include "Maze.h"
#include <iostream>

using std::vector;

Maze::Maze(){
  w = 20;
  h = 20;

  gen();
}
Maze::Maze( int w, int h ){
  gen( w, h );
}
Maze::~Maze(){}
void Maze::gen(){
  gen( w, h );
}
void Maze::gen( int w, int h ){
  this->w = w;
  this->h = h;

  structure.clear();
  for( int x = 0; x < w; ++x ){
    structure.push_back( vector<bool>() );
    for( int y = 0; y < h; ++y ){
      structure[ x ].push_back( WALL );
    }
  }

  stack.clear();

  stack.push_back( Coordinate( 1, 1 ) );
  stackIndex = 0;

  setCell( Coordinate( 1, 1 ), !WALL );

  int maxIndex = 0;

  int security = 1000000;
  bool keepGoing = true;
  bool first = true;

  do {

    checkNeighbours();

    int availNeighbourNumber = availableNeighbours.size();

    if( availNeighbourNumber == 0 ){

      --stackIndex;
      stack.pop_back();

    } else {
    
      Coordinate& head = stack[ stackIndex ];
      
      Coordinate &cellD = availableNeighbours[ random->gen() % availNeighbourNumber ];
      Coordinate cell = head.add( cellD );

      if( first ){
        std::cout << cellD.x << ", " << cellD.y << std::endl;
        first = false;
      }
      
      ++stackIndex;
      stack.push_back( cell );
      setCell( Coordinate( head.x + cellD.x / 2, head.y + cellD.y / 2 ), !WALL );
      setCell( cell, !WALL );

      if( stackIndex > maxIndex ){
        maxIndex = stackIndex;
        goal = cell;
      }


    } 
     
    keepGoing = --security > 0 && stackIndex > 0;

  } while ( keepGoing );
  
}
bool Maze::getCell( Coordinate coord ){
  if( coord.x > 0 && coord.x < w && coord.y > 0 && coord.y < h )
    return structure[ coord.x ][ coord.y ];
  else
    return !WALL;
}
void Maze::setCell( Coordinate coord, bool value ){
  structure[ coord.x ][ coord.y ] = value;
}
void Maze::fillPrintMap( vector<vector<char>>& map ){
  map.clear();
  
  for( int x = 0; x < w; ++x ){
    map.push_back(vector<char>());
    for( int y = 0; y < h; ++y ){
      map[ x ].push_back( structure[ x ][ y ] ? charWALL : charEMPT );
    }
  }

  map[ goal.x ][ goal.y ] = charGOAL;
}
void Maze::checkNeighbours(){

  availableNeighbours.clear();

  Coordinate head = stack[ stackIndex ];

  int i = 0;
  while( i != 4 ){
    Coordinate cell = head.add( neighbourDirs[ i ] );

    if( getCell( cell ) == WALL )
      availableNeighbours.push_back( neighbourDirs[ i ] );

    ++i;
  }
}

const Coordinate Maze::neighbourDirs[4] = {
  Coordinate(  0, -2 ),
  Coordinate(  2,  0 ),
  Coordinate(  0,  2 ),
  Coordinate( -2,  0 )
};
const bool Maze::WALL = true;
Random* Maze::random = new Random();

const char Maze::charWALL = 'x';
const char Maze::charEMPT = ' ';
const char Maze::charGOAL = '.';

Maze.h

#ifndef Maze_H
#define Maze_H

#include <vector>
#include "Coordinate.h"
#include "Random.h"

class Maze {
  public:
    Maze();
    Maze( int w, int h );
    ~Maze();
    void gen();
    void gen( int w, int h );
    std::vector<std::vector<bool>> structure;
    bool getCell( Coordinate coord );
    void setCell( Coordinate coord, bool value );
    void fillPrintMap( std::vector<std::vector<char>>& map );

  private:
    int w, h;
    std::vector<Coordinate> stack;
    int stackIndex;
    Coordinate goal;
    std::vector<Coordinate> availableNeighbours;
    void checkNeighbours();
    static const Coordinate neighbourDirs[4];
    static const bool WALL;
    static Random* random;
    static const char charWALL;
    static const char charEMPT;
    static const char charGOAL;
  };
#endif

Random.cpp

#include "Random.h"

Random::Random(){
  setSeed( static_cast<long int> (std::time(0)) ); 
}
Random::Random( long int seed ){
  setSeed( seed );
}
Random::~Random(){}
void Random::setSeed( long int seed ){
  a = seed + 5;
  b = seed + 31;
  c = seed + 1297;

  gen();
}
long int Random::gen(){

  if( c <= 0 )
    c = -c;
  c = ( b % c ) * 34332 - a;
  b = ( a + c ) * 942427;
  a += c % 422342321;

  last = c + b + a;
  if( last < 0 )
    last = -last;

  return last;
}

Random.h

#ifndef Random_h
#define Random_h

#include <ctime>

class Random {
  public:
    Random();
    Random( long int );
    ~Random();
    long int gen();
    long int last;
    void printABC();

  private:
    long int a, b, c;
    void setSeed( long int );
};

#endif