Procedural RPG World Generation

Featured

Having now completed my MSc, below is a brief summary of my dissertation project along with galleries and a video of the prototype. There’s also a download of the full report detailing the implementation process along with background on the topic for those interested in procedural content generation or studying something related.

Report:

737 Downloads

Video:

Since the days of Rogue, and Elite, games have utilised various procedural content generation techniques to create game worlds for players to explore, freeing developers from the hand-crafted approach typically seen in the majority of games. For me, it was the second Elder Scrolls game, Daggerfall in ’96 that inspired me enough to prompt this topic choice for my MSc dissertation project. Although Daggerfall was most certainly a flawed game, the sheer size of the game world is still unsurpassed even today, being roughly 162 square kilometers (about half the size of the Great Britain) and featuring over 15,000 towns, villages and dungeons. An amusing rumor is that it’s so big that you can fit every other subsequent Elder Scrolls game world into a pixel on Daggerfall’s world map.

When you have a game world that big, procedural content generation (PCG) is the only feasible way to populate it. Daggerfall’s world was generated ‘offline’ and shipped on the game media, making the world the same every time you played it. It’s main story-line areas and characters were hand-crafted, but the rest of its towns, dungeons and wilderness areas were all generated.

Scale comparison of the Elder Scrolls games.

Scale comparison of the Elder Scrolls games.

What I wanted to do, is to tackle a project that aimed to generate an RPG world in real-time so each world would be unique, and ultimately create an explorable 3D RPG world generator. What I actually wanted to do was create a full RPG game to play within these generated worlds (i.e. my dream game), but clearly this would never have been feasible in the time-frame and so I settled for a compromise by removing any game mechanics or AI from the project, effectively stripping out the ‘game’ aspect. Even with this, the project workload was going to be ridiculous considering I wanted to use my own DirectX engine and use it to generate the world, complete with dungeons, NPC towns and a day/night cycle.

Unlike most of my previous projects, there wasn’t going to be much focus on graphics and that actually fit nicely with my retro vision for a more modern looking Daggerfall-esque game, complete with sprites…lots of sprite.

My report can be found at the top of this post if you’re curious about some of the techniques I used in the prototype. I had little knowledge of how other games have really approached this from a technical point of view, other that what I had uncovered during my research on the topic. The developed prototype is therefore very much my own approach.

Since, the detail is all in the above report, I’ll just briefly mention some of the techniques the prototype involved:

The world generation itself was created using a procedural noise technique to generate a height-map. Multiple octaves of value noise are combined (Fractional Brownian motion) to create a resulting fractal noise suitable for generating realistic terrain formations. The noise implementation I used was specifically Voronoise, a method that combines a value grid-based noise type and a ‘jittered’ grid version of Voronoi (cellular noise) into an single adjustable function. I introduced a seed value into the noise generation to allow for reproducibility of worlds, given the same seed. The height-map is output in the pixel shader to a render target upon generation, and then used during the tessellation shader stages via patch control-point displacement when rendering the world.

fBM3

Summation of noise octaves.

terrains

A variety of generated worlds.

The prototype’s generated world size is not huge like Daggerfall, but it’s a fair size at around 16,777 square km. That’s a little under half the size of Skyrim’s world for example, but for a little prototype I’m happy with this and it still allows plenty of explorable terrain using the appropriate movement speed and not the super fast one as seen in my video!

Dungeons use a completely different generation method that I implemented off the top of my head after looking into various techniques. It’s an agent-based technique that uses diggers to burrow out corridors and rooms, with various rules thrown in to keep them in-check to ensure they generate sensible looking dungeons. They are also responsible for spawning the dungeons contents which include monsters and treasure chests and the up and down stairs. Here are some ASCII representations of the dungeon layouts generated by the method:

dungeons

The world is divided up into 32×32 terrain chunks that are each responsible for hosting their respective game objects such as flora, fauna, towns and dungeon entrances. For performance purposes frustum culling was a necessity due to the large scale of the terrain, and only chunks visible in the frustum are processed. Each chunk has a chance of creating towns and/or dungeons and checks such as suitably flat terrain are important factors in determining this. Each building performs a suitability check on the terrain mesh at a chosen spot to see if its within the gradient threshold, and if so places a random structure. If enough buildings are present in a town, NPCs will spawn within proximity of the town.

