Determining probability of finding exit

[2E1TqMoL]

Hey guys,

I've got the task to write a program which reads a kinda maze from a .txt file and marks the fields from which a person starting there could reach an exit. However there's a catch. When starting and everytime the person hits a wall, it randomly decides in which direction it will continue. Now for a maze like this:
https://gyazo.com/56560db0a2f0d6b3e27bf7e1c3aa42d4
the areas where the probability of finding an exit is 100% are marked green (I know it looks bad ;) . In every other case the person could end up in an infinite loop.

I have quite a bit of the program working, it finds allt he points I've marked above, but it also finds some more...
I would really appreciate it if somebody could have a look at the code I've got so far :).

#include <iostream>                             
#include <fstream>                              
#include <string>
#include <sstream>
#include <vector>
#include "random.cpp"



typedef std::vector<std::vector<char>> field_type;


struct vek
	{
		int y, x;
	};

vek operator+(vek a, vek b)   
{                                                            
	vek ret;
	ret.x= a.x + b.x;
	ret.y = a.y + b.y;
	return ret;
}


void init(std::string filename);
void start(field_type& vector, field_type& winner, int remCells);
void output(field_type vector, field_type winner);
bool test(field_type& vector, vek position, int r, vek Dir[]);
																	

int main()
{
	std::string filename;

	std::cout << "Please tell me the name of the file (with .txt):"<<std::endl;
	std::cin >> filename;	
	
	init(filename);
	
	std::cin.ignore();
	std::cin.get();
	return 0;
}

void init(std::string filename)
{

	int remCells = 0; 
	std::ifstream File;  
	File.open(filename, std::ios::in);


		
		while(!File)
		{
			std::cout << "Error: File not found!\n\n";
			std::cout << "Please tell me the name of the file (with .txt):"<<std::endl;
			std::cin >> filename;
			File.open(filename, std::ios::in);
		}

     
		
		std::string line;
		std::string buffer; 
		int height = 0;
		int width = 0;

		while (File.good()) 
		{              
			
			std::getline(File, line);	
			buffer += line;
			height++;
		}
		width = line.length();
		
		field_type vector(height, std::vector<char>(width)); 
	    feld_typ winner(height, std::vector<char>(width));

		int i = 0;
		for ( int j = 0; j < heigth; j++)
		{

			for ( int k = 0; k < width; k++)
			{
				vector[j][k] = buffer[i];
				std::cout << vector[j][k];
				if(vector[j][k] == ' ') remCells++;
				winner[j][k] = vector[j][k];
				i++;
			}
			std::cout << std::endl;
		}
		std::cout << std::endl;
	
	std::cin.ignore();
	std::cin.get();
	start(vector, winner, remCells);

}

void start(field_type& vector, field_type& winner, int remCells)
{
	
	
	vek Dir[] = { {0,-1}, {0,1}, {1,0}, {-1,0} };
	vek position;
	int z = 1;
	bool north, south, east, west;
	
	while(remCells > 0)
	{

		for(int i = 0; i < vector.size(); i++)
		{
			for (int j = 0; j < vector[i].size(); j++)
			{
				if (vector[i][j] == ' ')
				{
					position.x = j;
					position.y = i;
					
					north = test(vector, position, 0, Dir);
					south = test(vector, position, 1, Dir);
					east = test(vector, position, 2, Dir);
					west = test(vector, position, 3, Dir);
		
					if ( north && south && east && west) winner[i][j] = 'G';
					
					remCells--;
					for(int k = 0; k < vector.size(); k++)
					{
						for (int l = 0; l < vector[k].size(); l++)
						{
							if(vector[k][l]== '.')
							{
								vector[k][l] = ' ';
							}
						}		
					}
				}
			}
		}
	}
	output(vector,winner);
}


bool test(field_type& vector, vek position, int r, vek Dir[])
{
	bool exit = false;
	int alreadyVisited = 0;
	do{
						vector[position.y][position.x] = '.';
								
						if (vector[position.y + Dir[r].y][position.x + Dir[r].x] == '#')
						{
							r = Random::rnd(0,3);
						}
						else
						{
							position = position + Dir[r];
						}
						if(vector[position.y][position.x] == '.')
						{
							alreadyVisited++;
						}
						if(vector[position.y][position.x] == 'E')
						{
							exit = true;
							break;
						}
					} while(alreadyVisited < 100000);
	return exit;

}


