# CS50 Nuggets
## Implementation Spec
### Team XVI, Spring 2024
According to the [Requirements Spec](REQUIREMENTS.md), the Nuggets game requires two standalone programs: a client and a server.
Our design also includes player, map, gridpoint, and visualization 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 spec.
## Separation into Modules
### Programs
- [Client](#Client-Module)
- [Server](#Server-Module)
### Game-Logic Library
- [Player](#Player-Module)
- [Gridpoint](#Gridpoint-Module)
- [Map](#Map-Module)
- [Visibility](#Visibility-Module)
## Plan for division of labor
- Client Program - Zach
- Server Program - Michael
- Visibility - Will
- Map - Dylan
## Client Module
### Data structures
The client also heavily utilizes a module, `message`. More detail on the `message_` module can be found in its associated header file.
The message module initializes communication to a server.
On the client's end:
connect to server
message_loop
recieve keystrokes and send messages
PLAY, SPECTATE, KEY
The `message_loop` takes two functions to handle `input` and `messages`. Both functions will take a `void* arg` parameter. We will need to pass several client variables into these functions, so it is cleanest to store them all in a struct `user_t`:
```c
typedef struct user{
addr_t server;
char* playername;
char letter;
int goldStatus[3];
char explanation[100];
const char* quitExplanation;
}user_t;
```
* The `server` of type `addr_t` is a module off of `message`, and holds various _sin_ and _IP_ info.
* The `playername` should be `NULL` if the user is a _spectator_ otherwise it should be the provided playername.
* `letter` Is assigned to the user from an `OK L` message, where `L` is the user's spot in an alphabetical array.
* `goldStatus` is a 3-int array which stores `n`, `p`, & `r`: _gold recieved on newest move_, _total gold in purse_, & _remaining gold in game_ respectively
* `explanation` is allocated on the stack, and is the right-most information on the status line
* `quitExplanation` is recieved after inputting `Q` as a client. It prints after closing the game
### Definition of function prototypes
Validate and assign command-line arguments.
```c
static void parseArgs(const int argc, char* argv[], char** serverHost, char** serverPort, user_t* user);
```
Initialize display and begin communication with server.
```c
static void initializeClient(user_t* user);
```
Validate and process user keystrokes.
```c
static bool handleInput(void* arg);
```
Validate and process messages received from server.
```c
static bool handleMessage(void* arg, const addr_t from, const char* message);
```
Print out the visible map recieved from the server.
```c
static void displayGrid(const char* grid);
```
Print out game updates recieved from the server.
```c
static void displayStatusLine(user_t* user);
```
Helper functions to break up message handling.
```c
static void recieveGRID(const char* info);
static void recieveOK(const char* info, user_t* user);
static void recieveGOLD(const char* info, user_t* user);
static void recieveQUIT(const char* info, user_t* user);
static void recieveERROR(const char* info, user_t* user);
```
### Detailed pseudo code
#### `main`:
The main function should parse user arguments with `parseArgs`, set up client-side messaging with `initializeClient`, call a `message_loop`, and exit depending on the success of the loop:
parseArgs and validate user parameters
initializeClient and send initial messages to server
bool success mapped to message_loop(server, handleInput, handleMessage)
end ncurses
print any closing messages
return success casted as an interger
#### `parseArgs`:
To validate all the user parameters passed into the command line, a function`parseArgs` is helpful to handle all non-zero exit statements.
`parseArgs` should check that there is a correct count of parameters, initialize pointers from `argv[]`, validate those parameters, and exit non-zero at any point of failure:
if (parameters == 3 || 4)
initialize message module
on failure exit non-zero
print assigned port number
if (3 parameters)
declare client as a spectator
if (4 parameters)
declare client as a player
set user->playername
else
exit non-zero
#### `initializeClient`:
The `initializeClient` function should set up `ncurse` within the terminal for individual character parsing and a refreshing display.
On success, the function sends an initial `PLAY` or `SPECTATE` message to the server:
validate message addr_t
initialize curses
if (user->playername == NULL)
send "SPECTATE" to server
else
copy "PLAY " to message
copy playername to message
send message to server
#### `handleInput`:
The `handleInput` function is called from `message_loop` to continually get keystrokes and send them to the server:
create addr_t from arg*
if (addr == NULL)
return true and break _loop
if (addr != valid)
return true and break _loop
current char keystroke
bool valid keystroke
if getch() != ERR
char[] of possible lowercase keystrokes
iterate through []
if tolower(keystroke) == char[i] AND playername != NULL
valid is true
if keystroke == 'Q'
valid is true
else
return true
if valid
send "KEY " + keystroke
return false
#### `handleMessage`:
The `handleMessage` will recieve messages from the server.
The client should only be recieving `OK`, `GRID`, `GOLD`, `DISPLAY`, `QUIT`, and `ERROR` messages. For clarity sake, the `recieve` functions have been integrated into the switch. The logic should be separated:
So validate as such and display the grid:
set user->addr_t to new from addr_t
tokenize first word of message into char* phrase
tokenize rest of message into char* info
switch phrase
case "OK"
update user->letter to info
case "GRID"
scan rows and columns into ints
getmaxyx() for resolution of screen
while screen resolution < grid resolution
display warning in status line
case "GOLD"
scan n, p, r into goldStatus[3]
update explanation to display gold recieved
case "DISPLAY"
mvprintw infor on line below status (1,0)
case "QUIT"
copy quit explanation into user
case "ERROR"
update explanation to display error
#### `displayStatusLine`:
`displayStatusLine` is called through the message handler, and deals strictly with printing the `statusLine`(s) recieved from the server:
if user->playername != NULL
mvprintw player letter and their gold,
gold remaining,
and most recent status update
else
mvprintw gold remaining,
and most recent status update
refresh() ncurses
---
## Server Module
```c
// Global constants:
static int MaxNameLength = 50; // max number of chars in playerName
static int MaxPlayers = 26; // maximum number of players
```
### Data structures
### Definition of function prototypes
A function to parse and validate the command-line arguments.
```c
void parseArgs(int argc, char* argv[], char** mapText, int* seed);
```
A function to stop the game and free all memory.
```c
void gameOver(addr_t* playerAddresses, char* playerNames);
```
Called by the message loop each time a message is received; correctly responds to each message
```c
static bool handleMessage(void* arg, const addr_t from, const char* message);
```
send a GOLD message to all the players, specifically telling `player` how much new gold they aquired.
```c
static void sendGoldUpdates(addr_t* addresses, char player, int amt);
```
send a DISPLAY message to all the players with the current state of the map for their view.
```c
static void sendDisplayUpdates(addr_t* addresses);
```
get the player character corresponding to a given address
```c
static char getCharFromAddress(addr_t* playerAddresses, addr_t* address);
```
### Detailed pseudo code
#### `main`:
call parseArgs
call map_init with the map text filename
playerAddresses <-- an array of MaxPlayers+1 blank addr_t*'s
playerNames <-- an empty array of strings
numPlayers <-- 0
set up and start messaging loop
- log to stderr
- give handleMessage a copy of the playerAddresses and numPlayers
call gameOver
// clean up
free all memory associated with playerAddresses and playerNames arrays
close down map module
close down message module
#### `parseArgs`:
validate num of args
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()
#### `gameOver`:
intialize game over message
for char c in A..Z:
get final info about player c
add info to game over message
for address in playerAddresses:
send game over message to address
#### `handleMessage`:
these cases will likely be separated into their own functions.
unpack arg into playerAdresses array and numPlayers
char player <-- getCharFromAddress
switch on first word of message:
case PLAY:
if numPlayers == maxPlayers:
send quit message
else if no name:
send quit message for no name
else:
tell map to add a new character
if unsuccessful, tell client to quit
else:
send the OK message to client
normalize name
add player address and name to approriate arrays
send GRID message
send individual GOLD message
sendDisplayUpdates
return false
case SPECTATE:
if there is a spectator:
tell spectator to quit
set client address to start of playerAddresses
send GRID message
send individual GOLD message
send individual DISPLAY message
return false
case KEY: // right now this just skips an invalid key
if player is 0:
tell client to quit and that it needs to
start the game as a player or spectator
if key is 'q' or 'Q':
send QUIT message to client
remove player from map
remove player from server (free and null-out associated data)
else if key is a movement key:
if player is '@':
tell client ERROR: spectators cannot move
tell map to move character
if successful:
sendDisplayUpdates
if gold was collected:
sendGoldUpdates(player, amt)
if no more gold in the game:
return true
return false
default:
send a message-type error
return false
#### `sendGoldUpdates`:
t <-- get total remaining gold
for char c in @,A..Z:
p <-- get c's purse
if c is the player:
n <-- amt
else:
n <-- 0
send "GOLD n p t" to c's address
#### `sendDisplayUpdates`:
for char c in @,A..Z:
mapString <-- get c's map string
send "DISPLAY\nmapString" to c's address
#### `getCharFromAddress`:
for char c in @,A..Z:
if playerAdresses[c] matches given address:
return c
return 0
---
## Gridpoint Module
### Data structures
We implement a new data structure `gridpoint` that stores information about a location in the map. The gridpoint will store the default character of the map, the gold amount, a set of other gridpoints visible from each point, and the player at the gridpoint.
The gridpoint should be defined as follows:
```c
typedef struct gridpoint{
int x;
int y;
char mapChar;
char player;
int gold;
bool visible[MaxPlayers+1];
hashtable_t* visiblePoints;
} gridpoint_t*;
```
Where:
* *x* and *y* represent the (row,col) coordinates of the gridpoint
* *mapChar* represents the background character \{ + , - , | , # , • , etc. }
* *player* represents the letter occupying a space
* *gold* represents the quantity of gold occupying the space
* *visible* is an array of players to whom the gridpoint is visible. The 0-index represents the spectator, who can see everything; as such, every entry is always true.
* i.e., a gridpoint visible to players 'A' and the spectator would contain:
```c
[true, true, false, false ... false];
```
The module also makes use of our previously developed `hashtable` data structure to store calculated visibility from a certain gridpoint. This tactic allows us to perform the expensive player visibility computations only once per gridpoint and only when necessary.
### Definition of function prototypes
Set the visibility of a player at a certain gridpoint
```c
gridpoint_t* gridpoint_new(char mapChar);
```
Get the default map character at a certain gridpoint
```c
char gridpoint_getChar(gridpoint_t* gp);
```
Get the hashtable of gridpoints that can be seen from a certain gridpoint
```c
hashtable_t* gridpoint_getVisibility(gridpoint_t* gp);
```
Get the gold at a certain gridpoint
```c
int gridpoint_getGold(gridpoint_t* gp);
```
Get the player at a certain gridpoint, if any
```c
char gridpoint_getPlayer(gridpoint_t* gp);
```
Set the hashtable of gridpoints that can be seen from a certain gridpoint
```c
bool gridpoint_setVisibility(gridpoint_t* gp, hashtable_t* visible);
```
Set the gold at a certain gridpoint
```c
bool* gridpoint_setGold(gridpoint_t* gp, int gold);
```
Set the player at a certain gridpoint
```c
bool* gridpoint_setPlayer(gridpoint_t* gp, char player);
```
Print a gridpoint for debugging
```c
bool* gridpoint_print(gridpoint_t* gp);
```
### Detailed pseudo code
The functions within the gridpoint module are trivial (simply getting and setting the variables within a gridpoint), so we omit pseudocode for this module.
---
## Player Module
This module provides a player data structure to represent a single player of the game.
### Data Structures
```c
typedef struct player {
bool active;
int gold;
int xPos;
int yPos;
hashtable_t* seen;
} player_t*;
```
### Definition of Function Prototypes
Add a new player to the game:
```c
player_t* player_new();
```
Remove a player from the game:
```c
void player_delete(player_t* player);
```
Getters and Setters:
```c
void player_setGold(player_t* player, int gold);
int player_getGold(player_t* player);
void player_setPos(player_t* player, int x, int y);
int player_getX(player_t* player);
int player_getY(player_t* player);
```
---
## Map Module
```c
static int GoldTotal = 250; // amount of gold in the game
static int GoldMinNumPiles = 10; // minimum number of gold piles
static int GoldMaxNumPiles = 30; // maximum number of gold piles
```
### Data structures
We implement a new datastructure called `map`, which holds information about the game status. This includes an array of gridpoints, redefined as a `grid`, the total gold left in the game, the players in the game, and the number of players who have joined the game.
*Note: num_players is non-decreasing, a player leaving the game will not affect this value*
```c
typedef gridpoint_t*** grid_t;
struct map {
grid_t grid;
int totalGold;
int remainingGold;
player_t** players;
int num_players;
int width;
int height;
} map_t*
```
This map is initialized as a global variable, and all functions reference this global map.
### Definition of function prototypes
Initialize the map global variable from a provided text file
```c
bool map_init(fileName);
```
Distribute gold across the map in between minPiles and maxPiles piles
```c
static bool map_distributeGold();
```
Gets the remaining gold amount
```c
int map_getRemainingGold():
```
Get the amount of money in a player's purse
```c
int map_getPurse(char player);
```
Gets the player with certain char id
```c
static player_t* map_getPlayer(char player);
```
Randomly place character in map, create player struct
```c
char map_addPlayer();
```
Removes a player from the game
```c
void map_removePlayer(char player);
```
Returns the gridpoint at a certain location
```c
gridpoint_t* map_getLocation(int x int y);
```
Cleans up the map
```c
void map_delete();
```
Moves player in certain direction (key input)
```c
int map_movePlayer(char player, char direction)
```
Moves player exactly once, if possible.
```c
static int map_movePlayerOnce(char player, int dy, int dx);
```
```c
int map_getWidth();
int map_getHeight();
```
### Detailed pseudo code
Pseudocode for `map_init`:
```c
setWidth = false;
file = fopen(fileName);
while((c = getc(file)) != EOF):
if(c == '\n'):
setWidth = true;
map.height++;
elif(setWidth == false):
map.width++;
rewind(file);
map.grid = malloc(sizeof(gridpoint_t**)*height);
for(row in map.grid):
row = malloc(sizeof(gridpoint_t*)*width);
int x = 0;
int y = 0;
gridpoint_t* gp;
while((c = getc(file)) != EOF):
gp = gridpoint_new(c);
map.grid[y][x] = gp;
```
Pseudocode for `map_distributeGold()`
```c
int numPiles = rand()%(maxPiles - minPiles);
numPiles+=minPiles;
```
Pseudocode for `map_getPlayer()`
```c
return map.players[player-'A']
```
Pseudocode for `map_addPlayer()`
```c
if we don't have room for a new character:
return 0
else:
char player = numPlayers + '@';
increment number of players
placed = false;
while(!placed):
x = rand()%width
y = rand()%height
if(gridpoint_getChar(map.grid[y][x]) == '.' && gridpoint_getPlayer(map.grid[y][x]) == '\0' && gridpoint_getGold((map.grid[y][x])) == 0):
new_player = player_new(player);
if (new_player == NULL) return 0;
gridpoint_setPlayer(map.grid[y][x], player);
player_setPos(new_player, x, y);
add player to list of players;
placed = true;
return player
```
Pseudocode for `map_removePlayer()`
```
if player doesn't exist, return
free player struct
set pointer in players array to NULL
remove character from the grid
```
Pseudocode for `map_getLocation()`
```c
return map.grid[y][x]
```
Pseudocode for `map_movePlayer()`
```c
ignore invalid direction
if(isUpper(dir)):
move player until hitting a wall or swapping with a player
keep track of total gold collected
else:
move player once in direction if possible
record gold collected
if movement was unsuccessful, return -1
else return amt of gold collected
```
Pseudocode for `map_delete()` is omitted for the implementation spec, as it's relatively trivial
---
## Visibility Module
### Control Flow
Visibility functions are called only by the map module. visibility_set is called whenever a player moves or is added to the game. visibility_clear is called whenever a player moves, *before they move*.
### Data structures
Visibility relies on the `grid_t` 2D array of gridpoints contained within the global `map` structure. This module also needs access to the player structure.
### Definition of function prototypes
Calculates which gridpoints should be visible to a particular player.
```c
void visibility_set(map_t map, player_t* player);
```
resets the gridpoints that are visible while retaining those that have been seen
```c
void visibility_clear(map_t map, player_t* player);
```
### Detailed pseudocode
visibility_set:
if gridpoint at current location has a non-NULL hashtable
this location has been calculated before
for each gridpoint item in the hashtable:
set visibility for this gridpoint and provided player to true
otherwise, calculate all points that are visible
px = player_getX
py = player_getY
mark map[px][py] as visible and seen for current player
add map[px, py] to hashtable of visible gridpoints for this gridpoint
iterate through each gridpt gx, gy in the map
get the horizontal distance from player to gridpt
get the vertical distance from player to gridpt
dy/dx = vertical / horizontal
dx/dy = horizontal / vertical
float current x = px
float current y = py
bool checkRow = false
bool checkCol = false
Iterate through the rows, starting at py+1:
while cy is less than gridpoint y
current x += dx/dy
current y += 1
if the current row is a gridpt (cx % 1 = 0)
if the gridpt == {+,-,|,#} it blocks visibility.
set visibility to false, just in case
break out of while loop
otherwise, round down column
if both map[x][y] and map[x+1][y] == {+,-,|,#}:
set visibility to false, just in case
break out of while loop
if no wall detected, checkRow = true
if checkRow is false,
break and move to next gridpt
otherwise, reset cx and cy
Iterate through the rows, starting at py+1:
while cx < gridpoint x
current x += 1
current y += dy/dx
if the current col is a gridpt (cy % 1 = 0)
if the gridpt == {+,-,|,#} it blocks visibility.
set visibility to false, just in case
break out of while loop
otherwise, round down row
if both map[x][y] and map[x][y+1] == {+,-,|,#}:
set visibility to false, just in case
break out of while loop
if no wall detected,
checkCol = true;
if checkCol is false:
break and move to next column
otherwise:
mark map[cx][cy] as visible to player
add map[cx][cy] to visiblePoints for key "px,py"
visibility_clear:
for each row in the map:
for each col in the map:
gridpoint = map[x][y]
if a gridpoint was visible to current player
seen for current player is true
visibility for current player is false
### Error Handling and Recovery
Any error producing the visibility array would likely be fatal or result in unexpected behavior when displaying the map to a client. As such, the visibility functions do attempt to catch and respond to errors; this is left to the higher-level modules. Visibility functions assume a valid `map_t` map and an existing `player`, both of which should be validated prior to their inclusion as a parameter in a function call.
The use of a `hashtable` to document other gridpoints visible from a given gridpoint is a memory-intensive process. While visibility_set does not allocate memory for new sets, it does add items to existing sets. So long as `set_delete()` is eventually called on each gridpoint, no memory issues should occur.
---
## Testing plan
### unit testing
#### map and visibility
We plan to manually create a few small environment maps in which to test that the visibility functions run as expected. This will be implemented in a visibilityTest module, complementary to the visibility module.
* First, we will build a 4x4 room encased by walls to ensure that all gridpoints are visible to one or two players. For both scenarios, we will artificially 'move' the player by altering the contents of the player struct. To validate the resulting
* As display of characters and gold is handled by a simple conditional within the server's display, testing of this component will simply consist of checking a gridpoint's visibility and the results of calling gridpoint_getGold and gridpoint_getPlayer.
* Second, we will build a more complex corridor similar to the one in the demonstration video to test that hidden gridpoints remain hidden. Again, we will artificially 'move' players to check that the clearVisibility function accurately preserves seen gridpoints.
### integration testing
#### server
We plan to test the functional server with the provided dummy client scripts. We'll also make use of the simple stdin-based client to try out bad input.
- trying to joing while already playing
- spectating while already playing
- sending movement strokes as a spectator
#### client
We plan to test the functional client with the provided `miniserver.c`. When both the server and client are functional, we plan to test the two together in a variety of _valid_ cases, including:
* One player
* One spectator
* One player and one spectator
* Several players
* Several players and one spectator
As well, we will test the client for _invalid edge_ and _base_ cases:
* More than 1 spectator(s)
* More than 26 players
* Unopened server port
These tests will probe only the ability of the server and client to process joining and quitting. Full-function testing is described below.
### system testing
We plan to apply a provided bot testing script, complete with 26 players and a spectator. Each client sends random messages to the server. These messages are valid but may not code for valid movement.
We'll also try having too many clients and clients that leave and rejoin a lot
---
## Limitations
> To be updated as modules are implemented.
Sign in with Wallet
Connect another wallet