1

\documentclass[a4paper,12pt]{article}

     2

     3

\usepackage[utf8]{inputenc}

     4

\usepackage[english]{babel}

     5

\usepackage{amsmath}

     6

\usepackage[pdftex]{graphicx}

     7

\usepackage{listings} % For listing code

     8

     9

% Fancy headers

    10

\usepackage{fancyhdr}

    11

\fancypagestyle{plain} {

    12

    \fancyhf{}

    13

    \renewcommand{\headrulewidth}{0.4pt}

    14

    \lhead{\textbf{Group 66}}

    16

    \rhead{\textsl{AS-0.1102}}

    17

    \cfoot{\thepage}

    18

}

    19

\pagestyle{plain}

    20

    21

% Paragraph formatting

    22

\frenchspacing

    23

\setlength{\parindent}{0pt} 

    24

\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}

    25

    26

% Title information

    27

\title{Kishna Glista - Liero Clone\\Project Documentation}

    28

\author{\normalsize{\begin{tabular}{lll}

    29

Atle Kivelä & 79171V & atle.kivela@tkk.fi \\

    30

Eric Malmi & 80351A & eric.malmi@tkk.fi \\

    31

Tero Marttila & 79849E & tjmartti@cc.hut.fi \\

    32

Marko Rasa & 78726L & morasa@cc.hut.fi \\

    33

\end{tabular}}}

    34

    35

% The document begins

    36

\begin{document}

    37

\begin{titlepage}

    38

\maketitle

    39

\thispagestyle{empty}

    40

\end{titlepage}

    41

    42

\tableofcontents

    43

\newpage

    44

    45

\section{Instructions for compiling and use}

    46

    47

\subsection{Configuring CMake}

    48

You must first generate the project's CMake configuration inside of \textsl{build}. A simple script is provided to do

    49

so with some default settings. It will configure the install path as \textsl{~/opt}.

    50

    51

\begin{itemize}

    52

\item \textsl{cd build}

    53

\item \textsl{./mkcmake.sh}

    54

\end{itemize}

    55

    56

\subsection{Compiling and Installing}

    57

Once you have the CMake scripts in place, compiling should be as simple as running make:

    58

\begin{itemize}

    59

\item \textsl{make}

    60

\item \textsl{make install}

    61

\end{itemize}

    62

    63

This will build the binary, and then copy the binary and data files to the install path configured above.

    64

    65

\subsection{Command-line Arguments}

    66

Running the game is done using command-line arguments to the executable

    67

\begin{center}

    68

\begin{tabular}{l|l|l|l|l}

    69

\textbf{Short} & \textbf{Long} & \textbf{Value} & \textbf{Description} & \textbf{Default} \\

    70

\hline

    71

-p & \verb|--port| & PORT & Set server TCP/UDP port & 9338 \\

    72

-s & \verb|--server| &  & Run as a network server & false \\

    73

-c & \verb|--client| & SERVERHOST & Run as a network client on given server & false \\

    74

-g & \verb|--graphics| & & Enable graphics rendering & * \\

    75

\end{tabular}

    76

\end{center}

    77

    78

* = true, except false when --server is given

    79

    80

The options \verb|--server| and \verb|--client| are mutually exclusive, and both cannot be selected at the same time.

    81

    82

\subsection{Keyboard Controls}

    83

The default controls are identical to the origional Liero default controls, with some additions.

    84

    85

\begin{center}

    86

\begin{tabular}{l|l}

    87

\textbf{Action} & \textbf{Default key(s)} \\

    88

\hline

    89

Move Left & Arrow Left \\

    90

Move Right & Arrow Right \\

    91

Aim Up & Arrow Up \\

    92

Aim Down & Arror Down \\

    93

Dig & Move Left + Move Right \\

    94

Shoot & Right Control \\

    95

Jump & Right Shift \\

    96

Change Weapon & Enter + Arrow Left / Arrow Right \\

    97

Throw Rope & Change Weapon + Jump \\

    98

Release Rope & Jump \\

    99

Change Rope Length & Change Weapon + Aim Up / Aim Down \\

   100

