Project: Distributed Many in a Row

published on April 7, 2012

Technologies: 
IP Multicast
Python
Qt
Zeroconf
Time range: 
November 2009 to December 2009
As a: 
student

School year: first master year, first semester.

Many in a row: new game dialog Many in a row: in-game screenshot

For the “Distributed Systems” course, we had to build a small project (for 25% of the grades) in teams of 3 to gain deeper understanding of group communication and coordination in distributed systems. The goal was to build a 4-in-a-row game, with the following extensions:

  • variable number of players
  • players don’t’ have to wait for their turn to make a move (!)
  • the first player can choose the dimensions of the board (more than 7 columns is allowed)
  • “4 in a row” doesn’t have to be the endgame, the first player can choose the endgame
  • players can join and leave the game at any time

We had to use multicast (or a simulation of it) and an absolute requirement was that every player would see the exact same board at any given time; hence moves had to be displayed on every board in the same order. Even when there was significant network jitter, our game engine had to be able to cope with this.

Architecture

Our implementation (visualized in the architecture schema above) first built a layered distributed game engine. Each layer was dumb on its own and handled one specific task. We used six layers. The schema should be mostly self-explanatory. Layer 1 was the (unreliable & unordered) messaging layer, and provided zeroconf- and IP multicast-based messaging. Layer 2 was the service layer, which would allow one to advertise a service. Layer 3 provided reliable message delivery and tracked participating hosts (including leaving & joining). Layer 4 provides a very rudimentary basis for building distributed games on top of it, through message-passing only. Layer 5 finally contained the actual game.

This layered approach allowed us to build layer upon layer, to ensure everything in the lower layers was working correctly before working on the next layer.

  • Bully algorithm (to select a coordinator)
  • Zeroconf (for discovery)
  • Multiple games
  • Player/game metadata
  • Chat
  • AI player

If memory serves me correctly, I built the bottom four layers, Brecht Schoolmeesters and Kristof Bamps built the game logic, the AI and the GUI, and made some refinements to my work based on practical experience building the game on top of my infrastructure.

The code is available on GitHub.