void output(field_type vector, field_type winner)
{
	for ( int j = 0; j < vector.size(); j++)
		{

			for ( int k = 0; k < vector[j].size(); k++)
			{
				std::cout << vector[j][k];
			}

			std::cout << std::endl;
		}
		std::cout << std::endl;

		std::cout << std::endl << std::endl << "WINNERS"<< std::endl<< std::endl;
		
		for ( int j = 0; j < vector.size(); j++)
		{

			for ( int k = 0; k < vector[j].size(); k++)
			{
				std::cout << winner[j][k];
			}

			std::cout << std::endl;
		}
		std::cout << std::endl << std::endl;
}

[Duthomhas]

I get no output for this at all... (after fixing some typos -- you should cut and paste working examples when you post).

I haven't looked too hard at it, but I do notice you are using a PRNG in there...
Don't.
The solution to this problem is deterministic.

The idea is weird at first glance, but simple:
If someone trying to solve the maze chooses a random direction to walk at each juncture (every time he is forced to turn because he hit a wall), the possibility of exiting should always exist.

Let's consider a few scenarios:

(1)
Our first scenario we start at the solid brick and follow in one direction until forced to turn.
It is simple enough: we have two possible directions to choose, and at each turn two again -- one of which is back the way we started. No matter how long we spend going back and forth on the top row, the instant we "randomly" turn south we will walk into an exit.

# # # # # # # # # # # #
#   # ┌───█─────┐ #   #
#     │ # #     │     #
#     │ #       E #   #
#     │         # #   #
#     │               #
#   # E         E # # #
# # # # # # # # # # # #

(2)
Our second scenario is similar. The only difference is that at each juncture we have more decisions. At no point, however, does any decision lead us into a path where we cannot eventually find our way to an exit.

# # # # # # # # # # # #
#   # ┌───────┬─┐ #   #
#     │ # #   │ │     #
#     │ # ┌───█─E #   #
#     │   │   │ # #   #
#     │   │   │       #
#   # E───┴───┴─E # # #
# # # # # # # # # # # #

(3)
Our final scenario starts us at a bad position.
While it is very similar to our last starting position -- it does indeed present the random possibility of finding an exit -- it also presents the possibility of wandering off the the left side of the board, where, as we can see, there is no escape. (Remember, in order to turn, you must first walk into a wall. So it is possible to get there, but unless you "randomly" turn immediately back the way you came, you cannot get out.)

# # # # # # # # # # # #
# ║ # ┌───────┬─┐ #   #
# ║   │ # #   │ │     #
# ║   │ #     │ E #   #
# ╟─────┬─────┤ # #   #
# ║   │ │     │       #
# ║ # E─█─────┴─E # # #
# # # # # # # # # # # #

You can check in any time you like, but you can never leave.

In order to find those spots on the board where the only possibility is successful exit, you must follow every path available from your start position.

Using the first example, we start at (1,5).
Then we follow all possible directions.
To the west, we go to (1,3), then down to (6,3) which is an exit.
To the east, we go to (1,8), then down to (3,8) which is also an exit.
Having followed every path from every juncture we have verified that all paths lead to exit.

Hopefully this has suggested something to you:


TL;DR:
In order to solve this, you should be thinking of your maze as a graph and use a search algorithm on it (DFS or BFS, either will do):
    • If all the leaves in your search yield exits, then your start position is golden.
    • If any leaf in your search yields a dead end, then your start position is no good.

This is a fairly brute-force solution. In more advanced algorithms courses you can learn about stuff that can do it more efficiently, but don't worry any about that...

Hope this helps.

[2E1TqMoL]

Sorry about the typos ;). I also thought about using a brute-force algorithm, however there are some fairly large mazes (51x25) with a complex structure, where a brute-force solution would need quite a lot of time... Do you have any other idea?

[Duthomhas]

No, not without added complexity for which you are unprepared.

If you are concerned about time recomputing subproblems, memoize.