Towards Cross-Platform Based Mindset (I)

I believe a good game-dev environment should be capable of supporting all-platform philosophy and this can be achieved by being open enough to strive for enough learning and compassion.

The purpose of this blog-post series is to explore and show just that. We begin with the study of a cross-platform real-time graphics driver.

Vulkan is a cross-platform 3D graphics API and graphics driver meant for Real Time rendering. The best feature, for me personally, is the degree of control provided with the fortune of low-level programming tools which clears up the graphics rendering pipeline concept for enthusiasts and delivers major lesson for the uninitiated (who survive at the convenience of easy GL type function calls, not to say I’m not Glad, pun intended). Our friend Cherno is a great propagator of the API who introduced me to Vulkan. But we gonna extend his legacy and put the concept of cross-platform to test with all the stress-tests known to tech-kind.

Along with the official tutorial I have consulted Travis Vroman’s videos and some off-mainstream videos. In context of Karma, we don’t need to hook Vulkan as sole beneficiary but rather as any other regular library with enough fluidity of switching like so

#include "RendererAPI.h"

namespace Karma
{
    RendererAPI::API RendererAPI::s_API = RendererAPI::API::OpenGL;
}


Here we see it is matter of single line to change the rendering API for Karma. Clearly I plan to implement Metal/DirectX in future. Remember we need a decoupled way of hooking the library for cross-platform reasons. This results in the following folder hierarchy generating enough basis for the abstraction we are striving for

KarmaEngine  
│
└───Karma
│   │
│   └───src
│   │   │
│   │   └───Karma
│   │   │   │
│   │   │   └───Animations
│   │   │   └───Events
│   │   │   └───Renderer
│   │   │   Input.h
│   │   │   Core.h
│   │   │   Log.h
│   │   │   ...
│   │   │
│   │   └───Platform
│   │       │
│   │       └───Linux
│   │       └───Mac
│   │       └───OpenGL
│   │       └───VUlkan
│   │       └───Windows
│   │        
│   │   Karma.h
│   │   ...
│   │
│   └───vendor 
│   │   │
│   │   └───assimp
│   │   └───Glad
│   │   └───GLFW
│   │   └───GLM
│   │   └───glslang
│   │   └───ImGui
│   │   └───spdlog
│   │   └───stb 
│   │   ...
│
└───Application
    │   
    └───src
    │   KarmaApp.cpp
    │   ...

The entities thus formed are equipped with the ability to hook with high specificity and moral values (minding own business and not interfering with others in any sense). Then it becomes my job to deal with the decisions, for instance, how much ground to cover with how much depth such as to maintain the overall harmony in Karma. At this point in time, the following flow-chart captures the essence of Karma

Screenshot from 2022-07-02 07-52-59

Clearly, Vulkan is part of Rendering Engine, which, is an abstraction that can be visualized as a magical (not mystic though) box with the following diagram

image

The layer takes care of what platform we are running on and which rendering API we are rocking with. Then the concept of cross matching (within the scope of API-Platform support alliances) is obvious. Let me outline of the Rendering Engine (RE) functioning. In a typical Rendering loop, the following lines of code are a must

virtual void OnUpdate(float deltaTime) override
{
    Karma::RenderCommand::SetClearColor(/* Some Color */);

        Karma::RenderCommand::Clear();

    Karma::Renderer::BeginScene();

    /* Process materials and Bind Vertex Array. */

    Karma::Renderer::Submit(/* Some Vertex Array */);

    Karma::Renderer::EndScene();
}

Now we would want our APIs (Vulkan/OpenGL or whatever) to conform to these simple static function calls. That is where the RE magic comes in. No matter what the working philosophy of graphics API is, we need to channel that into a working set of routines such that the above OnUpdate function, called in the game loop, which can be identified with Karma's Rendering Handle in the flow chart, makes sense (works). Let me define and explain the actors of this play

  • Vertex Array: Can be imagined synonymous to a well behaved container of Mesh and Material (defined here). Each API should have its corresponding instantiation of Vertex Array.
  • Render Command: Is a static class with the rendering structure (curtsey TheCherno) and with the runtime-polymorphism responsibility to direct the calls to appropriate API (specified here). It holds the reference to RendererAPI which could be Vulkan or OpenGL after doing their initialisation specified in RendererAPI.cpp.
  • Renderer: A data-oriented static class containing the scene information (for instance camera) for relevant processing, and, rendering API information for Karma.

