Maze Gen Issue

[Hephaestus1233]

So when I execute my code, it seems to get stuck in a loop and then stop.
However I don't understand why because I inserted many points for the loop to either stop or break.
When I inserted a few breakpoints, I got an error that stated that one of my string variables couldn't access something. And it was located in a file called "xstring". I assume the file is the one you import using
#include <string>
but since I have no idea what is going on, I was hoping one of you would be willing to help me.

Here is the section of code with the error:

  void generateMaze(string maze[13][13]) {
	int sCell[2];
	getStarterCell(sCell);
	bool loop = true;
	int cCell[2] = {sCell[0], sCell[1]};
	int backable = 0;
	while (loop) { // gotta loop!
		string nDir = newD(maze, sCell); //breakpoint inserted here causes "access" error in xstring
		int nexCell[2]; //the next cell
		if (nDir == "None") { //backtrack start
			nDir = backD(maze, sCell);
			if (nDir == "None") {
				cout << "Error, Backtracking issue! Backable: " << backable;
				break;
			}
			else {
				backable--;
				nexCell[0] = {getNX(maze, cCell[0], nDir, 2) };
				nexCell[1] = {getNY(maze, cCell[1], nDir, 2) };
			}
		}
		else { //normal procedures
			backable++;
			nexCell[0] = {getNX(maze, cCell[0], nDir, 2)};
			nexCell[1] = {getNY(maze, cCell[1], nDir, 2)};
		}
		destWall(maze, cCell[0], cCell[1], nDir);
		cCell[0] = nexCell[0];
		cCell[1] = nexCell[1];
		if (backable <= 0) {
			cout << "Maze (should be) finished!";
			loop = false;
			break;
		}
	}
}

[ne555]

we may need to run your program.
post your full code and any necessary input.

[Hephaestus1233]

Full code:

//Maze using Recursive Backtracker Algorithm
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;

/*
System to circumvent making classes:
Unvisited Cells: O (Open Cell)
Visited Cells: X (First visit)
Used Cells: U (Backtracked visit)
Destroyed Walls: D
In cell arrays 0 = x, 1 = y
*/

void outputMaze(string table[13][13]) { //output the maze
	int x = 0;
	int y = 0;
	while (y < 13) {
		cout << table[x][y];
		if (x == 12) {
			cout << " \n";
			y++;
			x = 0;
		}
		else {
			x++;
		};
	};
}

void inputMaze(string maze[13][13]) { //create the maze
	int x = 0;
	int y = 0;
	while (y < 13) {
		int cX = x + 1;
		int cY = y + 1;
		if (y == 0 || x == 0) {
			maze[x][y] = "# ";
		}
		else if (y == 6 || x == 6) {
			maze[x][y] = "# ";
		}
		else if (cX % 2 == 0 && cY % 2 == 0) {
			maze[x][y] = "O ";
		}
		else {
			maze[x][y] = "# ";
		}
		if (x == 12) {
			x = 0;
			y++;
		}
		else {
			x++;
		}
	}
}
void cleanUp(string maze[13][13]) { //clean up the maze
	int x = 0;
	int y = 0;
	while (y < 13) {
		if (maze[x][y] == "U ") {
			maze[x][y] = "  ";
		}
		else if (maze[x][y] == "D ") {
			maze[x][y] = "  ";
		}
		else if (maze[x][y] == "O ") {
			maze[x][y] = "  ";
		}
		else if (maze[x][y] == "X ") {
			maze[x][y] = "  ";
		}
		if (x == 12) {
			x = 0;
			y++;
		}
		else {
			x++;
		}
	}
}

int getNX(string maze[13][13], int xpos, string dir, int c) { //get the new x 
	int x;
	if (dir == "Left") {
		if (xpos == 1) {
			x = xpos;
		}
		else {
			x = xpos - c;
		}
	}
	else if (dir == "Right") {
		if (xpos == 12) {
			x = xpos;
		}
		else {
			x = xpos + c; //c should not be any other number than 1 or 2
		}
	}
	else {
		x = xpos;
	}
	return x;
}

int getNY(string maze[13][13], int ypos, string dir, int c) { //get the new y cell
	int y;
	if (dir == "Up") {
		if (ypos == 1) {
			y = ypos;
		}
		else {
			y = ypos - c; //c should not be any other number than 1 or 2
		}
	}
	else if (dir == "Down") {
		if (ypos == 12) {
			y = ypos;
		}
		else {
			y = ypos + c;
		}
	}
	else {
		y = ypos;
	}
	return y;
}

