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;
using std::string;

const Coordinate dirs[] = {
  Coordinate( -1,  0 ),
  Coordinate(  0,  1 ),
  Coordinate(  0, -1 ),
  Coordinate(  1,  0 )
};
const char left[] = { 'a', 'h' };
const char down[] = { 's', 'j' };
const char up[] = { 'w', 'k' };
const char right[] = { 'd', 'l' };

bool isPartOf( const char arr[], char val ){
  return arr[0] == val || arr[1] == val;
}

int main(){

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

  std::cout << "maze width: ";
  std::cin >> w;

  std::cout << "maze height: ";
  std::cin >> h;

  if( w % 2 == 0 )
    w += 1;
  if( h % 2 == 0 )
    h += 1;

  Maze maze( w, h );


  vector<vector<char>> map;
  Coordinate player( 1, 1 );
  string dir;

  int round = 0;

  int security = 1000;
  while( --security > 0 && !( player.x == maze.goal.x && player.y == maze.goal.y ) ){
  
    std::cout << "start frame" << std::endl;

    maze.fillPrintMap( map );

    map[ player.x ][ player.y ] = 'o';

    std::system( "clear" );

    std::cout << std::endl << " Round: " << ++round << "\t pos: [" << player.x << "," << player.y << "]" << std::endl << std::endl; 

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

    std::cout << std::endl << " next moves (hjkl/aswd+ENTER): ";
    std::cin >> dir;

    unsigned int dirIndex = -1;
    while( ++dirIndex < dir.length() ){
      if( isPartOf( left, dir[ dirIndex ] ) && !maze.getCell( player.add( dirs[0] ) ) ){
        player = player.add( dirs[ 0 ] );
      }
      if( isPartOf( down, dir[ dirIndex ] ) && !maze.getCell( player.add( dirs[1] ) ) ){
        player = player.add( dirs[ 1 ] );
      }
      if( isPartOf( up, dir[ dirIndex ] ) && !maze.getCell( player.add( dirs[2] ) ) ){
        player = player.add( dirs[ 2 ] );
      }
      if( isPartOf( right, dir[ dirIndex ] ) && !maze.getCell( player.add( dirs[3] ) ) ){
        player = player.add( dirs[ 3 ] );
      }
    }

  }

  std::cout << security << std::endl;

  if( security == 0 )
    std::cout << "took too much, we were afraid the program broke" << std::endl;
  else
    std::cout << "YOU WIN!" << 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;

  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 );
      Coordinate hcell = head.add( Coordinate( cellD.x / 2, cellD.y / 2 ) );
      
      ++stackIndex;
      stack.push_back( cell );
      setCell( hcell, !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 );
    Coordinate goal;

  private:
    int w, h;
    std::vector<Coordinate> stack;
    int stackIndex;
    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