Please note that all screen shots displayed in this blog are works in progress and in no way represent the appearance of the final game. Check out the main site here.

Be sure to follow us everywhere with these links!



Tuesday, March 6, 2012

The Mathematics of Infinity

So we've been engaged in some pretty heavy stuff lately... Making an infinite world is definitely not easy. Doing it purely in memory? Yeah, that's pretty easy... But getting it to render into a world that you can explore? That's some serious math right there...

But we're not afraid of math. We're afraid of being eaten by a Grue, but we're not afraid of math.

"Why is it so hard?" I hear you ask? I'm glad you asked...

Complex procedural worlds are like onions... Or cakes... Or parfait... They have layers. A simple procedural world is as simple as just generating a fractal, but a complex one? With heightmaps? And water bodies? And biomes? Frikkin biomes! That's what makes it complex, and there is much more to it than simply generating a fractal (or diamond or blob, etc)

"What is a biome?" you say? A biome (for all the non-Minecraft players in the audience) is an area of a game world containing a particular climate or biological community. For example, an icy tundra is one kind of biome, whereas a rainforest is another. The world of Ahkranox is made up of biomes so that after trekking through the desert for miles you will eventually reach some mountains, or a forest, etc.

 Our planet is covered in biomes

Biomes are huge, spanning incredibly large areas and encompassing all within. To simulate this artificially, however, takes a large amount of complex mathematics.

"So why have them at all?" I hear you cry. Well, the simplest reason is the weather. Ahkranox is an infinite and persistent world. That's the key word there - persistent. That means that none of it is randomly generated. Because of that, it would make no sense to use randomly generated weather patterns so that one day it's snowing in Rhuthgart Village and the next day it's happy happy sunshine. Biomes keep the weather consistent, so that if you buy a house in the ice encrusted town of Ghurthak, then go questing in the sunny Wytchmeadow Fields, when you return home, your house still has a thick layer of snow on its roof. And we need that to happen EVERYWHERE in an infinite world.

"So how on earth does that work?" you ask? Well, that's what this blog entry is for. We've had loads of request for more technical information pertaining to the game. We can't give away too much about how we do the infinite thing for copyright reasons, but we can still show you a fair bit!

Like we said earlier, before Malevolence can show you the overworld like this:


It needs to generate a lot of information. Here's a quick rundown:


First of all, tier 1 needs to be generated in memory. Tier 1 is a rough imagining of the world around the player for about 500 miles in every direction. This is procedurally generated using the player's greater world co-ordinates, which keep a track of where in the world of Ahkranox they are. Once this is generated, it finds what colour the pixel is at the player's local world co-ordinates, which keep track of where the player is within their current greater world segment (In case you're wondering, there are 512x512 local world segments within a single greater world segment, and an infinite number of greater world segments). Based on the colour of that pixel, the biome is recognized. From this pixel, and the pixels surrounding it, the local world segment (tier 2) is generated. Why the second world segment type? It has to be done so that the player will see the edges of biomes approach as they walk towards them. It wouldn't do for the player to take a step and then *POP* be suddenly standing in a snowy version of where they had been. To prevent this, we generate the local world segment and work out where the edges of any nearby biomes are. Once the tier 2 segment is generated, we then look at the player's terrain co-ordinates and find where in the local world segment they are standing. There are 10x10 terrain segments within each local world segment. Of these, the player's map co-ordinates are used to find a grid of 3x3 of their local terrain segments (tier 3) to generate the terrain that they can actually see. This includes much more detail than before, such as flora, fauna and objects such as towns and whatnot. At the same time as this is happening, however, tier 4 is also being generated. Tier 4 is the player's local heightmap. This is responsible for generating the locations of hills and lakes, etc, which the player must traverse. The reason that this is done simultaneously is so that trees do not grow on the sides of cliffs or in the middle of lakes, etc. All of the details in the world are generated according to the heightmap and the current biome (for example, there isn't an abundance of flowers in an arctic biome, but there is in a forest biome)
Once all of this data has been processed, the 3D world can be created for the player to see. The player can walk about 100 meters in any direction before it needs to be generated again. However, the Hellfire 2 engine (upon which Malevolence is built) can process all of this information so quickly that it happens in the space of about 0.02 seconds. So, at most, the player will experience a tiny delay when moving between world segments (which you would have noticed in previous videos) which is really a very small price to pay considering that the world is infinite.

So hopefully that gives you a bit of insight into the complexities of this game!

On a more fun note, here's a video of procedural water bodies forming based on the world's heightmap (you can see the heightmaps generating in the top-right!) and you even can see some underwater temples spawning! Hours of fun!


So that's it for now. I hope this has been enlightening for you! More on the biomes when they're done and working properly!

3 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. Amazing to actually read and see that someone has actually designed and created something so similar to what I envisioned years ago after playing NWN's Infinite Dungeons.

    I thought, if you can do this, then you can create a world. Have the world be "static" and either have a random starting place for the "New Game" or a static location depending on player's Race.

    Then have the game, based on the longitude/lat. pull "item packs" central to that particular Global Location. Like you wouldn't see an Igloo in a Central Plains region ;)

    Then it's like a top down process. With the game using and placing items that makes sense for that area.

    I actually did a somewhat lengthy breakdown of the idea on the Titan Quest.net forums, discussing new IP game ideas.

    http://www.titanquest.net/tq-forum/threads/29748-Setting-for-new-ARPG/page5?p=330753&viewfull=1#post330753

    Back in 2009 :)

    So as you can see we have some similar ideas & concepts :)

    That said I will be more than happy to join the Kickstarter process!

    Very Best Regards & Best of Luck on the coming Launch. Will be anxiously awaiting and watching the progress in the months to come :)

    MM

    ReplyDelete
  3. I am curious if there will be sharp cliffs and canyons in the game world? Rocky terrain, forests, deserts, grass lands, patches of wild flowers, etc.? The more variety the more fun there is in exploring.

    Also, the more remote the area are the monsters more dangerous, rare, etc.?

    ReplyDelete