I added a few small graphical enhancements to the game such as faked atmospheric scattering, fog, layered sky domes, water and emission mapped buildings at night. They are each detailed in the report, but ultimately time was limited and any graphical enhancements were really a secondary concern. Despite this, I really wanted to add them and I think it does enough to achieve the overall atmosphere that I had envisaged, as demonstrated in the below comparison with a Daggerfall screenshot:

DaggerfallComparison

Aesthetic comparison between Daggerfall (left) and prototype (right).

The prototype initially starts into the table view where a map of the generated world is shown that can be rotated and zoomed in/out for examination. At a key press the camera moves into the first-person mode and plonks the player into the world. Worlds can be generated in first-person mode but it’s much more intuitive to do it in the table view. By tweaking the various settings in the UI i.e. noise values, town frequency and tree density; worlds can be tailored to whatever style you want, although currently you have to understand each of the noise settings and their influence on the generation process, to create something you have in mind. Failing that though, there’s trial and error. Ultimately, I’ll add predefined terrain settings that can be selected to simplify this process since it’s really not intuitive to know how ‘lacunarity’, ‘gain’ or ‘frequency’ for instance will effect the world, but academically, it’s quite useful to have them directly tweak-able. A seed value can be directly entered into the UI, with every unique value resulting in a unique world.

I hope at some point to continue with the project. There will be a hiatus for the foreseeable future while I work on other things. There is near infinite scope for the project, with so many things to add so it’s likely something I can keep coming back to.

I also produced a nifty tool for visualising noise which could have various uses for demoing. I’ll probably get this uploaded with a download of the prototype itself at some point.

As detailed in the report, the prototype uses various art assets (models/textures) sourced online via Creative Commons license. The project is for non-commercial use and many art assets are effectively placeholders used to finish the prototype during my studies.

 

 

The MSc Departmental Prize

bcs

Several weeks ago I was very pleasantly surprised by a letter from the British Computer Society stating I had won the ‘Departmental Masters’ Prize in Computer Science’ for my MSc degree!

Along with the nice certificate, I also received a cheque for £150 and a years membership to the BCS, making it most certainly the best bit of mail I’ve received through the letterbox for a good while.

BCS certificate

From speaking with the department I believe I was awarded this based on attaining the highest average score and so it’s nice to know that my effort along with the distinction, was doubly worth while. I’m already looking back fondly at my time at Hull uni and choosing to go on and do the MSc was definitely worth it.

On other fronts, I recently posted a video of my MSc dissertation project on my YouTube profile for anyone interested in the subject of procedural content generation. Making the video was a bit of a pain, and anyone who has recorded footage showcasing academic work previously will know where I’m coming from here, in the sense of making it both informative AND interesting. In the end I edited some raw footage of me exploring a generated world and showcased the various features the best I could.

When I get chance, I’ll be adding it to this site to complete my uni portfolio and uploading my dissertation report (basically because a) it took ages to write!  b) the possibility someone might find it useful and maybe even interesting!).

 

 

Update and MSc Results

It’s been 8 months since my last post and since then I have become a dad, completed my masters, relocated and become a programmer in the games industry! So, there’s been much to talk about but little time to do it. It’s been a crazy year.

Work is keeping me extremely busy, as is family life, so with what little time I do get I tend to try and keep my hand in with gaming. Having said this, I have a large backlog of games to play through including Fallout 4 which I’ve yet to even install. Due to all the above, this blogs been a little abandoned, though it’s served a very useful purpose of helping to display my portfolio and get me a job, something I’d strongly recommend any aspiring game developer to do. I’ll endeavor to post more now I have my weekends back and hopefully useful things and not just…stuff? Hopefully I’ll be getting back into some hobby programming projects I’m wanting to do such as some WebGL ray tracing stuff for this site, and I’m sure I can put some good tutorials together that will benefit all.

So, university then. It’s over. Done. 4 years of very hard toil and the question is was it worth it? A resounding YES, is the answer of course. I’m lucky now that I’m in a position where 4 years ago I was hoping to be, building invaluable experience working in industry.

The University of Hull has provided an excellent place of learning over the course of my BSc and MSc and importantly opened the doors needed to get me into what is a highly competitive industry. I’d like to thank all of the lectures, supervisors and staff that I’ve worked with over the years who made it a very positive experience. A good university is of course important in determining how much you take away from your time studying, but I will say that THE most important thing is your determination and self-motivation. You can coast through a CompSci degree, and take very little from it. Hopefully my grades demonstrate the fact I put my all into it, and at times, particularly in the MSc, the work load was intense. Intense like driving home at dawn from the lab having done 16hrs of red bull and vending machine fueled programming, knowing you need to get back to the lab in a few hours to do it all over again.

