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:

5434 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.

 

 

Cross-Platform Game Engine

Featured

In the first semester of my MSc Computer Science degree as part of the Games Development Architectures module we were tasked to design and implement a cross-platform game engine. A game would also be made using the engine.

The chosen platforms were a Windows PC and Windows Phone 8 device. I decided that considering Microsoft had developed a Universal Application framework for targeting both of these, I would utilise it. This was good from the point of view that it simplified the cross-platform compatibility, but introduced a few limitations (namely having to work with the Windows RT platform and resultant consequences for dealing with inputs via ‘ref classes’ etc.. Coming from experience with Win32 desktop programs, Windows RT feels very different to program for and much less flexible, but then again Win32 really does need some modernisation.

4

Project Details:

  • Engine coded in C++ (Visual Studio).
  • DirectX11 rendering engine component coded from scratch.
  • HLSL shaders.
  • The Universal App framework used to contain the code solution and deploy to both platforms.

We were given a design specification for a simple game called ‘Tunnel Terror’. It involved the player having to control a vehicle/object through a tunnel, avoiding various obstacles. The speed would gradually increase the longer the player survived and any collisions with obstacles would result in death. Score was determined by length of survival. I decided to add various extras including power ups such as coins and a randomised speed-up/slow-down. The game would need to play on both a PC and Windows Phone 8 device, allowing for the differing input controls to play. I decided the PC would utilise keyboard whereas the phone would rely on the accelerometer (tilt) sensor to manoeuvre the player through the tunnel. The PC also required a 2 player mode. Main menu, high score table and game over screens would be needed as well as Multiple camera modes such as first-person, third-person and death fly-by cameras.

3

Although marks were given for the game implementation and extra features, much of the module was graded based on the engine design, implementation and accompanying report. My report justified the design based on four principles of games architecture, namely ‘Simplicity’, ‘Reusability’, ‘Abstractness’ and ‘Modularity’. Below is an example of the UML design used for my engines platform independent rendering component, with examples given to how behaviour could be derived for both DirectX and OpenGL.

Renderer

In the report we also had to research how we would have implemented the game on next-generation architecture such as the PlayStation 4 and how the engine would deal with the addition of different kinds of input devices.

There were some marks awarded for graphics quality and since the target platforms were both Microsoft, DirectX11 was used for the graphics. I implemented normal bump mapping to give it a nice look when flying down the tunnel. I also randomly changed the textures of each tunnel section and reset them to the end of the sequence once passing behind the frustum to give the impression of an endless tunnel with non-repeating sections.2

Annoyingly because the game is a Windows Store application there is no runnable executable so without actually publishing it to the Store and getting past all the certification requirements I cannot put it up anywhere to play! What is worse though is that currently I know of no screen capture software that can even record footage of the game running (at a decent FPS), both Fraps and Bandicam do not capture it since it’s not a desktop application. Bandicam does have desktop capture support but this also didn’t seem able to see the game and is not suitable for high frame-rate applications. So, as it stands I can’t make a video of the game running without hardware recording. Hopefully, this is something that won’t always be the case.

I was very pleased with the final engine and received a 92% grade for the module. I have since improved upon it and reused design elements for subsequent modules such as Real-time Graphics. I think a lot of what I coded for this project will be extremely useful going forward.

 

 

 

Bit’s Blitz – Puzzle Game

Bit's Blitz - Puzzle Game

Bit’s Blitz – Puzzle Game

In the third year of my Computer Science BSc (2013) as part of the Commercial Games Development module, we were placed into groups and tasked to produce a computer themed game designed for children. Each of the group members had to produce a game design document, one of which would be chosen for the group to develop. My group consisted of me, Aaron Ridge, Michael Killingbeck, Andrew Woodrow, Joshua Twigg and Alex Lynch.

The group decided to go with my game design which was inspired by the classic puzzle game Chip’s Challenge, with the idea being to reimagine it and modernise the graphics.

Game synopsis:
 “‘Bit’s Blitz’ is a fun 2D puzzle game following the escapades of its protagonist ‘Bit’. The game takes place across a series of levels increasing gradually in difficulty, gradually introducing new game-play elements. The player controls ‘Bit’ around a grid, constrained by a series of maze-like blocks and hazards. ‘Bit’ must successfully collect all the computer components that are scattered around the level and then repair his computer to proceed to the next level.”

Details:
Developed using C# and the XNA framework for the PC platform (Windows XP+).

 

The nice thing about this game design was that we could focus on the puzzle aspect of the game, time and imagination permitting, due to the simple overhead on technical implementation. The tile-based game engine was written from scratch using XNA, utilising XML data structures to store level data and a custom made loader. A cool and free little program called Tiled was used to ‘paint’ the level layout and export it into our XML format. I’d strongly recommend this to any considering 2D tile-based games for constructing levels, having said that, it’s a nice programming exercise to develop your own editor if you get the chance.

All gameplay aspects including animations and particle systems were programmed for the game, using no other libraries except XNA. I designed the game framework based on the State Design Pattern which worked out really well and continue to use it for game development.

With the use of XML and Tiled it allowed us to churn out level designs at an alarming rate and the final product has over 20 levels! Not bad considering the 2 week development time. When giving the presentation of the game, we literally only had time to demonstrate about 5 of the best levels, odd considering level variety tends to be in short supply for prototypes.

Sound effects were added (free assets) however I’ve removed these from the video and added music since honestly, they weren’t brilliant! The above gameplay video demonstrates various levels (played by me). I could barely remember most of the levels so it’s pretty much a blind play-through with some genuine mistakes.

For the project we all chipped in and the group worked well together. The game was never released or published anywhere, though if anyone is interested I could stick the executable on here for download.

Solar System Orrery – HTML5 Canvas

Featured

Orrery Zoom

For quite a while I’ve been trying to get around to arranging some web hosting and putting my solar system Orrery online for people to access, I’m pleased to say I’ve finally got around to doing it.

(Click here to go to the Interactive Orrery)

The project was part of the 2D Graphics module course work for my Computer Science degree. It’s written in Javascript and utilizes the powerful HTML5 canvas for rendering.

It’s not an accurate scientific representation, however the planets distances are to scale in relation to each other (not in relation to the sun) and the frequency each planet completes a full orbit (year) is also accurate to real life. There are two orbit modes ‘circular’ and ‘elliptical’ and also two simulation modes where acceleration and velocity is calculated based on the mass each object and thus the force of gravity. One simulation mode keeps the Sun centered while the planets orbit around, the second mode allows the sun to be affected by it’s orbiting bodies.

elliptical

It’s really a bit of fun and you can create new planets of enormous size by simply holding down your mouse on the simulation until your happy with the size and let go and watch how all orbiting bodies are affected. You can also flick the planet when your holding it at the same time of release to set its starting velocity (seems to work much better in chrome then IE). I also highly recommend running it in full-screen mode by pressing ‘W’ if you have a reasonable spec system.

Another cool thing is the zoom feature, if you pause the program via ‘P’ you can scroll around with the cursor keys and take a look at some of the relatively hi-res images I used for each planet. The Earth and orbiting Moon is pretty cool to zoom right into as pictured above.

Detailed instructions are available on the page. Please check it out here and have a play around: www.alexrodgers.co.uk/orrery

simulation