Skip to content
Snippets Groups Projects
procgen.tex 6.61 KiB
Newer Older
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
\subtitle{Procedural Generation}
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
\date{Tuesday, 15 May 2018}
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
\begin{document}
	
	\begin{frame}
	\titlepage
	\end{frame}

\begin{frame}{Exercise}
\begin{block}{Question}
	What do we mean by procedural generation?
\end{block}

\end{frame}

\begin{frame}{A definition}
\begin{center}
	The act of \textbf{creating} content for games using \textbf{algorithms} as opposed to being \textbf{hand-crafted} by a human creator. 
\end{center}
\end{frame}

Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
\begin{frame}{A few notes...}
	\begin{itemize} 
		\item Far too broad an area for a single lecture\pause
		\item we'll try it anyway...\pause
		\item Used in lots of modern (and old school) games\pause
		\item When done well can add to a game
	\end{itemize}
\end{frame}

\begin{frame}{No Mans Sky}
	\begin{center}
		\includegraphics[width=\textwidth]{nomanssky}
	\end{center}\pause
	ok... maybe not that one.
\end{frame}

\begin{frame}{Early Procedural Generation}
	\begin{center}
		\begin{chronology}[5]{1974}{2000}{55ex}[\textwidth]
			\event{1978}{Beneath Apple Manor}
			\event{1980}{Rogue}	
			\event{1984}{Elite}
			\event{1991}{Civilization}
			\event{1996}{Diablo}
			\event{1998}{F-Zero X}
		\end{chronology}
	\end{center}

	\note{
		\begin{description}
			\item[BeneathAppleManor]{First Roguelike}
			\item[Rogue]{Dungeon generation}
			\item[Elite]{Galaxy generation}
			\item[Civilization]{4X TBS Map Generation}
			\item[F-Zero X]{Racing track generation}
		\end{description}
	}
\end{frame}

	\begin{frame}{History of Procedural Generation}
		\note{\begin{itemize}}
		\begin{center}
			\begin{chronology}[5]{1999}{2015}{55ex}[\textwidth]
				\event{2001}{Runescape}
				\event{2006}{Dwarf Fortress}
				\event{\decimaldate{01}{01}{2008}}{Spore}
				\event{2009}{Borderlands}
				\event{2011}{Minecraft}
				\event{\decimaldate{25}{12}{2013}}{Papers, Please}
			\end{chronology}
		\end{center}
		\note{\item Procedural Generation used to be used due to space constraints}
		\note{\item Nowadays it tends to be to provide more content}
		\uncover<2->{One of the most common uses for procedural generation is levels}
		\note{\item The games used PCG for:}		
		\note{\begin{description}
			\item[Runescape]{Dungeons}
			\item[Dwarf Fortress]{Everything}
			\item[Spore]{Music, Animation, and World}
			\item[Borderlands]{Guns from loot}
			\item[Minecraft]{Environment}
			\item[Papers, Please]{Immigrants}
		\end{description}}
	\end{frame}

Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
	\section{Level Generation}
	% level generation
	
	\begin{frame}
		\frametitle{Rogue}
		\begin{itemize}
			\item Spawned an entire genre based on procedural generation.
			\item Randomly generated dungeons
		\end{itemize}
	
		\begin{center}
		\includegraphics[width=0.75\linewidth]{rogue}
		\end{center}
	\end{frame}

	\begin{frame}
		\frametitle{Activity}
		
		\begin{block}{Question}
			What methods are commonly used for generating levels?
		\end{block}
	
		\pause
		\begin{itemize}
			\item Binary Space Partitioning
			\item Random walks
			\item Cellular Automata
			\item Answer Set Programming
			\item Noise-based
			\item Grid Based
		\end{itemize}
	\end{frame}

\begin{frame}[fragile]{Cellular Automata}
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
	
	\begin{itemize}
		\item Some states (2 or more)
		\item You need a rule (eg, if at least 4 of your neighbours are alive, then return alive, else return dead.)
	\end{itemize}
	