MSc Results:

Here are the results as per the University’s module results site:

With an overall average of 89.9%, this means I should be comfortably in the distinction category for my masters which I am thrilled about.

The big module for the MSc is the dissertation project and having done a pure graphics project for my BSc in CUDA ray tracing, I decided to suggest my own topic this time around and decided upon procedural content generation in RPG’s, a subject I have long been fascinated with. The scope of the project was massive, including the design and implementation of my own 3D DirectX11 engine and the creation of an explorable procedurally generated world with procedurally generated dungeons. Needless to say, the process nearly killed me and the report writing was also tough going since I was moving house with a new born and also working full-time! Considering all this, I achieved a great deal of what I had set out to do, as well as surprising my two supervisors quite considerably when they saw just how much I managed to get done!

I’ll be aiming to make a separate post regarding the dissertation project soon, as well as putting together some sort of video of it to complete my degree portfolio.

The project I’m currently working on at work is really exciting and I wish I could talk about it, but unfortunately I can’t…yet. I can say that since starting work I’ve done some business orientated Objective-C, worked with Unity and on my current project, I’m working on a very large mixed code-base of mainly C with bits of C++. Lets just say I’m glad I took note of all that hex, bit masking and bit-wise operations you can easily not pay attention to at Uni, despite being very much absent in more modern managed languages and coding styles.

 

 

 

 

CUDA Ray Tracer – Dissertation Project

Featured

After on and off work for a year, and many thousand words later, my final year BSc dissertation project and report was completed. Can a ray tracer ever be truly ‘complete’? This post a brief description and summary of my project.

A download to my full dissertation report can be found below and as well as a few renderings from my prototypes:

Report:

614 Downloads

Prototype Renderings:

The project from a personal point of view was an important one. It was a period where I gained heightened interest in graphics programming, gaining an understanding of the principles of computer graphics, the mathematics involved and also the creative satisfaction that comes from it. When creating realistic virtual graphics from essentially nothing but code, maths and a display, on the face of it, it’s very easy to gloss over the ‘magic’ of it all, especially when you understand the complexity of how we actually perceive the Universe and the shortcuts that must be taken for computers to accurately mimic the natural phenomena of our brain’s visual perception.

 

CUDA Ray Tracer - Dissertation Project

CUDA Ray Tracer – Dissertation Project

 

A Bit of Biology and Philosophy:

The modern computer when you think of it, is really just a primitive extension of our own bodies, simple enough that we can manipulate, manage and understand it, with much greater control and predictability then our biology. They allow us to achieve things we could not otherwise do and many of the components inside a computer carry out very similar roles to organs found within us. Of course we can think of the CPU as a brain, but what else? Going into more detail, the GPU could be seen as a specialised part of the brain engineered to handle visual computation, just as our brain has it’s own visual cortex. A virtual camera in a rendering program replicates the capabilities of part of our eye, defining an aperture or lens through which to calculate rays of light, and like-wise, an ‘image plane’ positioned in front of the camera, carries out essentially the same functionality as our retina, but using pixels to make up the visual image of what we see.

When you understand the detailed steps required to render something in 3D, you realise that we are essential trying to recreate our own little simplified universe, it’s a pretty profound concept that when taken much further, manifests itself in popular science fiction such as the Matrix. After all, is mathematics not simply the ‘code’ of our Universe? It’s perhaps not as silly as it may sound, when you get down to the fundamentals of game developers creating virtual worlds, graphics programming being an essential component, and looking just how real and immersive these worlds are starting to become.

So What Is Ray Tracing?

Ray Tracing

Of all popular rendering techniques, it’s ray tracing that perhaps stands out the most in respect to my previous comments above. We all know roughly how and why we see, where light rays shine from a light source such as our Sun, they travel millions of miles to get to us and out of all the infinite number of rays, the tiniest percentage may find it’s way directly into our eye. This could be from directly looking at the Sun (not recommended!), and also from scattered or reflected light that has hit a surface, finding it’s way on a collision course with our eye.
This is fundamentally close to how ray tracing works, but with important differences. If a computer had to calculate the trajectory of all possible rays been fired out from a light source, this would be impossible with modern hardware, there are just too many potential rays, of which, only an infinitesimally small amount would ever find there way into the camera (eye) of the scene, and it’s only these rays we are interested in anyway. Instead, and referred to as ‘Backwards Ray Tracing’, light is fired from the camera (eye) into the scene and then traced backwards as it is reflected, refracted or simply absorbed by whatever material it hits. We then only have to fire a ray from the camera for each pixel in the image, which is still potentially a considerable number of rays (1920×1080 = 2073600 primary rays) and that’s without counting all the secondary rays as light scatters throughout the scene, but at least this reduced number is quite feasible.

