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.

 

 

Dungeon Master – An Iconic RPG

Box Art

Box Art

Aged probably no more than 6, I looked on in excitement and fear at the Amiga monitor. My parents were playing Dungeon Master again, it’s labyrinthine dungeons, fiendish puzzles, stunning graphics (for the time) and always death, waiting around the next corner.

Dungeon Master was a pivotal game of my childhood, it taught me how real and immersive games could actually get, despite computer limitations. Using a 2D perspective trick, it could render a seemingly 3D environment as if seen from the eyes of the player. This of course was an illusion, but it did it so effectively, that it stood out back then with hugely impressive visuals. It wasn’t just nice to look at though; featuring groundbreaking level design and puzzle concepts, being brutally difficult but still rewarding; there was something about it that left a lasting impression on you. It was a little like the Dark Souls of it’s day.

Although there had been other well known ‘dungeon crawler’ games (as they came to be known) like Bard’s Tale and Wizardry, it was DM that really culminated the best attributes of the genre, distilling it into what is in my opinion the best of the lot, even to this day. It’s no coincidence that Almost Human’s ‘Legend of Grimrock’ in 2012, cited Dungeon Master as large inspiration and something that is clearly evident having finished Grimrock and noticing many ‘tips of the hat’ to DM’s puzzles, mechanics and creatures. All those puzzles of putting an item on a pressure plate to close a pit, or placing a torch in a wall sconce to open a secret door hearken back to this era.

DM was in fact the largest selling title of all time for the Atari ST, whose version differed only mildly from that of the Amiga, with the latter featuring improved 3D sound effects where most noticeably, you can hear creatures moving around with unnerving effect.

Using the free Amiga emulator WinUAE the past week, I have finally finished Dungeon Master after all these years. I loved every second of it, scarily so, because I was telling myself continually throughout, “why am I playing a 27 year old game in this day and age?”. Irrespective of the answer, I had more fun playing it then most state of the art games I have played recently! Why? Well, many reasons, the challenge and immersion are two, but ultimately, I guess I’m a pretty hardcore gamer and there’s just something about playing old school classic RPG’s, a charm or ambiance if you like, akin to rolling that dice in a pen and paper D&D game. I’m sure many can empathize with that.

A pack of skeletons.

A pack of skeletons.

Dungeon Master does have a story and plot, though sparse and not a driving force for the progression of the game. It revolves around having to descend into the depth of the mysterious dungeon and find an artifact known as the ‘Firestaff’, as tasked by your master ‘Lord Order’. Ultimately, if your party survive the horrors long enough, you come across writings detailing the evils that will occur should you complete this quest and instead come to realise that you must descend to the deepest depths of the dungeon, combine the staff with the ‘power gem’ and defeat ‘Lord Chaos’ (think Sauron), restoring ‘Balance’ to the world.

You start the journey in the ‘Hall of Champions’, a place at the start of the dungeon where you can look upon windows on the walls and see magically suspended heroes, whom you can either ‘resurrect’ or ‘reincarnate’ to join your party, up to a total of four party members. Resurrection ensures the character maintains it’s identity, combat skills and experiences whereas reincarnation allows you to rename the character, forfeiting their skill set, but gifting them enhanced physical attributes so to enhance learning and allow you to shape the character as you see fit. Ultimately, the tried and tested composition of two fighters at the front, a priest and a wizard at the back worked wonders for my play-through, though having four ‘jack-of-all-trades’ is viable too. As 2012’s Grimrock, the party moves through the dungeon in 1st-person view in a 2 by 2 formation, meaning that only the two members of your party at the front can reach enemies with melee weapons, with the back two having to rely on ranged, throwing weapons and spell casting. Consequently, only the front two will take damage from the front, and if a ‘baddie’ creeps up behind you, your squishy casters won’t be very happy. Part of the the games meta strategy, involves you being able to change your players around in the formation at any time e.g if your front fighters get wounded, you can swap them out with the back.

Character Inventory.

Character Inventory.

