SWG’s Dynamic World

This post is dedicated to the memory of John Roy, lead environment artist on Star Wars Galaxies. Help out his family here.

 

Let’s do some math. Let’s say that you need to have a pretty big world: sixteen kilometers on a side, and made out of tiles.

A tile needs to know what texture it is. That’s one byte. Not much, right? You only get 256 tiles on a planet, though, which isn’t a lot.

But wait, we can add some variety there, by putting in some colors. We’re in 3d, right, so we can tint the tiles slightly and get variation. It’s normally three bytes to apply a color, but let’s instead just say that each planet has a fixed list of colors, and you can have 256 of them, and that way each tile can look up into a list of colors and we only need one byte.

Oh, and it’s a 3d game heightfield, so we need to know what the elevation of the tile is! We’ll just say that there are only 256 levels of height, and that way we can keep it at a nice conservative three bytes per tile.

That’s good, because we need a lot of tiles. They’re one meter on a side. So that means that for a planet we need 16,384 just to make one edge. We need 16,384×16,384 to lay down the whole world.

That’s 268,435,456 bytes for this world. Of course, we need ten planets, not one. So, that’s more like 2,684,354,560 bytes. Nobody uses bytes, so that’s 2,621,440k. 2,048mb. 2.56 gigabytes, uncompressed.

That’s… not going to fit on a CD. I mean, that doesn’t include any art yet.

DVD drives weren’t yet widespread in 2003. In fact, taking up 2.5 gigs of space just for maps was unheard of.

The solution to that problem didn’t just let us ship Star Wars Galaxies, it also unlocked everything from player housing to crafting to giant Imperial vs Rebel battles.

Patent disclaimer

Before you read any farther, you should know that Sony Online actually patented some of the technology that I am going to describe. If you are someone who should not be reading technology patents, you should stop now.

Origins

I’ve described before how the abortive Privateer Online worked. That game, like other spaceflight classics, was intended to have thousands of worlds. This was going to be accomplished using a neat quirk of how random numbers work on computers: the fixed random seed.

You see, computers don’t actually generate random numbers. They generate predictable numbers using a seed value. To make the results more erratic, you constantly change the seed value — usually by using the current time down to the millisecond or something. There are many routines used in order to make numbers from a seed, but if you take the exact same routine from one computer to another, and then give it the exact same seed you’ve used elsewhere, you should, generally speaking, get back the same random numbers, in exactly the same order.

This is basically a really cool way to compress information. It’s not that different from knowing that given the formula to calculate pi, everyone will be able to get the exact same result out. So it’s a lot easier to just hand around a tiny formula than it is to try handing around a zillion individual digits. The formula fits in a few bytes; the individual digits take up a lot of space.

Each planet in Privateer Online used a single seed, and from it, we picked things like sky color, tile colors, and generated a whole map. So one seed value was enough for a small planet.

But it had to be small — the thing is that there are a lot of randomness generation routines for terrain out there, and they all sort of get… “patterned” after a while. If what you roll up is gentle rolling hills, you are going to get gentle rolling hills fairly consistently. If you have spiky mountains, well, that’s what you are going to have everywhere.

When we got to doing SWG, we had this stuff on the brain, of course. But we also saw that other projects at SOE were doing maps that were meshes. In some cases, they were actually sourced from procedural terrain generators, very fancy ones that you couldn’t run in realtime, and that involved a day-long baking process as the resultant maps were turned into meshes. Once they were meshes, you could run compression and level-of-detail routines on them to reduce their size… but there was still no way to get truly big worlds.

Actual size isn’t the only factor, of course. The granularity of the world matters too. You can have a 16km x 16km world with tiles that are a kilometer in size, and it’s going to take up the same data space as a 16 meter by 16m world. You can also have a game world like that of Eve Online where the vast vast majority of it is empty space; they procedurally generated theirs too, and as a little homage to Douglas Adams, the seed value for their procedural galaxy is the number 42. And it matters whether you can change this world; if it’s rolled up from a seed value, then you can’t exactly go carve a hole in it without storing the actual map in memory. This leads players to spend lots of time debating the right way to measure game world size.

