A8 - Multiplayer Game

1000 points

Online games have evolved over the past decades from simple multiplayer games such as Counter Strike 1.6 to entire metaverse environments such as GTA V Online . Multiplayer games have forever revolutionized entertainment and stand today as one of the most significant areas of distributed system innovation.

Designing a multiplayer game requires several areas of expertise, ranging from graphics design to physics realism. In this course, we focus on the networking challenges encountered in developing an online game.

---

Assignment

Your task is to develop a multiplayer game, focusing on the networking challenges of game development. For this, you must use Python with the regular lab environment. However, you may use third-party libraries such as PyGame for handling the graphical user interface and keyboard input.

To qualify for passing the assignment and obtaining the 1000 points, we require a sufficiently complex game. However, your focus should go towards the networking challenges of online gaming, not the graphics or game mechanics.

Games with a simple user interface and basic graphics are allowed if the game mechanics and networking capabilities are complex. Please refer to the Requirements section for detailed descriptions of required capabilities.

After you are done implementing your game, you must write a game documentation in a README.md file, describing the implementation details of each requirement, challenges encountered, and trade-offs considered. Additionally, your document must include installation instructions for the game. We expect you to use tools such as Python Build or Conda Build to create a release of the game.

Finally, we expect you to demo the game with a 2-5 minute video. Upload your video to a media sharing platform and include the link in your README.md documentation.

Live game demos

Teams that submit impressive games, that exceed our expectations in terms of networking requirements, but also graphics and game mechanics, will be granted the opportunity to present their work in front of a larger audience during our last lecture of the course.

Please let us know in advance if you would like to present your game during the final lecture.

---

Requirements

To qualify as a sufficiently complex game, your assignment must follow a list of strict networking and algorithmic requirements. We identify three classes of requirements your game must follow: protocol, connection handling, and algorithmic considerations. Carefully examine the requirements below when designing your idea and ensure that your game specification satisfies all criteria.

Generally, real-time games are better suited for the list of requirements below compared to turn-based games. We recommend designing the first; however, turn-based games may be allowed under certain circumstances. Please consult a teaching assistant about the implications of this model.

We recognize that the list of requirements might be limiting in terms of the variety of games that would be considered complex enough. If you have a game idea that does not meet some of the presented requirements, but introduces other advanced networking features, consider consulting one of our teaching assistants and submitting a game plan.

Protocol

Online games are a class of networking applications that prioritize latency over reliable transmission. To fulfill this, most online games utilize UDP as the transport layer protocol.

Several approaches to handling connections exist; however, for the purposes of this assignment, we define a clear pathway for you to follow. Your game implementation must follow all of the following requirements for handling connections.

1. Transport Layer Protocol The game must utilize UDP as the transport layer protocol for handling connections.

2. Peer-to-Peer Connections The game must be fully peer-to-peer, with the ability to recover from one of the clients disconnecting. Specifically, you are not allowed to use a central server for dispatching packets to connected players for synchronization.

3. Local Area Discovery Your game should present an interface that scans the local area network for players ready to play and provide a method to invite the players to a party. We do not require your game to handle connections outside the LAN. Hint: It might be useful to look into netcat and port scanning.
4. Party Size Your game design should facilitate more than two connections at the same time. Namely, $\text{party size} \ge 3$ is a hard requirement for your game. You will need to choose a game idea that benefits from larger party sizes; games that are designed for two players only will not suffice. Counter-examples: Pong, chess, checkers, tic-tac-toe, and Connect 4.

VU-Campusnet LAN issues

The VU-Campusnet network will usually block UDP connections and place different devices on completely different LANs. Therefore, we recommend using a mobile hotspot to serve your different devices with a common LAN.

Note: If you decide to use a mobile hotspot, make sure you take the necessary precautions to prevent excessive bandwidth usage. Your game should not require access to the outside network, but rather just the LAN that the hotspot provides.

Connection handling