The predominate theme of the game is undoubtedly ‘survival’. Staying alive is really, really not an easy thing unless you have learned the tricks and techniques generally gained after many horrible deaths, whether that be to the jaws of giant worms, starvation or plummeting down a pit arriving several levels lower than you could possibly hope to deal with. The only items you have at your disposal are those you find along the way, and that way is strewn with illusory walls, guarded chests, locked doors and secret passages that without consulting a guide or a printed map, you have little chance of ever finding yourself (hand holding pfff who needs it?). Even basic concepts we all take for granted in games today such as being able to SEE, is a premeditated game mechanic in dungeon master, where the dungeons are pitch black without a light source and torches are scarce, making the use of a wizard or others with the skills to cast ‘light’ spells essential.

One of the  most memorable mechanics which is still pretty innovative today is the magic system. To the right side of the screen are a bunch of runic symbols. The boxed game’s manual documented an alphabet of these symbols describing there purpose. As you cast a spell you first choose a rune representing the ‘power’ of the spell, would you cast a short duration spell or a potent offensive spell for instance? Then sequentially you chose the spells ‘elemental influence’, ‘form’ and ‘alignment’. It all sounds rather complicated but when you know off by heart that a weak fireball is LO FUL IR and a potent healing potion is PAL VI, it starts to become second nature, especially when you realise you can drop the power level if your priest is low on mana and make a weaker healing potion like LO VI for instance. In combat, you would be expected to click these runes in the correct order at the heat of the moment, you soon realised that if you didn’t ‘get gud’ and memorise them, then you simply got ‘dead’. In a funny kind of way, it really did feel like you were learning magic and having to go through the motions to learn and cast the spells your party depended on and I love that.

These runes are used to cast all the games many Wizard and Priest spells.

These runes are used to cast all the games Wizard and Priest spells.

Other mechanics such as food and drink meters for each character really puts that hanging dread over your party for the entirety of the game, since you never know when your next meal is coming up and when you’ll see a fountain again to refill your water skins. Realising your lost deep somewhere with no water left and down to your last couple of hunks of meat is pretty terrifying. Luckily though, some of the critters are edible if you can kill them, ‘Screamer Slice’, ‘Worm Round’ or ‘Dragon Steak’ anyone? Yum!

A water fountain, always a welcome sight!

A water fountain, always a welcome sight!

Having finally finished the game after all these years, I felt an immense sense of accomplishment because it’s a game that I grew up thinking was simply too tough for me to contend with, and to be fair, me being less than 10, it probably was! The end showdown with Lord Chaos is no simple matter. Once you have collected all the ‘Ra keys’, broken into the vault of the Firestaff, defeated it’s Stone Golem guardians and retrieved it, you then have to descend to the last level, defeat a wingless dragon and free the power gem with a spell you better have learned along the way or your buggered! (*cough* Google). You then must combine the staff with the gem, creating an ultimate weapon and then go back up a level and find Lord Chaos. Using the staff’s power you must surround him with ‘Fluxcages’ and finally ‘Fuse’ him to restore ‘Lord Balance’ and beat the game. If that sounds straightforward, it really isn’t, especially considering even if you do figure this all out on your own from a subtle hint in an very well hidden scroll, you have to do all this while being attacked by demons, black flame elementals and Chaos himself flinging fireballs at your face!

Defeating Lord Chaos and restoring Balance.

Defeating Lord Chaos and restoring Balance.

I’m currently now playing through it’s sequel ‘Chaos Strikes Back’ (Yes…it really IS called that) and it is unbelievably hard, as in Dark Souls has nothing, not a bean compared to this in terms of difficulty. CSM will eat you alive and then spit out your regurgitated remains for a second helping. Firstly, the sequel starts at the same difficultly level that DM ends at. You can import your characters which you may think will help and sure enough it does a little, but little prepares you for the first 10 seconds of the game which pretty much goes like this:

