Updates:

07.11.13: Additional return instructions and fixed link to paper + QIII unlagged link
20.11.13: Virtual machine instructions
21.11.13: Virtual machine instructions revised
22.11.13: Two different ways to use the virtual machines and additional notes for using it. Moved virtual machine instructions to page bottom.
22.11.13: Fixed link to Quake III Arena Game Structures paper.
18.11.14: Deadline + 1 week
02.12.14: Added link to Q3/ioquake3 academic articles

Assignment 2 - EXTENDED DEADLINE 9.12.14 @ 10:00 (was 2.12)

This assignment is about understanding others code while analyzing its operation. We've selected two fairly old examples, which are still in development; ioquake3, an open implementation of Id software's Id Tech 3 FPS engine and Freeciv, an open implementation of strategy game Civilization (compatible with Civilization 2).

In this assignment you'll have to look into the sources of both and to answer the questions and to think about the solutions. You are free to use any code analyzing software to help you in this work. Or do it from commandline by searching function usage, e.g., in source root

find * -type f -exec grep -s -n -e "function_call" {} +

Getting the source codes

Source codes of both are publicly available from their source code repositories and many Linux distributions offer them too. The benefit of distribution provided sources are that from these you can build packages that can be easily installed. E.g. with Debian based distributions you can do this by running in the source code root directory:

dpkg-buildpackage -rfakeroot -b -uc

ioquake3

ioquake3 source code is available on many Linux distributions, e.g. on Debian based systems you can get it simply: (no superuser needed)

apt-get source ioquake3

In order to build the code you must install some libraries, with Debian based systems it is easy (as superuser):

apt-get build-dep ioquake3

But because of the licensing issues, in Debian/Ubuntu the zlib library has been removed from the source, it might be more fluent to get the code from the git repository of ioquake3. To do this you'll need to first install git, on Debian based systems (as superuser):

apt-get install git

And then get the code:

git clone https://github.com/ioquake/ioq3.git

This will create a folder ioq3 under the current working directory. The build-dependencies can be installed as for the sources provided by your Linux distribution.

The code complies with plain make when you've installed the build-dependencies. For more details see the README in the git-sources.

Freeciv

Freeciv source code is available on many Linux distributions, e.g. on Debian based systems you can get it simply: (no superuser needed)

apt-get source freeciv

In order to build the code you must install some libraries, with Debian based systems it is easy (as superuser):

apt-get build-dep freeciv

In order to compile the code:

./configure # in this case make runs this too - so not necessary
make

The sources might be outdated in some distributions, therefore, you can get the most recent ones from their SVN:

svn checkout http://svn.gna.org/viewcvs/freeciv/trunk/ freeciv

Install the same dependencies as for the sources provided by your Linux distribution and compile with same instructions.

The assignment tasks

This assignment gives a total of 15 points. In following subsections the different tasks are specified. Some tasks are common for both sources (A. and D.) and some are source specific (B. and C.).

A. Common assignment tasks (6p)

These tasks are to for both sources.

1. The basic networking analysis (2p)

  • How the connection establishment works? Draw a MSC diagram of the connection procedure.
  • How the client activity is being checked at the server?

2. Connection characteristics (2p)

  • How the connection characteristics are checked?
  • What connection characteristics are analyzed/utilized?
  • What kind of optimization techniques are used for packets that are sent?

3. Game states (2p)

  • What the game states sent to clients contain?
  • How these game states are being sent to clients?
  • How are the states being kept synchronized?

B. ioquake3 assignment tasks (4p)

These tasks are for ioquake3 source

1. What is the built in lag in quake3/ioquake3 servers? (1p)

2. How does the countermeasures for UDP spoofing attacks work? (1p)

3. How does the client side prediction work? (2p)

C. Freeciv assignment tasks (2p)

These tasks are for Freeciv source.

1. Turn based communication (1p)

  • How the turn based approach works in Freeciv? How the progression of turns happens?
  • What kind of issues it can have with TCP connections?
  • Draw a MSC diagram of an example situation.

2. Server searching (1p)

  • How does the server searching work in Freeciv?
  • How it differs from the Quake3/ioquake3 approach?

D. Own ideas (3p)

1. How would you implement the lag compensation into ioquake3 sources? (2p)

