Multithreaded Socket Programming
QQ Tang, a Tencent multiplayer bombman game, was one of the most popular online games in China when I was a kid, with millions of players. The core gameplay is simple to learn, yet addicting and has a lot of depth. For the term project of my intro CS course at CMU, I took on the exciting task of remaking this childhood favorite game, and successfully implemented most of its functionality. I only just started programming back then, so the code was messy and many techniques I came up to overcome technical difficulties were hacky. Nevertheless, it was an insanely fun journey, and the one that made me fall in love with coding.
Course and Teammates
Nov - Dec 2015
Top project selected for auditorium presentation
Can support at most 8 players per game across the network
When I was a kid, all my friends played QQ Tang, Tencent's first multiplayer online game. It was arguably the most popular game in China from 2004 to 2007. The core gameplay is simple but addictive - players move around, place bombs, and cooperate with teammates to kill opponents, but the various items, nuanced bomb explosion mechanics, along with the dozen different game modes adds infinite depth and replayability to the game.
For my 15112 Term Project, I remade this multiplayer bombman game. This was my first CS course, and I did not have any experience with multithreaded socket programming, ip addresses, databases, or algorithms such as heartbeats and union find, so I had to look things up and figure out solutions on the way. In the end, I was able to remake the game with more than a dozen maps and characters, and 4 game modes:
Carry the bun: two teams of n players each start out
with a homebase of n buns, and attempt to carry as
many buns as possible from the enemy homebase back
to their own within the time limit. Players carrying the
bun are vulnerable: they move much slower and cannot
place bombs. Thus players must protect teammates
carrying the bun.
Build the tower: two teams of n players each attempt to build a tower of n levels faster than the other team. To build a level, players must find bricks by destroying hero statues, and carry the brick back to their tower. Players carrying the brick are vulnerable: they move much slower and cannot place bombs. However, players can press a button to place the brick on the floor any time to return to normal status.
Collecting treasure: many teams of players try to capture as much treasure as possible. Treasures are hidden in treasure chests, and come in different shapes and point worths. When a player is killed, he will first drop all of his treasure, then all of his items if he runs out of treasure. The team with the largest combined treasure points at the end of the time limit wins.
This mode also features pushable blocks.
Kungfu coliseum: many teams of players compete to show off their skills. The team with the most combined kills at the end of the time limit wins. There are many exclusive items to this mode,
including ones that transform the players into "characters" that have special abilities and an extra life.
The bombs in this game are actually balloons. Each balloon has an
explosion radius determined by the power of the player who placed it,
and a fixed explosion countdown. An explosion will expand gradually in
4 directions, incapacitating all players in the way. What really gives depth
to the explosion system is the linking mechanism. Balloons whose
explosion radius overlap are placed in the same group by the system,
and all balloons in the same group will explode simultaneously,
determined by the first placed balloon in the group. This means two
disconnected groups of balloons with different explosion times might explode
together if an extra ballon is placed, connecting the two groups. Expert gamers
exploit the linking mechanism to place balloons at the last second for unexpected explosion times.
The natural data structure to track explosion groups is union find. When a new balloon is placed, I search in its explosion radius for other balloons, and merge all these balloons into the same group.
Upon explosion, I gradually extend the explosion image in four directions, and check on each frame if any players are caught by the explosion.
The problem is made a bit more difficult because walls/blocks/caverns can block explosion radiuses, and some blocks are movable. Some characters can also kick balloons, which could change the explosion groups and explosion times.
I used the Python BSD socket interface to implement a server-client model. There is a central game server that handles all clients (players). The central game loop is run on the main thread, which maintains a queue of game event updates. The server uses a non-blocking socket with a static IP address and uses the select() call to wait for client messages. The server has a designated thread that listens for new clients. For each new client, the server will fork a new thread to listen from this client, and forward messages received from the client to the main queue. The main thread will then process messages from the queue in order, update the global game state, and send/broadcast updated global game state to the clients. The queue is protected by a read-write lock and the set of clients are protected by a mutex lock.
The main benefit of this central queue model is there is only a single source of truth, maintained by the server main thread. All client actions that can be potentially conflicting are sent to the server for resolution. For example, player 1 might want to move right, but at approximately the same moment player 2 places a balloon that blocks player 1's movement. If player 1 moved before player 2 placed the balloon, player 1 is allowed to move, but if player 2 placed the ballon first, player is not allowed to move. Only the server can be a fair judge of which action came first, and after judging, the server will send messages to tell both players if player 1 was allowed to move.
To alleviate the workload of the server, I used client-side caching, so that player actions that are not potentially conflicting are resolved locally and only sent to the server lazily. For example, if a player picked up an item, the server will not be updated immediately, but only when the player attempts to use the item.
To communicate between client and server, I used UTF-8 encoding and hardcoded my own crude message-passing protocol which uses simple English.
To deal with network failures, the server also broadcasts a heartbeat message every 6 frames, and drops clients whose socket connection is broken. When players are within the game (not in the waiting room), the heartbeat message is embedded within the timer message sent from the server to clients upon each timer tick. Thus I was able to avoid the game crashing when a user's disconnects from the game forcefully or unexpectedly.
There were a lot of user data I needed to store across multiple games, such as user accounts and passwords, and user game records and level. Without knowledge of databases, I resolved to using txt files with self-defined storage format and delimiters (such as "_", which I disallowed in usernames and passwords).
One interesting feature I achieved with this storage model was the replay feature, where players can choose games to record and replay later. Since each game can be unique represented by user actions, and user actions all go through the server queue, for each recorded game I saved all messages that enter the server queue to a txt file (along with the map id and user accounts). When replaying the game, I simply read the messages from the file into the queue for the server to process in order, instead of listening for client messages through sockets.
Various other features
For walking and bubble animations, I switched between various images upon timer ticks. For sound effects, I found friends to voice the character reactions when killed by enemies or saved by teammates. There was a naive rolling in-game chat. Within the waiting room before entering a game, users could pick characters (each with varying abilities), switch teams (represented by color), see the game records of other players, and pick cool outfits to decorate their bubbles and characters, such as the wings and purple bubbles in the bottom right gif. The host of the waiting room has special privileges such as blocking positions in the room and kicking out players.
There were a dozen different in-game items with weighted random drop rates to enhance the gameplay. For example, can be placed on the ground, and the first player to step on it will slide all the way to the next wall, block or balloon (very useful when carrying buns); will slow the player upon stepping upon it, and can be thrown in any direction and cause the first balloon hit to explode on impact.
There are also a few items that will cause players to transform into special characters with special abilities. For example, can kick balloons in any direction, while can make herself transparent and harder for other players to see.
For best user experience, I used Py2app to package the client side code and images into a downloadable zip file, and users could download and play my game without needing to install python or pygame.
Finally, one type of terrain I had difficulty implementing was the cavern, which is neither a destroyable block, nor an empty tile. Similar to blocks, the cavern could sever explosion groups and stop explosions, yet unlike blocks, caverns are valid locations for players to be on and can hide players. I ended up letting blocks, caverns and empty tiles all inherit from the tile class and implement canOccupy(), canHide(), canSeverExplosion(), and canExplode() differently.
After three weeks of intense coding, 7000 lines of python, and many rounds of testing with my friends, I was able to polish the multiplayer experience to be both smooth and fun, with little lag (though my mac roars when acting as a server to supporting 8 players).
My project was chosen as one of the best projects among more than 300 student projects, and picked in the annual showcase to present in CMU's McConomy Auditorium. In my presentation, I invited one friend of mine, 5 random members of the audience, along with my Professor Mark Stehlik to play a game of Carry the bun with me. Unfortunately, my friend, who was an expert at the game and back in his dorm room, did not know Mark was playing, and managed to kill his professor about 5 times within 2 minutes. It was quite a special experience.
Looking back at this game, it was the first major CS project I wrote, and naive in most aspects. Among other failures, I had terrible style, used poor object oriented design, did not fully understand thread-safety or locking, and failed to use a proper database. However, it was also an insanely fun and unforgettable experience, not only because this was my favorite childhood game, but also because I enjoyed every moment of encountering a difficult problem, breaking it down into small steps, and thinking of ingenuous approaches to tackle each step. This was the first step of a long journey I was to embark on.