Generating worlds, then, is kind of old hat. The harder part is, how do we make a world as living as possible, one that can change and evolve at a high level of detail, while still having plenty of room?

The layering tool

We actually published a very layman’s version what we did for SWG on the game’s website in advance of launch. You can still find the article on the Wayback Machine. The heart of the idea was marrying Photoshop layers with procedural generation. Here’s a screenshot of the tool from that article.

Shapes like ellipses, circles, and boxes are easily described mathematically. You can say “run this rule when you’re inside this circle, and this other rule when you’re outside of it.” You can say things like “run one rule that gives you gentle changes. Now use that rule as a blend value for how much of this mountainous rule to blend onto a third rule that is grassy plains.” You can see several of these circle rules on the map.

We never did do river generation, though; as a result, the rivers all tended to form loops, because that was what we could make. Water was a simple water table height, and anything under it was underwater. We also added the ability to insert “water sheets” at arbitrary heights so we could do things like the river in Theed, up top of the cliff. Early on we had big dreams about maybe doing underwater play, but that never even made it onto the schedule since it was so improbable.

To give a realistic example: on most all the mountainous areas, we wanted there to be ledges available pretty often. Ledges and “terracing” were easy to create; just say that whatever the mountain routine output, you clamped to a multiple of something. So instead of getting “1, 2, 3, 4, 5 ,6 ,7, 8, 9,” you’d get back 1, 4, 8. But if you do that across the entire map, you get something that looks like wedding cake, plus the areas are dead flat. Ah, if you say “but you should only run that rule in some places, and we’ll decide those places by taking another rule and checking for ‘high spots'” then you get flattening happening in little islands. So you stack the rules in order: Plains. A filter to put mountains only somewhere. Mountains. A filter to put ledges only some places. Ledges. A “gentle wavy” one to make the ledges not dead flat, applied across the entire map. And finally, a circle for a flat area where we need to build, say, Dee’ja Peak. Oh, and we used similar rules to put down color washes; terrain textures, which in some cases came with the wavy grass, and could also come with bumpmaps; trees, plants and rocks; even some sorts of points of interest.

You can in fact stack quite a lot of rules like that, and they still take up very little storage space. The beauty of the rules is that they save out to little text files; a planet on SWG was usually on the order of 16-32k of text. The beauty of something like Perlin noise as a terrain generator routine is that you ask for the elevation result at any arbitrary coordinate. You don’t have to generate the terrain “in order” and it’s not dependent on what is next to it. (I had met Ken Perlin, the inventor of Perlin noise, at a conference a while before, so we flew him out to the office and he helped optimize our algorithms).

This meant that we could use it for graphical level of detail too. Those of you who played may recall the “terrain detail” slider in options, which was capable of bringing your machine to a crawl. At max, what it did was query the elevation for every coordinate, out to your draw distance. At lower settings, it instead started skipping points: every other one, to start, but eventually computing only one out of every 8 or 16 elevations. This resulted in less terrain tiles, way out there, and you could see “popping” as you moved closer and more heights were computed, changing the profile of mountains. It was way way worse with trees, though, because whole forests would pop into view when they were finally above the generation threshold.

Nobody could actually run at max detail and get a decent framerate, at the time. The hope was that as machines grew more powerful, you’d be able to. These days, you could probably just compute the entire planet and put it in RAM on a beefy enough machine. We took our marketing screenshots at everything maxed, and just stood still while taking them. (Our tech director, Jeff Grills, gave a presentation at an AMD event on the challenges of rendering and performance; you can read it here, if you are technically inclined.) Even then, as many players have noticed, the quality of the graphics seemed lower between the early shots and later ones — the E3 demo had more shaders on everything, and better lighting in general. (The drop-off was so big that Gabe of penny Arcade actually wrote a post complaining about it). Most players don’t know it, but the bigger loss was actually on characters, not terrain; early characters looked way cooler, but we couldn’t afford the draw calls or something.

