Parallel Computing Assignment (OpenMPI)

basketball-match.cpp

#include <mpi.h>
#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

const int NUMPROCS = 12;
const int FIELD0 = 10; // (0,0)  -> (64,64)
const int FIELD1 = 11; // (65,0) -> (128,64)
const int ROUNDS = 1;

// MPI communication tags
const int TAG_BALL_LOC = 0; // field notify players of ball location
const int TAG_AT_BALL = 1; // player notify field his is at ball
const int TAG_REACHED_MAX_DIST_RAN = 2; // notify field a player has run 10 feet for that found already
const int TAG_WINNER = 3; // field notifies players about winner

struct PlayerBallChallenge {
	int player;
	int ballChallenge;
};

void initPositions(int half);
void initPlayerStats();
bool isField();
bool isPlayer();
int team();
bool atBall();
bool isFieldWithBall();

int numprocs, 
	id,
	playerStats[12][3], // players will be [0,4], [5,9]. length 12 used to keep indexing less confusing
	fieldWithBall, // using const FIELD0 or FIELD1
	pos[2], // position of self
	ballPos[2];

int main() {
	MPI_Init(NULL, NULL);
	MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
	MPI_Comm_rank(MPI_COMM_WORLD, &id);

	if (numprocs != NUMPROCS) {
		cout << "Please run with " << NUMPROCS << " processes" << endl;
		MPI_Finalize();
		return 0;
	}

	srand(time(NULL) + id);

	// init player stats
	initPlayerStats();
	// - verify correct stats
	if (isPlayer()) {
		if (playerStats[id][0] < 1 || playerStats[id][0] > 10
			|| playerStats[id][1] < 1 || playerStats[id][1] > 10
			|| playerStats[id][2] < 1 || playerStats[id][2] > 10) {
			cout << "Constraint not met: player " << id << " has a stat not in [1,10]" << endl;
		}
		if (playerStats[id][0] + playerStats[id][1] + playerStats[id][2] != 15) {
			cout << "Constraint not met: player " << id << " has sum of stats != 15" << endl;
		}
	}

	// init initial ball position in middle
	if (id == FIELD0) {
		ballPos[0] = 64;
		ballPos[1] = 32;
	}
	fieldWithBall = FIELD0;

	for (int half = 0; half < 2; half++) {
		// init players starting positions
		initPositions(half);

		for (int round = 0; round < ROUNDS; round++) {
			vector<PlayerBallChallenge> playersAtBall;
			int numPlayersAtMaxDist = 0, // (for fieldWithBall) number of players who completed running 10 feet this round
				distPts, // dist points available
				distToRun, // dist to run in 1 direction
				distRan = 0, // dist a player ran that round
				winner = -2,
				ballChallenges[10][2], // used by fieldWithBall [ player, ballChallenge ]
				stoppedRunning[10]; // used by fieldWithBall to track who stopped running
				
			MPI_Request 
				ballChallengeReqs[10], // used by fieldWithBall to listen to ball challenge requests
				stoppedRunningNotifications[10], // used by fieldWithBall to listen to players that they have reached max dist ran
				winnerNotification; // used by players to listen to fieldWithBall for winner notification

			fill_n(stoppedRunning, 10, -1);

			// players determine location of ball
			if (isFieldWithBall()) {
				// send ball position info to players
				// will send (-1, -1) if the ball is not in its area
				for (int i = 0; i < 10; i++) {
					MPI_Send(&ballPos, 2, MPI_INT, i, TAG_BALL_LOC, MPI_COMM_WORLD);
				}

				for (int i = 0; i < 10; i++) {
					fill_n(ballChallenges[i], 2, 0); // zero array

					// listen to player's ball challenges
					MPI_Irecv(&ballChallenges[i], 2, MPI_INT, i, TAG_AT_BALL, MPI_COMM_WORLD, &ballChallengeReqs[i]);
					// listen to players notification that they have stopped running
					MPI_Irecv(&stoppedRunning[i], 1, MPI_INT, i, TAG_REACHED_MAX_DIST_RAN, MPI_COMM_WORLD, &stoppedRunningNotifications[i]);
				}
			} else if (isPlayer()) {
				// players get ball position from fieldWithBall field process
				MPI_Recv(&ballPos, 2, MPI_INT, fieldWithBall, TAG_BALL_LOC, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

				// players listen to field notification on winner
				MPI_Irecv(&winner, 1, MPI_INT, fieldWithBall, TAG_WINNER, MPI_COMM_WORLD, &winnerNotification);
			} 

			// prevent field without ball from doing infinite loop here
			if (isField() && !isFieldWithBall()) {
				winner = -1; 
			}
			while (winner == -2) {
				//cout << id << " distRan is " << distRan << endl;
				if (isPlayer() && distRan < 10) {
					if (distRan < 10) {
						// continue running towards ball
						distPts = (rand() % playerStats[id][0]) + 1;

						// - ensure max distRan is 10
						if (distRan + distPts > 10) {
							if (distRan < 10) {
								distPts = 10 - distRan;
							} else {
								distPts = 0;
							}
						}

						// - start in x direction
						if (ballPos[0] != pos[0]) {
							distToRun = min(abs(ballPos[0] - pos[0]), distPts);
						} else {
							distToRun = 0;
						}
						if (ballPos[0] > pos[0]) { // ball is on left
							pos[0] += distToRun;
						} else if (ballPos[0] < pos[0]) {
							pos[0] -= distToRun;
						}
						distRan += distToRun;

						// - then in y
						if (ballPos[1] != pos[1]) {
							distToRun = min(abs(ballPos[1] - pos[1]), distPts - distToRun);
						} else {
							distToRun = 0;
						}
						if (ballPos[1] > pos[1]) { // ball is on top
							pos[1] += distToRun;
						} else if (ballPos[1] < pos[1]) {
							pos[1] -= distToRun;
						}
						distRan += distToRun;
					}

					if (distRan == 10) {
						// notify fieldWithBall that I will stop running
						MPI_Send(&id, 1, MPI_INT, fieldWithBall, TAG_REACHED_MAX_DIST_RAN, MPI_COMM_WORLD);
						cout << id << " telling field stopped running" << endl;
					}

					if (atBall()) {
						// notify field process player has reached ball (and send ball challenge)
						int tmpBallChallenge[2];
						tmpBallChallenge[0] = id;
						tmpBallChallenge[1] = ((rand() % 10) + 1) * playerStats[id][1];
						MPI_Send(&tmpBallChallenge, 2, MPI_INT, fieldWithBall, TAG_AT_BALL, MPI_COMM_WORLD);
						cout << id << " sent ball challenge" << endl;
					}

					// once (distRan == 10 || atBall) just wait for fieldWithBall to send winner notification
					if (distRan == 10 || atBall()) {
						MPI_Wait(&winnerNotification, MPI_STATUS_IGNORE);
					}
 				} // is player
				
				if (isFieldWithBall()) {
					int numStoppedRunning = 0;
					for (int i = 0; i < 10; i++) {
						cout << "stoppedRunning[" << i << "] = " << stoppedRunning[i];
						if (stoppedRunning[i] >= 0) {
							numStoppedRunning++;
						}
					}
					cout << endl << numStoppedRunning << " stopped running" << endl;

					winner = -2;
					if (numStoppedRunning == 10) {
						// all have stopped running
						winner = -1;
					} 

					// test/determine who is at ball
					int flag;
					playersAtBall.clear();
					cout << "after clear playersAtBall.size() = " << playersAtBall.size() << endl;
					for (int i = 0; i < 10; i++) {
						MPI_Test(&ballChallengeReqs[i], &flag, MPI_STATUS_IGNORE);
						if (flag) { // i is at ball
							// push to playersAtBall
							PlayerBallChallenge challenge = { ballChallenges[i][0], ballChallenges[i][1] };
							playersAtBall.push_back(challenge);
							cout << "seems like " << i << " is at ball? " << endl;
						} else {
							// cancel the remaining requests
							MPI_Cancel(&ballChallengeReqs[i]);
						}
					}

					// do ball challenge for those at ball
					PlayerBallChallenge currBallChallengeWinner = { -2, -1 };
					for (int i = 0; i < playersAtBall.size(); i++) {
						if (playersAtBall.at(i).ballChallenge > currBallChallengeWinner.ballChallenge) {
							// better ball challenge
							currBallChallengeWinner = playersAtBall.at(i);
							cout << "ball challenge (1) winner is now " << currBallChallengeWinner.player << endl;
						} else if (playersAtBall.at(i).ballChallenge == currBallChallengeWinner.ballChallenge) {
							// tie 
							if (rand() % 2 > 0) { // 50% chance to change currBallChallengeWinner
								currBallChallengeWinner = playersAtBall.at(i);
								cout << "ball challenge (2) winner is now " << currBallChallengeWinner.player << endl;
							}
						}
					}
					winner = currBallChallengeWinner.player;

					// notify players of a winner if any
					if (winner != -2) {
						for (int i = 0; i < 10; i++) {
							MPI_Send(&winner, 1, MPI_INT, i, TAG_WINNER, MPI_COMM_WORLD);
							cout << "notify players of winner: " << winner << ". players at ball = " << playersAtBall.size() << endl;
						}
					}
				} // if id is fieldWithBall
			} // while no winner
		}
	}

	MPI_Finalize();
	return 0;
}

void initPlayerStats() {
	// in 2nd dimention, 
	// - 0: speed
	// - 1: dribbling
	// - 2: shooting
	playerStats[0][0] = 6;
	playerStats[0][1] = 6;
	playerStats[0][2] = 3;

	playerStats[1][0] = 5; 
	playerStats[1][1] = 5;
	playerStats[1][2] = 5;

	playerStats[2][0] = 7; 
	playerStats[2][1] = 5;
	playerStats[2][2] = 3;

	playerStats[3][0] = 4;
	playerStats[3][1] = 4;
	playerStats[3][2] = 7;

	playerStats[4][0] = 5;
	playerStats[4][1] = 4;
	playerStats[4][2] = 6;

	playerStats[5][0] = 5;
	playerStats[5][1] = 7;
	playerStats[5][2] = 3;

	playerStats[6][0] = 4;
	playerStats[6][1] = 5;
	playerStats[6][2] = 6;

	playerStats[7][0] = 8;
	playerStats[7][1] = 3;
	playerStats[7][2] = 4;

	playerStats[8][0] = 5;
	playerStats[8][1] = 7;
	playerStats[8][2] = 3;

	playerStats[9][0] = 3;
	playerStats[9][1] = 4;
	playerStats[9][2] = 8;
}

void initPositions(int half) {
	if (team() == half) { // left team (x in [0, 64])
		// better shooters to nearer to center
		if (playerStats[id][2] > 5) {
			pos[0] = (rand() % 21) + 43; // [43, 63]
			pos[1] = (rand() % 21) + 22; // [22, 42]
		} else {
			pos[0] = (rand() % 31) + 10; // [10, 40]
			pos[1] = rand() % 65; // [0, 64]
		}
	} else { // right team (x in [64, 128])
		// better shooters to nearer to center
		if (playerStats[id][2] > 5) {
			pos[0] = (rand() % 21) + 65; // [65, 85]
			pos[1] = (rand() % 21) + 22; // [22, 42]
		} else {
			pos[0] = (rand() % 31) + 88; // [88, 118]
			pos[1] = rand() % 65; // [0, 64]
		}
	}
}

bool isField() {
	if (id == FIELD0 || id == FIELD1) {
		return true;
	}
	return false;
}

bool isPlayer() {
	if (id != FIELD0 && id != FIELD1) {
		return true;
	}
	return false;
}

// assumption: 0 <= id <= 9
int team() {
	if (id < 5) {
		return 0;
	}
	return 1;
}

bool atBall() {
	if (pos[0] == ballPos[0] && pos[1] == ballPos[1]) {
		return true;
	}
	return false;
}

bool isFieldWithBall() {
	return (id == fieldWithBall);
}

basketball-training.cpp

#include <mpi.h>
#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

const int NUMPROCS = 12;
const int FIELD0 = 10; // (0,0)  -> (64,64)
const int FIELD1 = 11; // (65,0) -> (128,64)
const int ROUNDS = 1;

struct PlayerBallChallenge {
	int player;
	int ballChallenge;
};

void initPositions(int half, int rank, int playerStats[12][3], int pos[2]);
void initPlayerStats(int playerStats[12][3]);
bool isField(int rank);
bool isPlayer(int rank);
int team(int rank);
bool atBall(int pos[2], int ballPos[2]);
int ballChallenge[2]; // [player, ball challenge]
PlayerBallChallenge currBallChallengeWinner;
int ballChallenges[10][2], ballChallengeReqFlag;
MPI_Request ballChallengeReqs[10];
vector<PlayerBallChallenge> playersAtBall;
int tmpBallChallenge[2];
int stoppedRunning[10];
MPI_Request stoppedRunningNotifications[10], stopRoundNotification;

int main() {
	// MPI communication tags
	const int TAG_BALL_LOC = 0; // to request for ball location
	const int TAG_AT_BALL = 1; // to notify field player is on ball
	const int TAG_REACHED_MAX_DIST_RUN = 2; // notify field a player has run 10 feet for that found already
	const int TAG_STOP_ROUND = 3; // field notifies players that a round will stop

	int numprocs, rank;
	int playerStats[12][3]; // players will be [0,4], [5,9]
	int pos[2],   // position of self
		dist,     // dist points available
		distRan,  // dist a player ran
		distToRun; // dist to run in 1 direction
	int ballPos[2];
	int ballIn; // 0|1 (using const FIELD0 or FIELD1)
	int tmpNull; // used as a "null" buffer
	int winner;

	MPI_Init(NULL, NULL);
	MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);

	if (numprocs != NUMPROCS) {
		cout << "Please run with " << NUMPROCS << " processes" << endl;
		MPI_Finalize();
		return 0;
	}

	srand(time(NULL) + rank);

	// init player stats
	initPlayerStats(playerStats);
	// - verify correct stats
	if (isPlayer(rank)) {
		if (playerStats[rank][0] < 1 || playerStats[rank][0] > 10
			|| playerStats[rank][1] < 1 || playerStats[rank][1] > 10
			|| playerStats[rank][2] < 1 || playerStats[rank][2] > 10) {
			cout << "Constraint not met: player " << rank << " has a stat not in [1,10]" << endl;
		}
		if (playerStats[rank][0] + playerStats[rank][1] + playerStats[rank][2] != 15) {
			cout << "Constraint not met: player " << rank << " has sum of stats != 15" << endl;
		}
	}

	// init initial ball position in middle
	if (rank == FIELD0) {
		ballPos[0] = 64;
		ballPos[1] = 32;
	}
	ballIn = FIELD0;

	for (int half = 0; half < 2; half++) {
		// init players starting positions
		initPositions(half, rank, playerStats, pos);

		for (int round = 0; round < ROUNDS; round++) {
			// clear variables
			playersAtBall.clear();
			int numPlayersAtMaxDist = 0; // numbers of players who completed running 10 feet this roundn
			int stopRound = 0;

			// captains determine location of ball
			if (isField(rank) && ballIn == rank) {
				// send ball position info to players
				// will send (-1, -1) if the ball is not in its area
				for (int i = 0; i < 10; i++) {
					MPI_Send(&ballPos, 2, MPI_INT, i, TAG_BALL_LOC, MPI_COMM_WORLD);
				}
				cout << "ball is at " << ballPos[0] << " " << ballPos[1] << endl;
			} else if (isPlayer(rank)) {
				// players get ball position from ballIn field process
				MPI_Recv(&ballPos, 2, MPI_INT, ballIn, TAG_BALL_LOC, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
			} 

			winner = -1;
			distRan = 0;
			// prevent other field from doing infinite loop here
			if (isField(rank) && rank != ballIn) {
				distRan = 10;
			}
			while (winner == -1 && distRan < 10) {
				if (isPlayer(rank)) {
					cout << "starting to run " << rank << " " << distRan << endl;
					// players start running towards ball
					dist = (rand() % playerStats[rank][0]) + 1;

					// - ensure max distRan is 10
					if (distRan + dist > 10) {
						if (distRan < 10) {
							dist = 10 - distRan;
						} else {
							dist = 0;
						}
					}

					if (rank == 0) { // debug
						cout << rank << "dist changed to " << dist << endl;
					}

					// - start in x direction
					distToRun = min(abs(ballPos[0] - pos[0]), dist);
					if (ballPos[0] > pos[0]) { // ball is on left
						pos[0] += distToRun;
						if (rank == 0) { // debug
							//cout << "running to left" << endl;
						}
					} else if (ballPos[0] < pos[0]) {
						pos[0] -= distToRun;
						if (rank == 0) { // debug
							//cout << "running to right" << endl;
						}
					}
					distRan += distToRun;

					// - then in y
					distToRun = min(abs(ballPos[1] - pos[1]), dist - distToRun);
					if (ballPos[1] > pos[1]) { // ball is on top
						pos[1] += distToRun;
						if (rank == 0) { // debug
							//cout << "running to top" << endl;
						}
					} else if (ballPos[1] < pos[1]) {
						pos[1] -= distToRun;
						if (rank == 0) { // debug
							//cout << "running to bottom" << endl;
						}
					}
					distRan += distToRun;
					if (rank == 0) {
						//cout << "player " << rank << " is at " << pos[0] << " " << pos[1] << " moved " << distRan << endl;
					}
 				}
				
				if (rank == ballIn) {
					// field, ballIn, start listening to players ball challenge 
					for (int i = 0; i < 10; i++) {
						MPI_Irecv(&ballChallenges[i], 2, MPI_INT, i, TAG_AT_BALL, MPI_COMM_WORLD, &ballChallengeReqs[i]);
					}
				} else if (isPlayer(rank)) {
					if (atBall(pos, ballPos)) {
						// notify field process player location
						tmpBallChallenge[0] = rank;
						tmpBallChallenge[1] = ((rand() % 10) + 1) * playerStats[rank][1];
						MPI_Send(&tmpBallChallenge, 2, MPI_INT, ballIn, TAG_AT_BALL, MPI_COMM_WORLD);
					}
				}

				if (rank == ballIn) {
					//cout << "b4 at ball test" << endl;
					// test/determine who is at ball
					for (int i = 0; i < 10; i++) {
						MPI_Test(&ballChallengeReqs[i], &ballChallengeReqFlag, MPI_STATUS_IGNORE);
						if (ballChallengeReqFlag == 1) { // i is at ball
							// push to playersAtBall
							PlayerBallChallenge challenge = { ballChallenges[i][0], ballChallenges[i][1] };
							playersAtBall.push_back(challenge);
						} else {
							// cancel the request
							MPI_Cancel(&ballChallengeReqs[i]);
						}
					}

					// do ball challenge for those at ball
					currBallChallengeWinner.player = -1;
					currBallChallengeWinner.ballChallenge = -1;

					for (int i = 0; i < playersAtBall.size(); i++) {
						if (playersAtBall.at(i).ballChallenge > currBallChallengeWinner.ballChallenge) {
							// better ball challenge
							currBallChallengeWinner = playersAtBall.at(i);
						} else if (playersAtBall.at(i).ballChallenge == currBallChallengeWinner.ballChallenge) {
							// tie 
							if (rand() % 2 > 0) { // if rand (0 - 1) == 1, then change currBallChallengeWinner
								currBallChallengeWinner = playersAtBall.at(i);
							}
						}
					}
					winner = currBallChallengeWinner.player;
					cout << "winner is " << winner << endl;
				} // if rank is ballIn
			} // while no winner
			
			if (rank == ba llIn) {
				cout << "winner is: " << winner << endl;
			}
			cout << "b4 cleanup " << endl;
			if (isPlayer(rank)) {
				
				MPI_Cancel(&stopRoundNotification);
			}

			cout << "end round " << round << endl;
		}
		cout << "end half " << half << endl;
	}

	cout << "b4 finalize" << endl;

	MPI_Finalize();
	return 0;
}

void initPlayerStats(int playerStats[12][3]) {
	// in 2nd dimention, 
	// - 0: speed
	// - 1: dribbling
	// - 2: shooting
	playerStats[0][0] = 6;
	playerStats[0][1] = 6;
	playerStats[0][2] = 3;

	playerStats[1][0] = 5; 
	playerStats[1][1] = 5;
	playerStats[1][2] = 5;

	playerStats[2][0] = 7; 
	playerStats[2][1] = 5;
	playerStats[2][2] = 3;

	playerStats[3][0] = 4;
	playerStats[3][1] = 4;
	playerStats[3][2] = 7;

	playerStats[4][0] = 5;
	playerStats[4][1] = 4;
	playerStats[4][2] = 6;

	playerStats[5][0] = 5;
	playerStats[5][1] = 7;
	playerStats[5][2] = 3;

	playerStats[6][0] = 4;
	playerStats[6][1] = 5;
	playerStats[6][2] = 6;

	playerStats[7][0] = 8;
	playerStats[7][1] = 3;
	playerStats[7][2] = 4;

	playerStats[8][0] = 5;
	playerStats[8][1] = 7;
	playerStats[8][2] = 3;

	playerStats[9][0] = 3;
	playerStats[9][1] = 4;
	playerStats[9][2] = 8;
}

void initPositions(int half, int rank, int playerStats[12][3], int pos[2]) {
	if (team(rank) == half) { // left team (x in [0, 64])
		// better shooters to nearer to center
		if (playerStats[rank][2] > 5) {
			pos[0] = (rand() % 21) + 43; // [43, 63]
			pos[1] = (rand() % 21) + 22; // [22, 42]
		} else {
			pos[0] = (rand() % 31) + 10; // [10, 40]
			pos[1] = rand() % 65; // [0, 64]
		}
	} else { // right team (x in [64, 128])
		// better shooters to nearer to center
		if (playerStats[rank][2] > 5) {
			pos[0] = (rand() % 21) + 65; // [65, 85]
			pos[1] = (rand() % 21) + 22; // [22, 42]
		} else {
			pos[0] = (rand() % 31) + 88; // [88, 118]
			pos[1] = rand() % 65; // [0, 64]
		}
	}
}

bool isField(int rank) {
	if (rank == FIELD0 || rank == FIELD1) {
		return true;
	}
	return false;
}

bool isPlayer(int rank) {
	if (rank != FIELD0 && rank != FIELD1) {
		return true;
	}
	return false;
}

// assumption: 0 <= rank <= 9
int team(int rank) {
	if (rank < 5) {
		return 0;
	}
	return 1;
}

bool atBall(int pos[2], int ballPos[2]) {
	if (pos[0] == ballPos[0] && pos[1] == ballPos[1]) {
		return true;
	}
	return false;
}