Sep 19
You weren’t using that 100MB, were you?
So I was grumbling to myself today about how tricky it is to be dealing with such a large world in MMORPG Tycoon 2; since the world terrain is generated procedurally as you move around in the world, it means that data such as the height of the terrain simply isn’t stored anywhere for locations which aren’t currently near the camera.
This can be a problem in many situations. One example is when you have AI developers putting monsters into a quest zone. The AI developers know approximately where the quest zone is, but if the camera isn’t actually near the quest zone, they have no way of knowing what the slope of the ground is, or precisely how high the ground might be. Often, I’ve found that these quest areas end up having all their monsters placed down at sea level, with the terrain being twenty or thirty meters above there, so the monsters can never actually be reached by the players.
As I was thinking about the problem, I worked out the maths and calculated that for the size world I’m talking about (20km x 20km), it would take nearly 100 megabytes of memory to store the terrain height, if I kept the whole world in memory at once. My old-school programmer brain immediately told me that this was complete madness, and threw away the possibility of doing this, and I went back to designing complicated queued fetch-and-correct systems for placing objects when not all the required data was actually present in memory, and it wasn’t until almost ten minutes later that something in the back of my mind clicked, and realised that no, 100 megabytes isn’t very much any more. So I did it.
As a result, I’ve increased MMORPG Tycoon 2′s memory footprint from 256 megabytes of RAM to 384 megabytes of RAM to store this terrain data. (To a programmer, those are nice round numbers; 256 is 2^8, and 384 is 2^8 + 2^7. Aren’t those nice and round?)
Anyhow. I set the game up to procedurally generate the whole world’s terrain when it starts. And on my (rather fast) computer, it takes between 70 and 90 seconds to do so. Which is completely unacceptable to me, so I changed the system to generate-and-cache-upon-demand, which means that the first time you visit an area, it runs at about the same speed as it did before, but is substantially faster each time you revisit an area you’ve been to before. This also solves the “no terrain data for areas which are far away from the camera” problem, solves lots and lots of different of bugs, and actually makes the terrain generation code much simpler overall. I’m quite pleased with how it’s turned out. And I could quite probably create a background thread to generate terrain data for areas you haven’t visited yet, while you’re working on other things.
But it does now use an extra 128 megabytes of RAM. This thing certainly won’t ever be running on the iPhone!
September 19th, 2009 at 11:43 pm
Just throw stuff in. I’m sure that you won’t use up all 4GB of my memory :D
Sounds good though. Will we be getting a play around soon?
September 20th, 2009 at 9:44 am
Perhaps you can abstract the interface to the cache, so that you can come up with a different solution for different platforms. I feel like there ought to be a good way of compressing terrain data on account of how regular it is. It doesn’t change that drastically when you perturb your coordinate in one direction, except for cliffs and stuff.
I had another idea. Can you modify your procedural algorithm so that you can calculate the z coordinate from an x,y coordinate? Or perhaps you can calculate the monster’s z coordinate lazily so that even though the devs place them at sea level, when they appear they appear at the proper height.
September 20th, 2009 at 10:57 am
not that I care about the extra 128MB(I can still run the game maybe 6 times and still have extra RAM), but like the guy above me said(I think) why not make it so things like buildings, toons, monsters, and devs are locked into being on the terrain, but make sure you can mark exceptions and/or offsets so things can hover if need be. This would allow you to keep the game smaller and faster(maybe).
P.S. I didn’t comment, but I like the idea of making the terrain look darwinian. hope that ends well. =-D
September 20th, 2009 at 12:36 pm
@Dan, the problem with lazy calculation of the Z position is that pseudo-random procedural data has a heavy overhead. If its anything like I’ve messed with in the past, the calculation of the Z may include 9 perlin extrapolations and a cosine interpolation smooth routine – which is painfully expensive to do with any frequency.
September 20th, 2009 at 1:42 pm
I stumbled on this site from being reminded of the original MMO Tycoon after playing Majesty 2. I noticed at times I felt like I was watching an MMO from above, the use of a party system and reward/defense flags acting as quests. Of course it’s missing so much to be classed as such and just made me want to play an MMO sim even more!
So it’s great to see you still working hard. I’m a fellow indie developer myself, although the not-as-cool shareware kind :P Indie’s really need to work on the tycoon genre, the commercial developers have killed the tycoon name with some very poor quality titles (Mall tycoon and Prison Tycoon series to name a few). So keep up the great work and give back some respect to the tycoon name! :-D
Wickedgenius: Don’t forget about the 2GB limit per process on 32bit, hehe.
September 20th, 2009 at 2:46 pm
@Dan: I’ve already abstracted the cache interface, so yes, it’s quite possible to change the underlying storage-vs-generation balance without causing any dramas. And the system already is built around the idea of generating the height from a 2D coordinate. As JD later commented, the real issue is that the maths involved in generating the terrain height data is very slow, so I’m trying not to do it too often.
@JD: I’m actually using two passes of 4-octave perlin noise (with different frequencies and amplitudes, rather than a single pass of 9-octave noise that JD mentioned; I find that this produces much more believable MMORPG terrain, than when using a single deep perlin noise source.) And I’m not using a consine interpolation; instead, I’m using 3x^2-2x^3, which gives a somewhat similar interpolation curve but is vastly cheaper to calculate. 3x^2-2x^3 is a topic that I’ve been meaning to write a technical post about for quite some time, now; it’s one of my very favourite things.
@Wickedgenius: Well, it’s still not ready to have people play with it; it’s far too brittle at the moment, as I’ve been kind of ignoring many error situations. For example, the game will crash at the moment if you bring the MMORPG online without having a starting area placed, or if a toon tries to set a home and discovers that none is available. Things of that sort; just handling all the little error conditions properly. But I’m hoping to make a lot of progress this coming week, so we’ll see how far we get. :)
September 21st, 2009 at 6:56 am
@JD WOW “Perlin extrapolations and a cosine interpolation” sounds like some wacko big bang theory episode title to me. though sounds like u tech guys know what ur on about… so this is me nodding and smiling :D
September 25th, 2009 at 10:11 pm
Oops, I appear to have dropped and broken my 100 MB. Guess I’ll need to lend you two 50 MBs until I get to the memory bank.