# CS50 Nuggets Implementation ## Implementation Spec ### Breaking-Bash (Team 7), Winter, 2023 According to the [Requirements Spec](REQUIREMENTS.md), the Nuggets game requires two standalone programs: a client and a server. Following our [Design Spec](DESIGN.md), we included a *grid* module to handle functions that manipulate and update details of the game. Here we describe each program and module separately focusing on the following sections: * Data structures * Definition of function prototypes * Detailed pseudocode for each function ## Plan for division of labor ### Rachel Rachel is responsible for implementing following functions: - Implement the server functions `parseArgs`, `initPlayerLocation`, `initGold`, `server_update_all_clients`, `handleMessage`, `movePlayer`, `handleSPECTATE`, `handleKEY`, `player_move` - Further debugging of the server ### Jonathan Jonathan is responsible for implementing the following: - Implement the handling messages function `handleMessage`, `handleQUIT` and `handleSPECTATE` ,`getPlayerIndex; `, `handleInput`, `initializeGame` - Finish testing of `server.c` and help debug server. ### Khanh Khanh is responsible for implementing the following: - Implement `grid_updateVisibility`, `grid_isVisible` `serverUpdatePlayers`, `gameOver` - Write `grid.h` and `grid.c` - Write and test grid module. - Write `README.md` for `grid` module - Create a new map and upload it in `maps/` directory. - ## Server ### Data structures #### Global Constants: ```c #define MaxNameLength 50 // max number of chars in playerName #define MaxPlayers 26 // maximum number of players static const int GoldTotal = 250; // amount of gold in the game static const int GoldMinNumPiles = 10; // minimum number of gold piles static const int GoldMaxNumPiles = 30; // maximum number of gold piles ``` #### `game` struct: ```c typedef struct game{ grid_t* map; //game-global map grid_t* originalMap; //Base map //Information on gold in the game int goldPilesLeft; int goldCollected; int goldLeft; //Array of all players in the game player_t* allPlayers[MaxPlayers]; int totalPlayers; addr_t spectator; } game_t; ``` #### `player` struct: ```c typedef struct player{ grid_t* mapSeen; //Map visible to a specific player addr_t address; char playerRep; //A-Z char name[MaxNameLength]; //Player's name // player's gold purse int totalGoldCollected; int recentGoldCollected; // player's location int row; int col; } playter_t; ``` #### Global variable ```c static game_t* game; ``` ### Definition of function prototypes > For function, provide a brief description and then a code block with its function prototype. > For example: A function to parse the command-line arguments, initialize the game struct, initialize the message module, and (BEYOND SPEC) initialize analytics module. #### `parseArgs` Extracts arguments from the command line into function parameters such as the map and seed for random number generator: ```c static void parseArgs(const int argc, char* argv[], char** gridPathname, int* seed); ``` #### `initPlayerLocation` Initializes a new player's location on the map randomly. ```c void initPlayerLocation(player_t* player); ``` #### `initGold` Drops gold piles in random location on the map. ```c void initGold(); ``` #### `initializeGame` Initializes a game and launches it by loading the grid and allocating memory for information on the game struct. ```c void initializeGame(char* gridPathname); ``` #### `initializePlayer` Initializes a new player's details. ```c void initializePlayer(player_t* player); ``` #### `getPlayerIndex` Extracts a player's index in from the array of players in the global game struct. ```c static int getPlayerIndex(const addr_t address); ``` #### `handleMessage` Callback function that handles messages coming from a client and calls other functions based on the message content. ```c static bool handleMessage (void* arg, const addr_t from, const char* message); ``` #### `handlePlay` Handles 'PLAY ' message from the client and adds a player to the game. ```c bool handlePlay(void* arg, const addr_t from, const char* message); ``` #### `handleKey` Handles 'KEY ' message from client. Moves the player or quits the client's program if key is valid. ```c bool handleKey(void* arg, const addr_t from, const char* keyGiven); ``` #### `handleSpectate` Handles the 'SPECTATE ' message from client. Replaces an existing or adds a new spectator to the game. ```c bool handleSpectate(const addr_t from); ``` #### `handleQuit` Ends game session with the client that sent the message. ```c bool handleQuit(const addr_t address); ``` #### `movePlayer` Moves the player to the new location based on the key they pressed. ```c bool movePlayer(player_t* player, int row, int col); ``` #### `serverUpdatePlayers` Updates clients on the all changes made on the game grid and like when a player moves or quits. ```c static void serverUpdatePlayers(void); ``` #### `gameOver` Ends the game and prints the game leaderboard. ```c static void gameOver(); ``` ### Detailed pseudo code > 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() ``` #### `initPlayerLocation` ``` while player position is not valid get a random position on grid if position is in an empty room spot position is valid add player to grid update player location ``` #### `initGold` ``` generate random num bw GoldMinNumPiles and GoldMaxNumPiles initialize number of piles, collected gold, and gold left in game for each gold pile determine random num gold nuggets in pile determine random location of gold pile while location is not valid get random row and col if it is an empty room spot location is valid add gold char (*) to grid add gold value to gold array ``` #### `initializeGame` ``` open the map txt file for reading allocate memory for the game initialize unique address for spectator initialize game map and the game original map load both game map and original map from textfile call initGold to initialize gold on grid close the map txt file ``` #### `intializePlayer` ``` initialize player's total collected and recent collected to zero obtain player's index as num of players in game Create player's alphabet representation initialize player's location using initPlayerLocation(player) create the player's mapSeen ``` #### `handleMessage`: ``` create copy of the message if message is "PLAY " return value of handlePlay if message is "KEY " extract the key return value of handlePlay if message is "SPECTATE" retun value of handleSpectate else message is malformed Log error message return false; ``` #### `handlePlay`: ``` check if player provided a name if no name send back quit message else if number of players in game if MaxPlayers send back quit message else allocate memory for new player truncate and clean up player's name call initializePlayer add new player to the game update the game grid-map send OK message to player send GRID message to player ``` #### `handleKey` ``` get player's index from the array if index is negative log a message with log_v extract the player's details if key is Q call handleQuit extract player's location Move player depending on key if 'h': left if 'H': farthest left if 'l': right if 'L': farthest right if 'j': down if 'J': farthest down if 'k': up if 'K': farthest up if 'y': up,left if 'Y': farthest up,left if 'u': up,right if 'U': farthest up,right if 'b': down,left if 'B': farthest down,left if 'n': down,right if 'N': farthest down,right max default case: log a message send message to client if all gold is collected return true else return false ``` #### `handleSpectate` ``` if there is an old spectator send quit message to them initialize the new spectator send GRID message the spectator call serverUpdatePlayers return false ``` #### `movePlayer` ``` check if position is moveable if position is gold add gold to player totalGoldCollected set recentGoldCollected to gold subtract 1 from goldPilesLeft on game add gold to goldCollcted on game subtract gold from goldLeft on game set gold on gold array to 0 update player position to empty spot move player to spot if another player steal their gold set moving player's recent gold collected set other player's purse to 0 if empty spot update player position to empty spot move player to spot ``` #### `getPlayerIndex` ``` loop through array of players to get a matching address Compare the addresses, if they match set the index and break from loop return the index ``` #### `serverUpdatePlayers` ``` for the spectator create the GOLD message and send send DISPLAY message loop through all the players send GOLD message to them reset the number of recent collected gold update their mapSeen using visibility create and send DISPLAY message ``` #### `gameOver` ``` Create quit game over title loop through all players create memory for the player's results get player's total gold collected and name create quit game over message send message to spectator and players free memory allocated for player's mapSeen and each player delete the game map and original free game ``` ## Grid module ### Data structures ```c typedef struct grid { int nrow; int ncol; char** array; int** goldArr; } grid_t; ``` ### Definition of function prototypes ```c grid_t* grid_new(int nrows, int ncols); void grid_load(FILE* fp, grid_t* grid); void grid_update(grid_t* grid, int row, int col, char c); void gold_update(grid_t* grid, int row, int col, int gold); int grid_getGold(grid_t* grid, int row, int col); char grid_getchar(grid_t* grid, int row, int col); bool grid_isGold(grid_t* grid, int row, int col); bool grid_isBoundary(grid_t* grid, int row, int col); bool grid_isEmptyRoom(grid_t* grid, int row, int col); bool grid_isPlayer(grid_t* grid, int row, int col); bool grid_isRock(grid_t* grid, int row, int col); bool grid_isMoveable(grid_t* grid, int row, int col); bool grid_isBlocked(grid_t* grid, int row, int col); void grid_print(grid_t* grid); bool grid_isVisible(grid_t* basemap, int pr, int pc,int r, int c); void grid_reset(grid_t* basemap, grid_t* seenmap); void grid_updateVisibility(int pr, int pc, grid_t* basemap, grid_t* seenmap, grid_t* rawmap); int grid_getRow(grid_t* grid); int grid_getCol(grid_t* grid); char* grid_toString(grid_t* grid); void grid_delete(grid_t* grid); ``` The `grid_new` function is responsible for creating a new 2D array and for each row and each column, or each spot [row][col] for a character. The `grid_load` function is responsible for loading the map.txt file into the grid. The `grid_update` function is responsible for updating changes to the map (e.g. dropping golds and players on the map) The `gold_update` function updates the gold character on the raw map The `grid_getGold` function returns the num of gold at location the provided The `grid_getchar` function returns the character at a specific location on the map. The `grid_isGold` function checks for gold character on the map (`*`). The `grid_isBoundary` function checks for boundary character on the map (`|`, `-`, `+`). The `grid_isEmptyRoom` function checks for empty spot on the map (`.`). The `grid_isPlayer` function checks for player character on the map (`A-Z`, '@'). The `grid_isRock` function checks for rock on the map (` `). The `grid_isMovable` function checks whether a spot allows a player to move to. The `grid_isBlocked` function checks if a player's view is blocked. The `grid_print` function prints the grid map for testing. The `grid_isVisible` function calculates player's view in the game The `grid_reset` function changes game's map based on visibility when the player moves The `grid_updateVisibility` function resets map and updates area seen by player The `grid_getRow` function returns number of rows in grid The `grid_getCol` function returns number of columns in grid The `grid_toString` function returns a string that represents the grid for display The `grid_delete` function frees memory allocated to grid when deleting grid ### Detailed pseudo code #### `grid_new`: ``` if valid number of rows and columns: allocate memory for the grid if grid is not null: allocate memory for the rows if rows is not null: allocate memory for the columns for each rows, which means allocating memory for each character in the map ``` #### `grid_load`: ``` find the number of rows and columns from the map for each line in map read the line get the character and store it in the grid ``` #### `grid_getchar`: ``` get character at the specified location on the grid ``` #### `grid_isGold`: ``` compare character at the specified location to `*` ``` #### `grid_isBoundary`: ``` compare character at the specified location to `|`, `+`, and `-` ``` #### `grid_isEmptyRoom`: ``` compare character at the specified location to `.` ``` #### `grid_isPlayer`: ``` compare character at the specified location 'A-Z' character ``` #### `grid_isRock`: ``` compare character at the specified location to ` ` ``` #### `grid_isMovable`: ``` compare character at the specified location to all the movable spot. ``` #### `grid_isBlocked`: ``` check if character at the specified location is the boundary or passage spot (which restrict the visibility of players) ``` #### `grid_isVisbile`: ``` check whether at current location (pr, pc), player can see the specified location on the map (r,c) if on the same row or column: check visibility for all the spots in between pr r or pc c if not: calculate the slope and check whether the slope passes through the gridpoint if yes, check if that point is visible if no, for each row that the slope pass through, check for the visibility of two adjacent column for each column that the slope pass through, check for the visibility of the two adjacent row ``` #### `grid_isVisbile`: ``` check whether at current location (pr, pc), player can see the specified location on the map (r,c) if on the same row or column: check visibility for all the spots in between pr r or pc c if not: calculate the slope and check whether the slope passes through the gridpoint if yes, check if that point is visible if no, for each row that the slope pass through, check for the visibility of two adjacent column for each column that the slope pass through, check for the visibility of the two adjacent row ``` #### `grid_updateVisibility`: ``` for each grid point on the map check for the visibility if visible update the map ``` #### `grid_toString`: ``` for each character in the grid store it in the result grid string ``` #### `grid_reset`: ``` if the gold character or a player is no longer within a player's view update the seenMap to the original map character ``` #### `grid_delete`: ``` free the memory allocated for the grid array free the memory allocated for the gold array free the grid ``` #### `grid_getCol`: ``` return num of cols in map ``` #### `grid_getRow`: ``` return num of rows in map ``` --- ## Testing plan ### Unit testing Our impementation has two main components, the *grid* module and the *server* which has the main program. As described in our DESIGN.md, each function in the module will be thoroughly tested to ensure that the grid's functions work seamlessly. Since the *grid* is innately connected to the all parts of the server, we will create a `testgrid` program that will load test maps and call all the *grid* functions on it. The tests will focus on ensuring that the grid is properly updated whenever a change is made in the game including visibility. ### Integration testing For the `server`, we will test the areas such as dropping gold in random spots on the grid, assigning players random locations, displaying the game, as well as testing that all changes done on the grid are reflected in the game. This will be achieved firsrt by using the `miniclient` program already provided in the program in addition to the `bot` program, as mentioned, again, in DESIGN.md then using the full client program provided. We'll write a bash script to handle all the test cases and run the programs using a Makefile. Finally, we will run VALGRIND on the `server` while using the `testgrid` to check memory leaks and other errors to ensure that all allocated memory is freed. ---