Still, it is ray tracing’s close semblance to how light interacts with us in the real world that makes it a very elegant and simple algorithm for rendering images, allowing for what is known as ‘physically based rendering’, where light is simulated to create realistic looking scenes with mathematically accurate shadows, caustics and more advanced features such as ‘global illumination’, something that other faster and more common rendering techniques like rasterization (pipeline-based) cannot do.

Illumination and Shading:

Phong Shading

Phong shading

The ultimate main job of firing the rays into a scene in the first place is to determine what colour the pixel in our image should be. This is found by looking at what a ray hits when fired into a 3D scene. Put simply, if it hits a red sphere, the pixel is set to red. We can define the material information for every object in the scene in similar fashion to how we know in the real world that a matt yellow box reflects light. Technically, the box is yellow because it reflects yellow light, and is matt (not shiny) because it has a microscopically uneven surface (diffuse) that scatters the light more evenly away from the surface. Compare this to light hitting a smooth (specular) surface, most of the light would bounce off the surface in the same direction and appear shiny to our eyes. Clearly, for computer graphics, we are not likely to program a surface material literally in such microscopic detail as to define if it is rough or smooth, but we can cheat using a popular and effective local illumination model such as Phong, essentially using the ‘normal’ of a surface, the directions of our light source and camera and some vector math to put it all together and calculate the colour of the surface based on it’s material and angle, creating a smooth shaded object rather than a ‘flat’ colour.

Intersections, Distance Functions and Ray Marching:

Implicit Functions

So we know why we need to fire the rays, but how do know a ray has hit a surface? There’s a few different ways this can be done, all down to the complexity of the geometry you’re trying to render. Ray intersections with simple shape such as planes or spheres can be calculated precisely using linear and quadratic equations respectively. Additionally, for complex explicit 3D models made from triangle mesh, linear algebra and vector math can also be used to compute the intersections.

Another technique, has been gaining popularity in recent years, despite been around quite some time in academic circles. Rendering complex implicit geometry using ‘distance functions’ with nothing but a pixel shader on your GPU as shown on websites like Shadertoy have popularised a subset of ray tracing called ‘ray marching’, requiring no 3D mesh models, vertices or even textures to produce startlingly realistic real-time 3D renderings. It is in fact, the very freedom from mesh constraints that is apparent when you observe the complex, organic and smooth ray marched geometry possible using the technique. Ray marching allows you to do things you simply cannot do using explicit mesh, such as blending surfaces seamlessly together, akin to sticking two lumps of clay together to form a more complicated object. Endless repetition of objects throughout a scene at little extra cost using simple modulus maths is another nifty trick allowing for infinite scenes. By manipulating the surface positions along cast rays, you can effectively transform your objects, twist, contort and even animate; it’s all good stuff.

The Dissertation Project:

My development project was comprised of two parts, a prototype phase to create a ray tracer using GPGPU techniques and a hefty report detailing the theory, implementation and outcomes. For those unfamiliar, General-purpose computing on graphics processing units (GPGPU) is a area of programming aimed at using the specialised hardware found in GPU’s to perform arithmetic tasks normally carried out by the CPU, and is widely used in supercomputing. Though the CPU hardware is singularly much more powerful than the processors in a GPU; GPU’s make up for it in sheer numbers, meaning they excel and outperform CPU’s when computing simple highly parallel tasks. Ray tracing, is one such highly parallel candidate that is well suited to GPGPU techniques and for my dissertation I was tasked to use NVIDIA’s GPGPU framework called CUDA to create an offline ray tracer, done from scratch using no existing graphics API. Offline rendering means not real-time, and is clearly unsuitable for games, yet is commonly used in 3D graphics industry for big budget animations like those by Pixar and DreamWorks, with each frame individually rendered to ultra high quality, sometimes over a period in excess of 24 hours for a single frame.

