Gamasutra: The Art & Business of Making Gamesspacer
View All     RSS
September 1, 2014
arrowPress Releases
September 1, 2014
PR Newswire
View All





If you enjoy reading this site, you might also want to check out these UBM Tech sites:


Opinion: The difficulties of an infinite video game world
Opinion: The difficulties of an infinite video game world
May 2, 2012 | By Alex Norton

May 2, 2012 | By Alex Norton
Comments
    16 comments
More: Console/PC, Design



[In this reprinted #altdevblogaday opinion piece, Visual Outbreak creative director Alex Norton shares how his team set out to create an infinite, procedurally generated game world.]

Procedural generation is definitely in vogue, and I personally have believed that it is the way forward in video gaming for many years now. Using procedural generation in games is nothing new of course, as fans of games such as Elite or The Sentinel will know that we've been seeing it in games for a good 25 years.

Older titles made good use of it due to the memory constraints of the hardware of the time. It was simply more efficient to have generated levels rather than hand -rafted ones, but that is no excuse for games not to make better use of it now that we have better specced hardware.

Fans of the RPG genre will no doubt remember The Elder Scrolls II: Daggerfall, which had one of the largest in-game worlds ever seen, and still to this day tramples almost every RPG made in terms of world size. I recall reading somewhere that the in-game world of Daggerfall was equal to twice the landmass of the British Isles.

That is a heck of a lot of world to explore, and – from a game design perspective – a nightmare to recreate by hand. Through clever use of procedural generation, however, it is easily possible, which is what Bethesda Softworks did with Daggerfall. The settlements and towns were hand-crafted, with the wilderness in between being generated by the game.

But why stop there? Why have world borders at all? Procedural generation code hasn't changed much in the last 25 years. People are still stuck using fractals and diamonds and blobs to do everything, which becomes repetitive and quite simply looks like procedurally generated content. To any programmer looking at it, it virtually smells of procedural generation.

On top of all this, if you get it wrong, it will end up VERY wrong. The indie crowd seems to do it best, with titles like Dwarf Fortress generating MASSIVE worlds with lush histories and more world than you could ever hope to explore. But still, they aren't pushing the envelope.

My aim was to fix that by making it work. An infinite game world should be possible, and indeed it is.

The idea

Just over two years ago I began assembling a team to make the first truly infinite, fully 3D fantasy RPG, entitled Malevolence: The Sword of Ahkranox. It was to be played in a style similar to the classic grid-based, first person RPGs of the late '80s and early '90s such as Might & Magic, Eye of the Beholder and Dungeon Master, but set in a literally infinite world.

We had originally thought to make it a planet-sized world, but in the end decided on the story being that the game's world was being created within the imagination of a sentient sword, which would act as a way to "explain" the infinity of it.

After much experimentation and very complex math, we got it working, but all in raw data. Nothing really playable. But we had in front of us an infinite world filled with infinite dungeons and infinite cities filled with infinite NPCs. We then worked to get a game working in such a world (some of the efforts of which, you may have read about in my last post).

Now, just to confirm, this world wasn't being randomly generated. It was both infinite AND persistent. Without going into too much detail, this is achieved by making the world dynamically affected by the passing of time. Every part of the world is identified as either affected by time or timeless. The lay of the land with its hills and caverns… That's all timeless, and never changes.

Because those parts never change and cannot be affected by the player, they only need to be loaded into memory when the player can see them (or if they are needed to generate quest information, etc). However, if an object is affected by time (for example, the contents of a chest), then they have a time coefficient applied to the procedural algorithm that generates them.

This means that a chest in a dungeon, for example, will have different items in it depending on WHEN the player opens the chest. If the player was the clear out that chest, that act is stored in a database of player changes, but then re-set when a certain amount of time has passed. This ensures that the database of player changes to the world never exceeds a certain size (which is estimated to be around 250mb at the very most, but more realistically around 50mb)

This generation accounts for almost everything in the game. Spell creation, item creation, weapon creation, potion creation, NPC dialogue system, even the spell effects that happen on the screen.

Due to this, the world that the player explores will be ever-changing and infinite. They won't keep finding the same old weapons or items, there will be no end to the number of spells they can find or use, they won't even keep having the same conversations with NPCs. This is necessary to keep a player interested for long enough in an infinite world.

Public acceptance

Back when the game Elite was first being worked on, it was planned to have around 282 trillion galaxies with around 256 star systems in each one, but their publisher, Firebird, were worried that such a large in-game universe would be intimidating to players and put them off. I have to say I had wondered at that, and was interested to see how the public would react to an even bigger in-game world.

I was surprised at the results.

We've been quite public with our development process for the game so far and generated a small cult following on communities such as IndieDB, but very few people seem to quite grasp the scale of an infinite world, despite our thorough descriptions of it. We had put up renders of the world generation data, showing just a tiny fraction of the world:


And then, we showed them this:


That inland sea is around the size of the entire in-game world of Skyrim. Funnily enough, the largest response we got from this information was disbelief. Many called us liars and that it simply wasn't possible. Others began to believe that the world size of Malevolence was the entire above image, rather than infinite. Only about 20 percent of people really understood.

So, from a marketing perspective, it's been a bit of a nightmare to have an infinite world. We've even had many suggest that Malevolence is just a rip-off of Legend of Grimrock, despite the fact that Malevolence was started about a year before. But that's always going to happen, no matter what the game. What happens upon release will happen, and that's just how the cookie crumbles with game development.

Funnily enough, that hasn't been the hardest bit. The hardest bit has been the math involved in making a world like this one.

The Math

Being infinite, procedural AND persistent, most of the mathematics behind Malevolence is theoretical math – that is, mathematics with few or no fixed/known values acting in a volatile space. But we've broken the world creation down into multiple layers.

The first layer is the one you saw above. A large world segment is generated which covers an area of about 400x400km. This is the only layer of the game that uses a standardised procedural generation system (perlin noise)

That is then broken down into chunks that are around 3x3km, calculating the biome information within that area, like so:


In the end, all of these steps need to be completed when each new world segment is generated in order to turn the raw data into this:


That is just for the overworld. Every world segment that is VISIBLE to the player (as in the view above) is given a unique code, generated by the procedural algorithm. If there is a dungeon entrance in that segment, the dungeon is generated using this unique code, ensuring that every time the player returns to that spot, the same dungeon will be there:


This same method is used for town generation, graveyards, ruins or anything else that the player may encounter. And this goes on forever. If a player was to turn off collision and hold down the 'move forward' button, it would take them just under three weeks to walk from one end of a world segment to another, and then they would simply move to a new world segment seamlessly, and then another, forever.

The biggest question we have been given is how we have dealt with the data type limitations on player co-ordinates, but unfortunately we can't give away all our secrets :) But I can tell you that Malevolence doesn't suffer from the Minecraft world-edge issue, it just keeps going on and on.

Conclusion

Using procedural generation in your game can be a rewarding experience, but definitely don't rush into it. It takes good planning, clever usage and most of all it needs to feel seamless, otherwise the public simply won't accept it.

If you'd like to read more about Malevolence: The Sword of Ahkranox, you can check out these links:

[This piece was reprinted from #AltDevBlogADay, a shared blog initiative started by @mike_acton devoted to giving game developers of all disciplines a place to motivate each other to write regularly about their personal game development passions.]


Related Jobs

Aechelon Technology, Inc.
Aechelon Technology, Inc. — San Francisco, California, United States
[08.31.14]

Geospatial Engineer
Aechelon Technology, Inc.
Aechelon Technology, Inc. — San Francisco, California, United States
[08.31.14]

Geospatial Modeler
AtomJack
AtomJack — Seattle, Washington, United States
[08.29.14]

Level Designer
GREE International
GREE International — Vancouver, British Columbia, Canada
[08.29.14]

Senior Game Designer










Comments


Wylie Garvin
profile image
The real difficulty with an infinite video game world is that you can't make an infinite amount of meaningful story content to fill it with. The human touch is still an essential part of storytelling, in games as much as other media. No matter how good the procedural content generator is, I don't think it will be able to take players along a meaningful emotional arc through the events that happen to the characters. There's a reason why games like Diablo have a fixed length and human-authored story content even though the levels, monsters and loot are randomized.

David Navarro
profile image
That's only an issue if "a meaningful emotional arc" is what you're after. I admit it has been a long time, but I don't remember "meaningful emotional arcs" in Elite, for example.

Mathieu MarquisBolduc
profile image
I believe there is room for the whole spectrum, from story-based, heavily directed games like Uncharted or complete sandbox games like Dwarf Fortress, and everything in between. In sandbox games its not about the stories the game tell you but the stories you create. If some think they can't be fun enough...

http://www.nzfortress.co.nz/forum/showthread.php?t=20768&p=1

Thats an example among thousands. As an EA guy once told me, in the end its about the player experience. You want the player to tell his friends what awesome thing happened while he was playing that game, wheter its the result of a scripted story or deep, emergent gameplay.

Moses Wolfenstein
profile image
I definitely agree with Mathieu and it actually ties into the post I reblogged here a little while back about how games are not monolithic. Video game technologies can create so many different types of experiences. There's a wonderful future for games that leverage procedurally generated content just as there will continue to be space for "big narrative" games that engage the player primarily through story, not to mention a whole array of other game types including competitive and cooperative games where the value comes primarily from other players. It's why I love this medium. It does so many things so well, and we arguably haven't even seen the best of it yet.

Oh also, great post. Very interesting read.

Matthew Wells
profile image
This is very cool, but aren't you running the risk of destroying the joys of shared player experience with this sort of thing? I could post on a gaming board about the difficulties in completing The Snow Storm mission in GTA4 (well, I could a few years ago), and everyone would instantly know what I was talking about. If we're all just tunnelling through our own narrow subsets of your vast world, it seems like a lot of that social aspect is lost.

shayne oneill
profile image
One of the biggest "shared story experience" games on the net, in terms of the ability to make players tell stories is dwarf fortress, whos world wasn't just procedurally generated, it was random for each player too. But thats because its so damn complicated an incredible amount of emergent gameplay comes out of it.

Actually come to think of it, so is minecraft, which is actually rather simple, but all about emergent gameplay.

Chuck Bartholomew
profile image
I think the combination of a procedurally generated world like the one described here and something like Skyrim's radiant story system could be used to imbue a compelling, hand-crafted narrative into an infinite world. The radiant story system allows for placeholders to be left open in a quest or storyline to be filled in later. Such a game would be very difficult to write a play-through guide for, though.

Jeremy Reaban
profile image
I'll be darned if I can find it again, but back in the 1990s there was a computer utility for Spacemaster (the pen & paper RPG from Iron Crown Enterprises) that had a procedurally generated galaxy.

And by that, I mean not only stars, but planets. And not just planets (which Elite 2 & 3 did in 3D), but cities, down to the street level and buildings.

All using ASCII graphics, since it was the mid early 90s. But still one of the most amazing things I've seen. Wish I could find it again, got it from a BBS

shayne oneill
profile image
I wrote a little galaxy generator in python with eve online style jumpgates a bunch of years ago and posted it on the eve forums here:http://community.eveonline.com/ingameboard.asp?a=topic&threadID=7
46406Folks are free to play + do things with it if they want, its a bit clumsy and naive.. Iiterative experimentation code.

Craig Page
profile image
I think the biggest difficulty would be remembering where you parked your horse.

Chris Moeller
profile image
Very cool article!

Just being able to create a "infinite" procedural world is a great feat, and definitely something you can do a lot with.

In reality, not many players will probably go and try to explore the infinite world- there will still be some type of 'finite' bounds, if nothing else their curiosity.

Still, using it as a selling point is a good idea, but it's probably not one of the main reasons people might play.

I remember playing GTA San Andreas- just driving along the freeway, from the city into the country, with cabins, different vehicles, ect, that was one of my most exciting game moments- it made the world feel almost alive.

I never really tested to see if I could fall of the edge of the world somewhere, but having many different environments to explore left it exciting.

Still, I only played until the story ended as well as exploring the content the designers had felt most important. Have to balance it with unique experiences- a game can never truly be infinite, gamers will grow too familiar and move on to a new world to explore.

Tadhg Kelly
profile image
Impressive.

And yet the issue that I always come back to with procedural techniques is sameness. It's possible, for example, for space-trading games to generate masses of data, from geography to missions. And yet they often feel very samey, lacking authorship or direction.

Michael Joseph
profile image
No way to alleviate the problem if nobody is trying.

Nick Harris
profile image
There are four solutions to this:

1. Go the MMO route where you rely on the actions of a great many collaborating clans of players to create their own economic and political history in which you get to play a part or simply be a witness (like EVE Online).

2. Pretty much the same as 1. except all the other players are controlled by the computer.

3. Pretty much the same as 2. except the game continually tries to assert its underlying theme, abandoning all hope at a prescripted narrative in exchange for equivalent dramatic resonance. Can such cheats and contrivances make the player adopt a role whose character arc is funnelled towards a resolution? Can dramatic structures shape an open world experience by setting up a scenario with off-stage NPCs in the hopes that the player will stay in-character, continue to care about the responsibilities that they had taken on earlier in the game (e.g. rescue the princess), triggering generic transition graphs that work with whatever matching characters are availiable when a fuzzy pattern of game state is encountered to encourage them towards a key objective and a further commitment - or will the player just "muck about" blowing random stuff up? Is it sufficient to make the game reward the player for the quality of their role play, not merely their kill/death ratio? What if the theme required their role play to result in a heroic sacrifice? "Game Over" could always be replaced by "Adventure Abandoned" if the player came over all GTA and shot an RPG at a schoolbus when he should have been trying to finesse a girl into a first date at the local bowling alley? Would it be so terrible if these worlds remembered our psychopathic acts and hunted us down to permadeath as punishment for our juvenile attitude to a maturing art?

4. Pretty much the same as 3. except with cooperative multiplayer. The problem with player versus player is that of discontinuity in long-running campaigns: you don't want everyone to be forced to play 24/7 for fear of their avatar being smothered in their sleep. Yet, a group of friends can agree to only play through a cooperative multiplayer campaign when they are all online, so that if any of them pauses none of them can play in the meantime and the game world's clock effectively stops. Consequently, pair-play on the same TV is an appropriate medium for this.

Are these role players merely gamers seeking to identify the underlying ruleset and subvert it for an easier win, or are they capable of being rehabilitated towards non-psychopathic empathy and authentic pantomiming through game mechanisms that reinforce "correct behaviours" (like the use of the bounding cover manoevre in Full Spectrum Warrior)? Why did I adjust the accuracy, heath and reaction time of the enemies in the 007 Mode of Goldeneye on the N64 once I'd completed the game, if not to see if I was finally good enough to "be Bond"? Okay, given my over-familiarity with the levels in the game I could only claim to have managed to be Pierce Brosnan competently hitting his marks in a distorted echo of the original movie, but it was close enough to fuel my childhood fantasies of what it would be like to work for MI6, rather than the humdrum paper-pushing reality.

R Hawley
profile image
Funnily enough procedural content is something I'm just returning to after 15 years so this was interestng to read. Way back we generated galaxies with solar systems down to individual planetary surface textures and mining content for SuperVGA, using Kepler and Newtonian laws to shape systems.

As for explorable worlds of infinite size and lack of direction, well, the greatest quest of them all comes to mind. The quest for the Holy Grail, an unreachable goal where the journey is more important. The story of Monkey aka Journey to the West, Star Trek. There's too much focus on story sometimes. Sentinel, Minecraft, Elite. Telling your own story can be as interesting especially if they can be shared. The whole procedural idea can take a backseat and enable some compelling mechanics IMO. All very exciting, I look forward to seeing where you take this.

Josh Foreman
profile image
I'm really excited for the possibilities inherent in this concept. Ever since reading Infinite Game Universes back in the 90's I keep waiting for someone to make a quality proof of concept. I've got my design sitting on my hard drive waiting for the day. Hope this game can be what I've been waiting for!


none
 
Comment: