Attempting to traverse a quad tree to determine height

Question

I'm currently trying to auto-generate a maze of randomly generated room objects that are linked via pointers in 4 directions - n, s, e, and w. I begin at Room *home, and build out with each new room having a 1/3 chance in creating a door in each of the other three directions (it of course has a door back to where it came from). This runs until all "leaves" have three null pointers to the other directions. I believe the map is being created properly, as I am able to "move around" within it using another function (not included below). My question is how can I find the height of this structure. It is essentially a quad-tree. Here is my code for building the maze and attempting to find the height. I get a segmentation fault when executing. If I comment out any three of the four recursive calls in height, it does not fault.

void buildMaze(Room *newRoom, char d)
{  
    int rando;

    Room *last = newRoom;

    //coming from south
    if(d == 's')
    {
        newRoom = new Room();
        newRoom->southDoor = last;
        last->northDoor = newRoom;

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 's');//build north room

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'w');//build east room

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'e');//build west room
    }
    //coming from north
    else if(d == 'n')
    {
        newRoom = new Room();
        newRoom->northDoor = last;
        last->southDoor = newRoom;

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'n');//build south room

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'w');//build east room

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'e');//build west room
    }
    //coming from east
    else if(d == 'e')
    {
        newRoom = new Room();
        newRoom->eastDoor = last;
        last->westDoor = newRoom;

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 's');//build north room

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'n');//build south room

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'e');//build west room
    }
    //coming from west
    else if(d == 'w')
    {
        newRoom = new Room();
        newRoom->westDoor = last;
        last->eastDoor = newRoom;

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 's');//build north room

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'n');//build south room

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'w');//build east room
    }
    //home room always has 4 doors
    else
    {
        buildMaze(newRoom, 's');//build north room
        buildMaze(newRoom, 'n');//build south room
        buildMaze(newRoom, 'w');//build east room
        buildMaze(newRoom, 'e');//build west room
    }
}

//longest distance from home
int height(Room *r)
{
    int n, s, e, w;
    if (r == nullptr)
        return 0;
    else
    {
        //compute the height of each subtree
        n = height(r->northDoor);
        s = height(r->southDoor);
        e = height(r->eastDoor);
        w = height(r->westDoor);

        //return the largest tree height
        if (n >= s && n >= e && n >= w)
            return (n + 1);
        else if(s >= n && s >= e && s >= w)
            return (s + 1);
        else if(e >= n && e >= s && e >= w)
            return (e + 1);
        else
            return (w + 1);
    }
}

I believe there is a high possibility of an almost infinite recursion which may cause the segfault. Please check the below link. https://stackoverflow.com/questions/2964852/why-infinite-recursion-leads-to-seg-fault — Will_Panda, Mar 07 '18 at 05:02
It'll be easier for you to debug if you figure out where the segfault is. Run it in gdb and see what happens. — Ari, Mar 07 '18 at 06:01
I realized the infinite recursion after I put this away for the night. Thank you for the confirmation and the link. It makes sense. — Zachary Brusko, Mar 07 '18 at 13:46

john · Accepted Answer · 2018-03-07T06:18:33.247

As Will_Panda says there is infinite recursion because the links back to the room you came from mean you just go round in a recursive loop.

Simplest way to fix is to add a field to you Room class to indicate that the room has already been visited as part of the height calculation. Then if visited is false before you start your calculation you can use it to avoid infinite recursion. E.g.

//longest distance from home
int height(Room *r)
{
    int n, s, e, w;
    if (r == nullptr)
        return 0;
    else if (r->visited) // already been here
        return 0;
    else
    {
        //compute the height of each subtree
        r->visited = true;
        n = height(r->northDoor);
        s = height(r->southDoor);
        e = height(r->eastDoor);
        w = height(r->westDoor);

        //return the largest tree height
        if (n >= s && n >= e && n >= w)
            return (n + 1);
        else if(s >= n && s >= e && s >= w)
            return (s + 1);
        else if(e >= n && e >= s && e >= w)
            return (e + 1);
        else
            return (w + 1);
    }
}

Once you know the height you will have to go through all the rooms again clearing all the visited fields

//clear visited fields
void clear_visited(Room *r)
{
    if (r == nullptr)
        return;
    else if (!r->visited) // already cleared
        return;
    else
    {
        r->visited = false;
        clear_visited(r->northDoor);
        clear_visited(r->southDoor);
        clear_visited(r->eastDoor);
        clear_visited(r->westDoor);
    }
}

Completely untested code.

I did it by simply passing in the room I came from, so I could avoid going back down that path, similarly to how I built the maze of rooms. Same result, though, Thanks for your advice. — Zachary Brusko, Mar 07 '18 at 13:48

Attempting to traverse a quad tree to determine height

1 Answers1