Pointer / Linked list question

[DemonGal711]

Okay, I'm making a program that will let you traverse a maze where the beginning is the top right corner (coming from the right) and it ends in the bottom left corner (going to the right). We have a 2D array for the board and are using a stack to keep the values entered so that if they hit a dead end, they can back track to where they messed up and try another path.

Now, I'm obsessive of making my program look good, so I decided to make it so that it looks at the previous input and the recent output, and then uses that to to tell what symbol should be inputted (like if you came from the left to right, it prints out a straight line, if from up to right, it does a sort of corner that shows how it goes down then turns right).

Would it be better to have two pointers (one pointing to top and the other to the previous response) or would it be better to handle this some other way?

Second, the first value, no matter what it is, the previous value should be 'R' cause it starts from the right. How would I initiate it so that R is the previous value even though it shouldn't be within the stack?

If anything isn't clear, tell me and I'll try to figure out another way to phrase it. I'm just a little sleepy at the moment to really put it into major details.

[Alex Edwards]

I thought I had the specs right until you said down-right instead of up-right in your 2nd paragraph.

Maybe a picture will be helpful?

Also, what are you using to graphically display your program? Is it a Console program or are you using some kind of GUI API? This question is merely out of curiosity.

[DemonGal711]

Well, I can see why, I totally murdered describing it. Obviously I shouldn't try to explain things on no sleep.

Basically, say this is my maze. I want it to fill in so that it looks like this. The actual maze is basically a 2D array surrounded by a border.

If you look at those two pictures, you can see that to make the line that runs through the maze, you need to know where it is coming from and which direction it is going to. I figured to handle most of that, I could just use two pointers, one that points to the top of the stack, and the one that points to the one item below the top.

That should work in most cases except the beginning. At the beginning, it needs to interpret the previous item in the stack as an 'R'. Of course, the problem is that the stack should be empty. I'm not sure how to handle that.

I thought about initializing my stack with an 'R' in it, but I didn't think that would be good cause if it was told to pop that value out, it would mess up the program. So, any clue how to handle this? Can I make it so that it won't pop that value out? Any help?

And, your last question Edwards, just the standard output stream. Nothing fancy cause we haven't learned any of that yet.

[gregorynoob]

ehh, now i'm confused... it would be helpful to see some code you've done already, but this is my suggestion: don't use a stack. it's a maze... a pretty straightforward graph. if you know where you should start, and where you should finish, you bfs through the graph, keeping track of node parents in another array. (you should set the first slot to null or something). after your bfs has traversed the graph, you have the list of parent nodes which you then follow from the last to the root, marking the steps as you go, which gives you the path.
this seems like the easiest way to do it, only problem would be if you were assigned that problem to solve using some other way..

[DemonGal711]

At the moment, the only coding I have is taking in the code and outputting what the maze looks like. I can give you that, but it isn't gonna help with what I'm asking. Right now I'm just planning how to tackle the stack and getting the answers to the parts I can't solve by myself.

And, I have to use a stack, it's part of the program guidelines. We're suppose to let the user input which direction to go. If they hit a dead end, we send them back and let them make a different choice.

[DemonGal711]

Okay, looking at it again, I'm only need one pointer, but that still doesn't solve my issue.

Could I just do something that my stack takes in a value (say L cause the person wants to move left). So, my stack would be comprised of an L and the NULL. Could I just say something like:

if (tPtr->next == NULL)
{ prev = 'R'; }
else prev = tPtr->next;

cause basically I need it to assume the previous value is 'R' at the beginning, but other then that, it needs to take the previous input and use it. Think that would work?

[stilllearning]

I don't think just L and R will cut it.

Lets say your maze is a rectangle that has n number of points, and there are walls inside it that construct a number of paths. Now the user needs to take the path that will take him/her to the finish.

You'll probably have an initial state for your maze where you have the points and the paths which are open from that point. From each point you could ideally move in 4 directions, Left(L), Right(R), Top(T) and Down (D) to the next point.

If your start point is X, push X onto your stack. Then based on the state for X, you could give the user a set of valid moves, say R, D. The user chooses R, so you move to the point at location R, push that onto the stack and give the user the next set of valid moves. If at any time you reach a point which has no valid moves, then you pop it off the stack, and ask the user to choose a different option.

Something like this might work ..

[DemonGal711]

Actually, I think I figured it out. But just in case, this is what I'm worried about.

In general there are 6 different symbols I could put in each cell of that 2D array:
Symbol 1
Symbol 2
Symbol 3
Symbol 4
Symbol 5
Symbol 6

Now, since the maze starts from the opening to the right, the only three values that the program should focus on are the first three cause they touch the left side of the space which would create a line like I want.

The problem is that, I ask the user to choose a direction. That direction is stored in my stack. Then my program looks at that direction and the previous one. That will work for all cases except the first one.

For the very first input, whatever it is, if I tell the program to look at the previous output, it will point at NULL instead of a directional input.

What I'm trying to figure out is if there is a way I can make it that so that the program will know that the previous value for the first input is 'R'.

Right now I'm gonna try something like this:

if (tPtr->next == NULL)
{ prev = 'R'; }
else prev = tPtr->next;

and see if it works. If not though, any other suggestions?

[stilllearning]

You could just have a pointer called "start" and when "current == start" you can set the input as you need.