Maze Project

[sm4ckth3monkey]

Hello I am working on a project for my roommate that involves reading in a text file that has x's and o's. The x's mean a wall and the o's mean an open path.

The maze begins at 0,0 and ends at 15, 15. This makes the graph 15x15.

I was thinking about using Breadth-First Search to accomplish this as I am looking for the SHORTEST PATH to the end.

I have been working on this for 10 hours today and can't think of a way to translate the path into a visible format.

Soxxxxooooooxxxx
oooooooooooxoxxo
xooooooxxxxoooox
xoxxxoxoooooooox
xxxoooxoooxxxxox
ooooxxxxoooxooox
oxoooxoooooxooox
oxoooxooooxooooo
oxoooxxxxoxoxooo
oxoooxooooxxxxxo
xxxxoxxxxoxooxoo
oooooxoooooooxoo
oxooooooxxxxxxoo
oxxxxooooxxooooo
ooxoooooxoxoxxxx
oooooxxxooxooooF

If this is the maze then the S is the start and the F is the finish.

What I was asked to do was to show the shortest path from the start to the finish. Any output would work if it would show the original maze modified so that there is a path somehow visible.

I took an approach where I would read in the text from a file (as instructed) then would place each character into a 2-dimensional array (15x15). Next I would convert this into a linked list/tree with 4 pointers (up, down, left, right). Then I would use BFS to determine a path availible. Finally I would convert it back into an array so I could output the maze in a 15x15 format.

Heres an example of what the completed program would do:

.oxxxxooooooxxxx
......oooooxoxxo
xoooo.oxxxxoooox
xoxxx.xoo......x
xxx...xoo.xxxx.x
ooo.xxxxo.oxoo.x
oxo.oxooo.oxoo.x
oxo.oxooo.xooo.o
oxo.oxxxx.xoxo..
oxo..xooo.xxxxx.
xxxx.xxxx.xooxo.
oooo.xo...oooxo.
oxoo....xxxxxxo.
oxxxxooooxx.....
ooxoooooxox.xxxx
oooooxxxoox.....

I could include my code but its very messy.

Any help would be greatly appreciated including any completely new ideas.

[sm4ckth3monkey]

I have still not found a solution to this problem. Please help!

[sm4ckth3monkey]

Okay so I started over this time using an array of my linked list structure but now I get a SIGSEGV crash. I know it is because of the way I am trying to access the data in the struct but I do not know how to access it properly.

#include <iostream>
#include <queue>
#include <fstream>

using namespace std;

struct node {
    char data;
    node* left;
    node* right;
	node* up;
	node* down;

	node(char e)
	{
		data = e;
		left = NULL;
		right = NULL;
		up = NULL;
		down = NULL;
	}
};

int main()
{
	char a;
	bool found=false;
	ifstream in;
	node* root[20][20]={NULL};
	in.open("maze.txt");

	if (!in)
	{
		cout << "Could not Open!" << endl;
		return 1;
	}

		for (int i = 0; i <=15; i++)
		{
			for (int j = 0; j <= 15; j++)
			{
				in >> a;
				if(root == NULL)
				root[i][j] = new node(a);

				root[i][j]->up = root[i-1][j];
				//root[i][j]->down = root[i+1][j];
				//root[i][j]->left = root[i][j-1];
				//root[i][j]->right = root[i][j+1];
				//cout << root[i][j].data;
			}
			cout << endl;
		}

		while (found==false)
		{
			found = true;
		}

        for (int i = 0; i <=15; i++)
		{
			for (int j = 0; j <= 15; j++)
			{
			    //a = root[i][j]->data;
			    cout << a;
			}
		}


	return 0;
}

[VernonDozier]

Lines 43 and 44 don't make sense:

if(root == NULL)
root[i][j] = new node(a);

This would make more sense:

if(root != NULL)
root[i][j] = new node(a);

The whole point of checking for NULL is so that you don't dereference a NULL pointer. You're checking to make SURE it's a NULL pointer, THEN dereferencing it. You don't want to do that.

1. Create the node.
2. Check to make sure the node is not null.
3. Use the node.

[sm4ckth3monkey]

Thanks for the post! You made me realize what was wrong with my code although your response wasn't what I was looking for.

if(root[i][j] == NULL)
root[i][j] = new node(a);

The problem was that I was referencing root as a pointer and not as an object. I wanted to check if the root at a specific point in the array was empty so I wouldn't overwrite.

[VernonDozier]

Thanks for the post!

You're welcome.

You made me realize what was wrong with my code although your response wasn't what I was looking for.

What are you looking for?