There is an entire branch in which we attempt to hook Vulkan API and which succeeded almost as expected (with some reservations and I plan to do a stress test with large number (millions perhaps billions of triangles)). But let me first chalk out the partial-abstractions acting like an interface between the static routines, in the above block, and low level Vulkan commands. The following are the Vulkan adaptations of Karma’s abstract classes.

  1. Vulkan Shader (derived from Shader)
  2. Vulkan Buffer (derived from Buffer)
  3. Vulkan Context (derived from Graphics Context)
  4. Vulkan RendererAPI (derived from RendererAPI)
  5. Vulkan VertexArray (derived from VertexArray)

Please note I am using the video as raw material and vulkan-tutorial for regular checks in what I understand and write henceforth.

The goal for any decent graphics API is to provide means (tangible and intangible) to map the coordinates of a triangle (read my blog-post for underlining importance of triangles in Real Time rendering) to the pixels on monitor or screen. This is it! What basically creates the market for various APIs IS the need for a hardware friendly algorithm which is considerate enough not only for scaling to billion triangles but also for providing natural fit to the taste of the programmer. Taste may include various levels of legitimate control based on what the programmer may think serves the purpose.

To be continued…

First triangle (drawn by Karma)

 

Playing video games is not only fun but also an engaging activity which can lead to catharsis. But there is a novel dimension to this activity which many players enjoy even more. It is building the game itself. This is the reason why many games come with level editors. For me, video games are not only the mode of experiencing a given world, but also an opportunity to modify and enhance that world to express myself.

I find game programming intellectually satisfying. It basically translates to building an interactive world and providing a structure to that world by enforcing the rules set by the programmer, who, then, can witness the world evolve under those conditions. It is an ecstatic activity to watch your own creation unfold before your eyes which you experience as being an integral part of.

Almost all the games are made using Game Engines. Unreal Engine and Unity are the prime examples of open-source game engines available in the market. As a serious game developer, it is a good exercise to write your own game engine. It not only exposes you to the current state-of-the-art game development methodologies but also provides the complete control over the scheme of building process. With this in mind, I have embarked upon the journey of writing a game engine myself. I call it Karma and it can be found here.

A game engine has several sub-systems including a rendering engine. As the name suggests, its aim is to draw (render) graphics corresponding to the visible game objects (like player character, weapons, mountains etc), on the screen. The engine has to draw the entire scene quickly enough (typically one frame is rendered within 16.6 milliseconds) so that 60 frames can be drawn in one second and illusion of continuous motion (of game objects) can be generated in real time. In this blog-post we will be focusing on rendering graphics.

Computer graphics in real time are rendered using triangles. They are the building blocks of CG just like strings are the building blocks of matter in String Theory (or, for faint hearted, cells are the building blocks of life in biology). Triangles are optimal candidates for real time rendering because

  • triangle is the simplest polygon
  • triangle is always planar
  • triangle remains triangle under most transformations
  • virtually all the commercial graphics-acceleration hardware is designed for triangle rasterisation 

A simple demonstration of triangles generating graphics can be found here and here. Therefore rendering a triangle in an efficient manner is a crucial step in real time computer graphics. I will demonstrate here how Karma does it.

First grab the code from my GitHub repository. GitHub is a service which provides software hosting (for free!) and version control using Git. One can track down the software in its various stages of development back in time. Make sure you have Git installed. Open the cmd (on Windows) or shell (Linux) and type

git clone --recurse-submodules https://github.com/ravimohan1991/KarmaEngine.git
cd KarmaEngine
git reset --recurse-submodules --hard 9e3046842db787eb847e636baf5058f5a6068fe9

The above lines of code basically download the Karma engine and reset the state of the local repository to the state, back in time, when first triangle was rendered by the Karma. Now depending of the platform proceed as follows

Windows

Make sure you have Visual Studio 2017 (or higher) installed. Go the the KarmaEngine directory, in the explorer, and click the file GenerateProjects.bat. This will create KarmaEngine.sln file which then can be opened in Visual Studio. Karma can now be built from the Visual Studio!

Linux

Type the following in Linux shell

