\documentclass[a4paper]{article}
% generated by Docutils <http://docutils.sourceforge.net/>
\usepackage{fixltx2e} % LaTeX patches, \textsubscript
\usepackage{cmap} % fix search and cut-and-paste in Acrobat
\usepackage{ifthen}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{color}
\usepackage{float} % float configuration
\floatplacement{figure}{H} % place figures here definitely
\usepackage{graphicx}
\setcounter{secnumdepth}{0}

%%% Custom LaTeX preamble
% PDF Standard Fonts
\usepackage{mathptmx} % Times
\usepackage[scaled=.90]{helvet}
\usepackage{courier}

%%% User specified packages and stylesheets

%%% Fallback definitions for Docutils-specific commands
% basic code highlight:
\providecommand*\DUrolecomment[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
\providecommand*\DUroledeleted[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
\providecommand*\DUrolekeyword[1]{\textbf{#1}}
\providecommand*\DUrolestring[1]{\textit{#1}}

% fieldlist environment
\ifthenelse{\isundefined{\DUfieldlist}}{
  \newenvironment{DUfieldlist}%
    {\quote\description}
    {\enddescription\endquote}
}{}

% inline markup (custom roles)
% \DUrole{#1}{#2} tries \DUrole#1{#2}
\providecommand*{\DUrole}[2]{%
  \ifcsname DUrole#1\endcsname%
    \csname DUrole#1\endcsname{#2}%
  \else% backwards compatibility: try \docutilsrole#1{#2}
    \ifcsname docutilsrole#1\endcsname%
      \csname docutilsrole#1\endcsname{#2}%
    \else%
      #2%
    \fi%
  \fi%
}

% hyperlinks:
\ifthenelse{\isundefined{\hypersetup}}{
  \usepackage[colorlinks=true,linkcolor=blue,urlcolor=blue]{hyperref}
  \urlstyle{same} % normal text font (alternatives: tt, rm, sf)
}{}
\hypersetup{
  pdftitle={Dungeon on the fly},
}

%%% Title Data
\title{\phantomsection%
  Dungeon on the fly%
  \label{dungeon-on-the-fly}}
\author{}
\date{}

%%% Body
\begin{document}
\maketitle


\section{A project in the course Procedural methods for images, TNM022%
  \label{a-project-in-the-course-procedural-methods-for-images-tnm022}%
}
%
\begin{DUfieldlist}
\item[{Date:}]
2016-12-13

\item[{Author:}]
Morgan Bengtsson

\item[{Contact:}]
\href{mailto:benmo417@student.liu.se}{benmo417@student.liu.se}, \href{mailto:bengtsson.morgan@gmail.com}{bengtsson.morgan@gmail.com}

\item[{Verson:}]
1.0

\item[{Abstract:}]
Methods for procedural modeling are analysed. Mainly by using procedurally adjustable building blocks. Which resulted in an application that generates a complete and versatile dungeon.

\end{DUfieldlist}


\section{Introduction%
  \label{introduction}%
}

This is a report for the final project in the course Procedural methods for images, TNM022 at Linköping university.

Procedural methods for generating content for games is an attractive subject. Done right it can help to give the appearance of very big game world, without to much work regarding modeling and texturing. There are different routes to take when doing things procedurally. Either everything is fully procedural. Within the realm of 3D graphics meaning that, from each vertex in the models to every pixel in the textures are generated from mathematical functions. Another option is to combine procedural methods with manually made building blocks. This is the approach taken in this work, where predefined components are used with adjustable parameters to affect their appearance. Procedural methods can then be used to adjust those parameters. Furthermore also to choose what components are created, where they are placed, how many and so forth. This approach is often called shape algebra or procedural modeling. In this work these ideas are used to generate a dungeon, inspired from old games such as \hyperref[daggerfall]{Daggerfall}.

\begin{figure}
\noindent\makebox[\textwidth][c]{\includegraphics[width=0.700\linewidth]{daggerfall.jpg}}\phantomsection\label{daggerfall}

\caption{A dungeon from the old game Daggerfall.}
\end{figure}


\section{Noise%
  \label{noise}%
}

The mathematical functions used for generating values are arbitrary. Though in this work mainly noise functions are used. An important property of them is that they are deterministic, meaning that the same input values will always generate the same output. Hence with the same input the exact same dungeon will be generated again in the end. This is important for games, since if the player comes back to a location, the same geometry should be present. Noise is also artistically pleasant for creating sense of randomness, while the predefined components gives a sense of structure. The main noise functions used throughout the implementation are described below:

\hyperref[simplex-range]{simplex\_range} is a function that generates deterministic random values within a defined range. Three dimensional inputs are most often used, though others types are supported. The function is available in an integer and a float variant.
%
\begin{quote}{\ttfamily \raggedright \noindent
\DUrole{keyword}{template}\DUrole{operator}{<}\DUrole{keyword}{class}~\DUrole{name}{\DUrole{class}{T}}\DUrole{operator}{>}~\\
\DUrole{keyword}{\DUrole{type}{int}}~\DUrole{name}{simplex\_range}\DUrole{punctuation}{(}\DUrole{keyword}{const}~\DUrole{name}{T}~\DUrole{operator}{\&}\DUrole{name}{seed}\DUrole{punctuation}{,}~\DUrole{keyword}{const}~\DUrole{keyword}{\DUrole{type}{int}}~\DUrole{name}{min}\DUrole{punctuation}{,}~\DUrole{keyword}{const}~\DUrole{keyword}{\DUrole{type}{int}}~\DUrole{name}{max}\DUrole{punctuation}{)}~\DUrole{punctuation}{\{}~\\
~~\DUrole{comment}{\DUrole{single}{//~Noise~value~in~range~-1.0f,~1.0f.\\
}}~~\DUrole{keyword}{auto}~\DUrole{name}{s}~\DUrole{operator}{=}~\DUrole{name}{glm}\DUrole{operator}{::}\DUrole{name}{simplex}\DUrole{punctuation}{(}\DUrole{name}{seed}\DUrole{punctuation}{);}~\\
~\\
~~\DUrole{comment}{\DUrole{single}{//~Scale~it~to~the~min~,~max~range.\\
}}~~\DUrole{keyword}{auto}~\DUrole{name}{n}~\DUrole{operator}{=}~\DUrole{punctuation}{(((}\DUrole{name}{s}~\DUrole{operator}{+}~\DUrole{literal}{\DUrole{number}{\DUrole{float}{1.0f}}}\DUrole{punctuation}{)}~\DUrole{operator}{*}~\DUrole{punctuation}{(}\DUrole{name}{max}~\DUrole{operator}{-}~\DUrole{name}{min}\DUrole{punctuation}{))}~\DUrole{operator}{/}~\DUrole{literal}{\DUrole{number}{\DUrole{float}{2.0f}}}\DUrole{punctuation}{)}~\DUrole{operator}{+}~\DUrole{name}{min}\DUrole{punctuation}{;}~\\
~~\DUrole{keyword}{return}~\DUrole{name}{\DUrole{function}{int}}\DUrole{punctuation}{(}\DUrole{name}{n}\DUrole{punctuation}{);}~\\
\DUrole{punctuation}{\}}~\\
~\\
\DUrole{keyword}{template}\DUrole{operator}{<}\DUrole{keyword}{class}~\DUrole{name}{\DUrole{class}{T}}\DUrole{operator}{>}~\\
\DUrole{keyword}{\DUrole{type}{float}}~\DUrole{name}{simplex\_range}\DUrole{punctuation}{(}\DUrole{keyword}{const}~\DUrole{name}{T}~\DUrole{operator}{\&}\DUrole{name}{seed}\DUrole{punctuation}{,}~\DUrole{keyword}{const}~\DUrole{keyword}{\DUrole{type}{float}}~\DUrole{name}{min}\DUrole{punctuation}{,}~\DUrole{keyword}{const}~\DUrole{keyword}{\DUrole{type}{float}}~\DUrole{name}{max}\DUrole{punctuation}{)\{}~\\
~~\DUrole{comment}{\DUrole{single}{//~Noise~value~in~range~-1.0f,~1.0f.\\
}}~~\DUrole{keyword}{auto}~\DUrole{name}{s}~\DUrole{operator}{=}~\DUrole{name}{glm}\DUrole{operator}{::}\DUrole{name}{simplex}\DUrole{punctuation}{(}\DUrole{name}{seed}\DUrole{punctuation}{);}~\\
~\\
~~\DUrole{comment}{\DUrole{single}{//~Scale~it~to~the~min~,~max~range.\\
}}~~\DUrole{keyword}{auto}~\DUrole{name}{n}~\DUrole{operator}{=}~\DUrole{punctuation}{(((}\DUrole{name}{s}~\DUrole{operator}{+}~\DUrole{literal}{\DUrole{number}{\DUrole{float}{1.0f}}}\DUrole{punctuation}{)}~\DUrole{operator}{*}~\DUrole{punctuation}{(}\DUrole{name}{max}~\DUrole{operator}{-}~\DUrole{name}{min}\DUrole{punctuation}{))}~\DUrole{operator}{/}~\DUrole{literal}{\DUrole{number}{\DUrole{float}{2.0f}}}\DUrole{punctuation}{)}~\DUrole{operator}{+}~\DUrole{name}{min}\DUrole{punctuation}{;}~\\
~~\DUrole{keyword}{return}~\DUrole{name}{n}\DUrole{punctuation}{;}~\\
\DUrole{punctuation}{\}}
}
\end{quote}

\hyperref[simplex-bool]{simplex\_bool} is a convenience method that either gives true or false depending on the input.
%
\begin{quote}{\ttfamily \raggedright \noindent
\DUrole{keyword}{template}\DUrole{operator}{<}\DUrole{keyword}{class}~\DUrole{name}{\DUrole{class}{T}}\DUrole{operator}{>}~\\
\DUrole{keyword}{\DUrole{type}{bool}}~\DUrole{name}{simplex\_bool}\DUrole{punctuation}{(}\DUrole{keyword}{const}~\DUrole{name}{T}~\DUrole{operator}{\&}\DUrole{name}{seed}\DUrole{punctuation}{)}~\DUrole{punctuation}{\{}~\\
~~~\DUrole{keyword}{return}~\DUrole{name}{glm}\DUrole{operator}{::}\DUrole{name}{simplex}\DUrole{punctuation}{(}\DUrole{name}{seed}\DUrole{punctuation}{)}~\DUrole{operator}{>}~\DUrole{literal}{\DUrole{number}{\DUrole{float}{0.0f}}}~\DUrole{operator}{?}~\DUrole{name}{\DUrole{builtin}{true}}~\DUrole{operator}{:}~\DUrole{name}{\DUrole{builtin}{false}}\DUrole{punctuation}{;}~\\
\DUrole{punctuation}{\}}
}
\end{quote}


\section{Components%
  \label{components}%
}

There are two types of components defined to generate the dungeon: doors and entities.


\subsection{Door%
  \label{door}%
}

Doors are small objects that define the connection between two entities. A door consist of a transform matrix, a pointer to the next entity and a \hyperref[door-model]{model for rendering}. The door has two \emph{states}; open and closed, which are set by the \hyperref[simplex-bool]{simplex\_bool} function. Input for that method is the door position.

\begin{figure}
\noindent\makebox[\textwidth][c]{\includegraphics[width=0.700\linewidth]{doors.png}}\phantomsection\label{door-model}

\caption{Door model with two states, open and closed.}
\end{figure}


\subsection{Entity%
  \label{entity}%
}

The entity is a base component that the following components are based from. The
common denominator is that an entity can contain several doors that lead to new entities. An entity takes a transformation matrix that specifies where the entity should be generated. Each entity also contains a bounding box that is used for collision detection in the \hyperref[algorithm]{algorithm}.


\subsubsection{Corridor%
  \label{corridor}%
}

The corridor is a simple entity where the only adjustable parameter is its \emph{length}. The length is defined with the \hyperref[simplex-range]{simplex\_range} function with position as input. At the end of the corridor an exit door is created. Only one \hyperref[corridor-model]{model} is used for rendering and it is repeated until the desired length is reached.

\begin{figure}
\noindent\makebox[\textwidth][c]{\includegraphics[width=0.700\linewidth]{corridor.png}}\phantomsection\label{corridor-model}

\caption{The corridor model.}
\end{figure}


\subsubsection{Elevator%
  \label{elevator}%
}

The elevator is similar to the \hyperref[corridor]{corridor} entity. With the difference that it extends in the vertical direction. Hence the \emph{height} is the only adjustable parameter, populated by the \hyperref[simplex-range]{simplex\_range} function, with position as input. The model for this entity looks a bit different since it also has an animated cart, as shown in the \hyperref[elevator-model]{image}. The model is repeated vertically until the desired height is reached.

\begin{figure}
\noindent\makebox[\textwidth][c]{\includegraphics[width=0.700\linewidth]{elevator.png}}\phantomsection\label{elevator-model}

\caption{The elevator model, with the cart to the left.}
\end{figure}


\subsubsection{Room%
  \label{room}%
}

The room is the most advanced and most configurable entity. Meaning that it can change much in appearance depending on what values are used to create it. The main values are its \emph{size} in two dimensions and the room \emph{type}. The \hyperref[simplex-range]{simplex\_range} function is used to initialize both, with room position as input. The input position is scaled a bit for the second \emph{size} dimension, to not get square rooms.

The \emph{type} value determines which set of models to use when creating the room. There are three sets, one with stone material one with metal material and one with wood material. There are several models that builds a room such as floor, edge models and corners. Some of the variations are shown in the \hyperref[room-edges]{room edges} figure.

\begin{figure}
\noindent\makebox[\textwidth][c]{\includegraphics[width=0.700\linewidth]{room_edges.png}}\phantomsection\label{room-edges}

\caption{Different types of room edges.}
\end{figure}

When the room \emph{type} is determined, the corresponding set of models are used to build the room. A two dimensional loop fills the room with models. Edge models for walls, special models for corners, entries, exits and floor models in the middle. What model variation that is used depends on the \hyperref[simplex-range]{simplex\_range} function with model position as input. As seen in the \hyperref[room-edges]{room edges} figure, the stone material room has many variations. Walls are also varied slightly in height with the \hyperref[simplex-range]{simplex\_range} function.


\subsection{Stairs%
  \label{stairs}%
}

Stairs are similar to the \hyperref[corridor]{corridor} with its only adjustable parameter being its \emph{length}. This variable is again populated by the \hyperref[simplex-range]{simplex\_range} method with position as input. The difference is that the stairs extends both vertically and horizontally. An exit door is added to the end of the model. There two versions of this entity, one that goes up and one that goes down, as shown in the \hyperref[stairs-models]{stairs models} figure.

\begin{figure}
\noindent\makebox[\textwidth][c]{\includegraphics[width=0.700\linewidth]{stairs.png}}\phantomsection\label{stairs-models}

\caption{Stairs up and down.}
\end{figure}


\section{Items%
  \label{items}%
}

To further spice up the environment, some extra items are added to each \hyperref[room]{room}. If they are placed on a floor model in the \hyperref[room]{room} depends on the \hyperref[simplex-bool]{simplex\_bool} function and the model position. Which item is used is determined by \hyperref[simplex-range]{simplex\_range}, and the same position. The \hyperref[item-models]{item models} are shown below:

\begin{figure}
\noindent\makebox[\textwidth][c]{\includegraphics[width=0.700\linewidth]{items.png}}\phantomsection\label{item-models}

\caption{A table, a package and a tree.}
\end{figure}


\section{Algorithm%
  \label{algorithm}%
}

To generate a dungeon the first entity has to be created manually. Then a loop iterates through all the entities, a defined number of times. Each time the loop checks for doors in each entity that has an empty pointer to their next entity. If that is the case a new entity is created and linked to that pointer.

Before the entity is linked to the door. The entity bounding box is checked for collision with all other bounding boxes in the level. If a collision is detected, the entity is discarded and the door hence leads nowhere. The door state is marked as closed in this case.

What type of entity that is generated is decided by a method that takes the door position as input and uses the \hyperref[simplex-range]{simplex\_range} method to get an index value. The index value is used on a container filled with all types of entities described in previous sections. When each entity is created it takes the door transform as input for further processing.


\section{Implementation%
  \label{implementation}%
}

The implementation is done in C++ with a couple of helper libraries. One is \href{https://github.com/morganbengtsson/mos}{Mos}, mainly used for defining models and meshes for rendering. Another important one is \href{http://glm.g-truc.net/0.9.8/index.html}{GLM}, which is used for all the maths. Especially the simplex noise method that is essential for the \hyperref[algorithm]{algorithm} and the procedural nature of all the entities. All models are made with \href{https://www.blender.org/}{Blender}.

The level is generated in its own thread at start up, to show how the dungeon generates and not to stall the rendering.

The code itself is available at \url{https://github.com/morganbengtsson/dungeon} and can be downloaded with the following git command:
%
\begin{quote}{\ttfamily \raggedright \noindent
git~clone~-{}-recursive~https://github.com/morganbengtsson/dungeon.git
}
\end{quote}


\subsection{Build%
  \label{build}%
}

The application uses \href{https://cmake.org/}{CMake} as the build system. To build, create a directory named \emph{build} in the downloaded source  directory. From the \emph{build} directory run the following command:
%
\begin{quote}{\ttfamily \raggedright \noindent
cmake~..
}
\end{quote}

This should generate appropriate Makefiles for the Linux platform, or a Visual Studio project on the Windows platform.


\section{Results and discussion%
  \label{results-and-discussion}%
}

A \href{https://www.youtube.com/watch?v=-ZhnmNAsNJo}{video} of the resulting application is available along with a \hyperref[screenshot]{screenshot} below:

\begin{figure}
\noindent\makebox[\textwidth][c]{\includegraphics[width=0.700\linewidth]{screenshot.png}}\phantomsection\label{screenshot}

\caption{The resulting dungeon after six iterations.}
\end{figure}

The results for generating a dungeon procedurally this way are quite positive. With only a few basic models it is possible to generate a quite versatile dungeon. Many parameters are tweak-able, to quickly get a desired result. In contrast to manual modeling, which would take much longer. Also the numerical representation of a whole dungeon is very compact, only the first entity and a position.

Improvements that could be done are optimizations to the rendering. Even more variations in the different entities. The \hyperref[room]{room} could be customized even further for example. With more floors, different shapes and materials. Procedural methods could have been used even further, to place or randomize vertex positions in the models. That would be at the cost of performance though.

\end{document}