Once your players have established a peer-to-peer connection, the game state must be handled between all players considering the fact that real-world connections are not always as reliable as a LAN. Additionally, you should consider network efficiency when designing your game, even if your game idea does not entail a competitive aspect. Ensure that your game is latency-friendly in the way it transmits packets over the network.

Your game must implement all of the following requirements when sending data between peers.

1. Ping Tracking Your game should keep track of the ping of all connected players and display this information in a specific menu.

2. Packet Loss Your game must deal with packet loss by either implementing retransmissions based on sequence numbers or by implementing redundant packet sending. Implementing retransmissions should follow the TCP model, simplified for the latency-sensitive nature of the game (i.e., you should not have to implement the entire TCP state machine). Redundant packet sending implies transmitting a window size of data packets at each synchronization step instead of a single packet. If some packets $n \le \text{window size}$ are lost, the game can simply display the lost packets in quick succession to recover.

3. Delta Compressions When transmitting game state over the network, it is often wasteful to send the entire range of data, when the difference between two states is minimal. For example, think of handling positions in an open-world game: position variables might range the entire 4 byte integer limit, but if the player can move at a fixed speed of $\le 255$ units of space per time unit, it would be beneficial to transmit only 1 byte of data representing the difference between the previous and current positions. Your game must implement delta compression in game state transmission whenever possible, with periodic full state (synchronization) transmissions in the case of packet loss.

4. Binary Protocol Your game must transmit packets in a pre-defined binary protocol. The game state must be encoded in binary format, with clearly defined values for different fields. To differentiate between packets, you will need to define a delimiting method. Note: When defining your protocol, it is essential not to embed any assumptions into it (e.g., the position field will never reach the value 0xB00F00AA therefore we can use these bytes for delimiting the packets).

Algorithmic considerations

Multiplayer games need several algorithmic systems to handle real-world networking challenges. These requirements help improve gameplay smoothness, reduce unfair advantages from lag, and avoid sending unnecessary data.

Your game should implement the following algorithmic considerations in its design. When picking your game idea, consider whether the real-time aspect of the game applies to these algorithms.

1. Dead Reckoning Your game should simulate game states in between updates from other peers to facilitate a smoother experience (in terms of visible frame rate) and reduce network load. For example, instead of sending state packets every 4 milliseconds, consider synchronizing every 30 milliseconds and applying dead reckoning. For example, player positions might be updated without receiving any new packets based on the current velocity and direction of movement.

2. Ping Arbitration Almost all games should include a win condition, which may be affected by the different pings players have. Implement an algorithm that fairly arbitrates ping-based interactions, without reducing the overall gameplay experience. For example, in the case of a racing game, you might choose to implement a 150 millisecond window for crossing the finish line and compare the time it took to cross the finish line within the 150 millisecond window proportionally to the ping each player has.

3. Interest Management In most games, not all player interactions matter to all other players. Implement an algorithm that keeps track of which players should receive packet updates from which other players, and refrain from sending redundant updates to uninterested parties. This may include players that are not currently visible on the screen or players that have already completed the current state of the game.

---

Game plan

Before getting started with your game, you are encouraged to consult a teaching assistant regarding your game idea; you do so through a game plan. A game plan is a PDF document describing the following:

• A general description of your game idea.

• The game mechanics and their network applicability.

• A list of requirements the game will follow, usually larger than or equal to the requirements set provided.
• An intuition of the implementation details in regard to the system requirements.

Submitting a game plan is not mandatory, but it greatly increases your chances of having your game submission approved. If a teaching assistant approves your game plan, you can be sure that your game will be rewarded with 1000 points once implemented, given that everything described in the plan matches the final product.

Submitting your game without a game plan constitutes a risk taken; we do not guarantee that a game that does not meet all requirements will be approved. However, omitting the game plan might save you a lot of time, given the sheer size of the assignment. Carefully analyze the trade-offs between submitting and not submitting a game plan.

If you decide to include only a subset of the mandatory requirements, having your game plan approved by a teaching assistant is mandatory.