“Ok, let’s go, hmm it’s pitch black…where am I? My party is naked with no weapons…I can hear things moving around me…let me cast a light spell. That’s better! SHIT there’s four armoured worms in here with me and no exits…no wait, SIX worms…EIGHT….I’m surrounded…can’t move….DEAD.”

That’s your first taste of Chaos Strikes Back, shoved into an infested pit of worms with no weapons and no obvious way out, but like Dark Souls, I still love it.

As reported in 2012 in a Rock, Paper, Shotgun article here, one chap amazingly spent 6 months, eight hours a day of his own time, programming 120,000 lines of code to port the Atari ST version, creating a C++ executable version that runs today on any modern PC. It can be found here free: Chaos Strikes Back for Windows (and Linux, MacOS X, Pocket PC)

For those used to emulators, by getting hold of the Amiga .adf ROM file (basically an image of the game disk), you can run it in WinUAE (my personal preference for the better sounds) but ultimately, only ex-Amiga junkies would likely do this over the ported PC version :D.

Dungeon Master is a truly iconic game that has undoubtedly influenced many great games, not just across the dungeon-crawler and RPG genres like the classic ‘Eye of the Beholder’ series or recently the ‘Legend of Grimrock’, but also modern popular AAA titles such as the Elder Scrolls. It’s a testament to it’s influence that the game still has it’s own updated Encyclopedia site: http://dmweb.free.fr/  and even an online message forum with an active and thriving community: http://www.dungeon-master.com/forum/.

I would encourage anyone who is curious about classic RPG’s games, interested in why modern games are like they are and all that jazz to check out old titles like Dungeon Master, because although the graphics leave much to be desired by today’s standards, the game play is still truly as good as it ever was. It’s clear there is still much to wonder and marvel at, in both game design and execution in this old gem.

My party in the hall of fame after beating the game!

My party in the hall of fame after beating the game!

 

Falling In with Fallout

fallout-3-1010-small

Over the course of the past year I’ve been working my way through the newer Fallout games specifically Fallout 3 and New Vegas. I finished Fallout 3 a couple of months back and when I say “finished” I mean 95%+ of all the content, I completed every expansion pack except for Mothership Zeta, visited nearly every location in the world maps (184 out of the 200+ excluding Zeta) and generally lost myself in what is in my opinion one of the finest role-playing experiences to be had.

Getting It…:

I didn’t always feel this way about Fallout 3, like many I played it when it first came out and meandered through it for a few hours before losing my way and getting rather bored trawling through endless metro stations. I decided to pick it up and give it another crack several years later and have never looked back since.

I’m not sure whether its myself that changed or not but this time the games magical atmosphere enthralled me and I can say happily I loved every minute of it. The dawning realisation that Fallout 3’s strength is not in it’s rather mediocre storyline but the sandbox and open world game play. This game has that incredibly hard to come-by feeling of authenticity that allows the game through your imagination to create it’s own believably unique stories from your actions with your character and the decisions you make throughout playing.

2012-09-27_00005

An Authentic World:

The authenticity of Fallout 3’s world is achieved from a variety of factors and surprisingly barely any of them from actual talking NPC characters. Most of the atmosphere is created through the futuristic 1950’s themed timeline that emanates charm, naivety and an innocence in stark contrast to the brutal and barbaric post-war world.

The world is also sentimental which on a personal level is quite touching. Imagine if the world had been destroyed and your a generation of survivors who have only known the wasteland of the aftermath, how would the ruins of the past world seem to you? Would the world before Armageddon seem alien to you or comforting? To see the pre-war world frozen in time as the atomic bombs hit, families huddled in their homes, people going to work, people packing their bags in preparation of the nuclear war but clearly too late, you wander the wasteland of the old world and can’t help but be touched by the sentiment created by Bethesda. Pompeii and it’s destruction at the hands of Vesuvius draw eerie parallels, today you can still wander the ruins of the city and see it’s citizens frozen in time by the molten ash flow that covered them.

Untold Stories:

If there were anyone who worked on the Fallout games (both Fallout 3 and Obsidian’s New Vegas) who’s hand I’d like to shake the most it’s those responsible for the creating the myriad of untold stories that litter the wasteland and these people as much as anyone help forge that authenticate world.

Times such as walking into a shack and seeing a skeleton in a bath-tub…with a toaster are moments of genius that will stay with me. It leaves you wondering, who was that person? Why did they resort to suicide? Were they a good person or bad? Your imagination goes into overdrive and it fleshes out the world beautifully.

I wonder what the story behind this guy was?

I wonder what the story behind this guy was?

Just one of many hilarious easter eggs to be found.

Epic.

The Originals:

Now I’m not going to write an article on Fallout without mentioning the original Fallout games. These of course made a lot of what Bethesda built upon when making FO3, and not everyone thinks that they went in the right direction. Fallout 1 and 2 are brutal games and the world is darker and grittier then that portrayed in FO3 that’s for sure. New Vegas goes some way to fixing this, being an all round darker game but since I’m still currently playing New Vegas I’ll not comment much on it until I’ve completed it.

fallout

I can say that I’m a little ashamed at having not finished the original Fallout games and I will be fixing that when time permits, nevertheless having played Fallout 1 upon it’s release I loved it and it’s influence over all post-apocalyptic games since is apparent (as in-turn is the Mad Max influence over the Fallout universe).

Branding:

Much of the character in Fallout stems from the excellent and original branding established mainly in the original games whether it’s Nuka-Cola, Robco or Vault-Tec or the imaginative array of narcotics and drugs such as Mentats, Jet, Pscho and Rad-X. They are so shoved in your face whether through subliminal advertising in game through posters and artwork or constantly seeing their logos on items and in-game memorabilia that sometimes I have to pinch myself to realise Nuka-Cola doesn’t actually exist and that I can’t just go and buy a bottle!

Probably every main brand in Fallout has some part to play in FO3 and that’s one reason I love it. Whether it’s visiting the Nuka-cola plant and hacking into long abandoned employee terminals or collecting rare Nuka-Cola Quantums for a obsessed fan out in the wasteland you learn about the brand and it’s history and what kind of business they really were. It’s infectious and as of right now my phone is proudly sporting a Pip-Boy HUD picture and my desk has a bobble-head on it.

Late game Enclave incinerator troops are pretty tough, nothing the Alien Blaster can't handle though!

Late game Enclave incinerator troops are pretty tough. Nothing the Alien Blaster can’t handle though!

V.A.T.S:

One thing Bethesda really “hit the nail on the head” with is the remarkable V.A.T.S system which integrates first-person real-time combat with a turn-based location targeting system.   Quite simply, it works and works marvellously. With V.A.T.S combat plays out   cinematically akin to Robin Hood: Prince of Thieves famous arrow view camera. It never ceases to be entertaining to watch limbs and heads explode and even eyes pop out! The violence of the originals was left in place because the Fallout universe is brutal and quite rightly doesn’t shy away from adult themes. It’s no kids game and as such emphasises the brutality of a world in a post-apocalyptic environment rife with slavery, raiders, cannibalism and mutated horrors.

Your typical bloody aftermath from a VATS combat.

Your typical bloody aftermath from V.A.T.S combat.

Conclusion:

I could likely go on far more about the Fallout games and quite possibly will later on when I complete New Vegas. Fallout 3 is a hidden gem in my eyes, it received wide acclaim but perhaps unjustly less so then the Elderscrolls games like Oblivion and Skyrim. It’s likely a topic for a whole new blog but Fallout 3 surpasses the post Morrowind Elderscrolls games in doing what any good RPG should do, creating a believable authentic and original world that you can escape into, and more so Fallout does it with a dry wit which doesn’t take itself too seriously, something Skyrim most certainly did do.

To end on, below are some of my end game character stats from FO3, Garviel the wasteland wanderer was godlike by the end but this certainly didn’t detract from the fun, “one-shotting” heads off with a scoped magnum never did get tiresome!

ScreenShot3

ScreenShot5

ScreenShot25