In the end I produced four different ray tracing prototypes for comparison, incorporating previously mentioned techniques. Prototype 1, running purely on a CPU single thread using simple implicit intersections of spheres and planes. Prototype 2, the same but implemented using a single CUDA kernel and running purely on the GPU across millions of threads. Prototype 3, a CPU ray marcher using distance functions to render more complex implicit geometry. Prototype 4, the same as 3, but implemented using CUDA. My aim for the project was to assess GPGPU performance and the rendering qualities of the ray marching technique, the findings of which can be found in the report.

I knew when I picked this project that I was not taking an easy topic by any stretch, and a great thing I can take away from this is the extensive research experience and planning needed to simultaneously implement many different difficult concepts I had no prior knowledge about, yet still managed to produce a cohesive project, and fully working prototypes, achieving an 88% mark for my efforts, which I am very pleased with. As expected, with heinsight there are things that I would do differently if repeated, but nothing too major, and really, it’s all part of the learning process.

Ray tracing, ray marching, GPGPU, CUDA, distance functions and implicit geometry were all concepts I had to pickup and learn. I bought some books, but in the end, research on the internet in the form of tutorials, blogs, academic papers and lectures proved more beneficial. Sometimes, it takes a certain kind of way to present the information for your brain to ‘click’ with certain principles, and all of us are different. The Internet is a treasure trove in this regard, if you spend the time, you can usually eventually find some explanation that will suit your grey matter, failing that, re-reading it a million times can sometimes help!

Future Plans:

On the back of this, I will be continuing this subject into my masters degree and will likely be pursuing this further during my masters dissertation. I am already busy at work on a real-time implicit render with UI functionality running in DirectX 11 (A couple of early screenshots above). Additionally, I’d love to get a chance to contribute to a research paper on the subject, but we’ll see.

I plan to make some easy to follow tutorials on implementing ray tracing and ray marching at some point for this website, when I get the chance. Hopefully, they could  help out other students or anyone else wanting to learn the aforementioned topics. I know first hand and from friends, that at times it can be frustrating since although there is theory out there, there is comparatively very little information on actual implementation details for the subject, when compared to say pipeline-based rendering.

My BSc in Computer Science – Results Summary

The past three years at the University of Hull have flown incredibly fast; A good sign, that I have thoroughly enjoyed my time there studying for my BSc in Computer Science with Games Development. In fact, it was probably one of the best decisions I ever made, despite how hard it was to take up the challenge as a 27 year old with commitments and nearly 10 years since prior academic study.

My plan will now be to continue on at Hull University to study a post-graduate MSc degree in Computer Science. Relocation and seeking employment will be on the cards aferwards, but I can rest assured having ‘put my all’ into the past several years, I am proud of the results I have acheived and I certainly never expected to do as well as I did, acheiving a First Class honours degree. Below is a summary of my results from the past three years:

Year 1

Module Mark Credit
Computer Systems 73 20
IT and Professional Skills 80 20
Programming 1 92 20
Programming 2 96 20
Quantitative Methods for Computing 87 20
Software Engineering and HCI 77 20
Year 1 average

Year 1 average

Year 2

Module Mark Credit
2D Graphics and User Interface Design 89 20
Advanced Programming 83 20
Artificial Intelligence 78 20
Networking and Games Architecture 88 20
Simulation and 3D Graphics 94 20
Systems Analysis, Design and Process 83 20
Year 2 average

Year 2 average

Year 3

Module Mark Credit
Commercial Games Development 81 20
Games Programming & Advanced Graphics 94 20
Mobile Devices and Applications 83 20
Visualization 86 20
Development Project 88 40
Year 3 average

Year 3 average

 

A ‘Mature’ Reflection:

To any people out there reading this who may fall into the mature student catagory of being a little older and thinking of studying a degree, I would say this; If you are passionate about the subject that you want to study, have proven your interest in it through personal projects, and can cope with the lower standard of living while you study, then go for it and don’t look back. It’s not just about career development, but also a time of personal acheivement and self discovery, where you can find much about your own abilities that perhaps you never knew you had. I think many people can muddle on in life not knowing if they would be any good at ‘this’ or ‘that’. A formal degree can help answer this, giving you confidence in that discipline, which can be it’s own reward. When you realise that generally speaking, unless your lucky enough to be the next Einstein, people achieve great things not through raw intellect or genius, but ‘hard work’ and effort. In this regards, mature students probably have a motivational advantage, since they have more to lose, less time to dawdle and life experience to help them focus.