saiam@333: \documentclass[a4paper,12pt]{article}
saiam@238: 
saiam@238: \usepackage[utf8]{inputenc}
saiam@238: \usepackage[english]{babel}
saiam@331: \usepackage{amsmath}
ekku@349: \usepackage[pdftex]{graphicx}
saiam@238: \usepackage{listings} % For listing code
saiam@238: 
saiam@238: % Fancy headers
saiam@238: \usepackage{fancyhdr}
saiam@238: \fancypagestyle{plain} {
saiam@238:     \fancyhf{}
saiam@238:     \renewcommand{\headrulewidth}{0.4pt}
saiam@238:     \lhead{\textbf{Group 66}}
ekku@364:     \chead{\textbf{Kishna Glista - Liero clone}}
saiam@238:     \rhead{\textsl{AS-0.1102}}
saiam@238:     \cfoot{\thepage}
saiam@238: }
saiam@238: \pagestyle{plain}
saiam@238: 
saiam@238: % Paragraph formatting
saiam@238: \frenchspacing
saiam@238: \setlength{\parindent}{0pt} 
saiam@238: \setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}
saiam@238: 
saiam@238: % Title information
saiam@356: \title{Kishna Glista - Liero Clone\\Project Documentation}
saiam@238: \author{\normalsize{\begin{tabular}{lll}
saiam@238: Atle Kivelä & 79171V & atle.kivela@tkk.fi \\
ekku@269: Eric Malmi & 80351A & eric.malmi@tkk.fi \\
terom@344: Tero Marttila & 79849E & tjmartti@cc.hut.fi \\
terom@344: Marko Rasa & 78726L & morasa@cc.hut.fi \\
saiam@238: \end{tabular}}}
saiam@238: 
saiam@238: % The document begins
saiam@238: \begin{document}
saiam@356: \begin{titlepage}
saiam@238: \maketitle
saiam@356: \thispagestyle{empty}
saiam@356: \end{titlepage}
saiam@356: 
saiam@356: \tableofcontents
saiam@356: \newpage
saiam@238: 
saiam@238: \section{Instructions for compiling and use}
saiam@293: 
terom@344: \subsection{Configuring CMake}
terom@344: You must first generate the project's CMake configuration inside of \textsl{build}. A simple script is provided to do
terom@344: so with some default settings. It will configure the install path as \textsl{~/opt}.
terom@344: 
saiam@293: \begin{itemize}
saiam@293: \item \textsl{cd build}
saiam@293: \item \textsl{./mkcmake.sh}
terom@344: \end{itemize}
terom@344: 
terom@344: \subsection{Compiling and Installing}
terom@344: Once you have the CMake scripts in place, compiling should be as simple as running make:
terom@344: \begin{itemize}
terom@344: \item \textsl{make}
saiam@293: \item \textsl{make install}
saiam@293: \end{itemize}
saiam@293: 
terom@344: This will build the binary, and then copy the binary and data files to the install path configured above.
saiam@293: 
terom@344: \subsection{Command-line Arguments}
terom@344: Running the game is done using command-line arguments to the executable
terom@344: \begin{center}
terom@344: \begin{tabular}{l|l|l|l|l}
terom@344: \textbf{Short} & \textbf{Long} & \textbf{Value} & \textbf{Description} & \textbf{Default} \\
terom@344: \hline
terom@344: -p & \verb|--port| & PORT & Set server TCP/UDP port & 9338 \\
terom@344: -s & \verb|--server| &  & Run as a network server & false \\
terom@344: -c & \verb|--client| & SERVERHOST & Run as a network client on given server & false \\
terom@344: -g & \verb|--graphics| & & Enable graphics rendering & * \\
terom@344: \end{tabular}
terom@344: \end{center}
terom@344: 
terom@344: * = true, except false when --server is given
terom@344: 
terom@344: The options \verb|--server| and \verb|--client| are mutually exclusive, and both cannot be selected at the same time.
terom@344: 
terom@344: \subsection{Keyboard Controls}
terom@344: The default controls are identical to the origional Liero default controls, with some additions.
terom@344: 
saiam@293: \begin{center}
saiam@293: \begin{tabular}{l|l}
saiam@293: \textbf{Action} & \textbf{Default key(s)} \\
saiam@293: \hline
terom@344: Move Left & Arrow Left \\
terom@344: Move Right & Arrow Right \\
terom@344: Aim Up & Arrow Up \\
terom@344: Aim Down & Arror Down \\
terom@344: Dig & Move Left + Move Right \\
terom@344: Shoot & Right Control \\
terom@344: Jump & Right Shift \\
terom@344: Change Weapon & Enter + Arrow Left / Arrow Right \\
terom@344: Throw Rope & Change Weapon + Jump \\
terom@344: Release Rope & Jump \\
terom@344: Change Rope Length & Change Weapon + Aim Up / Aim Down \\
terom@344: Suicide & Left Control + K \\
terom@344: Exit Game & Esc \\
saiam@293: \end{tabular}
saiam@293: \end{center}
saiam@293: 
terom@344: \subsection{Running the game}
saiam@347: To simple start a local singleplayer game, just run \verb|kg| without any arguments.
terom@344: 
saiam@347: To start a network server on the default port, run \verb|kg --server|
saiam@347: (\verb|kg -s|). You may optionally also specify the \verb|--graphics|
saiam@347: argument to have the server passively draw the graphics.
terom@344: 
saiam@347: To start a network client, connecting to a server running on the
saiam@347: default port, run \verb|kg --client=ADDRESS| (\verb|kg -c <address>|).
terom@344: 
saiam@347: To use a non-default port, simply specify \verb|--port=PORT|
saiam@347: (\verb|-p <port>|) on both client and server.
saiam@293: 
saiam@238: \subsection{Configuration}
saiam@347: All global game constants are defined in \textit{src/Config.hh}, and may be
saiam@347: experimented with. Weapon parameters are defined in \textit{src/Weapons.cc}.
saiam@238: 
saiam@238: \section{Program architecture}
saiam@348: The program consists of four main parts: Graphics\&Input, GameState,
terom@352: Network and Physics. Each part contains various classes; the relations
saiam@348: show up in the doxygen generated documentation of the program.
terom@344: 
terom@352: The program starts from the Application class, which then starts the Engine,
terom@352: which creates GameState, Graphics and the Network Client/Server. Physics
terom@352: simulation is started when GameState is created.
saiam@347: 
saiam@348: GameState contains PhysicsWorld which inherits from Terrain and
saiam@348: contains a list of PhysicsObjects. GameState also contains Player and
saiam@348: Projectile objects which inherit from PhysicsObject (and are contained
saiam@348: in PhysicsWorld).
terom@344: 
saiam@348: Player objects have a list of Weapon objects which they can use to
saiam@348: create Projectiles. Every Player also has a Rope object, which is a
saiam@348: separate PhysicsObject, and is either folded away, being thrown or
saiam@348: attached to the terrain.
terom@344: 
terom@352: Graphics and Input are handled in their own classes. Graphics has an
saiam@348: Input object which contains InputHandler objects for various classes
saiam@348: of input. One such object is PlayerInput which affects the GameState's
saiam@348: LocalPlayer. Other object is GuiInput which just modifies what the GUI
saiam@348: look like on the client side.
saiam@348: 
saiam@350: The network code is a bit complicated and has several layers. There
saiam@350: are some nice diagrams about the program structure in the doxygen
saiam@350: documentation.
saiam@278: 
terom@362: \begin{figure}[!ht]
terom@362:  \centering \includegraphics[width=\textwidth]{images/class_Player_inherit_graph.png}
terom@362:  \caption{Player class inheritance graph. \label{class_Player_inheritance}}
terom@362: \end{figure}
terom@362: 
terom@362: \begin{figure}[!ht]
ekku@363:  \centering \includegraphics[width=0.6\textwidth]{images/class_GameState_collaboration_graph.png}
terom@362:  \caption{Relationships of core GameState class. \label{class_GameState_collaboration}}
terom@362: \end{figure}
terom@362: 
ekku@361: \subsection{Network}
ekku@361: 
ekku@361: The network code is implemented as separate NetworkServer and NetworkClient modules, which use a common high-level
ekku@361: network interface, NetworkSession and NetworkObject.
ekku@361: 
ekku@361: The low-level details are implemented using ClanLib's CL\_IPAddress (referred to as NetworkAddress) and CL\_Socket.
ekku@361: NetworkUDP provides an interface to send and receive NetworkPackets to/from specific NetworkAddress's across a 
ekku@361: NetworkSocket. NetworkTCP provides a NetworkTCPTransport interface, which can send/receive NetworkPackets on a
ekku@361: NetworkSocket (using NetworkBuffer to buffer socket I/O). NetworkTCPServer is a listen() socket which accepts client
ekku@361: connections as NetworkTCPTransports, and NetworkTCPClient is a NetworkTCPTransport that's connect()'d to some address.
ekku@361: 
ekku@361: NetworkSession encapsulates some simple application server/client behaviour, it can function as both a server, and
ekku@361: represents remote NetworkSessions (either clients or servers) as NetworkNode objects. These then provide an interface
ekku@361: to send and receive NetworkPackets on specific NetworkChannelDs, using either TCP or UDP as a reliable/unreliable
ekku@361: transport.
ekku@361: 
ekku@361: NetworkObject then implements a kind of object-oriented network protocol. A NetworkObjectController (with specific
ekku@361: subclasses for server/client behaviour) uses a NetworkSession to send messages on a specific NetworkChannelID. This
ekku@361: controller then creates and looks up NetworkObjects (again, with specific subclasses for server/client behaviour).
ekku@361: Clients and servers can then communicate by having the server construct new NetworkObjects (which are allocated an
ekku@361: unique id), and then sending NetworkPackets with a specific NetworkMessageID type on a specific object. The message is
ekku@361: then delivered directly to the NetworkObject instance on the remote end of the connection, or a new NetworkObject is
ekku@361: constructed using the data in the NetworkPacket. This enables an easy way to send events for specific objects, and
ekku@361: referr to other objects in these messages.
ekku@361: 
ekku@361: NetworkServer then implements a core NetworkServer class which has a NetworkSession and a
ekku@361: NetworkObject\_ServerController. Players that connect are represented as NetworkServerPlayers, which inherit from
ekku@361: LocalPlayer and NetworkObject\_Server. This class then overrides methods in Player to deliver messages on the Player
ekku@361: object to the clients, or to create new NetworkServerProjectiles. NetworkServerProjectile inherits from Projectile and
ekku@361: NetworkObject\_Server, and sends messages when constructed, upon hitting a player, and upon being destroyed.
ekku@361: 
ekku@361: NetworkClient is a bit more complicated as it must handle both the LocalPlayer, and a number of RemotePlayers. Again,
ekku@361: NetworkClient has a NetworkSession and a specialized NetworkClientController, which then creates objects of various
ekku@361: other NetworkClientClasses upon receiving messages from the server.
ekku@361: 
ekku@361: Two of these classes are NetworkClientLocalPlayer and NetworkClientRemotePlayer. Both inherit from
ekku@361: NetworkClientPlayerBase, which inherits Player (virtually) and NetworkObject\_Client. NetworkClientLocalPlayer and
ekku@361: NetworkClientRemotePlayer then also inherit LocalPlayer and Remote player virtually, respectively.
ekku@361: NetworkClientPlayerBase contains the common methods that update the Player's state in response to messages received
ekku@361: from the server. NetworkClientLocalPlayer overrides handleInput to send the input mask to the server, and
ekku@361: NetworkClientRemotePlayer can handle remote clients disconnecting from the server.
ekku@361: 
ekku@361: In addition, there is a NetworkClientProjectile class, which inherits from Projectile and NetworkObject\_Client.
ekku@361: this is created when a Player fires a Weapon on the server, and handles events received from the server like the
ekku@361: projectile hitting a player (inflicting damage), or being destroyed (by hitting the terrain or something similar).
ekku@361: 
ekku@361: When the player first connects to the server, the server sends a large packet containing the terrain array to the
ekku@361: client, which updates its own GameState world's terrain array with the received data.
ekku@361: 
ekku@361: Currently, the client only sends handleInput using unreliable UDP messages, and the server only sends position updates
ekku@361: (as sent in response to handleInput events) unreliably. All other events are sent using reliable TCP.
ekku@361: 
terom@362: \begin{figure}[!ht]
terom@362:  \centering \includegraphics[width=\textwidth]{images/class_NetworkObject_inherit_graph.png}
terom@362:  \caption{Use of NetworkObject in network code. \label{class_NetworkObject_inherit}}
terom@362: \end{figure}
terom@362: 
ekku@363: \clearpage
ekku@363: 
saiam@238: \section{Data structures and algorithms}
ekku@269: 
saiam@278: \subsection{Basic data structures}
saiam@278: 
saiam@278: \begin{itemize}
saiam@278: \item Vector
saiam@278: \item List
saiam@278: \end{itemize}
saiam@278: 
ekku@269: \subsection{World and Objects}
ekku@269: 
saiam@301: % COMMENT: I think these should be in a very basic level and they
saiam@301: % shouldn't discuss too much about the game itself. The idea is just
saiam@301: % to explain different kinds of structures and algorithms.
ekku@269: 
saiam@301: % Terrain
saiam@301: The terrain is an important part of our game. We represent our terrain
saiam@301: as a large array. Each shell of the array has a type that tells what
saiam@301: is in that position. Currently, possible terrain types are EMPTY, DIRT
saiam@301: and ROCK. 
saiam@301: 
saiam@301: % Usually, in side view 2D-games, the terrain is representated as a
saiam@301: % polygon. This allows us to implement collision detection and
saiam@301: % bouncing rather easily, and it is also a very compact way of storing
saiam@301: % the map. In our opinion Liero, however, is fundamentally a pixel
saiam@301: % based game and therefore we represent the terrain as a large array
saiam@301: % of pixels. These pixels are, however, abstract pixels, i.e. they are
saiam@301: % not necessarily in the same scale than the physical resolution. In
saiam@301: % other words, the server has an abstract resolution, which is the
saiam@301: % same for all clients, and the clients can visualize this abstract
saiam@301: % array of pixels in any resolution they wish.
saiam@301: 
saiam@301: % Objects
saiam@301: In our physics simulation the shapes of the different elements in the
saiam@301: game are represented as polygons. A polygon is a vector of points that
saiam@301: define the edges of the shape.
saiam@301: 
saiam@301: % On top of the terrain, the world also includes a list of all objects
saiam@301: % in it (players, projectiles and ropes). The objects have a polygon
saiam@301: % shape which is used in the collision detection between the objects
saiam@301: % and the terrain and the objects with each other.
ekku@269: 
ekku@269: \subsection{Collision Detection}
ekku@269: 
saiam@278: \begin{itemize}
saiam@278: \item Polygon collision detection
saiam@278: \item Pixel collision detection
saiam@278: \end{itemize}
ekku@269: 
saiam@301: Collision detection algorithms check if objects in the physics
saiam@301: simulation are colliding with eachother. Because our terrain is
saiam@301: represented as an array and objects are represented as polygons we
saiam@301: have two different kinds collision detection algorithms.
saiam@301: 
saiam@301: The pixel based collision detection used to check collisions with the
saiam@301: terrain is quite simple. It ``draws'' a line between two points A and
saiam@301: B. The algorithm iterates over the line from point A to B and on each
saiam@301: iteration it checks if theres a collision (i.e. the type of the
saiam@301: current point is ROCK or DIRT).
saiam@301: 
ekku@357: In order to implement the bouncing from the terrain we have to be able
ekku@357: to calculate a normal for the slope of the terrain in the collision
ekku@357: point. We came up with the following algorithm which gives us an
ekku@357: approximation of the normal
ekku@357: 
ekku@357: \begin{enumerate}
ekku@357:  \item Take the collision point ($p_1$) and the point
ekku@357: before the collision ($p_2$) and consider a 3x3 array of pixels which has the
ekku@357: collision point in the middle of it.
ekku@357:  \item Find the empty points that are connected to $p_2$ with bredth-first search algorithm
ekku@357: or something similar.
ekku@357:  \item Calculate the vectors pointing from the collision point to the empty points. Sum of these vectors gives us the approximation of the normal.
ekku@357: \end{enumerate}
ekku@357: 
ekku@357: Picture \ref{algo} explains the algorithm a lot. In the middle of the pictured we have zoomed to the collision point. The red arrow is the sum of the black arrows and thus it is our approximation for the normal.
ekku@349: 
ekku@349: \begin{figure}[!ht]
terom@362:  \centering \includegraphics[width=0.7\textwidth]{images/normaali_algo.png}
ekku@349:  \caption{Visualizing the algorithm for approximating the normal. \label{algo}}
ekku@349: \end{figure}
ekku@269: 
ekku@269: \subsection{Physics}
saiam@310: 
saiam@310: The fourth-order Runge-Kutta method is a numerical method for
saiam@310: approximating the solution of an ordinary differential equation. In
saiam@310: our game the Runge-Kutta method is used to calculate positions and
saiam@310: velocities of physics objects when we apply forces to them.
saiam@310: 
saiam@331: The mathematical formulation of the Runge-Kutta method:
saiam@331: If we have an initial value problem of the form
saiam@333: \begin{equation*}
saiam@331: y' = f(t, y), \quad y(t_0) = y_0.
saiam@333: \end{equation*}
saiam@331: The we can describe the RK4 method for this problem by equations
saiam@333: \begin{align*}
saiam@331: y_{n+1} &= y_n + \tfrac{1}{6}h\left(k_1 + 2k_2 + 2k_3 + k_4 \right) \\
saiam@331: t_{n+1} &= t_n + h \\
saiam@333: \end{align*}
saiam@331: where $y_{n+1}$ is the RK4 approximation of $y(t_{n+1})$, and
saiam@333: \begin{align*}
saiam@331: k_1 &= f(t_n, y_n) \\
saiam@331: k_2 &= f(t_n + \tfrac{1}{2}h, y_n + \tfrac{1}{2}h k_1) \\
saiam@331: k_3 &= f(t_n + \tfrac{1}{2}h, y_n + \tfrac{1}{2}h k_2) \\
saiam@331: k_4 &= f(t_n + h, y_n + h k_3) \\
saiam@333: \end{align*}
saiam@331: The next value $(y_n+1)$ is determined by the present value $(y_n)$,
saiam@331: the product of the interval $(h)$ and an estimated slope that is
saiam@331: defined as $\frac{1}{6}h\left(k_1+2k_2+2k_3+k_4\right)$.
saiam@310: 
ekku@357: \subsection{Texture generation}
ekku@357: 
ekku@357: In texture generation we use random fractal terrain generation algorithm \cite{fractal}.
ekku@357: In one dimension algorithm starts with one straight line. Then it affects to that
ekku@357: line's midpoint with some random multiplied with H-value. After those first steps
ekku@357: it simply calls itself to both parts of line changing H-value smaller.
ekku@357: 
ekku@357: We use the two dimensional version of the algorithm. It needs step for point's between
ekku@357: last density and step diagonal to last density's points -- otherwise it is quite similar
ekku@357: to the one dimensional version. We decide to implement the algorithm as iterative instead of recursion.
ekku@357: 
terom@352: \subsection{Input}
terom@352: 
terom@352: All input is represented as a bitmask, composed of bits from \textsl{enum PlayerInputBits}. Additionally, the Graphics
terom@352: code uses some local-only flags defined in \textsl{enum GuiInputBits}. These bitmasks are built using the
terom@352: \textsl{InputHandler} class, which is defined as a generic template. On every update, it goes through its keymap,
terom@352: which is defined as an array of InputKeymapEntry structs. These contain the input bit, flags, and up to two keycodes.
terom@352: The InputHandler then reads keycodes from the keyboard and sets bits in the current input mask based on the entry
terom@352: keycodes (which may be negative to indicate the the specified key must NOT be pressed down) and any key-repetition
terom@352: rules defined by flags.
terom@352: 
terom@352: Key repetition is implemented using InputKeyRepeatQueue, which contains a list of InputKeyRepeatEntry's. To rate-limit
terom@352: keypresses, the input code is push()'d to the queue, and it eventually removed from the queue once it expires, or
terom@352: the key is released.
terom@352: 
terom@352: The Graphics code then reads the input mask from time to time, resetting the InputHandler's mask to zero, and passes 
terom@352: it on to LocalPlayer, which then either handles it locally, or sends it to the remote server.
terom@352: 
terom@352: Since some inputs like walking, aiming and moving up and down the rope are time-dependant, the InputHandler also tracks
terom@352: how many milliseconds the input mask has been held, and this time delta is applied by LocalPlayer.
terom@352: 
saiam@238: \section{Known bugs}
saiam@340: \begin{enumerate}
saiam@340: \item If player dies while rope is attached the rope will still be
terom@352:     attached when the player spawns.
nireco@345: \item If rope is thrown without releasing it first, rope will pull worm
terom@355:     while in mid-air
ekku@357: \item Collisions with the terrain are only tested for the vertices
ekku@357:     of the polygon. It is thus possible for the player to move through some pixels.
terom@352: \item Existing Player ropes and Projectiles are not sent to the client when it connects, which can cause apparent
terom@352:     glitches in what the terrain looks like and how players move.
saiam@340: \end{enumerate}
saiam@238: 
saiam@238: \section{Tasks sharing and schedule}
terom@352: We could have followed the schedule a lot better. We basically forgot the whole
terom@352: schedule and had a lapse in activity during the middle weeks, which caused us
terom@352: to be delayed in terms of the schedule. The positive side was that we almost
terom@352: always had all the team members working on their own things in parralel and
terom@352: communicating together; either at Maari or using our IRC channel.
saiam@340: 
saiam@340: Tasks sharing worked pretty much as planned. Tero did all the network
terom@352: code and worked on keeping the rest of the code network-safe. Most of our
terom@352: eye-candy (like terrain textures) was done by Marko, who was responsible for
terom@352: the graphics. Marko, Eric and Atle worked on everything Physics related plus
terom@352: the GameState/Player/Rope/etc code. Most of the time all team members were
terom@352: working together, so the code was written using common agreement.
saiam@340: 
terom@352: We feel that the workload was shared reasonably evenly. % Or does someone disagree with this?
saiam@238: 
saiam@238: \section{Differences to the original plan}
saiam@340: The original plan was quite loose and it let us make decisions during
terom@352: development, which was a good thing. The basic structure of the program is
terom@352: pretty much as the one we thought about while planning, although the Network
terom@352: code ended up being a fair bit more simple-minded due to lack of time to
terom@352: implement more UDP-based behaviour.
saiam@238: 
ekku@361: Currently, the program lacks an AI which was in the original plan and most of the optional features were also omitted. Liero clone proved to be, however, a very interesting software project and we are hoping to release Kishna Glista 2.0 one day.
ekku@361: 
saiam@238: % References
saiam@238: \begin{thebibliography}{99}
ekku@361: \bibitem{gaffer} Gaffer on games. Game Physics. 2006. \\
ekku@361:  http://gafferongames.wordpress.com/game-physics/ (read: 2008-12-08)
ekku@363: \bibitem{fractal} Terrain texture generation \\
ekku@363: http://www.gameprogrammer.com/fractal.html
saiam@238: \end{thebibliography}
saiam@238: 
saiam@238: \end{document}