vendor/bin/Premake/Linux/premake5 gmake
make

This will build the Karma engine in the “build” directory from where you can run it. You will get something similar to what is shown in the first image of this blog-post.

So now that you have the code, let us first understand the theory behind rendering triangles. Later we will see how that is implemented in C++. In order to render a triangle, we need the information regarding its vertices. The information (vertex attributes) can be composed of the position of each vertex, the unit normal/tangent at each vertex, diffuse/specular color and texture coordinates for each vertex.

For simplicity, let us consider rendering a cube (using triangles, as shown in the figure)

and the information consisting of only position data. Then we need a data structure to store the triangular tessellation in effective way. We use two buffers

  • vertex buffer: consists of all the vertices to be rendered
  • index buffer: consists of triples of vertices that make up the triangles

This is done to avoid the duplication of the data and save the GUP bandwidth required to process the associated transformations (model space to view space or clip space). Once this is done, shaders are deployed to compute the attributes, like color, per pixel (by interpolation or using some texture maps).

To render graphics we will use OpenGL which is cross-platform graphics rendering API. If you are running Windows or Linux on modern hardware, chances are that your system already has OpenGL support. If we look into the code here we find 

glGenVertexArrays(1, &m_VertexArray);
glBindVertexArray(m_VertexArray);

This basically generates the vertex array (required by the core OpenGL profile, basic initialisation for vertex attributes) and binds it to the m_VertexArray variable id. Next we have

glGenBuffers(1, &m_VertexBuffer);
glBindBuffer(GL_ARRAY_BUFFER, m_VertexBuffer);

// Clip space coordinates
float vertices[3 * 3] = {
	-0.5f, -0.5f, 0.0f,
	0.5f, -0.5f, 0.0f,
	 0.0f, 0.5f, 0.0f
};
// Upload to GPU
glBufferData(GL_ARRAY_BUFFER, sizeof(vertices), vertices, GL_STATIC_DRAW);

Here we are generating the vertex buffer and binding it to m_VertexBuffer variable. GL_ARRAY_BUFFER is the target type which tells that OpenGL that we intend to use the buffer for vertex attributes. And finally we define the matrix of vertices specifying the coordinates of the vertices of the triangle in clip space (which spans from -1 to 1 in all directions). And finally we upload the data to GPU. GL_STATIC_DRAW means that we are not rendering the stream of dynamic data. It is static!

Next we have

glEnableVertexAttribArray(0);
glVertexAttribPointer(0, 3, GL_FLOAT, GL_FALSE, 3 * sizeof(float), nullptr);

 which tells OpenGL about the layout of the data we have specified so that it can be used by the default shader. glVertexAttribPointer tells that at index 0, there are 3 floats (GL_FLOAT), not normalised (GL_FALSE), stride is the amount of bytes between each vertices of vertex array (3 * sizeof(float)) and offset of the attribute which we set to nullptr.

Finally we do the same thing with index buffer, we generate and bind the buffer to m_IndexBuffer. Then we define the sequence of indices to be rendered in counter clockwise order and upload the data to GPU. The GPU then provides a default shader which colours all the pixels within triangle white.  After the initialization, this piece of code draws the triangle on the screen. The end result is shown in the first figure of this blog-post. 

So this is it! Once a triangle is rendered, we are a step closer in understanding how realtime graphics are rendered in games. From here we can start building up and render more complex surfaces leading to beautiful scenes that we desire to produce.

 

Story of Maryam’s mathematical magic

MaryamMirzakhani.jpg

Gravity is a difficult concept to understand as a quantum theory. Therefore physicists (and their mathematician friends) study quantum gravity in 2 dimensions where equations are more tractable. Just like any good quantum theory, the path integral for quantum gravity is defined by Z(\beta) = \frac{1}{\text{vol}}\int \mathcal{D}\phi\mathcal{D}g e^{-I} where “vol” is the volume of the diffeomorphism group implying that the integration should be done on \phi and g upto diffeomorphism and I is the action of a model knowns as Jackiw-Titelboim (JT) theory. Once the partition function is known, a quantum theory can be solved.