Suicide & Left Control + K \\

   101

Exit Game & Esc \\

   102

\end{tabular}

   103

\end{center}

   104

   105

\subsection{Running the game}

   106

To simple start a local singleplayer game, just run \verb|kg| without any arguments.

   107

   108

To start a network server on the default port, run \verb|kg --server|

   109

(\verb|kg -s|). You may optionally also specify the \verb|--graphics|

   110

argument to have the server passively draw the graphics.

   111

   112

To start a network client, connecting to a server running on the

   113

default port, run \verb|kg --client=ADDRESS| (\verb|kg -c <address>|).

   114

   115

To use a non-default port, simply specify \verb|--port=PORT|

   116

(\verb|-p <port>|) on both client and server.

   117

   118

\subsection{Configuration}

   119

All global game constants are defined in \textit{src/Config.hh}, and may be

   120

experimented with. Weapon parameters are defined in \textit{src/Weapons.cc}.

   121

   122

\section{Program architecture}

   123

The program consists of four main parts: Graphics\&Input, GameState,

   124

Network and Physics. Each part contains various classes; the relations

   125

show up in the doxygen generated documentation of the program.

   126

   127

The program starts from the Application class, which then starts the Engine,

   128

which creates GameState, Graphics and the Network Client/Server. Physics

   129

simulation is started when GameState is created.

   130

   131

GameState contains PhysicsWorld which inherits from Terrain and

   132

contains a list of PhysicsObjects. GameState also contains Player and

   133

Projectile objects which inherit from PhysicsObject (and are contained

   134

in PhysicsWorld).

   135

   136

Player objects have a list of Weapon objects which they can use to

   137

create Projectiles. Every Player also has a Rope object, which is a

   138

separate PhysicsObject, and is either folded away, being thrown or

   139

attached to the terrain.

   140

   141

Graphics and Input are handled in their own classes. Graphics has an

   142

Input object which contains InputHandler objects for various classes

   143

of input. One such object is PlayerInput which affects the GameState's

   144

LocalPlayer. Other object is GuiInput which just modifies what the GUI

   145

look like on the client side.

   146

   147

The network code is a bit complicated and has several layers. There

   148

are some nice diagrams about the program structure in the doxygen

   149

documentation.

   150

   151

\begin{figure}[!ht]

   152

 \centering \includegraphics[width=\textwidth]{images/class_Player_inherit_graph.png}

   153

 \caption{Player class inheritance graph. \label{class_Player_inheritance}}

   154

\end{figure}

   155

   156

\begin{figure}[!ht]

   157

 \centering \includegraphics[width=0.6\textwidth]{images/class_GameState_collaboration_graph.png}

   158

 \caption{Relationships of core GameState class. \label{class_GameState_collaboration}}

   159

\end{figure}

   160

   161

\subsection{Network}

   162

   163

The network code is implemented as separate NetworkServer and NetworkClient modules, which use a common high-level

   164

network interface, NetworkSession and NetworkObject.

   165

   166

The low-level details are implemented using ClanLib's CL\_IPAddress (referred to as NetworkAddress) and CL\_Socket.

   167

NetworkUDP provides an interface to send and receive NetworkPackets to/from specific NetworkAddress's across a 

   168

NetworkSocket. NetworkTCP provides a NetworkTCPTransport interface, which can send/receive NetworkPackets on a

   169

NetworkSocket (using NetworkBuffer to buffer socket I/O). NetworkTCPServer is a listen() socket which accepts client

   170

connections as NetworkTCPTransports, and NetworkTCPClient is a NetworkTCPTransport that's connect()'d to some address.

   171

   172

NetworkSession encapsulates some simple application server/client behaviour, it can function as both a server, and

   173

represents remote NetworkSessions (either clients or servers) as NetworkNode objects. These then provide an interface

   174

to send and receive NetworkPackets on specific NetworkChannelDs, using either TCP or UDP as a reliable/unreliable

   175

transport.

   176

   177

NetworkObject then implements a kind of object-oriented network protocol. A NetworkObjectController (with specific

   178

subclasses for server/client behaviour) uses a NetworkSession to send messages on a specific NetworkChannelID. This

   179

