So I'm trying to make an algorithm that starts at the first "room" and then recursively goes outward and starts deleting all rooms from the outside in. A room is a struct with 4 "doors" (pointers to rooms): North, South, East, and West.
The function takes two arguments: pointer to the current room and a char (to identify the direction: North, South, East, or West).
Here is my logic for the algorithm (roomDelete):
Base Case
- Start at the first room and call the function (roomDelete) on any non-NULL pointers; input to the function calls should be appropriate pointer to the room to the N/S/E/W, and appropriate char representing the direction N/S/E/W.
- Check to see that all pointers (N/S/E/W) are NULL --> delete this current room.
- Done/return.
Recursion
- Make sure not to backtrack (travel back in the direction you came from), by using a char to hold the value opposite of the direction char.
- Call the function on any non-NULL, non-backtrack pointers/directions.
- Break connection to previous room.
- Check to see that all pointers are NULL --> delete this current room.
Here is a simple picture on what the rooms/pointers look like: https://i.stack.imgur.com/9W1UO.png
I have code that I tried to test. If I have a room (by itself), then the function works. But as soon as another room is thrown into the mix, then the function never returns/finishes. I'm not sure why. Is my logic sound? Am I missing something? Any help is appreciated.
CODE:
#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>
using namespace std;
#define NUM_DOORS 4
struct room {
struct room * north;
struct room * south;
struct room * east;
struct room * west;
} ;
int roomDelete(room *, char);
int main(void)
{
room * test_ptr = new room;
cout << "Created room at location: " << test_ptr << endl;
test_ptr->north = NULL;
test_ptr->south = NULL;
test_ptr->east = NULL;
test_ptr->west = NULL;
test_ptr->north = new room;
cout << "Created room at location: " << test_ptr->north << endl;
test_ptr->north->north = NULL;
test_ptr->north->south = test_ptr;
test_ptr->north->east = NULL;
test_ptr->north->west = NULL;
int test = roomDelete(test_ptr, '\0');
cout << test << endl;
return 0;
}
int roomDelete(room * room_ptr, char coord)
{
char coordinate[NUM_DOORS] = {'N', 'S', 'E', 'W'};
char coordinate_opposite[NUM_DOORS] = {'S', 'N', 'W', 'E'};
char coord_opp = '\0';
// call function on any remaining rooms
if(coord == '\0') // this is the beginning/initial room
{
for(int i = 0; i < NUM_DOORS; i++)
{
switch (coordinate[i])
{
case 'N':
{
if(room_ptr->north != NULL)
roomDelete(room_ptr->north, 'N');
break;
}
case 'S':
{
if(room_ptr->south != NULL)
roomDelete(room_ptr->south, 'S');
break;
}
case 'E':
{
if(room_ptr->east != NULL)
roomDelete(room_ptr->east, 'E');
break;
}
case 'W':
{
if(room_ptr->west != NULL)
roomDelete(room_ptr->west, 'W');
break;
}
default:
cout << "There was an error deallocating for the room at location: " << room_ptr << endl;
}
}
// delete the current room
if(room_ptr->north == NULL && room_ptr->south == NULL && room_ptr->east == NULL && room_ptr->west == NULL)
{
cout << "Deleting room at location: " << room_ptr << endl;
delete room_ptr;
}
else
return 2; // outward rooms have not been deleted yet
}
else // recursion
{
// this sets the value for the door that won't be handed to the delete function
for(int j = 0; j < NUM_DOORS; j++)
{
if(coord == coordinate[j])
coord_opp = coordinate_opposite[j];
}
if(coord_opp == '\0')
{
cout << "An error occurred while setting the value of the opposite coordinate.\n";
return 1;
}
// call the function on any remaining rooms
for(int k = 0; k < NUM_DOORS; k++)
{
if(coordinate[k] != coord_opp) // this is to avoid backtracking (which would cause infinite recursion)
{
switch (coordinate[k])
{
case 'N':
{
if(room_ptr->north != NULL)
roomDelete(room_ptr->north, 'N');
break;
}
case 'S':
{
if(room_ptr->south != NULL)
roomDelete(room_ptr->south, 'S');
break;
}
case 'E':
{
if(room_ptr->east != NULL)
roomDelete(room_ptr->east, 'E');
break;
}
case 'W':
{
if(room_ptr->west != NULL)
roomDelete(room_ptr->west, 'W');
break;
}
default:
cout << "There was an error deallocating for the room at location: " << room_ptr << endl;
}
}
}
// delete connection (ptr's) between current room and previous
switch(coord)
{
case 'N':
{
room_ptr->south->north = NULL;
room_ptr->south = NULL;
}
case 'S':
{
room_ptr->north->south = NULL;
room_ptr->north = NULL;
}
case 'E':
{
room_ptr->west->east = NULL;
room_ptr->west = NULL;
}
case 'W':
{
room_ptr->east->west = NULL;
room_ptr->east = NULL;
}
default:
cout << "There was a problem with severing the connection for the room at location: " << room_ptr << endl;
}
// delete current room
if(room_ptr->north == NULL && room_ptr->south == NULL && room_ptr->east == NULL && room_ptr->west == NULL)
{
cout << "Deleting room at location: " << room_ptr << endl;
delete room_ptr;
}
else
return 3; // outward rooms have not been deleted yet
}
return 0; // successful in deallocating the entire complex
}
I don't understand your algorithm, but I can tell where you are failing.
room_ptr->north at this moment is a null pointer and you are thus writing at location you are not allowed to.
Maybe you don't fully understand switch statements? It has so called "fall-through" behavior , i.e. it doesn't break out by itself just because it is a new case, it will just find a place where to start executing code and keep executing it until it hits "}" or finds explicitly written "break;" in it's way.