Thread: c - travelling through maze recursively & inserting nodes in all spaces

  1. #1
    Registered User
    Join Date
    Nov 2019
    Posts
    3

    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.

    c - travelling through maze recursively & inserting nodes in all spaces-screenshot-15-jpg

    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]
    Last edited by Salem; 11-09-2019 at 05:14 AM. Reason: Removed crayola

  2. #2
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    It appears that you haven't even tried :/

    Edit: P.S. if that current code is written by your teacher then they're a crappy programmer.
    Last edited by Hodor; 11-09-2019 at 05:14 AM.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Quote Originally Posted by Hodor View Post
    It appears that you haven't even tried :/
    Apart from trying somewhere else as well
    C - Travelling Through Maze Recursively & Inserting Nodes In All S - C And C++ | Dream.In.Code
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Nov 2019
    Posts
    3
    Quote Originally Posted by Hodor View Post
    It appears that you haven't even tried :/

    Edit: P.S. if that current code is written by your teacher then they're a crappy programmer.
    I did try. All the stuff under computeGraph is mine. That and in addition to stuff I had to write for other files that aren't related to this particular problem. Like I said in the post, I don't mind posting all my files if necessary but I only posted what I thought was relevant to the issue. I admitted recursion isn't my strong suit and I'm new to pointers but if my knowledge is too low-level for this entire forum then that's understandable.
    Last edited by FirePandas; 11-09-2019 at 06:02 AM.

  5. #5
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    So all of this is yours?

    Code:
    // 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();
    
    }
    





    I doubt it -- you have a very strange commenting style if all of that is yours. But anyway.

    There is nothing too "low-level" for this entire forum, but I think that most (all?) of us expect that the person who posts a question (what was your question) at least makes an attempt to solve it themselves. I don't think you've made an attempt at all. If I am wrong, then I apologise but if you want to be a programmer then you should develop an interest in problem solving. Grab a pen(cil) and a piece of paper and work it out (for this problem I think 30 minutes with a pen(cil) and paper should suffice). From what I've seen so far (and yeah I could be wrong) you've shown no interest in problem solving at all and just want stuff handed to you on a plate. If you can't be bothered even attempting to develop a solution then why should I give you one? Why do you want to be a programmer if you don't like solving problems? You didn't even ask a question; it's pretty hard to answer a question when you didn't ask one.
    Last edited by Hodor; 11-09-2019 at 06:40 AM. Reason: Removed my edit because OP responded while I was typing it

  6. #6
    Registered User
    Join Date
    Nov 2019
    Posts
    3
    No that was given by my teacher. I meant under the function computeGraph. I'm not asking for help on the other parts of the program, my question is directed towards the computeGraph function only. I'm not concerned about the other parts yet.

  7. #7
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by FirePandas View Post
    No that was given by my teacher. I meant under the function computeGraph. I'm not asking for help on the other parts of the program, my question is directed towards the computeGraph function only. I'm not concerned about the other parts yet.

    Well, make an attempt and ask a question! You haven't even asked a question yet, you've just provided a bunch of crappy incomplete code that we're all suppose to stare at in awe(?)

  8. #8
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by FirePandas View Post
    No that was given by my teacher. I meant under the function computeGraph. I'm not asking for help on the other parts of the program, my question is directed towards the computeGraph function only. I'm not concerned about the other parts yet.
    Ok, you haven't asked a question, but I'll ask you one. Forget about programming a solution for the moment. Can you solve the problem, for any of the mazes, using just pen and paper? Not solve as in develop an algorithm, but solve as in getting the answer. I think that would be a good first step.

    Edit: What I mean is forget about graphs and recursion and all that nonsense and just solve the problem on paper. Once you can solve it on paper then introspect and ask yourself "how did I do this?" After you can solve it on paper and rationalise how you solved it on paper then turn that into your program.
    Last edited by Hodor; 11-09-2019 at 06:53 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List - inserting nodes
    By johngoodman in forum C Programming
    Replies: 7
    Last Post: 02-19-2013, 12:13 AM
  2. Inserting Nodes at Binary Trees
    By blondeamon in forum C++ Programming
    Replies: 3
    Last Post: 12-25-2007, 08:27 AM
  3. Binary tree not inserting nodes correctly
    By jk1998 in forum C++ Programming
    Replies: 7
    Last Post: 09-22-2007, 12:37 PM
  4. inserting strings into linked list nodes
    By occams razor in forum C Programming
    Replies: 8
    Last Post: 03-31-2007, 12:17 AM
  5. Navigating a maze recursively
    By JOsephPataki in forum C Programming
    Replies: 4
    Last Post: 06-06-2003, 01:36 AM

Tags for this Thread