The partition function for the 2 dimensional quantum gravity (after imposing appropriate boundary conditions on two manifold U with the topology of a disc) turns out to be Z_{U}(\beta) = \int_{0}^{\infty}dE\rho_0(E)e^{-\beta E} where \rho_0=\frac{e^S}{4\pi^2}\sinh^2(2\pi\sqrt{E}). S is the renormalized coefficient for Einstein-Hilbert term (ignore it if you don’t know what it means).

Holographic duality

From AdS/CFT correspondence we know that the 2 dimensional quantum gravity is dual to 1 dimensional simple quantum system on the boundary of U. This implies that the partition function that we computed earlier form JT model should be Z_{U}(\beta) = \text{Tr}_{\text{H}}e^{-\beta \hat{H}} where \hat{H} is the Hamiltonian operator of the associated 1 dimensional quantum system. In other words, Z_{U}(\beta)=\int_0^\infty dE\sum \delta(E - E_i)e^{-\beta E}. This clearly is not equal to the partition function computed in the previous paragraph and that is problematic. The dual theories should have same partition function

Random Matrix theory

The idea here is to consider an ensemble of random matrices (with certain properties) and define the ensemble average of the partition function \langle Z(\beta)\rangle = \langle \text{Tr}_{\text{H}}e^{-\beta \hat{H}} \rangle. In the matrix literature it is common to work with the inverse Laplace transform of the partition function given by R(E) = -\int_0^\infty d\beta Z(\beta)e^{\beta E} known as the resolvent. So the resolvent correlation function has the “genus” expansion as follows \langle R(E)\rangle = \sum_{g=0}^{g=\infty}\frac{R_{g,n}(E)}{L^{2g+n-2}} (it is asymptotic series expansion) where L is the dimension of the matrices of the ensemble. The terms R_{g, n} can be computed systematically from what are known as “loop equations”, in terms of \rho_0(E) which is the “average density of the eigenvalues of random matrix of the ensemble”. The loop equations are streamlined into simple recursion relations which yield the correlation function upto all orders (in 1/L^2)  once \rho_0(E) is specified.

2 dimensional gravity again

In the JT model, there is a prescription to compute the quantity \langle Z(\beta) \rangle which involves integrating over connected 2d geometries with specified boundary length and value of dilation field at the boundary. The partition function turns out to be \langle Z(\beta)\rangle = e^{S_0}Z^{\text{disc}}_{\text{sch}} + \sum_{g=1}^{\infty} e^{(1-2g)S_0}bdbV_{g, 1}(b)Z^{\text{trumpet}}_{\text{sch}}(\beta, b) where b is the length of a geodesic and V_{g, 1}(b) is the Weil-Petersson volume of moduli space of Riemann surface with genus g.

In the phenomenal paper Maryam Mirzakhani showed that the Weil-Petersson volume follow certain recursion  relation which was shown to be equivalent to the recursion relation of matrix ensemble, we saw earlier, if we use the leading (genus 0) contribution of the JT path integral as \rho_0(E) thus resolving the problem described earlier.

There is analogous story for supersymmetric quantum gravity but I am in no mood to write about it. If you are interested read this paper by Witten and Stanford.

Strings in AdS_3 and Spectral Flow

Studying string theory in \text{AdS}_3 is useful in understanding \text{AdS/CFT} correspondence as it sheds the light on one half of the “million dollar” conjecture beyond gravity approximation. The recent progress with the exact \text{AdS}_3\text{/CFT}_2 duality makes it important to study the string theory and understand the isomorphism of the physical states on both the sides. In this blog-post, I will explain the bosonic version of the string theory with emphasis on something known as “Spectral Flow”.

The spectral flow was an answer to some earlier issues raised by the study of string theory on \text{AdS}_3 which involved existence of an upper bound in the internal energy of string (independent of the string coupling) and absence of the “long string” states in the spectrum. In 2000, Maldacena and Ooguri wrote seminal paper (actually it was a series of three papers 1, 2 and 3) which established the consistency of the theory and opened gates for further study in the field and the million dollar conjecture.