Challenges

Procedural environments have a sameyness to them, though. If you have the rules tweaked enough, they can actually add more detail than a human will, because the algorithm isn’t bound by time constraints. But you need quite a lot of fine detail variation on the rules to get back to where the terrain really does surprise you. Like the real world, most of it is fairly bland. (In fact, one of the classic videogame map tricks is to heighten slopes dramatically compared to the real world; after all, most real world slopes are much gentler than 30 degrees!)

So artists used to handcrafting environments had trouble with this tool for quite a while. I worked for months hand-in-hand with the late John Roy, the lead environment artist, to tweak our best practices and our basic understanding of how to use the rules. John passed away a few months ago, and if you were an admirer of the eventual result in Galaxies, I’d like to urge you to donate to the memorial fund for his family.

The use of circles and boxes as rules allowed artists to craft the very specific film locations to a pretty huge degree of accuracy, but it did call for iteration: trying different seeds until you got something that matched what we had seen in the film. Also, there was a performance limit on how many rules you could pile into a map. If you hit hundreds, it would slow down the calculation as the code had to check, for every point, whether it was under the influence of a given rule (imagine hundreds of point-in-circle tests for every point on the map). So they were under budgets as far as rule usage.

I also recall that the lead graphics programmer wrestled for a while with the issue of how to do nice smooth blending between tiles. It would require a ton of blend maps and overdraw, because tiles were stamped down at every tile; you could in theory have one tile with eight different neighbors. He worked on trying to deal with it in a way that would provide decent performance for a few weeks. After a while I remember asking him why he didn’t just always stamp tile textures down in 2×2 blocks, so that you never had more than two tiles meeting. He got an angry look on his face, and tile blending worked the next day.

The other big issue from all this, of course, was that the server needed to know all the map info too. And our servers were really no great shakes. I mentioned in the Jedi post how we discovered that our servers were going to be less powerful than we had anticipated — there was some sort of budget savings from re-using old EQ servers, or something, so we ended up with Pentium III-600s as servers. But where a given player’s machine needed to calculate everything around to the horizon for just that one player, a server needed to know the terrain around every player and every AI, so that pathfinding routines could be run, collision checked, AIs could move about, etc. And the server sometimes couldn’t keep up. This is part of why the AI alert radius, and the combat radius, fell so dramatically during beta, and why shooting through the ground was occasionally possible. (It may also be why we never got full 3d collision, meaning that you couldn’t jump over tiny little walls).

Dynamic rules and the content it unlocked

So, procedural terrain was kind of a big experiment, and it gave us a lot of headaches. Many of them were quite possibly game-impacting to a degree that was really damaging. In the meanwhile, Everquest 2 and Planetside were managing to move forward with their hand-crafted mesh solutions. But we stuck with it for another big reason. We could add rules on the fly.

Rules could be attached to any object in the world. And this unlocked the ability to place any building anywhere. We limited ourselves to simple circles, since they were the easiest to compute (distance from center). They would do a simple strong smoothing routine: clamp everything inside the circle to the elevation at the center of the circle. They’d have a little bit of a fade off at the edge of the circle. They might re-texture the terrain, and they’d have a no-rock-flora-or-other-crap set up.

The result was that we were able to do

