2 Replies - 254 Views - Last Post: 09 November 2019 - 12:08 PM Rate Topic: -----

#1 Evilgaga   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 05-October 19

c - travelling through maze recursively & inserting nodes in all s

Posted 09 November 2019 - 03:16 AM

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 traverse 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.

maze.c:
	#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[i][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;
	  }else if(prevNode->down != 1){ 
		prevNode->down = newNode;
	  }else if(prevNode->left != 1){ 
		prevNode->left = newNode;
	  }else if(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[i]);

		// 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[i]);  // 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[i]);
		// 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:

        // 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.
	typedef struct 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
	typedef struct gr {
	  Node       *rootNode;
	  struct gr  *nextGraph;
	} Graph;


	// This struct represents a set of maze graphs
	typedef struct {
	  Graph  *firstGraph;
	  Graph  *lastGraph;
	} GraphSet;




maze pics: https://imgur.com/a/NIOEKDu

This post has been edited by Skydiver: 09 November 2019 - 11:59 AM
Reason for edit:: Fixed code tags. Thanks for trying.


Is This A Good Question/Topic? 0
  • +

Replies To: c - travelling through maze recursively & inserting nodes in all s

#2 Salem_c   User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 2397
  • View blog
  • Posts: 4,530
  • Joined: 30-May 10

Re: c - travelling through maze recursively & inserting nodes in all s

Posted 09 November 2019 - 04:31 AM

Also cross-posted here
https://cboard.cprog...tml#post1290979
Was This Post Helpful? 2
  • +
  • -

#3 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7139
  • View blog
  • Posts: 24,247
  • Joined: 05-May 12

Re: c - travelling through maze recursively & inserting nodes in all s

Posted 09 November 2019 - 12:08 PM

Well, you are in a world of hurt if the first thing you do in your computeGraph() is to erase the maze that has been given to you to try to solve. (e.g. mazes.c, lines 11-16)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1