\begin{minted}[breaklines]{python}
for tile in grid:
	neighbors = get_alive_neighbours(tile)
	grid[tile] = rule(neighbours)
\end{minted}
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed

\href{https://blog.jrheard.com/procedural-dungeon-generation-cellular-automata}{Demo}
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
	\begin{frame}
	\frametitle{Grid Based}
	
	\begin{itemize}
		\item Split the map into blocks
		\item Pick (or generate) a template for each block
		\item Place template on grid
	\end{itemize}

	Examples: \gametitle{UFO: Enemy Unknown}, \gametitle{\href{http://tinysubversions.com/spelunkyGen2/}{Spelunky}}
	\end{frame}

	\begin{frame}
	\frametitle{Noise Based}
	
	\begin{itemize}
		\item Generate noise (usually gradient Noise)
		\item Interpret noise as values
		\item Place template on grid
	\end{itemize}
	
	Examples: \gametitle{The Dwarves of Glistenveld}, \gametitle{\href{https://notch.tumblr.com/post/3746989361/terrain-generation-part-1}{Minecraft}}
	\end{frame}
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
	\section{Assets}
	% music, units, etc...
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
	\begin{frame}
		\frametitle{Generating Assets}
		
		\begin{itemize}
			\item Mostly game specific
			\item Not as much available publicly about how these are done.
		\end{itemize}
	\end{frame}
	
	\begin{frame}
		\frametitle{Speedtree}
		
		\begin{itemize}
			\item Used widely by games and film industry
			\item Mixed procedural generation and hand-crafted
		\end{itemize}
	
		\href{https://someuser-321.github.io/TreeGenerator/TreeD.html}{A bit like this...}
	\end{frame}

	\begin{frame}
	\frametitle{Borderlands}
	\begin{columns}
		\begin{column}{0.5\textwidth}
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
	
	\begin{itemize}
		\item \href{http://borderlands.wikia.com/wiki/Weapons}{Randomly generated} weapons
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
		\item Over 17,750,000 different combinations
		\item Lots of properties which determines effects
	\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\includegraphics[width=\textwidth]{borderlands-weapon}
		\end{column}
	\end{columns}

Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
	\end{frame}

	\begin{frame}
	\frametitle{Galactic Arms Race}
	\begin{columns}
		\begin{column}{0.5\textwidth}
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
	
	\begin{itemize}
		\item Generate Weapons based on particle systems
		\item Based on NEAT evolutionary algorithm
		\item Choices based on what the player does
		\item Adapt to the player's experience based on usage
	\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\includegraphics[width=\textwidth]{garGUI}
		\end{column}
	\end{columns}

	\href{http://galacticarmsrace.blogspot.co.uk/p/demo.html}{Demo on their website}
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
	\end{frame}

	\begin{frame}
	\frametitle{Papers, Please}
	\begin{columns}
		\begin{column}{0.5\textwidth}
			\begin{itemize}
				\item Procedural generated people with procedurally generated documents
				\item Gameplay dependant on unpredictability
				\item Hand crafted story elements
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\includegraphics[width=\textwidth]{papers-please}
		\end{column}
	\end{columns}
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
	\end{frame}
	
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
	\section{Full Games}
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
	% games by angelina
	\begin{frame}{Rulesets}
		\begin{center}
			\includegraphics[scale=0.5]{schmidhuber}
		\end{center}
		\begin{itemize}
			\item Evolve rulesets for a given environment
			\item Uses learnability as predictor of fun
		\end{itemize}
	\end{frame}
	
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
	\begin{frame}{Full Games}
		\begin{itemize}
			\item What about games?
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
			\item We can try and generate those to
			\item Try to evolve games that need skill
Joseph Walton-Rivers's avatar
Joseph Walton-Rivers committed
			\item \url{http://www.gamesbyangelina.org/games/}
		\end{itemize}
	\end{frame}
	
Piers Williams's avatar
Piers Williams committed
\end{document}