string cellType(string maze[13][13], int x, int y) { // get us the cell type so we can do some more functions
	string type;
	if (maze[x][y] == "U ") {
		type = "Used";
	}
	else if (maze[x][y] == "D ") {
		type = "DestW";
	}
	else if (maze[x][y] == "O ") {
		type = "Open";
	}
	else if (maze[x][y] == "X ") {
		type = "Visited";
	}
	else if (maze[x][y] == "# ") {
		type = "Wall";
	}
	return type;
}

void destWall(string maze[13][13], int x, int y, string dir) { //destroy wall
	int change = 1;
	int wall[2] = { getNX(maze,x,dir,change), getNY(maze,y,dir,change) };
	//string type = cellType(maze,wall[1],wall[2]);
	maze[wall[0]][wall[1]] = "D";
}

void getStarterCell(int sCell[2]) { //self explanatory
	srand(time(0));
	int posi[6] = { 1,3,5,7,9,11 };
	sCell[0] = posi[(rand() % 6)];
	sCell[1] = posi[(rand() % 6)];
}

string newD(string maze[13][13], int cCell[2]) { //first step is getting the new direction
	string nDir = "";
	string dirs[4] = { "Left", "Right", "Down", "Up" };
	string dTypes[4];
	string pDirs[4];
	int index = 0;
	for (int i = 0; i < 4; i++) { //determine usability of each direction
		int tx = getNX(maze, cCell[0], dirs[i], 2);
		int ty = getNY(maze, cCell[2], dirs[i], 2);
		string tType = cellType(maze, tx, ty);
		dTypes[i] = tType;
	}
	for (int i = 0; i < 4; i++) { //parse through array to give access to new, usable directions
		if (dTypes[i] == "Open") {
			pDirs[index] = dirs[i];
			index++;
		}
	}
	if (index > 0) {
		int ttt = (rand() % index);
		nDir = pDirs[ttt];
	}
	else {
		nDir = "None";
	}
	return nDir;
}

string backD(string maze[13][13], int cCell[2]) { //if the first step failed then we find the next backtrackable spot
	string nDir = "";
	string dirs[4] = { "Left", "Right", "Down", "Up" };
	string dTypes[4];
	string pDirs[4];
	int index = 0;
	for (int i = 0; i < 4; i++) { //determine usability of each direction
		int tx = getNX(maze, cCell[0], dirs[i], 2);
		int ty = getNY(maze, cCell[2], dirs[i], 2);
		string tType = cellType(maze, tx, ty);
		dTypes[i] = tType;
	}
	for (int i = 0; i < 4; i++) { //parse through array to give access to new, usable directions
		if (dTypes[i] == "Visited") {
			pDirs[index] = dirs[i];
			index++;
		}
	}
	if (index > 0) {
		int ttt = (rand() % index);
		nDir = pDirs[ttt];
	}
	else {
		nDir = "None";
	}
	return nDir;
}

void generateMaze(string maze[13][13]) {//need complete remake
	int sCell[2];
	getStarterCell(sCell);
	bool loop = true;
	int cCell[2] = {sCell[0], sCell[1]};
	int backable = 0;
	while (loop) { // gotta loop!
		string nDir = newD(maze, sCell); //the new direction
		int nexCell[2]; //the next cell
		if (nDir == "None") { //backtrack start
			nDir = backD(maze, sCell);
			if (nDir == "None") {
				cout << "Error, Backtracking issue! Backable: " << backable;
				break;
			}
			else {
				backable--;
				nexCell[0] = {getNX(maze, cCell[0], nDir, 2) };
				nexCell[1] = {getNY(maze, cCell[1], nDir, 2) };
			}
		}
		else { //normal procedures
			backable++;
			nexCell[0] = {getNX(maze, cCell[0], nDir, 2)};
			nexCell[1] = {getNY(maze, cCell[1], nDir, 2)};
		}
		destWall(maze, cCell[0], cCell[1], nDir);
		cCell[0] = nexCell[0];
		cCell[1] = nexCell[1];
		if (backable <= 0) {
			cout << "Maze (should be) finished!";
			loop = false;
			break;
		}
	}
}


int main() {
	string maze[13][13] = {}; //a thirteen by thirteen maze
	inputMaze(maze); // just so i dont get bored typing it over and over and over again
	generateMaze(maze);
	cleanUp(maze); //make it presentable/readable
	outputMaze(maze); // output it
	return 0;
}

[ne555]