controller then creates and looks up NetworkObjects (again, with specific subclasses for server/client behaviour).

   180

Clients and servers can then communicate by having the server construct new NetworkObjects (which are allocated an

   181

unique id), and then sending NetworkPackets with a specific NetworkMessageID type on a specific object. The message is

   182

then delivered directly to the NetworkObject instance on the remote end of the connection, or a new NetworkObject is

   183

constructed using the data in the NetworkPacket. This enables an easy way to send events for specific objects, and

   184

referr to other objects in these messages.

   185

   186

NetworkServer then implements a core NetworkServer class which has a NetworkSession and a

   187

NetworkObject\_ServerController. Players that connect are represented as NetworkServerPlayers, which inherit from

   188

LocalPlayer and NetworkObject\_Server. This class then overrides methods in Player to deliver messages on the Player

   189

object to the clients, or to create new NetworkServerProjectiles. NetworkServerProjectile inherits from Projectile and

   190

NetworkObject\_Server, and sends messages when constructed, upon hitting a player, and upon being destroyed.

   191

   192

NetworkClient is a bit more complicated as it must handle both the LocalPlayer, and a number of RemotePlayers. Again,

   193

NetworkClient has a NetworkSession and a specialized NetworkClientController, which then creates objects of various

   194

other NetworkClientClasses upon receiving messages from the server.

   195

   196

Two of these classes are NetworkClientLocalPlayer and NetworkClientRemotePlayer. Both inherit from

   197

NetworkClientPlayerBase, which inherits Player (virtually) and NetworkObject\_Client. NetworkClientLocalPlayer and

   198

NetworkClientRemotePlayer then also inherit LocalPlayer and Remote player virtually, respectively.

   199

NetworkClientPlayerBase contains the common methods that update the Player's state in response to messages received

   200

from the server. NetworkClientLocalPlayer overrides handleInput to send the input mask to the server, and

   201

NetworkClientRemotePlayer can handle remote clients disconnecting from the server.

   202

   203

In addition, there is a NetworkClientProjectile class, which inherits from Projectile and NetworkObject\_Client.

   204

this is created when a Player fires a Weapon on the server, and handles events received from the server like the

   205

projectile hitting a player (inflicting damage), or being destroyed (by hitting the terrain or something similar).

   206

   207

When the player first connects to the server, the server sends a large packet containing the terrain array to the

   208

client, which updates its own GameState world's terrain array with the received data.

   209

   210

Currently, the client only sends handleInput using unreliable UDP messages, and the server only sends position updates

   211

(as sent in response to handleInput events) unreliably. All other events are sent using reliable TCP.

   212

   213

\begin{figure}[!ht]

   214

 \centering \includegraphics[width=\textwidth]{images/class_NetworkObject_inherit_graph.png}

   215

 \caption{Use of NetworkObject in network code. \label{class_NetworkObject_inherit}}

   216

\end{figure}

   217

   218

\clearpage

   219

   220

\section{Data structures and algorithms}

   221

   222

\subsection{Basic data structures}

   223

   224

\begin{itemize}

   225

\item Vector

   226

\item List

   227

\end{itemize}

   228

   229

\subsection{World and Objects}

   230

   231

% COMMENT: I think these should be in a very basic level and they

   232

% shouldn't discuss too much about the game itself. The idea is just

   233

% to explain different kinds of structures and algorithms.

   234

   235

% Terrain

   236

The terrain is an important part of our game. We represent our terrain

   237

as a large array. Each shell of the array has a type that tells what

   238

is in that position. Currently, possible terrain types are EMPTY, DIRT

   239

and ROCK. 

   240

   241

% Usually, in side view 2D-games, the terrain is representated as a

   242

% polygon. This allows us to implement collision detection and

   243

% bouncing rather easily, and it is also a very compact way of storing

   244

% the map. In our opinion Liero, however, is fundamentally a pixel

   245

% based game and therefore we represent the terrain as a large array

   246

