Flowy generates (usually) solvable Flow Free levels.

Flowy.cpp

//Has to be complied and built using the option -std=c++0x
//TODO: Beautify some of the functions. Introduce parameters to control the difficult of the generated board.
#include <tuple>
#include <ctime>
#include <vector>
#include <ctype.h>
#include <cstdlib>
#include <iostream>

typedef std::tuple<int, int, int> flow;

class Board {
	
	private:
		
		int N;
		std::vector<std::vector <char> > board;
		
		flow get_seed();
		flow move(flow t);
		void remove_flow(char c);
	
	public:
		
		Board();
		int fix();
		int full();
		void add_flow(char c);
		void remove_short(char c, int i, int j);
		void print_board(int question);
};

/**
* Constructor decides the side of the board randomly within sane limits. Also prefills the board with ".".
*/
Board::Board() {
	
	srand((unsigned) time(NULL));
	N = rand() % 6 + 4;
	board.resize(N);
	
	for(int i = 0; i < N; i++) {
		board[i].resize(N);
		
		for(int j = 0; j < N; j++)
			board[i][j] = '.';
	}
}

/**
* Loops throughout the board and returns 0 if it is not full else 1.
*/
int Board::full() {
	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			if(board[i][j] == '.')
				return 0;
	
	return 1;
}

/**
* Prints the board by allocating diffrent colors for different flows.
*/
void Board::print_board(int question = 0) {
	
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			if(board[i][j] == '.' || (question && board[i][j] > 'Z')) {
				std::cout << ".  ";
				continue;
			}
			std::cout << "\033[1;" << tolower(board[i][j]) - 66 << "m" << board[i][j] << "\033[0m  ";
		}
		std::cout << '\n';
	}
}

/**
/The function replaces all instances of the given flow characters by the "." character. Used to remove messed up flows.
*/
void Board::remove_flow(char c) {
	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			if(tolower(board[i][j]) == c)
				board[i][j] = '.';
}

/**
* Adds a flow to the board by using the character passed as the flow character. Calls the get_seed() function to get the intial position
* and direction of flow. The start and end of the flow are marked by uppercase characters while the path is made up of lowercase characters.
* The length of the flow is also decided randomly at the beginning of the function.
*/
void Board::add_flow(char c) {
	
	flow f = get_seed();
	int flow_length = rand() % N + 1;
	
	board[std::get<0>(f)][std::get<1>(f)] = toupper(c);
	
	for(int x = 0; x < flow_length + 1; x++) {
		try {
			f = move(f);
			board[std::get<0>(f)][std::get<1>(f)] = (x != flow_length) ? c : toupper(c);
		}
		
		catch(...) {
			if(x < 2)
				remove_flow(c);
			
			else
				board[std::get<0>(f)][std::get<1>(f)] = toupper(c);
			
			break;
		}
	}
	
	remove_short(toupper(c), std::get<0>(f), std::get<1>(f));
}

/**
* Seeks through the board collecting index of empty cells and returns a random index along with a random direction.
* The index along with the direction is returned as a tuple.
* Returned data acts as a seed for a new flow.
*/
flow Board::get_seed() {
	
	std::vector<flow> f;
	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			if(board[i][j] == '.')
				f.push_back(std::make_tuple(i, j, rand() % 4));
	
	return f[rand() % f.size()];
}

/**
* Receives a tuple containing the current cell and direction and makes an attempt to move along the current direction.
* Such an attempt may fail due to one of the following two reasons.
*   1. A pre-drawn flow stands in the way.
*   2. Current flow has reached the border of the board.
* Under such conditions, the functions recursively calls itself by turning in the perpendicular direction.
* 
* A flow might also be stuck in a dead end. (surrounded by border or other flow in all four directions)
* Such conditions are identified and the flow is prematurely terminated.
* 
* A randomness in the path of the flow has also been included so that it takes turns every now and then to increases
* difficulty of the level.
*/
flow Board::move(flow f) {
	
	int i = std::get<0>(f);
	int j = std::get<1>(f);
	int direction = std::get<2>(f);
	
	//Check if the current position is at a dead end.
	if(i == 0 || board[i - 1][j] != '.')
		if(i == N - 1 || board[i + 1][j] != '.')
			if(j == 0 || board[i][j - 1] != '.')
				if(j == N - 1 || board[i][j + 1] != '.')
					throw std::exception();
	
	switch(direction) {
		//Try moving left.
		case 0:
			if(i > 0 && board[i - 1][j] == '.' && rand() % 10 > 8)
				return std::make_tuple(i - 1, j, direction);
			
			//Turn along perpendicular axis. (up or down)
			return move(std::make_tuple(i, j, rand() % 2 + 2));
		
		//Try moving right.
		case 1:
			if(i + 1 < N && board[i + 1][j] == '.' && rand() % 10 > 8)
				return std::make_tuple(i + 1, j, direction);
			
			//Turn along perpendicular axis. (up or down)
			return move(std::make_tuple(i, j, rand() % 2 + 2));
		
		//Try moving up.
		case 2:
			if(j > 0 && board[i][j - 1] == '.' && rand() % 10 > 8)
				return std::make_tuple(i, j - 1, direction);
			
			//Turn along perpendicular axis. (left or right)
			return move(std::make_tuple(i, j, rand() % 2));
		
		//Try moving down.
		default:
			if(j + 1 < N && board[i][j + 1] == '.' && rand() % 10 > 8)
				return std::make_tuple(i, j + 1, direction);
			
			//Turn along perpendicular axis. (left or right)
			return move(std::make_tuple(i, j, rand() % 2));
	}
}

/**
* Called after multiple flows have been added to the board. Tries to move the start and end of each flow into
* empty spaces to further fill the board. Returns an integer stating the result of the effort. The function is called
* multiple times to ensure optimal board configuration is achieved.
*/
int Board::fix() {
	
	int changed = 0;
	
	for(int i =0; i < N; i++)
		for(int j = 0; j < N; j++)
			if(board[i][j] == '.') {
				if(i != 0 && isupper(board[i - 1][j])) {
					board[i][j] = board[i - 1][j];
					board[i - 1][j] = tolower(board[i -1][j]);
					changed = 1;
				}
				
				else if(i != N - 1 && isupper(board[i + 1][j])) {
					board[i][j] = board[i + 1][j];
					board[i + 1][j] = tolower(board[i + 1][j]);
					changed = 1;
				}
				
				else if(j != 0 && isupper(board[i][j - 1])) {
					board[i][j] = board[i][j - 1];
					board[i][j - 1] = tolower(board[i][j - 1]);
					changed = 1;
				}
				
				else if(j != N - 1 && isupper(board[i][j + 1])) {
					board[i][j] = board[i][j + 1];
					board[i][j + 1] = tolower(board[i][j + 1]);
					changed = 1;
				}
				
				if(changed)
					remove_short(board[i][j], i, j);
			}
	
	return changed;
}

/**
* Ensures that flows with adjacent start and end points are removed.
*/
void Board::remove_short(char c, int i, int j) {
	
	if((i != 0 && board[i - 1][j] == c) || (i != N - 1 && board[i + 1][j] == c) || (j != 0 && board[i][j - 1] == c) || (j != N - 1 && board[i][j + 1] == c))
		remove_flow(tolower(c));
}

int main() {
	
	Board b;
	const char alphas[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
	
	for(int i = 0; i < 26 && !b.full(); i++)
		b.add_flow(alphas[i]);
	
	//Nasty hack to fill the board as much as possible. :)
	while(!b.full() && b.fix());
	
	b.print_board(0);
	
	return 0;
}