string newD(string maze[13][13], int cCell[2]){
//...
   int ty = getNY(maze, cCell[2], dirs[i], 2); //out of bounds

int getNX(string maze[13][13], int xpos, string dir, int c){ //¿what's c?
//...
  		if (xpos == 1) { //¿why is 0 banned?
			x = xpos;
//...
   x = xpos + c; //c should not be any other number than 1 or 2
  //c = 2, x = 11, out of bounds 

[Hephaestus1233]

1. The temporary y shouldn't be out of bounds. I attempted to make it not possible to return an out of bounds value.

2. The variable c is the unit of change for how far the new x position is from the original.
Since I am trying to get a new x position from a direction and an array, a change of 1 would be looking at the nearest 'wall' if the surrounding walls weren't destroyed, while a change of 2 would be looking at the next cell around the current cell.

3. 0 is banned because when looking at the array, the x position of 0 is the walls of the maze
here is a visual help:

# # # # # # # # # # # # #
#   #   #   #   #   #   #
# # # # # # # # # # # # #
#   #   #   #   #   #   #
# # # # # # # # # # # # #
#   #   #   #   #   #   #
# # # # # # # # # # # # #
#   #   #   #   #   #   #
# # # # # # # # # # # # #
#   #   #   #   #   #   #
# # # # # # # # # # # # #
#   #   #   #   #   #   #
# # # # # # # # # # # # # 

4. There is a 'fail-safe' or a check to make sure we do not go out of bounds:

if (xpos == 12) {
	x = xpos;
}
else {
	x = xpos + c;
}

Note:
To make the output prettier for the eyes i added spaces to the cells and walls like this:

"# " and " "
To help you see:
"#_" and "__"

You can also comment out the generate maze function, and/or the clean up function to see what it gives out.

[Enoizat]

Sorry, Hephaestus1233, can you please describe better what you're trying to achieve?

1) For what I can see, your maze doesn't have any exit - doesn't it mean it hasn't got any solution?

2) I don't know the "Recursive Backtracker Algorithm", but where do you implement it? What's its purpose?

3) I think you're making your life unnecessarily hard using a two-dimensions array of std::strings.
std::strings themselves are variable-length arrays of characters, aren't they? So what you're dealing with, at the end of the day, looks like a 3D char array...
It seems you only use std::string to manage an extra space after the ‘meaningful’ characters. If so, you could evaluate not to manage it inside your 2D array, but only at printing time.

I mean, if you use a ‘traditional’ C-style array:
char maze[13][13];
and you add an extra space when you're printing it:
std::cout << maze[x][y] << ' ';
in my opinion you could get the same result by a far simpler code.

Of course you could opt out for an array of std::strings
std::string maze[13]; // it's a 2D char array anyway
or, even better, for a std::vector of std::strings
std::vector<std::string> maze(13);


4) If I understand your code, you're having a hard time when filling in data into your 2D array.
That sort of problems are usually better managed by a for-loop nested inside another for-loop.
The outer one deals with ‘columns’ and the inner one with ‘rows’ (or vice versa, according to your own perception):

for(int col = 0; col < 13; ++col) { // outer loop: manages columns
    for(int row = 0; row < 13; ++row) { // in each row, get every cell
        if( col == row ) { maze{col][row] = '#'; }
        else             { maze[col][row] = ...; }
    }
}

So, if you can, please describe what your code should do.

Happy coding!

[ne555]

1.

int ty = getNY(
   maze,
   cCell[2], //out of bounds
   dirs[i],
   2
);

2. `change' would be a better name, or `neighbourhood'

3. ¿but 12 is valid?

4. look at the example, x = 11, c = 2
x+2 is 13, out of bounds

$ ./a.out
foo.cpp:136:15: runtime error: index 15 out of bounds for type 'basic_string [13]'
foo.cpp:139:20: runtime error: index 15 out of bounds for type 'basic_string [13]'
foo.cpp:142:20: runtime error: index 15 out of bounds for type 'basic_string [13]'
foo.cpp:145:20: runtime error: index 15 out of bounds for type 'basic_string [13]'
foo.cpp:148:20: runtime error: index 15 out of bounds for type 'basic_string [13]'

[Hephaestus1233]

@ne555
Very sorry, if you see cCell[2] I most likely meant 1.
This is the new code:

int ty = getNY(
   maze,
   cCell[1], //out of bounds
   dirs[i],
   2
);

Also:
3. 12 shouldn't be valid because that would be the other wall. My program most likely needs an entire new code.

@Enoizat
Goal: Every time the program runs, output an ASCII Maze. Each maze should be relatively unique and random compared to the last one.

1. The solution should be when there are no more back-trackable spots to go back to, which should mean that all cells have been used up.

2. I can't give you a good explanation, but wikipedia has one here:
https://en.wikipedia.org/wiki/Maze_generation_algorithm

3. Since I started this project when I had rudimentary knowledge of C++, I hadn't thought of trying to make it with Vectors. Vectors might be better but I just haven't tried it.
As for making it an array of characters, it could actually save me some time but I would need to do some tweaking with the code.
When transfering vectors through function algorithms, I faced some issues where apparently it wasn't possible to pass them through. This is obviously a prototype and I haven't gone past this. I should probably recode the whole thing.

4. What would the advantage be over my while loops, if it ain't broken don't fix it as they say.