Final Lab (Hooray!)

April 20, 2012

Prelab (complete before lab)

Ensure you can access the CS servers.  Review the lab that covers structures. 

Part 1

In this lab, we will be writing a complete, if simple, C program. Specifically, we will make a version of a text-based adventure game. This program will show you how to allocate memory dynamically, review structures, review input/output, and give you a feel for a somewhat larger C program.

First, let us write our program header and a loop that takes user input.  Create a main function, and add include statements for the libraries 

stdio.h

stdlib.h

string.h

Within the main function,  we want a loop that will only terminate when a user wants it to. Write a while loop that depends on the value of an integer.  Give the user the option to enter the options "1) Go north", "2) Go south", "3) Go east", "4) Go west", and "5) Exit".  Use scanf to get their numeric response. Test out your code to make sure it only exits when you enter '5'.

As we do not have saved game data, our "game" is going to be constructed by the player as they go. In this game, the player can move north, south, east, or west, and whenever they move, they get a description of the area into which they have moved.  

Connected together, the places a player finds form a graph.  The graph will grow dynamically based on where the player walks, so new vertices must be allocated.  To store a vertex, we are going to use a new C struct we'll name place. This struct needs to have a string for the description of the place and four pointers to the neighboring places. The string for the description should be just a pointer to a string, not an allocated string (i.e. char* ).

Checkoff 1.  Write your code for the place structure.  Hint: remember that a struct type can be referred to as "struct _name" where _name is whatever the struct was called.

If we add a typedef, we can refer to place instead of struct place,

typedef struct place place;

Part 2

Now we have a data type to build our graph and a loop for user input.  Next, let us make a factory function for struct place. A factory function is a function that allocates a struct of a specific type for you and returns its pointer.  These are especially useful in C as C structs do not have constructors as Java and C++ classes do.

Write a function that takes a pointer to a string as an argument and returns a pointer to a place. The first thing this function needs to do is to allocate memory for a new place object. To do this, we use malloc. This function allocates N bytes of memory, where N is the argument given to malloc.  To allocate enough bytes of memory for a place struct, we can use the sizeof command, which returns the number of bytes a type uses.

struct place* new_place = malloc(sizeof(struct place));

The factory function should also initialize elements of the struct.  In our case, the north, south, east, and west pointers should all be initialized to 0. And the description element should be initialized to the string that is passed in to the function.

Now we are ready to create our starting area.  In the main program, before the while loop, dynamically allocate a place struct called origin using the new factory function. Give it the description "You are standing in an open field west of a white house.".

Checkoff 2.  Write your definition of the place struct called origin.

Part 3

Now we just need to let the user populate the graph as they walk around.  Add a pointer to a place struct that points to the origin. We will refer to this pointer as the 'current place'.

Within the user input loop, create an if statement that is triggered if the user selects to go north, i.e. enters a '1'. Within this loop we want to

1. Check if the struct place to the north is 0.
2. If it is,
3. prompt the user to enter a description,
4. allocate a new struct place,
5. set the current place's north pointer to point to the new place,
6. set the new place's south pointer to point to the current place,
7. set the current place to be the new place.
8. else,
9. set the current place to be the place to the north.

One difficulty here is reading a full description, which will likely be multiple words.  The easiest way to read such a description is to use the getline function. This function takes three arguments: a pointer to a string, a pointer to an integer, and "stdin", which tells the function to read from the console.  The string argument must be allocated beforehand, and the integer second argument should be the number of characters in the string.  e.g.

int size = 25;

char* desc = (char*)malloc(size + 1);

getline(&desc, &size,  stdin);

Checkoff 3.  Why is 1 added to size when allocating the description?

We can now use something like the above to get a description from the user.  One caveat, though, is that mixing scanf and getline is tricky.  scanf only reads one string, so it will leave the implied '\n' character on the input buffer.  If we call a getline directly after a scanf, we will only get that last '\n' character.  To use this, then, we must make a throwaway call after our scanf.  We can do this cleanly with a function such as 

void clear_input()

{

	int max = 10;

	cha* throwout = (char*) malloc(max + 1);

	getline(&throwout, &max, stdin);

}

...

scanf("%i", &input);

clear_input();

...

getline(&whatever, &size, stdin);

Now you should be able to implement the pseudocode given above. Remember that pointers to structure elements use the -> operator instead of the . operator.

Checkoff 4. Give your C code for the above pseudocode.

Part 4

Test your code above by walking north and creating new places.  You should also be able to walk south and visit places you already made.  

Now we just need to expand our program to handle south, east, and west.  Expand the if statement to handle these cases.  You should be able to copy your 'north' code directly and then use find/replace to make all the needed changes.

You should now be able to walk in any direction, creating places as you go.

Checkoff 5. What's the best place description you wrote?

Part 5

When you allocate memory dynamically, you need to free it when you are done using it.  To do this, we use the free command,

struct place* my_place = place_factory("This is a cool place");

...

free(my_place);

In our case, this is not strictly needed as the memory is freed when the program exits.

Checkoff 6. Describe how you would free all the allocated memory in the graph if you needed to.  You do not need to give C code, merely describe your approach. Are there any pitfalls?