2. Freeciv into "RTS" (1p)

  • If the Civilization type games were made into RTS (Real Time Strategy) games, where turns happen in real time, what would have to be done for the existing implementation relying on TCP? What restrictions and challenges would it bring?
    • Do not think about the gameplay too much, focus on the networking.

3. Own contribution / bug fix (extra 1-3p)

  • If you notice that something is missing from the sources or you'd like some feature to be enhanced in some direction (or even new feature to be implemented) from the networking point of view additional point(s) can be given.
  • If you clearly see a bug that has not been reported - commit a bug report (or even fix it!) and points will be given.

What sources to look at

To ease the workload, here are some hints you could use while doing this assignment.

ioquake3

The code base is large, over 230k SLOC (Source lines of code) and there is no need to look every single file. The files you need to look at for the tasks:

qcommon/qcommon.h
qcommon/net_chan.c
qcommon/net_ip.c
qcommon/huffman.c
client/cl_net_chan.c
server/sv_client.c
server/sv_net_chan.c
server/sv_snapshot.c

But you probably venture into other files too. The code structures of Quake III Arena are analyzed in a paper by Stefyn et. al. And further info about ioquake3 can be read from their wiki and a list of Q3/ioquake3 academic articles.

Freeciv

common/dataio.c
common/dataio.h
common/connection.c
common/connection.h
common/packets_gen.c
common/packets_gen.h
common/packets.h
client/clinet.c
client/clinet.h
client/packhand.c
client/packhand.h
client/packhand_gen.c
client/packhand_gen.h
client/servers.c
client/servers.h
server/connecthand.c
server/connecthand.h
server/handchat.c
server/handchat.h
server/sernet.c
server/sernet.h
utility/netintf.c
utility/netintf.h

Additional return instructions

In this assignment feel free to use any text editor you like (Word, LibreOffice, LyX, some TeX-editor, etc.) for writing the answers but convert the document into PDF-format before submitting to the SVN. I.e. only PDF-documents are accepted. Pseudocode can be written directly to the answer document but it can be put into separate files too. And of course, if you code something return these as usual.

When you look some other information sources and learn from them (do not copy directly) reference them in your returned assignment (char style[] = “free”). If you use the material that was given on this pages reference them too.

Remember that this is an individual assignment - plagiarism will not be tolerated, all incidents are reported.

Virtual machine usage

There are also virtual Ubuntu images on 4 classroom 6218 computers (lut1813, lut1814, lut1815 and lut1816), where you can install packages and to e.g., sniff traffic of the games by using Wireshark. Details about virtual machine use:

  • Use VirtualBox, from commandline:
    virtualbox
  • The virtual images can be found from
    /opt/VirtualboxVM/protocl\ design\ methods\ with\ games/
  • Option 1
    1. Open the folder with your file manager
    2. Open VirtualBox virtual media manager (File→)
    3. Drag the .vdi -file to VirtualBox virtual media manager and close it
    4. Drag the .vbox -file to VirtualBox main window
    5. Start the Virtual Ubuntu with correct settings
  • Option 2
    1. Create new virtual machine
    2. Set type to Linux and version to Ubuntu
    3. Use an existing virtual hard drive (from /opt/VirtualboxVM/protocl\ design\ methods\ with\ games/)
    4. Create it
    5. Go to Settings→Network and select Bridged adapter for Adapter 1
    6. See on the host machine which physical network adapter (ethX) hasn't got any IP address with
      ifconfig
    7. Select that ethX as physical adapter to use
  • NOTE: the virtual images are writable by all users so changes to it are available for anyone who uses them
    • Additionally, other users can remove the changes - virtual machines are not reliable for storing own data
  • NOTE: if you want to delete the virtual machine always select keep the virtual file image, otherwise it will be deleted from that computer
  • The password will be emailed to all of you
    • the user as sudo rights -you can install required packages to the virtual machine
      • E.g. with
        sudo apt-get install packagename
      • Or via synaptic
      • The changes will be set to that particular virtual machine on that computer
  • Computers are on University DMZ-network - no direct access to e.g. classroom computers (the 4 computers running virtual machines are on the same network)
  • If you need to find a package that has a specific file:
    sudo apt-get install apt-file
    apt-file update
    apt-file search filename
    • A list of packages which have matches will be provided