The worldsheet description of the theory takes the form of SL(2,\mathbb{R}) WZW model. Just like any story in physics, we first start with the classical version of the model. The action is S = \frac{k}{8\pi\alpha^\prime}\int d^2\sigma\text{Tr}\left(g^{-1}\partial gg^{-1}\partial g\right)+k\Gamma_{\text{WZ}}. Here g is the SL(2,\mathbb{R}) group element. Next we define left and right moving coordinates on the world sheet as x^{\pm}= \tau\pm\sigma. Then the equation of motion is given by \partial_{-}(\partial_{+}gg^{-1})=0 such that the general solution is given by g = g_{+}(x^{+})g_{-}(x^{-}). Furthermore the string is closed under \sigma\to \sigma + 2\pi which leads to constraint g_{+}(x^{+}+2\pi) = g_{+}(x^{+})M and g_{-}(x^{-}-2\pi) = M^{-1}g_{-}(x^-) where the monodromy M is defined only upto the conjugation by SL(2,\mathbb{R}) and classical solutions of WZW model are defined according to conjugacy class of M. Of course we still need to impose the Virasoro constraint that the stress energy tensor vanishes on-shell (just like the bosonic strings theory on flat-space).

The classical stage is set. Now we study some examples. Consider the solution g_{+}=Ue^{iv_{+}(x^{+})\sigma_{2}} and g_{-}=e^{iu_{-}(x^{-})\sigma_{2}}V (it is easy to check that it satisfies equation of motion for U = \mathbb{I}) where U and V are constant SL(2,\mathbb{R}) matrices. The energy-momentum tensor of the solution is T^{\text{AdS}}_{\pm\pm}=-k(\partial_{\pm}v_{+}/u_{-})^2. Now let there be excitations in the compact \mathcal{M} of \text{AdS}_3\times\mathcal{M} and let the T^{\mathcal{M}}_{\pm\pm}=h then the Virasoro constraints imply (\partial_{+}v_{+})^2=(\partial_{-}u_{-})^2=\frac{h}{k}. Solving for v_{+}/u_{-} and substituting in the solution ansatz yields the result g = U\begin{pmatrix}\cos\alpha\tau & \sin\alpha\tau\\-\sin\alpha\tau & \cos\alpha\tau\end{pmatrix}V where \alpha = \pm\sqrt{\frac{4h}{k}}. \sigma drops out and solution is only in terms of \tau. This can be interpreted as “string collapsing to a point”. For U=V=\mathbb{I}, it is essentially a particle sitting at the center of \text{AdS}_3 as shown in the figure.

PointString

Similarly, one can write spacelike solution in the form g = U\begin{pmatrix}e^{\alpha\tau} & 0\\0 & e^{\alpha\tau}\end{pmatrix}V.

Now given a classical solution g=\tilde{g}_{+}\tilde{g}_{-}, one can generate new solutions g_{+}=e^{i\frac{w_R}{2}x^{+}\sigma_2}\tilde{g}_{+} and g_{-}=\tilde{g}_{-}e^{i\frac{w_L}{2}x^{-}\sigma_2} which may be regarded as an action of the loop group \hat{SL}(2,\mathbb{R})\times \hat{SL}(2,\mathbb{R}). This is known as the spectral flow in CFT literature.

B for Behavior, Blackboard and Brain (3)

This is the  final blog-post of the series (for previous parts see here and here). As promised, here we will see the implementation of Reinforcement Learning through Behavior Tree (in natural Unreal Engine environment). The method written is fairly general and can  be used to generate BT corresponding to any RL based algorithm.

The k-armed bandit (which for our case turns into shooting colored boxes) algorithm can be categorized into 5 tasks.

  1. Select a box (based on probabilities and estimates)
  2. Rotate towards box (for more complex, locomotion may be involved)
  3. Shoot the box
  4. Wait (for reward assesement)
  5. Update the estimates

The tree built  with this categorization of the tasks is shown in figurerlbt

The Engine also provides an powerful interface for Blueprints to interact with C++. This is a good way to unify the artistic and programming development of a game. We will show that in real time here.

Consider the task BTTask_FindAppBox node. The Blueprint implementation is shown in the figure

taskfindbox

In the Engine, every BT task starts with the node Event Receive Execute AI. So we start with that and  make the connection to Cast node yielding the object corresponding to class MAIPlayerController. Once that is done, we invoke the C++ method through the node Look for App Box and by  setting the target pin as the casted object. The C++ method is posted here.

Similarly rest of the three tasks (except the Engine default task Wait) are implemented through this C++-Blueprint interface. Another example is BTTask_UpdateEstimates

estimates

with the corresponding C++ code posted here.