• player housing. Players were able to put down housing anywhere that wasn’t disallowed. Oh, we disallowed some of the wrong spots (for fiction reasons, we weren’t allowed to let people build suburbs around the core cities, even though those were the absolutely most obvious places to let suburban sprawl happen; as a result, we got fictional cities with a weird empty ring around them filled with newbie monsters, followed by an outer ring or “crust” of player city.
• dynamic points of interest. These were encounters that spawned complete with some structures, rather than just spawning a monster. This let us in theory even have questlets spawn, which I have written about before. Dynamic POIs of this sort didn’t ever make it to launch, but spawning structures along with enemies certainly did. In general, spawning in SWG Wasn’t based on where in the world you were; it was based on where players already were, like random encounters in D&D. This was intended as an anti-camping mechanism, though it all too often resulted in spawns dumping a building on your head.
• lairs. Rather than spawning single creatures, we generally spawned a creature spawner. The literal design spec was “like in Gauntlet.” Lairs spawned creatures up to a given population limit. Some of what they spawned were babies, intended for capture and taming by creature handlers. The others were adults, and “aggro” or attack-on-sight for peaceful creatures was driven by whether you were approaching their lair or not — everything defends its home, after all. Blow up the lair, and you actually killed the spawn. This concept started clear back in Ultima Online, where we spawned orc camps complete with orc wizards and whatnot. Unfortunately, as housing used up all the clearings in UO, these spawns eventually had nowhere to appear!
• campsites. Players were able to build camps out in the wilderness that conferred much of the benefit of being in a town. Today, Galaxies players often remember camps as one of the most social features of the game.
• military bases, which unlocked huge chunks of the Galactic Civil War for players.

This unlocked an enormous amount of gameplay. You could spawn a little bandit camp on the side of a mountain, on a cliff even. It would create its own little ledge. When the camp was deleted later on, the rule would go with it, and the cliff would be restored to its original appearance.

Lastly, and perhaps most critically, this also unlocked the ability to do harvesting anywhere in the world, which was a crucial component of the game economy.

In UO we had invisible resources attached to grass, to the rocks, to everything really. (see these three posts: 1, 2, 3). But all METAL was the same. There were no stats on METAL; originally, it was all steel-gray, even. One day I hacked in a system to that, which used (you guessed it) fixed random seeds to determine what kind of metal you got from a given location, and then I just attached a flag to the resultant ore. I checked for that flag at every step in the crafting process, and transferred the flag from the ingredient to the next stage. The result was colored armor of many different mineral types.

I knew we wanted this for SWG, and the best way to do it was to use an inheritance tree instead:

METAL

• Ferrous
  • Iron
• Non-Ferrous
  • Copper

…and so on. Designer Reece Thornton was assigned the system, and he went crazy with it, providing each resource with an array of statistics which could then be leveraged by the crafting system. We were able to swamp out the resources underneath the whole map, and allow players to build harvesters and factories anywhere at all, following the gold rushes and oil booms within the game. This then tied back into the crafting system, the game economy, and yes, the combat game itself, shaping the game very powerfully and helping to make it fell like a real world. The SWG economy and crafting system deserves its own post, but I did write about it here at a high level, in the midst of a post about something else.

So in the end, a huge part of the “living world” quality of Galaxies came down to the idea that we shouldn’t necessarily know what was in our world. That it should be surprising us, as well as the players. Yeah, we had a lot of empty frontier land — it was supposed to have been thickly populated with handcrafted little encounters, cool locations, and so on, but we never managed that despite applying a small army of designers to it. But what it did offer: malleability and the unexpected — that turned out to be a key asset. It probably saved the production literally millions of dollars, for all the troubles it introduced, and might very well work even better on computers today, without all the issues that the system presented. Add in shadows, and butterflies, and procedural wind blowing things to and fro, and a day/night cycle where the stars actually moved across the sky, and pretty soon you were somewhere that while still low on framerate and blurred and choppy, could feel very immersive.

I used this picture as my desktop for years. I would be asked where the picture was taken, quite regularly. I think people expected to hear Arizona, and were taken aback when I instead said it was from a galaxy far, far away.

Also in this series:

1. Temporary Enemy Flagging and PvP
2. A Jedi Saga
3. The Dynamic World
4. A living society, part one
5. A living society part two
6. Did Star Wars Galaxies fail?