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}}

    15

    \chead{\textbf{Kishna Glista - liero clone}}

    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

   203

\section{Data structures and algorithms}

   204

   205

\subsection{Basic data structures}

   206

   207

\begin{itemize}

   208

\item Vector

   209

\item List

   210

\end{itemize}

   211

   212

\subsection{World and Objects}

   213

   214

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

   215

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

   216

% to explain different kinds of structures and algorithms.

   217

   218

% Terrain

   219

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

   220

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

   221

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

   222

and ROCK. 

   223

   224

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

   225

% polygon. This allows us to implement collision detection and

   226

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

   227

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

   228

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

   229

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

   230

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

   231

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

   232

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

   233

% array of pixels in any resolution they wish.

   234

   235

% Objects

   236

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

   237

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

   238

define the edges of the shape.

   239

   240

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

   241

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

   242

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

   243

% and the terrain and the objects with each other.

   244

   245

\subsection{Collision Detection}

   246

   247

\begin{itemize}

   248

\item Polygon collision detection

   249

\item Pixel collision detection

   250

\end{itemize}

   251

   252

Collision detection algorithms check if objects in the physics

   253

simulation are colliding with eachother. Because our terrain is

   254

represented as an array and objects are represented as polygons we

   255

have two different kinds collision detection algorithms.

   256

   257

The pixel based collision detection used to check collisions with the

   258

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

   259

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

   260

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

   261

current point is ROCK or DIRT).

   262

   263

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

   264

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

   265

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

   266

approximation of the normal

   267

   268

\begin{enumerate}

   269

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

   270

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

   271

collision point in the middle of it.

   272

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

   273

or something similar.

   274

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

   275

\end{enumerate}

   276

   277

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.

   278

   279

\begin{figure}[!ht]

   280

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

   281

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

   282

\end{figure}

   283

   284

\subsection{Physics}

   285

   286

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

   287

approximating the solution of an ordinary differential equation. In

   288

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

   289

velocities of physics objects when we apply forces to them.

   290

   291

The mathematical formulation of the Runge-Kutta method:

   292

If we have an initial value problem of the form

   293

\begin{equation*}

   294

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

   295

\end{equation*}

   296

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

   297

\begin{align*}

   298

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

   299

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

   300

\end{align*}

   301

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

   302

\begin{align*}

   303

k_1 &= f(t_n, y_n) \\

   304

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

   305

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

   306

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

   307

\end{align*}

   308

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

   309

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

   310

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

   311

   312

\subsection{Texture generation}

   313

   314

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

   315

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

   316

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

   317

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

   318

   319

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

   320

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

   321

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

   322

   323

% TODO: something network related?

   324

   325

\subsection{Input}

   326

   327

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

   328

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

   329

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

   330

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

   331

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

   332

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

   333

rules defined by flags.

   334

   335

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

   336

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

   337

the key is released.

   338

   339

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

   340

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

   341

   342

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

   343

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

   344

   345

\section{Known bugs}

   346

\begin{enumerate}

   347

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

   348

    attached when the player spawns.

   349

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

   350

    while in mid-air

   351

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

   352

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

   353

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

   354

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

   355

\end{enumerate}

   356

   357

\section{Tasks sharing and schedule}

   358

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

   359

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

   360

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

   361

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

   362

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

   363

   364

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

   365

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

   366

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

   367

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

   368

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

   369

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

   370

   371

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

   372

   373

\section{Differences to the original plan}

   374

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

   375

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

   376

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

   377

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

   378

implement more UDP-based behaviour.

   379

   382

% References

   383

\begin{thebibliography}{99}

   386

\bibitem{fractal} Terrain texture generation.  http://www.gameprogrammer.com/fractal.html

   387

\end{thebibliography}

   388

   389

\end{document}