# CS50 Nuggets ## Implementation Spec ### imac, Winter, 2022 > This **template** includes some gray text meant to explain how to use the template; delete all of them in your document! According to the [Requirements Spec](REQUIREMENTS.md), the Nuggets game requires two standalone programs: a client and a server. Our design also includes map and logic modules. We describe each program and module separately. We do not describe the `support` library nor the modules that enable features that go beyond the spec. We avoid repeating information that is provided in the requirements and design specs. ## Plan for division of labor Charlie will work on the server module Alexander will work on the client module Ike and Mubbie will work together on the map module Ike will work on the logic module We will each work on (unit) testing and documenting the modules we are assigned to. The integration and system tests will be worked on together as a team. ## Player/Client ### Data structures The client **game_info struct** stores relevant data for game operations. The struct definition is as follows: ```c struct game_info { addr_t server; char* playername; char* hostname; int gridX; int gridY; } ``` ### Definition of function prototypes The client is implemented in one file `client.c`, with five functions, - main(), which initializes server connection and display and calls functions - parseArgs(), which parses and validates command-line arguments - client_init(), which connects to server as new player or spectator - client_send(), which sends a keystroke in the form of a KEY message to the server - client_receive(), which handles network protocol input from the server and prints to display ```c int main (const int argc, char* argv[]); static int parseArgs(const int argc, char* argv[], char** hostname, int* port, char** playername); addr_t* client_init(char* hostname, int port, char* playername); bool client_send(void* arg); bool client_receive (void* arg, const addr_t from, const char* message); ``` ### Control flow: Detailed pseudo code The client will run as follows: `main` pseudocode: ``` call parseArgs on the command line arguments parseArgs returns nonzero exit nonzero call client_init and pass hostname and port (and playername if exists) if client_init returns NULL exit nonzero if failed to connect to server exit nonzero call message_loop and pass send and receive functions if message_loop returned false exit nonzero exit zero status ``` `parseArgs` pseudocode: ``` if number of arguments is not three or four return nonzero set hostname equal to the second argument if port number is not a number return nonzero else set port number to third argument if there is a fourth argument set playername to fourth argument return zero ``` `client_init` pseudocode: ``` instantiate new addr_t as message_noAddr call message_setAddr with hostname and port if message_setAddr returns false return NULL call message_send with address and PLAY playername or SPECTATE accordingly ``` `client_send` pseudocode: ``` receive character from stdin with getch send message to server with KEY [char] form ``` `client_receive` pseudocode: ``` if message is QUIT print quit message call message_done and exit if message is OK and client is player store player letter in game struct if message is GRID store nrows and ncols in game struct call initscr call cbreak call noecho call clrtoeol if message is GOLD print status of gold to first line in display refresh if message is DISPLAY get size of display with getmaxyx if grid x+1 or y+1 is larger than display x or y prompt user to increase screen size else print display to screen with mvprintw refresh if message is ERROR and the \_\_LOG\_\_ flag is defined log the error message ``` --- ## Server ### Data structures To keep track of each player and all of their necessary data for the server, the server will implement a **player struct**, with the following properties: ```c typedef struct player { char* portID; char playerID; // uppercase character: A, B, C,... char* playerName; // name of player passed in int* playerLocation; // size: 2; x,y coordinate of player int numGold; // number of gold found by this player int** playerVision; // size: grid width * grid height bool visionFull; // flag for whether or not a player has seen all the spots on the map } player_t*; ``` The server **game_info struct** stores relevant data for game operations on the server side. The struct definition is as follows: ```c struct game_info { player_t** allplayers; counters_t* goldPiles; int goldRemaining; } ``` The game_info struct is the only global variable in the server. All the players will also be stored in an array of `player` pointers. To keep track of where the gold piles are in the game and how many nuggets each pile has, server will implement a **counter** of map gold with the `key` being each gold pile's location (paired into an `integer`) and the `count` being how many nuggets are in the pile. ### Definition of function prototypes The server is implemented in one file `server.c`, with eight functions and some helper functions, - server_init(), which calls a function to create the map - generate_piles(), which randomly divides `goldTotal` into a random number of piles such that the number of piles is between `goldMinPiles` and `goldMaxPiles` inclusive - server_connection(), handles the connection between server and client - server_updateGold(), which sends a network protocol `GOLD` message to update all players on the status of gold - server_sendMapfile(), which sends network protocol messages to a player that show the player's map - server_movePlayer(), which handles a client's movement `KEY` message - server_tokenizeName(), tokenizes the players real name - server_endGame() which ends the game ```c int server_init(const int argc, char* argv[]); counters_t* generate_piles(map_t* map); bool server_connection(map_t* map, counter_t* gold) int* server_movePlayer(map_t* map, counter_t* gold, player_t* player, char key); void server_updateGold(map_t* map, counter_t* gold, player_t* player); void server_sendMapfile(int playerID); char* server_tokenizeName(char* realName); void server_endGame(); ``` ### Control flow: Detailed pseudo code The `server` will run as follows: `server_init` pseudocode: ``` parse the command line verify the map.txt argument by trying to read the file if that fails, send an error message and exit if there is a seed verify the seed argument by making sure it is a positive integer if that fails, send an error message and exit pass the seed to srand(seed) else send the pid to srand(getpid()) set new map struct equal to map_init(FILE* map.txt) call generate_piles with the open spaces array in the new map struct if that fails, send an error message and exit if server_connection returns false send an error message and exit zero exit ``` `generate_piles` pseudocode: ``` create a new counter_t* for gold piles if the gold piles counter is NULL, return false pick a random number of gold piles between GoldMinNumPiles and GoldMaxNumPiles, inclusive for each gold pile from 1 to the number of piles store the last valid location loop through the entire grid if the location is valid, generate a random number if this is the last gold pile, place the rest if the number is below 0.2(or another threshold), set int nuggets to a random-number generated from minimum of one and a maximum of (nuggets not yet in a pile / by the piles that need gold) break call map_placeGold() with the gold piles counter ``` `server_connection` pseudocode: ``` create a socket on which to listen name socket using wildcards if bind returns -1, return false get length of server address if getsockname fails, return false print assigned port number initialize int number of players to 0 initialize spectatorCounter start listening for connections while true accept connection and receive communication socket if accept fails, return false wait for messages from clients if client sends a message PLAY call helper method handlePlay() else if client sends a message SPECTATE call helper method handleSpectate() else if client sends a message KEY k call helper method handleKey() return true ``` `server_movePlayer` pseudocode: ``` convert the key to lowercase if the key is a valid move key, i.e one of h, l, j, k, y, u, b, n, if map[playerLocation x - 1][playerLocation y - 1] = "." or "#" update playerLocation send new DISPLAY message to all clients call server_updateGold return new playerLocation else return an unchanged playerLocation ``` server_updateGold() pseudocode: ``` set int key to (row * mapArea) + column if counter_get(goldCounter, key) for gold counter > 0 player numGold += counter_get(players_location) GoldTotal -= counter_get(players_location) send all clients GOLD message if GoldTotal == 0 call game_end() ``` server_sendMapfile() pseudocode: ``` if client is a spectator send map_spectatorDisplay message if client is a player send map_playerDisplay message ``` tokenize_name() pseudocode: ``` if name is NULL return NULL if length of name is > MaxNameLength truncate name for each char in name if !isgraph(char) and !isblank(char) char = "_" ``` server_endGame() pseudocode: ``` send message to all players: "QUIT GAME OVER:" followed by the top 3 players they playerIDs, number of nuggets, and the player's real name delete all memory ``` #### Helper functions handlePlay() pseudocode: ``` if number of players >= 26 send client message: "QUIT Game is full : no more players can join" else if the player's real name is empty send client message: "QUIT Sorry - you must provide player's name." else create a player struct for the player tokenize player's real name if player's tokenized name is NULL return false store a char* for the player's tokenized real name char playerID is toascii(65 + number of players) number of players goes up by 1 send message to player: "OK "playerID"" char* playerName is the player name given by player int* playerLocation = map_openLocation int numGold is 0 send client GRID message send client GOLD message send client DISPLAY message ``` handleSpectate() pseudocode: ``` if counter_get(spectatorCounter, 1) is 0 int item portID use counters_set for the (1, portID) pair send client GRID message send client GOLD message send client DISPLAY message else send message to current spectator : "QUIT You have been replaced by a new spectator" ``` hendleKey() pseudocode: ``` if k != Q, h, l, j, k, y, u, b, n, H, L, J, K, Y, U, B, N send error message continue if k = Q if client portID = counters_get(spectatorCounter, 1) send client message: "QUIT Thanks for watching!" close communication socket call counters_delete on spectatorCounter initialize a new spectatorCounter else send client message: "QUIT Thanks for playing!" close communication socket delete player struct else call server_playerMovement to find new playerLocation ``` > For each function write pseudocode indented by a tab, which in Markdown will cause it to be rendered in literal form (like a code block). > Much easier than writing as a bulleted list! > For example: #### `parseArgs`: validate commandline verify map file can be opened for reading if seed provided verify it is a valid seed number seed the random-number generator with that seed else seed the random-number generator with getpid() --- ## Map ### Data structures To handle the grid line system/layout of the game, the map module will implement the following structure: ```c typedef struct map { char** mapLines; // each char in the map, line by line int numCols; // number of columns in the map int numRows; // number of rows in the map int** emptySpaces; // index pair of empty spots, '.' on the map } map_t*; ``` ### Definition of function prototypes Detailed descriptions of each function's interface is provided as a paragraph comment prior to each function's implementation and is not repeated here. ```c map_t* map_init(FILE* mapFile); int map_getNumCols(map_t* map); int map_getNumRows(map_t* map); void map_insertGold(map_t* map, counters_t* goldPiles); void map_insertGoldHelper(void* arg, int key, int value); char* map_spectatorDisplay(map_t* map, player_t** players, int playerCount); counters_t* map_playersLocationsHelper(palyer_t** allplayers, int playerCount, int mapArea); counters_t* map_playerLocationHelper(player_t* player, int mapArea); char* map_PlayerDisplay(map_t* map, player_t** allplayers, int playerCount, player_t* playerInFocus); void map_playerVisibility(player_t* playerInFocus); bool map_isVisible(player_t* player, int rowX, int colY) int** map_getEmptySpaces(map_t* map); void map_delete(map_t* map); ``` ### Control flow: Detailed pseudo code We create a re-usable module `map.c` to handle the the gridline system/layout where all the gameplay happens. This includes settings up the grid to start the game using the text file representing the grid, placing the gold piles where they should be, providing details about the grid anytime the server needs it, changing player location when they move, controlling and displaying what a spectator and/or player can see at anytime in the game, as well as providing details about the empty spaces in the grid at anypoint in the game that the server needs it. We chose to write this as part of a seperate module, in `./modules` to encapsulate all the knowledge about how to initialize and manage a `map` during game play, anticipating use in various parts of the game. A map is stored in a 2D array of characters. Every gridpoint, in the map, is one of these characters: -` ` solid rock - interstitial space outside rooms -`-` a horizontal boundary -`|` a vertical boundary -`+` a corner boundary -`.` an empty room spot -`#` an empty passage spot Pseudocode for `map_init`: ``` // takes in a FILE* pointer to the map file // assumes the mapFile is valid i.e. a perfect rectangle call mem_assert to allocate memory for a new map object char** mapInitMemError = genMemCrashErrorMessage(mapInitMemErrorId); map_t* map = mem_assert(sizeof(map_t), mapInitMemError) get the number of rows by: char** firstLine = file_readLine(mapFile) int numRows = strlen(firstLine) map->numRows = numRows file_rewind(mapFile) get the number of columns by: int numCols = file_numLines(mapFile) map->numCols = numCols allocate space for the empty space i.e. [][], map->emptySpaces emptySpaceIndex = 0; for int i < numRows && (line = file_readLine(mapFile)) != NULL: for int j < numCols map->mapLines[i][j] = line[j] if line[j] = '.': map->emptySpaces[emptySpaceIndex] = {i, j} return map; if error, NULL ``` map_getNumCols() pseudocode: ``` Takes the map to get the number of colums return map->numCols if not NULL, else 0 ``` map_getNumRows() pseudocode: ``` Takes the map to get the number of rows return map->numRows if not NULL, else 0 ``` map_insertGold() pseudocode: ``` Takes the map to insert the gold in, and the counters set with the gold piles counters_iterate(goldPileCounters, map, map_insertGoldHelper) ``` map_insertGoldHelper() pseudocode: ``` Takes a void arg, in this case the map, the key and value as integers map_t* theMap = arg; if key!= 0 && value != 0: // error check int* coord = getCoordinates(key, theMap->numCols * theMap->numRows) theMap->mapLines[coord[0]][coord[1]] = '*' else: ifdef ERRORLOGGING: print error messag ``` map_spectatorDisplay() pseudocode: ``` Takes in a map object, and a list of current players in the game, and the number of players in the game Validates each parameter to ensure non is NULL or error // find the locations occupied by players occupiedByPlayers = map_playersLocationsHelper (list of players in game, number of players in game, map->numCols * map->numRows) // build the data to print Caller is responsible for calling free on the memory used Initializes a character array: char* spectatorView = mem_alloc(map->numCols * map->numRows) int viewIndex = 0 for int i < map->numRows for int j < map->numCols int possibleFind counter_get(occupiedByPlayers, getCountersKey(i, j, mapArea)) if possibleFind != 0 // meaning there is a player at the location spectatorView[viewIndex] = (char) possibleFind else: // there is no player at the location spectatorView[viewIndex] = map->mapLines[i][j] viewIndex++; counters_delete(occupiedByPlayers) return spectatorView ``` map_playersLocationsHelper() pseudocode: ``` Takes a list of players in the game, and the number of players in the game, and the area of the map create a new counters object counters_t* occupied = counters_new(); for each player in the game for int i < numberOfPlayersInTheGame: int rowXLoc = players[i]->playerLocation[0] int colYLoc = players[i]->playerLocation[1] int playerKey = getCountersKey(rowXLoc, colYLoc, mapArea) counters_set(occupied, playerKey, players[i]->playID) // where player id is char or int return occupied; caller is responsible for deleting counters after use ``` map_playerLocationHelper() pseudocode: ``` Takes a player in the game, the area of the map create a new counters object counters_t* visible = counters_new(); for each item in the players visibility for int i < player->visibleCoordCount: int locKey = getCountersKey(player->playerLocation[0], player->playerLocation[1]) counters_set(visible, locKey, 1) // just put one there ``` map_PlayerDisplay() pseudocode: ``` Takes a map object, a list of the players currently in the game, the number of players currently in the game, and the player who's view we desire to display // if the player has already seen all parts of the map if player->visionFull == true return map_spectatorDisplay(map, listOfPlayersInTheGame, numberOfPlayers) else: // find the locations occupied by players occupiedByPlayers = map_playersLocationsHelper (list of players in game, number of players in game, map->numCols * map->numRows) // stores the players visibility seenByPlayer = map_playerLocationHelper(player, mapArea) // build the data to print Caller is responsible for calling free on the memory used Initializes a character array: char* playerView = mem_alloc(map->numCols * map->numRows) int viewIndex = 0 for int i < map->numRows for int j < map->numCols // ensure that the location is in the player view int inView = counters_get(seenByPlayer, getCountersKey(i, j, mapArea)) if inView == 1: // check if there is a player there int possibleFind counters_get(getCountersKey(i, j, mapArea)) if possibleFind != 0 // there's a player at the location playerView[viewIndex] = (char) possibleFind else: // there is no player at the location playerView[viewIndex] = map->mapLines[i][j] viewIndex++; else: continue counters_delete(occupiedByPlayers) counters_delete(seenByPlayer) return playerView ``` map_playerVisibility() pseudocode: ``` if it is equal to the mapArea return the entire grid loop through all the rows loop through the columns if map_isVisible() increment visibleCoordCount else: remove gold visibility once they are out of range ``` map_isVisible() pseudocode: ``` loop through the rows between player and location, exclusive loop through the columns between player and location, exclusive, if the location is blocking one, return false return true ``` map_getEmptySpaces() pseudocode: ``` takes the map object allocate memory for an array to hold the empty locations, outputArray outputIdx = 0; for int i < map->numRows for int j < map->numCols if map->mapLines[i][j] == '.' outputArray[outputIdx] = {i, j} outputIdx++ return outputArray ``` map_delete() pseudocode: ``` takes the map that we want to delete mem_free(map) ``` --- ## Logic We create a module `logic.c` with methods that can be reused in various parts of the program. These method implement simple logic that simplify our interactions with elements of the map, and clients in the game. We choose to write this in the directory `./modules`, encapsulated with other modules used for the full functionality of the `nuggets` game. ### Data structures The logic module does not implement or use any significant data structures. ### Definition of function prototypes Detailed descriptions of each function's interface is provided as a paragraph comment prior to each function's implementation and is not repeated here. ```c int getCountersKey(int rowX, int colY, int mapArea); int getrowX(int countersKey, int mapArea); int getColY(int countersKey, int mapArea); int* getCoordinates(int countersKey, int mapArea); ``` ### Control flow: Detailed pseudo code getCountersKey() pseudocode: ``` Takes in three integers: rowX // x coordinate of a position on the map colY // y coordinate of a position on the map mapArea // the total area of the map i.e. map->numCols * map->numRows; might change to numCols since that is a smaller col limit return (int) rowX * mapArea + colY ``` getrowX() pseudocode: ``` Takes in two integers: countersKey // the key storing the index in a counters mapArea // the total area of the map i.e. map->numCols * map->numRows return (int) countersKey % mapArea ``` getColY() pseudocode: ``` Takes in two integers: countersKey // the key storing the index in a counters mapArea // the total area of the map i.e. map->numCols * map->numRows return (int) countersKey / mapArea ``` getCoordinates() pseudocode: ``` Takes in two integers: countersKey // the key storing the index in a counters mapArea // the total area of the map i.e. map->numCols * map->numRows Allocate memory for an array storing the coordinates, caller is responsible int* coords = mem_calloc(2, sizeof(int)) coords[0] = getrowX() coords[1] = getColY() return coords ``` --- ## Error handling and recovery All the command-line parameters are rigorously checked before any data structures are allocated or work begins; problems result in a message printed to stderr and a non-zero exit status. Out-of-memory errors are handled by extensive null checking, which result in a message printed to stderr and a non-zero exit status. The program will exit with an error message when this occurs. All code uses defensive-programming tactics to catch bad parameters or pointers to avoid fatal errors. Modules will also log useful information and errors that can be saved in a logfile to know where any errors are coming from, when appropriate. ## Testing plan ### Unit Testing #### **Server** The Server Module can be tested by passing client commands using the client module provided in the ~/cs50-dev/shared/nuggets/linux` directory. Some tests we can run are: - Various forms of invalid arguments to server - Player on our server using the provided client and player - Player on our server using the provided client and player as a bot - Write a script to play as 26 background bots, to see how well out server handles - Run the server and try to have more than 26 players join - Run the server overloaded, i.e. with 26 players or bots, and with valgrind to test for memory leaks and errors - Have all the players leave mid game Methodology: The server can also print out input received from the client and vice versa. This would confirm that the server receives and responds to client properly. When the map module functions properly, the server could also make calls to map functions and print out map grids to further demonstrate functionality. #### **Client** The Client Module can be tested by passing server commands using the server module provided in the `~/cs50-dev/shared/nuggets/linux` directory. Some tests we can run are: - Running the client and logging when it sends messages to be sure we are sending the correct thing - Playing the game to ensure that our client can progressively play and move in the game with no trouble on the server - Run the client with valgrind to test for memory leaks and errors - Try to join a server as a player that is already full - Join as a spectator when one already exists - Join as a spectator and then have another spectator join - Send invalid keystrokes (i.e. not `h`, `j`, `k`, `l`, `y`, `u`, `b`, `n` (lowercase or uppercase), or `Q`) Methodology: The client can also print out input received from the server and vice versa. This would confirm that the client receives and responds to server properly. #### **Map** The Map Module can be tested by calling map functions with hardcoded input (such as a .txt file) and printing the resulting map. The module can also be tested with a functioning server module we write and a provided client module from `~/cs50-dev/shared/nuggets/linux` to confirm the map handles gameplay properly. Some tests we can run are: - Calling map_init with a provided map.txt file and printing the char** mapLines representation of the map - Confirm proper creation of a map with correct map_getNumRows and map_getNumCols returns - Generating gold on an existing map and confirm that random gold generation was successful - Run a game with a functioning server module and the provided client class to confirm proper functionality in other methods, especially: - map_spectatorDisplay - map_playerDisplay - map_playerVisibility #### **Logic** The Logic Module is tiny; it could be tested using a small C 'driver' to invoke its functions with various arguments, but it is likely sufficient to observe its behavior during the system test. ### Regression Testing For routine regression tests, we run the Nuggets game with 1-2 players and confirm general functionality and proper data transmission. This can involve the server and client that we write, our server and the provided client, or our client and the provided server. ### System and Integration Testing The entire system can be tested together by creating a server and joining it from multiple client devices. The game can then be played and tested to make sure that all game mechanics work properly. Mechanics that should be tested include: - Player movement - Immediate up, down, left, right steps - "Capital" keystrokes - Wall collision - Pathways between rooms - Player collisions - Gold count - Collecting gold - Keeping track of gold - Printing gold count on game end - Player visibility - Player and spectator displays - Player quit - Game end - Playing with the maximum number of players, 26 - Trying to join when max players already playing/already a spectator --- ## Limitations > Bulleted list of any limitations of your implementation. > This section may not be relevant when you first write your Implementation Plan, but could be relevant after completing the implementation.