Apr 202015
 

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

 

Corellia0023Let’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.

Corellia0004That’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.

Endor0040

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.

bullet

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.

bullet

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.

mtnstest1

Very early experiments

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.

screenShot0001When we got tEndor0021o 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?

bullet

The layering tool

t_editor

The 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.

swo_0001

Very early work on Tatooine, showing the terracing technique described here

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).

jungleScreen03

When we only had one tree

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 markSwamp1eting 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.

bullet

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!)

john_roy1

John Roy

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.

The earliest work on the Theed cliffs

The earliest work on the Theed cliffs

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).

bullet

Dynamic rules and the content it unlocked

tuskens raid hermit

One of the dozens of dynamic POI theaters I built

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.
  • swgfactionbattlemilitary 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.

A size comparison between all of UO pre-Trammel, and SWG

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.

swo_0002

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?

 

  44 Responses to “SWG’s Dynamic World”

  1. Thank you for another awesome post, Raph.

    I remembered zipping around the various planets on my landspeeder, constantly refreshing my Resource Surveying screen to check where specific resources were in highest quantities, and setting up a large number of harvesters in a clusters. I loved searching for the best resources with highest yield, willing to dump as many credits into those harvesters as I could. That activity, I think, is still prevalent today in a gameplay sense, in that many players seek to optimize their efforts with as much gain as possible. It wasn’t uncommon to be refreshing your Surveying screen to find the ideal yield value for any given resource only to find that a number of players had already discovered that hot spot and had set up their harvesters around it. Overall, it was a great lesson in economics, and really helped facilitate trade practices for those types of players wanting to sell (or even consume their own extracted resources) for crafting.

    I loved that the overall endeavor of creating terrains with all of those rulesets afforded those great features. Because you were embedding resources into the surface, allowing dynamic POIs to spawn in somewhat suitable locations, allowing plots of land to be claimed for player housing or PvP bases… they all yielded gameplay opportunities away from the cities. That gave players a reason to explore that wasn’t soley quest-centric. Running around a planet with the intent of advancing profession or combat skills, acquiring resources, and indulging in player-created content was hugely valuable to the great experiences that I had when playing.

    Crafting a terrain with a deep systemic approach like what you’ve described is something I miss in modern MMOs. Most often it seems most (if not all) of the content is hand-placed, resources are static nodes and disappear once extracted only to be re-instantiated once a timer has ended, and in some games the player housing is instanced in “dimensions” that are separated and isolated from the rest of the world. It seems fewer games these days attempt to craft as immersive a game as the SOE team did with Galaxies, probably because of the risks involved (time, budget, whatever).

  2. Thanks for another awesome post, Raph.

  3. To the end of my days I will insist that the resource part of the crafting system in SWG was one of the greatest bits of game design ever. And I believe part of that is because one of the key components of the resource-hunting game in SWG was that it was — as Raph describes here — dynamically-spawning content that didn’t require direct contact with other players.

    Because resources were always being swapped out, there was always something new to discover — maybe one day you’d find a Polysteel Copper like the Ynesa I discovered on Radiant/Naboo with the incredible stats. You could strike out on your own and locate a mother lode of some resource, fling every harvester you had on it, and sell everything you mined for a great price. And with so many big planets, you could do it as much as you liked.

    So in addition to the game design bits that encouraged players to interact with each other directly, there was still a place for us introverts in this massively-multiplayer game. We could enjoy our own kinds of fun while still contributing to the dynamic economy.

    I will always appreciate the designers of SWG for that.

  4. Because of the issues we had with the random number generator in UO causing streaks, I was very interested in finding out what kind of random number generator SWG had. I was pleasantly surprised that SWG used the Mersenne Twister algorithm, something I had used in one of my dice rolling apps for my D&D campaigns I ran. The Mersenne Twister algorithm generates numbers much closer to a secure hardware random number generator than most psuedo-random number generators, but can be predicted with seeds.

    During the GCW update, I added a bunch of zones to the map and used the layering tool to make team versus battlefields. I had to choose areas with no housing and from multiple planets to spread the combat load. One of the battlefields was an island in the ocean on Endor. I spent a long time working on the layers and got the best looking beaches in the game made, with rolling dunes, on it (http://deathduel.com/images/endor_island.jpg).

    As an aside, one group of weapons fired AOE explosions (lava cannon being one of them). The rate of fire was every 0.25ms, which is something that put a huge load on SWG servers. Players were complaining of lag during combat. I began a witch hunt to figure out what was causing the problem. It turns out, even though the load on the servers was large, the problem was client based. The particle system could emit emitters. I found that the lava cannon (and many other weapons) were emitting maximum particles (256) and then firing sub-emitters with more particles on them. I believe each shot was trying to create over 40,000 particles. I was able to reduce the particle emission by 100x (400 particles), which fixed the issue. However, the 0.25ms AOE did continue to cause combat issues with high traffic. I didn’t get around to reducing the firing rate, before I left the team.

    Also, during the same time, we started seeing issues with the resource system. Each resource was given a unique ID and statistics. The databases were filling up with these automatically created resources. We had to go through and find a solution to reducing the database size, without impacting existing mined resources. The statistics were snow flaked, once generated. So, we had to purge databases, after checking cross-referenced items. I don’t remember coming up with a long-term solution (should have used referenced statistics tables).

  5. Cleaning up of old resources could have been done as simply as giving them a half-life so to speak, and decaying them out. Probably wouldn’t have impacted the game at all.

    Battlefields were actually in the original spec, there was even at least one half-built one with markers left in the sand in Tatooine, if I recall. 😛

    Totally unsurprised to hear about the excessive particles.

  6. I had a lot of fun making the battlefields. They asked that I put in all classes, though. I had to incorporate quests for crafters, entertainers, combat classes, and stealth. We had a construction phase, so the crafters would build the defenses and offenses. If your side didn’t prepare enough, you would be at a disadvantage during the combat phase. Entertainers gave special combat buffs. Stealth classes could sneak up and sabotage offenses/defenses.

  7. Huh, I think asking for entertainer stuff in the middle of battlefields is actually sort of weird. Getting professions that are non-combat to conform to combat stuff was what we were trying to get AWAY from.

  8. I didn’t do the design for the entertainers, so I can’t be specific on what it was for. I do know that city cantinas were used for their quests. I believe I remember they gave buffs out in a cantina and healed troops that went into the cantina during battle. I have my design document, but I didn’t expand on the design for them very much. I have their rewards listed, but that’s it. We did redesign them prior to the GCW release to allow them to customize their buffs in an entertainer trade window for players to purchase from them. The customizable entertainer buffs made quite a difference in the last couple years SWG was around.

  9. Cantinas were used for the quests in the battlefields? Interesting, then maybe I take it back, I was picturing a poor dancer running around in the midst of something like the Battle of Hoth. 🙂 Minus the snow of course.

  10. I pretty much expected to see you here, Hanse. The Data Runner island you made, while I never played on it, was a cool spot.

    Side note to the above, there were actually PvP battlefields on 7 of the 9 planets when it shipped. I believe it was Endor, Naboo, Rori (x2 I think), Corellia, Talus, Tatooine, and Dathomir. They were removed ~1 year after launch. Then, there were PvE battlefields too. The only one that ever seemed to work was the Rebel one on Corellia.

  11. Yeah! I wanted to do a flag run on the island. I randomly chose a player and made them the target. The entire team was supposed to protect the runner, which in our tests turned out to be a lot of fun. It also kept the strongest and hardest to kill from hogging the flag (if we’d used a flag). I played a lot of Team Fortress at the time and I felt that was something I wanted to avoid.

    We did the Battle for Hoth. Lucas Entertainment gave me all the voice overs I wanted except Princess Leia’s hangar speech, including Commander Veers stating, “Target. Maximum Firepower!” The first time the AT-AT’s walked up to the generators and he said that I got tingles down my spine. 🙂 I spent two weeks making the entire sequence of characters moving around the base (which, if you follow the script, they teleport a lot due to the distances involved – I chalked that up to some type of transporter in the base). Someone kept moving objects in the way of Darth Vader’s path during world building. I got so fed up with it I yelled at the team, “Does Darth Vader have to choke a bitch!!!”, after the umpteenth time. I also got to make new abilities for Darth Vader to use in the battle. 🙂

    The interesting challenge there was how do we make the Rebels feel that they won, even though they lost every battle. We had them defend the escape ships and win for their side if enough got away.

  12. See, that sounds like the sort of content Is wanted at launch. 🙁

  13. Lucas Entertainment stopped being overbearing on the design approval process, when I joined the team. I heard horror stories of long turn-around times on designs being approved and LEC employees making pointless changes to designs to justify their jobs (of course, those tales were skewed as they were told to me by SOE designers).

    If LEC had seen I was putting in the “Shoot First” ability for Smugglers in their skill tree, I’m not so sure it would have gone in. 🙂

    None of the battleground/pvp designs were even glanced at by LEC, that I know of.

  14. Its great that the game is still out there and being played. Can you imagine using the same everythinggame idea, what you could do now!

  15. The game is still available to this day to play private server wise if anyone would still like to embark on the journey .

    http://swgnightwing.org/

  16. Raph – Really enjoying these posts about the mechanics / background of SWG. The ‘unexpected’ is one of the things that made that universe so compelling to me. No other game has ever captured that feeling of being dynamic and alive.

    I’d love to hear some more about the resource system such as original ideas that didn’t make it to live and any problems created by the system. Did you foresee players being able to make buffs and armor that could resist 99% of damage? Was the idea that decay would eventually cycle those items out of the system? Do you feel that it was too easy to mass produce these high stat items (armor, weapons) to the point that decay had little effect on removing them from the economy?

  17. Actually, I think you answered many of my questions in another recent post, but any other thoughts you have would be interesting to hear.

  18. Wow…

    My, this game was ahead of its time.

Sorry, the comment form is closed at this time.