Recursive memory "tree": properly freeing memory

Question

Fresh out of my first CS class, I wanted to get more practice with recursive memory allocation, so I decided to make a little game known as the "Recursive Dungeon." It simply allows users to roam through an infinite dungeon by recursively generating a new "room" every time a player enters an empty (NULL) room.

The new room is then saved, and can be accessed by...

1. Going down the exact same path that was used when entering the room
2. If you leave the room, retracing your steps back to the same room

*The program doesn't use cycles (at least, I don't think it does). I'm unfamiliar with the concept of a cycle as well as how to use it.

The problem I'm running into is when I try to clean up all the recursively-allocated memory (the "rooms"), I receive the classic error "segmentation fault: core dumped".

Below is my structure "room":

    struct room
    {//begin struct

        room* backward;
        room* left;
        room* forward;
        room* right;

        string desc;
  
        room() { //begin
    
            backward = NULL;
            left = NULL;
            forward = NULL;
            right = NULL;
    
        /*End*/}
 
    /*End struct*/};

Each "room" has other rooms connected to it (left/right/forward/backward). The user starts in an empty room pointer "startingpoint", and may go in any of the above directions. Upon attempting to enter an empty (NULL) room, a new room is randomly generated for the user enter into.

Once the player is satisfied exploring, I attempt to clean up the allocated memory using an array that stores all the rooms before ending the program. Instead, it causes the segmentation fault. Here is the code:

    void ClearAllocatedMemory(room* aRoom, room** roomArray, int& raIndex) {

        for(short i=0; i<raIndex; i++) {//begin for
    
            delete roomArray[i];
    
        /*End for*/}
    
        delete[] roomArray;

    /*End func*/}

Here is the code that makes my array and defines its first (0th) index:

    room** roomArray;
    int raIndex = 0;

    room* startingpoint = new room();
    roomArray[0] = startingpoint;

And here is the code that adds in new rooms to the roomArray index:

    room* GenRoom(room** roomArray, int& raIndex) {

        room* newroom = new room();
    
        newroom->desc = GenRoomDesc( rand()%12 + 1 );
    
        raIndex++;
    
        roomArray[raIndex] = newroom;

        return newroom;


    }

Answer 1

Doing some more research, recalling stack vs heap memory, and reading through this article- I think I may have figured out the issue in the above code.

After changing how I clean up my memory, from using recursion to using an array as @Quimby suggested, I implemented a room** array to hold all the rooms. The issue I'm running into is that I'm attempting to delete the room** when it shouldn't be deleted: the room** is allocated off the stack instead of the heap since I didn't use the keyword new to create it.

Therefor, to fix my code, I simply need to take out the delete[] roomArray; from my function.

Answer 2

Your algorithm would not work even if double delete was okay. If you have two rooms connected to each other, they will recursively try to delete each other leading to stack overflow. I.e. you cannot delete cycles with simple recursion.

You have a design problem - who owns each room? Had this been written in a garbage-collected language, you would not care and the rooms would own each other simply by their own existence. In C++ you must care and the design should reflect that.

shared_ptr and std::weak_ptr would be messy in this case. Even if you could establish an tree-like hierarchy and thus use unique_ptr, it can lead to stack overflow simply due to the nested destructors for deep trees.

The best and easiest solution is to create a single std::vector<Room> that is the clear owner of all the rooms. The neighbours can then use indices into this vector. One caveat is that deallocating rooms in the center of the vector invalidates the higher indices. This can be resolved with a swap with the last element and fixing just their connections. It would also make delete from the middle O(1).

If the map is really dynamic, as is your case, I could argue either for std::list<Room> - use iterators or pointers for the neighbours - or std::vector<std::unique_ptr<Room>> - use raw non-owning pointers.

Just a warning with these neighbour-only solutions - when a player explores rooms in a loop, you have no tools how to determine whether that room already should exist or not. E.g. going 2 up, 2 right, 2down, 2 left should return the player to the initial room. You might want to consider actually using 2D grid (and worry about memory/performance later).

Answer 3

Your algorithm would work if your room graph where a plain tree (no going back). Since you can go back, you need to take care not to process again a room you are already processing.

I will show two ways of doing so, one is good for an arbitrary graph and the other one only for a tree with back links.

---

Method 1. The room class should have a boolean visited flag (not visited by the gamer, but by the deplete sequence). The initial value is false. Then your delete function should be modified like this:

ClearAllocatedMemory(room* aRoom) {
   if (aRoom == nullptr || aRoom->visited) return;
   aRoom->visited = true;
   ClearAllocatedMemory(aRoom->backward);
   ClearAllocatedMemory(aRoom->left);
   ClearAllocatedMemory(aRoom->forward);
   ClearAllocatedMemory(aRoom->right);
   delete room;
}

This essentially turns the deletion process into Depth-first search.

---

Method 2. The room deletion routine should know what room it has been reached from, and not touch that room.

ClearAllocatedMemory(room* aRoom, room* parent) {
   if (aRoom == nullptr) return;

   if (aRoom->backward != parent)   ClearAllocatedMemory(aRoom->backward, aRoom);
   if (aRoom->left     != parent)   ClearAllocatedMemory(aRoom->left,     aRoom);
   if (aRoom->forward  != parent)   ClearAllocatedMemory(aRoom->forward,  aRoom);
   if (aRoom->right    != parent)   ClearAllocatedMemory(aRoom->right,    aRoom);

   delete room;
 }

This is just normal top-to-bottom tree traversal, with added checks that prevent going up.

---

The first method is probably preferable because it is universal, and you can make the deletion routine a destructor, as it should be in C++. But this is bor another occasion.

Note also that this check

if ( (aRoom->backward == NULL) && (aRoom->left == NULL)\
        && (aRoom->forward == NULL) && (aRoom->right == NULL) ) {

doesn't make a lot of sense. Every room needs to be deleted, not just those that do not have outgoing paths.