% of pixels. These pixels are, however, abstract pixels, i.e. they are

   247

% not necessarily in the same scale than the physical resolution. In

   248

% other words, the server has an abstract resolution, which is the

   249

% same for all clients, and the clients can visualize this abstract

   250

% array of pixels in any resolution they wish.

   251

   252

% Objects

   253

In our physics simulation the shapes of the different elements in the

   254

game are represented as polygons. A polygon is a vector of points that

   255

define the edges of the shape.

   256

   257

% On top of the terrain, the world also includes a list of all objects

   258

% in it (players, projectiles and ropes). The objects have a polygon

   259

% shape which is used in the collision detection between the objects

   260

% and the terrain and the objects with each other.

   261

   262

\subsection{Collision Detection}

   263

   264

\begin{itemize}

   265

\item Polygon collision detection

   266

\item Pixel collision detection

   267

\end{itemize}

   268

   269

Collision detection algorithms check if objects in the physics

   270

simulation are colliding with eachother. Because our terrain is

   271

represented as an array and objects are represented as polygons we

   272

have two different kinds collision detection algorithms.

   273

   274

The pixel based collision detection used to check collisions with the

   275

terrain is quite simple. It ``draws'' a line between two points A and

   276

B. The algorithm iterates over the line from point A to B and on each

   277

iteration it checks if theres a collision (i.e. the type of the

   278

current point is ROCK or DIRT).

   279

   280

In order to implement the bouncing from the terrain we have to be able

   281

to calculate a normal for the slope of the terrain in the collision

   282

point. We came up with the following algorithm which gives us an

   283

approximation of the normal

   284

   285

\begin{enumerate}

   286

 \item Take the collision point ($p_1$) and the point

   287

before the collision ($p_2$) and consider a 3x3 array of pixels which has the

   288

collision point in the middle of it.

   289

 \item Find the empty points that are connected to $p_2$ with bredth-first search algorithm

   290

or something similar.

   291

 \item Calculate the vectors pointing from the collision point to the empty points. Sum of these vectors gives us the approximation of the normal.

   292

\end{enumerate}

   293

   294

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.

   295

   296

\begin{figure}[!ht]

   297

 \centering \includegraphics[width=0.7\textwidth]{images/normaali_algo.png}

   298

 \caption{Visualizing the algorithm for approximating the normal. \label{algo}}

   299

\end{figure}

   300

   301

\subsection{Physics}

   302

   303

The fourth-order Runge-Kutta method is a numerical method for

   304

approximating the solution of an ordinary differential equation. In

   305

our game the Runge-Kutta method is used to calculate positions and

   306

velocities of physics objects when we apply forces to them.

   307

   308

The mathematical formulation of the Runge-Kutta method:

   309

If we have an initial value problem of the form

   310

\begin{equation*}

   311

y' = f(t, y), \quad y(t_0) = y_0.

   312

\end{equation*}

   313

The we can describe the RK4 method for this problem by equations

   314

\begin{align*}

   315

y_{n+1} &= y_n + \tfrac{1}{6}h\left(k_1 + 2k_2 + 2k_3 + k_4 \right) \\

   316

t_{n+1} &= t_n + h \\

   317

\end{align*}

   318

where $y_{n+1}$ is the RK4 approximation of $y(t_{n+1})$, and

   319

\begin{align*}

   320

k_1 &= f(t_n, y_n) \\

   321

k_2 &= f(t_n + \tfrac{1}{2}h, y_n + \tfrac{1}{2}h k_1) \\

   322

k_3 &= f(t_n + \tfrac{1}{2}h, y_n + \tfrac{1}{2}h k_2) \\

   323

k_4 &= f(t_n + h, y_n + h k_3) \\

   324

\end{align*}

   325

The next value $(y_n+1)$ is determined by the present value $(y_n)$,

   326

the product of the interval $(h)$ and an estimated slope that is

   327

defined as $\frac{1}{6}h\left(k_1+2k_2+2k_3+k_4\right)$.

   328

   329

\subsection{Texture generation}

   330

   331

In texture generation we use random fractal terrain generation algorithm \cite{fractal}.

   332

