1 Attachment(s)
c - travelling through maze recursively & inserting nodes in all spaces
So basically I'm a maze program where it takes 5 mazes and the program inserts nodes into the outlines of those mazes. I'm creating a directed graph that can represent the freespaces in the maze by placing a graph node at each free space grid location and connecting them together with edges.
I'm stuck on a function that actually involves filling the freespaces of the maze with nodes and connecting them. The nodes don't need to follow a certain pattern at the moment, they just need to fill up all empty space like the images shown below. My program right now just displays a blank maze with no nodes.
I'm given a set of guidelines which are commented in the function Graph *computeGraph for the mazes.c program, but I am really stumped as to how I would trace a maze recursively. Recursion isn't really my strong suit and I just learned about pointers so I apologize if this question seems dumb. My code under the function is gibberish and doesn't do anything. I'm really lost as to what to do and would appreciate some help or guidance. I'm not asking for anything else in the program to be touched, only the Graph *computeGraph function as it's my problem right now. Also I should mention that I'm not allowed to create any extra arrays for this task which makes the problem even harder.
If the comments are not enough, basically the function's purpose is to allocate space for the new graph and return it. Each node of the graph must be dynamically-allocated and connected by setting the appropriate Node up/down/left/right pointers.
Thanks again for any help. I can post the full code/all the files for the program if required, but I just posted only what I thought was necessary for this particular problem.
Attachment 15883
maze.c:
Code:
#include<stdio.h>
#include<stdlib.h>
#include"graphSet.h"
#include"mazeDisplay.h"
// Compute the graph for the given maze and add it to the given graph set.
Graph *computeGraph(char maze[HEIGHT][WIDTH])
{
// Create the initially-empty graph
int i, j;
for (i = 0; i < HEIGHT; i++) {
for (j = 0; j < WIDTH; j++) {
maze[j] = '\0';
}
}
// Find a starting node, then trace out the maze recursively. A starting node can be
// found by searching from top to bottom, left to right, for a non-wall maze location.
// You MUST NOT hard-code this start location ... it must be determined by your code.
Node *newNode;
Node *currNode;
Node *prevNode;
currNode = *rootNode;
currPos[0][0];
prevNode = NULL;
while (currNode != NULL) {
if (currPos[0][0] == maze[x][y]) {
break;
}
prevNode = currNode;
}
newNode = malloc(sizeof(Node));
if (prevNode->up != 1) {
prevNode->up = newNode;
}
elseif(prevNode->down != 1) {
prevNode->down = newNode;
}
elseif(prevNode->left != 1) {
prevNode->left = newNode;
}
elseif(prevNode->right != 1) {
prevNode->right = newNode;
}
// To trace out the maze recursively, you will likely want to create a recursive
// procedure that is called by this one. It should take parameters to indicate
// the location in the maze to start tracing from, the maze itself and also the node
// that led to this node (i.e., the previous one in the tree that led here). If you
// start with the root node, then the previous node should be NULL.
//
// As you go through the maze, make sure to mark off maze locations that you have
// visited (perhaps by putting a '2' character at that location) so that you do not
// go back to that location again and end up with infinite recursion. So you can
// stop the recursion when you reach a wall (i.e., a '1' character in the maze) or a
// '2' character. A '0' character means that it is a free space that you just arrived
// at for the first time. Make sure to check recursively in all directions. In my
// solutions (shown on the assignment), I used an ordering of up/down/left/right. So
// if you want solutions to look like mine, you should follow that ordering as well.
//
// As you traverse the maze, make sure to connect the previous node to the current one.
// You'll have to check which direction you can from (i.e., x and y values) so that
// you know whether it is the up/down/left or right pointer to set.
}
// This procedure must clean up graph by removing all nodes in which the previous and
// next nodes have the same x or y value as it.
void cleanUpGraph(Node * n, Node * previousNode)
{
}
// This is where it all begins
int main()
{
char mazes[5][HEIGHT][WIDTH] = {
{"111111111111111111111",
"100000001000100000001",
"101111111010111011111",
"100000000010000010001",
"101110111111101110111",
"100010001000000000001",
"111011111111111110111",
"101010001000100000001",
"101110111011101011101",
"100010000000001010001",
"101010111011111111111",
"101000001000100000001",
"101111111110101111101",
"100010100000100000101",
"111110101110101111101",
"100010001000000010101",
"101010111111111010111",
"101010001000000010001",
"101111111010111011101",
"100000000010001000001",
"111111111111111111111"},
{"111111111111111111111",
"100000000000000000001",
"101111111111111111111",
"100000000000000000001",
"101111111111111111111",
"100000000000000000001",
"111111111111111111101",
"100000000000000000001",
"101111111111111111111",
"100000000000000000001",
"111111111111111111101",
"100000000000000000001",
"101111111111111111111",
"101111111111111111101",
"101111111111111111101",
"101000100010001000101",
"101010101010101010101",
"101010101010101010101",
"101010101010101010101",
"100010001000100010001",
"111111111111111111111"},
{"111111111111111111111",
"100000000000000000001",
"101010101010101010101",
"100000000000000000001",
"101110111011101110111",
"100000000000000000001",
"101111101111101111101",
"100000000000000000001",
"101111111001111111101",
"100000000000000000001",
"101111111111111111101",
"100111111111111111001",
"100011111111111110001",
"100001111111111100001",
"100000111111111000001",
"100000011111110000001",
"100000001111100000001",
"100000000111000000001",
"100000000010000000001",
"100000000000000000001",
"111111111111111111111"},
{"111111111111111111111",
"111111111111111111111",
"111111111111111111111",
"111111111111111111111",
"111111111111111111111",
"111111111111111111111",
"111111111111111111111",
"111111111111111111111",
"111111111111111111111",
"111111111111111111111",
"111111111110111111111",
"111111111111111111111",
"111111111111111111111",
"111111111111111111111",
"111111111111111111111",
"111111111111111111111",
"111111111111111111111",
"111111111111111111111",
"111111111111111111111",
"111111111111111111111",
"111111111111111111111"},
{"111111111111111111111",
"111100000000000000001",
"111000000000000000001",
"100000000000000000001",
"100000000000000000001",
"100000000000000000001",
"100000000000000000001",
"100000000000000000001",
"100000000000000000001",
"100000000000000000001",
"100000000000000000001",
"100000000000000000001",
"100000000000000000001",
"100000000000000000001",
"100000000000000000001",
"100000000000000000001",
"100000000000000000001",
"100000000000000000001",
"100000000000000000001",
"100000000000000000001",
"111111111111111111111"}
};
// Open a display window
openDisplayWindow();
// Allocate a GraphSet to store the graphs for each maze
GraphSet *gSet;
// Compute the graphs for each maze and add them to a Graph Set
for (int i = 0; i < 5; i++) {
Graph *g = computeGraph(mazes);
// Add g to gSet properly
// ...
}
// Show the graphs
Graph *g; // ... set this to the first graph in gSet ...
for (int i = 0; i < 5; i++) {
drawMaze(mazes); // Draw the maze
// drawGraph(g->rootNode); // Draw the graph
getchar(); // Wait for user to press enter
// cleanUpGraph(g->rootNode, NULL); // Clean up the graph
// drawMaze(mazes);
// drawGraph(g->rootNode);
// ... get the next graph in the set ...
// ... INSERT A LINE OF CODE HERE ...
getchar(); // Wait again for the user to press ENTER before going on to the next maze
}
// Free up all allocated memory
// ...
// Close the display window
closeDisplayWindow();
}
graphSet.h:
Code:
// This struct represents a single intersection/Node in a maze. It keeps track
// of the x(i.e., column) and y (i.e. row) of the intersection in the maze
// as well as the Nodes in all 4 directions around it). NULL is used to
// indicate that no Node is beside it in a particular direction.
typedefstruct nd {
int x;
int y;
struct nd *up;
struct nd *down;
struct nd *left;
struct nd *right;
} Node;
// This struct represents a single maze graph
typedefstruct gr {
Node *rootNode;
struct gr *nextGraph;
} Graph;
// This struct represents a set of maze graphs
typedefstruct {
Graph *firstGraph;
Graph *lastGraph;
} GraphSet;
[/FONT][/COLOR]