In one dimension algorithm starts with one straight line. Then it affects to that

   333

line's midpoint with some random multiplied with H-value. After those first steps

   334

it simply calls itself to both parts of line changing H-value smaller.

   335

   336

We use the two dimensional version of the algorithm. It needs step for point's between

   337

last density and step diagonal to last density's points -- otherwise it is quite similar

   338

to the one dimensional version. We decide to implement the algorithm as iterative instead of recursion.

   339

   340

\subsection{Input}

   341

   342

All input is represented as a bitmask, composed of bits from \textsl{enum PlayerInputBits}. Additionally, the Graphics

   343

code uses some local-only flags defined in \textsl{enum GuiInputBits}. These bitmasks are built using the

   344

\textsl{InputHandler} class, which is defined as a generic template. On every update, it goes through its keymap,

   345

which is defined as an array of InputKeymapEntry structs. These contain the input bit, flags, and up to two keycodes.

   346

The InputHandler then reads keycodes from the keyboard and sets bits in the current input mask based on the entry

   347

keycodes (which may be negative to indicate the the specified key must NOT be pressed down) and any key-repetition

   348

rules defined by flags.

   349

   350

Key repetition is implemented using InputKeyRepeatQueue, which contains a list of InputKeyRepeatEntry's. To rate-limit

   351

keypresses, the input code is push()'d to the queue, and it eventually removed from the queue once it expires, or

   352

the key is released.

   353

   354

The Graphics code then reads the input mask from time to time, resetting the InputHandler's mask to zero, and passes 

   355

it on to LocalPlayer, which then either handles it locally, or sends it to the remote server.

   356

   357

Since some inputs like walking, aiming and moving up and down the rope are time-dependant, the InputHandler also tracks

   358

how many milliseconds the input mask has been held, and this time delta is applied by LocalPlayer.

   359

   360

\section{Known bugs}

   361

\begin{enumerate}

   362

\item If player dies while rope is attached the rope will still be

   363

    attached when the player spawns.

   364

\item If rope is thrown without releasing it first, rope will pull worm

   365

    while in mid-air

   366

\item Collisions with the terrain are only tested for the vertices

   367

    of the polygon. It is thus possible for the player to move through some pixels.

   368

\item Existing Player ropes and Projectiles are not sent to the client when it connects, which can cause apparent

   369

    glitches in what the terrain looks like and how players move.

   370

\end{enumerate}

   371

   372

\section{Tasks sharing and schedule}

   373

We could have followed the schedule a lot better. We basically forgot the whole

   374

schedule and had a lapse in activity during the middle weeks, which caused us

   375

to be delayed in terms of the schedule. The positive side was that we almost

   376

always had all the team members working on their own things in parralel and

   377

communicating together; either at Maari or using our IRC channel.

   378

   379

Tasks sharing worked pretty much as planned. Tero did all the network

   380

code and worked on keeping the rest of the code network-safe. Most of our

   381

eye-candy (like terrain textures) was done by Marko, who was responsible for

   382

the graphics. Marko, Eric and Atle worked on everything Physics related plus

   383

the GameState/Player/Rope/etc code. Most of the time all team members were

   384

working together, so the code was written using common agreement.

   385

   386

We feel that the workload was shared reasonably evenly. % Or does someone disagree with this?

   387

   388

\section{Differences to the original plan}

   389

The original plan was quite loose and it let us make decisions during

   390

development, which was a good thing. The basic structure of the program is

   391

pretty much as the one we thought about while planning, although the Network

   392

code ended up being a fair bit more simple-minded due to lack of time to

   393

implement more UDP-based behaviour.

   394

   395

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.

   396

   397

% References

   398

\begin{thebibliography}{99}

   399

\bibitem{gaffer} Gaffer on games. Game Physics. 2006. \\

   400

 http://gafferongames.wordpress.com/game-physics/ (read: 2008-12-08)

   401

\bibitem{fractal} Terrain texture generation \\

   402

http://www.gameprogrammer.com/fractal.html

   403

\end{thebibliography}

   404

   405

\end{document}