This may seem off-topic now, but I want to introduce another key issue of virtual worlds: How to make a virtual world come to life. This is about procedural life and societies.
Last century I developed a massive online game called StarPeace along with some friends. The game ended up published a few times, but it never became mainstream. For the story of the game, please check out the Wikipedia article. The game is still ran by different fan communities, but I finished my involvement with it long time ago.
It featured an unique and very powerful simulation engine. Most of the techniques that were pioneered there would still apply today. Actually no other product that I know of has come close to the volume of simulation this game was doing and how realistic the results were.
A quick tour of one StarPeace world
StarPeace worlds can be very large in MMPOG standards, covering thousands of square kilometers (note that a single World of Warcraft instance is about 500 square kilometers). A single world may have dozens of cities, each one hosting a few million virtual citizens. The image below shows a screen capture of a young city. The area covered by this image is 1/1000 of the world and it contains a few hundred facilities. Approximately two million virtual citizens live in this city.
Each virtual citizen is accounted for in the simulation. They need a place to live, the may work somewhere or have their own business, they consume goods that they pay for with the money they earn. While doing so, they alter their environment, they produce pollution, crime, or just wear down existing utilities. They require services like hospitals, police and education. They have a will of their own, usually moving from one place to another looking for better jobs, better commerce, or avoiding adverse conditions like pollution, crime, or even people from a different social class.
It is up to the players to let all this happen and control it to their advantage. Virtual citizens cannot build any facilities, so they depend entirely on the decisions taken by players. The main way a player can modify the world is by building a new facility.
There are several hundreds of different facility types in StarPeace, but they can be classified into a few large groups: Residential, Commerce, Industry and Civic. These groups have very distinct characteristics.
Residential buildings rent units to virtual citizens. Their occupancy ratio is determined by how many people are moving into the city, how fair the rent price is and how well the building is maintained. Environmental conditions like crime, pollution, access to commerce also have great influence.
The next screenshot shows several residential buildings of the same type, all belonging to the same player:
Commerce buildings depend on their location to get virtual citizens to spend their money in exchange of some good or service. Aside from location, many factors affect the performance of commerce, mainly the price and quality of the goods or services being sold.
Industrial buildings take some input materials and produce new materials or goods, which may go directly to commerce outlets or could become the input of another type of industry. Industries can be connected into complex networks, often including warehouses, which buffer the transfer of goods, stabilizing the overall economy. Some industries, like farming, are affected by the ever-changing conditions of the weather.
The next screenshot shows an industry park:
Civic buildings have an effect on their environment or often at a city wide scale. Police stations will reduce crime in their neighborhood, a park will increase the beauty of the area, however a Museum is something the entire city benefits from.
This tightly entangled network of facilities is connected by a road system. Two industries can exchange goods only if they are connected by roads. Since roads are very expensive to build, they play a key strategic role in the early development of StarPeace worlds.
Eventually the entire world is connected by a single road system. At this point the economy becomes truly global. This poses a great challenge to the simulation engine: Imagine that player A goes bankrupt in one city, at this point all his workers are laid out. The unemployment ratio could go up in the city to the point many citizens may decide to move to a city very far away that is showing a more promising future. Player B, located in the further city, may see a rise in the occupancy for his residential buildings there and benefit from player A's misfortune. All this needs to happen in a few seconds.
A StarPeace year happens in 12 real world hours. This implies that not only a very large world needs to be simulated, it has to be done at 700 times the speed of the real world.
Architecture Overview
The following diagram shows StarPeace's main components:
The first trait to notice is that this is strictly client-server. Clients do not connect to each other. The subject of the simulation was economics and politics so clients could never be trusted. Clients were built to be as thin as possible, barely a glorified console able to explore the world's terrain and buildings, and post user commands to the server.
The bulk of the work is carried out by the Model and Interface servers. The Model Server keeps a memory representation of the world which is completely updated every few seconds. This is a data model that was specifically designed for simulation speed. The entire data model can be dumped to disk when a maintenance downtime is planned for the server.
The Interface Server deals with online users. It provides basic interaction between clients, like chat, mail, but most of all, it acts as a buffer between clients and the Model. Most of the information in the Model is cached at the Interface Server. This reduces the number of requests to the Model Server.
And then there is the Directory Server. This server contains information about the user's account, like their login credentials, profile picture, history of achievements and so on. A single StarPeace world requires one dedicated Model server and one dedicated Interface server. The Directory server, on the other hand, is unique for the entire StarPeace universe. This way the identity of the user is preserved between across worlds.
The economic simulation engine of the game is what makes it unique. For that reason this article only covers what happens inside the Model Server.
Everything flows
The Model server holds the representation of the virtual world in memory and updates it every few seconds. The simulation uses two main different abstractions. Most of the phenomena in the virtual world fall into one of this two.
The first abstraction is used to model the production and exchange of goods. It assumes everything moving in the world is a fluid. Fluids are of a given type, they have some magnitude and they have some quality. Surprisingly, the same abstraction is used to model population and workforce. From the simulation point of view, people are no different than shoes or electric appliances.
These fluids move from point to point in the world. At any given point, the fluid may be transformed into something else. Very often several fluids converge in a single point, where they get mixed. Each one of these points is actually a simulation block. A simulation block is a black box device, it may take several input fluids and produce several output fluids:
To this extent, the entire world is a circuit made of these blocks connected in many different ways. This abstraction simplifies the model to a point that allows for very quick updates.
In most cases it takes a single block to simulate a facility. Other phenomena, like migrations between cities require the use of intangible blocks which cannot be associated with any clear object in the virtual world. The following diagram shows how blocks are connected to simulate population behavior:
From the left to right, this process can be described as follows:
In any given city, there may be a large number of residential buildings. Each building will have its own simulation block, which show in the diagram as boxes labeled "Residential 1" to "Residential N". Each residential block has one input and one output.
The input is a population delta describing how many people moved into the building in the current simulation turn. This number may be a fraction, meaning that someone partially moved to the building during the time slice of the turn.
The output is how many people moved out of the building in the same time slice.
As noted in the diagram, each residential input has a "R" label next to it. This is the "resistance" for that particular input. In this case, resistance is very similar to the resistance found in elements of a an electrical circuit. Higher resistances in the input will make the flow smaller.
All residential blocks are connected to a single block in the city, the "City Population Controller". This block has one output that is linked to every residential input. At a given simulation turn, the controller will have a number of people that are seeking a new place to live. This value is fed to the output so it will be split by the circuit simulation logic among all residential blocks, depending on their individual resistances.
The resistance of a residential block is determined by its intrinsic properties, like rent price, maintenance level of the building, and other environmental factors like crime, pollution, access to commerce, schools, etc.
It can be seen that this model successfully represents phenomena like people moving from one building to another within the same city. On every turn, the block generates a small fraction of people who are willing to find a better location in town. This number is fed to the output of the block. The sum of this effect is collected by the input at the city controller, which will end up knowing how many people in total are willing to relocate in the city. This is the same number that is fed to the city controller's output and then split among all residential blocks depending on their resistance.
A block with unfavorable conditions will generate a larger fraction of people willing to move out, but will receive less people moving in because of its high resistance, so eventually most of it occupants will move to better places.
A similar flow happens at the world level, where each city population controller outputs a signal containing how many people are willing to abandon the city. All these outputs are collected at the "world population controller" and then split among all cities based on their individual resistances. In the case of a city, resistance is determined by more global indicators, like unemployment and quality of public services.
Simulating other aspects of the world, like people choosing where to work, was achieved in the same way. There were other types of fluid transfers that used a slightly different approach. When it came to exchange of goods like raw materials, machinery, shoes or food, the inputs and outputs needed to behave differently.
The following example will help to see why. Let's assume player A has a farm. Player A has set up the farm so it will sell its produce to food processor plants own by another three players: B, C and D. Under the hood, this is translated into several blocks connected as shown in the following diagram:
There are four blocks here, one for the farm and three for the food processors. The output of the farm is connected to the input of each food processor. In this case the approach of distributing the farm's output according to each processor's resistance won't work, because the owner of Farm A may not really want to distribute the output among all processors. In this case, Food Processor B should get as much produce as possible, then, if there is anything left, it should go to Processor C, and whatever remains should go to Processor D.
The circuit simulation logic account for this by providing two main types of inputs and outputs: push and pull. Push inputs and outputs are used to model the population and workforce flow. Pull inputs are used for transfers of goods where priorities between connections has to be respected.
The Environment
Many aspects of the simulation can be successfully modeled as a circuit of interconnected blocks. Other phenomena, like crime and pollution, turned out to be very difficult to represent using this approach. The second main abstraction in the StarPeace simulator deals with them.
The following screenshot shows a pollution map in the game:
Areas with high pollution show in red, while areas which reduce pollution, like parks, show in green. The next screenshot shows an island of crime in one city:
Here red identifies areas where crime is high, and blue those areas that are under the control of the police.
The overall idea is that each block in the simulation may influence nearby blocks. This influence may be manifested in different planes at the same time. For instance, a residential building inhabited by low class citizens may produce pollution and crime at the same time.
This is not limited to the obvious environmental effects like pollution or crime. The simulation of commerce relies heavily on environmental factors as well. The presence of a restaurant in one area can be felt by the other restaurants in the same area. In the same way, a commerce outlet must know how many potential customers may come from nearby areas. Population reacts and contribute to the environment at the same time: high class citizens dislike the presence of lower social classes, and will try to move away from them.
All these effects are simulated using a single pairs of objects: "modifiers" and "integrators". For the sake of simplicity, let's focus on one environmental plane: pollution. Some blocks, like factories and residential buildings contribute pollution to this plane. Other blocks, like parks, have a negative effect on the plane; that is, they remove pollution. The concept of a "modifier" allows to represent this. Each block in this case would register a modifier in the pollution plane.
The modifier is a geometrical volume, like it is shown in the following diagram:
This volume represents the contribution of this particular block to the environmental plane. In some occasions the volume may extend for kilometers, like pollution from factories, which can travel far away. In other cases, like commerce, they are restricted to smaller spaces.
To know the pollution in any given point in the world, it would be enough to add the values of each pollution volume that contributes in that point. Some volumes are actually negative, like parks, so they end up reducing the final value.
Blocks still need an efficient way to incorporate the environmental values into their intrinsic simulation. A residential block, in each turn, will need to know what is the value of pollution in its surroundings. This is achieved by using "integrators".
An integrator is an object the block may register in an environmental plane. The integrator provides a sum of all the volumes in a given area, and it is able to recompute this value continuously, at a frequency that is actually decoupled from the simulation tick.
The following diagram shows a residential in the vicinity of a factory:
In this case, the residential will pick up the pollution generated from the factory by using an integrator in the area marked by the blue rectangle. If there were other factories nearby, their effect would be picked up by the integrator as well.
A single block may register several modifiers and integrators at the same time. Commerce outlets rely heavily on this. The following list is a breakdown of all the modifiers and integrators a single store will register:
- Three integrators for population density, one for each social class: low, middle and high. These are used to know what is the potential customer base for the store.
- Three modifiers for population density, one for each social class. People who work in the store are also present in the area, so the store reports them in the corresponding population planes.
- One modifier for the commerce density. Each type of commerce has its own environmental plane. This plane represents how strong that type of commerce is in any given area.
- One integrator for the same commerce density. If the store is alone, it will pick up only the value that is produced by its own modifier. If there are nearby competing stores, however, the value picked up will be much higher. The ratio between the value the store sets on its commerce modifier and what it sees from its commerce integrator is a very good indication on what share of the local market the store should get. Stores with a strong presence will have bigger modifiers. The magnitude of the modifier depends on intrinsic factors like the quality of the service, the amount of advertisement done for the store, etc.
- One integrator for "beauty". Beauty is a loose indicator of how appealing the area is to humans. Parks and nice buildings increase beauty. Factories and dilapidated buildings hurt it.
- One integrator for crime. Crime will have an adverse effect in the store.
- One integrator for pollution. Same as crime, pollution will hurt the store.
As it was shown, the simulation uses two main principles to model the virtual world: a circuit of connected blocks, and a series of environmental planes where each block may contribute and read. Very often the two are combined to achieve a single effect.
In the example of the store, not all customers will come from the nearby areas. Some stores will offer a bargain that is good enough for customers to ignore locality and travel large distances just to access the store. This particular case is modeled using circuits. So a single magnitude for the store, how much is sells, is computed by using the two main abstractions together.
Anatomy of a Simulation Beat
The Model Server uses several threads to carry out the simulation. One evaluates the circuits. Another one deals with environmental modifiers and integrators. A third thread computes the connectivity of the road system, which is needed to make sure facilities are actually connected so they can exchange goods. And then there are other threads which deal with backups of the model or queries made from the Interface Server. All these threads work a different frequencies, each one doing the best it can. Their interaction, if any, is coordinated by shared events and critical sections.
The circuit simulation thread is the one that dictates the simulation frequency that is perceived by players. At the end of each circuit simulation cycle, new values have been produced for all the parameters in all entities in the simulation. At this time, players see the amount of money on their bank accounts change, facilities being built show some progress, virtually everything in the world updates. To keep the game-play interesting, it was necessary to have simulation ticks in no more than three seconds.
To speed things up, the circuit simulation takes advantage of inter-tick consistency. This means the values produced by the current tick are used as the input for the next tick.
The circuit simulation is carried out in three phases:
- Iterate through all the blocks in the model. For each block, the pull inputs are evaluated. A pull input will "suck" fluid from all connected outputs. It will try to get as much as possible from the first output, then if there is capacity left, it will pull fluid from the next output in line.
- Iterate through all blocks again, this time evaluating the intrinsic block function. This is a function that is hidden in the block and it is able to transform the values in the inputs into new values for the outputs. Pull inputs got their values already updated in the current turn, push inputs got their value from the previous simulation turn.
- Iterate through all blocks one last time, this time evaluating the push outputs and inputs. The values produced in this iteration will be used in the next simulation beat.
While this is going on, the thread simulating the environmental layers is iterating through all the integrators it has registered. The information for each layer is kept in a geometrical format the whole time, the modifiers are never rasterized into 2D maps. The reason for that is that there were too many different layers for each layer to have its own 2D map. This would blow out the memory requirements for the server (remember this system was designed around 1998).
For each integrator, the environmental thread would see which modifiers it would intersect. This was sped up using a Quad tree, and then it would use the geometrical description of the modifier to compute the contributing volume.
Last, the road system thread needed to make sure facilities were actually able to trade goods. This needed to be done with great accuracy. Very often two remote cities would be connected by a single large road. If this road would break at any point, all the facilities in one city would loose connection to the facilities in the other city.
This was achieved by discovering circuits of roads. The roads were represented in a vectorial format in the server. The connectivity of these vectors was recomputed frequently by the road simulation thread. All the segments that were connected together were place in the same circuit. Then each block would know which circuits were nearby. Two blocks sharing at least one circuit should be able to trade with each other, so testing for connectivity between two blocks was reduced to intersecting two very small sets.
In conclusion
The simulation engine of StarPeace was able to convince players real economies and societies were taking place in the world. It was also able to do it at interactive rates, so players would not get bored waiting for their changes to take effect.
The massive scale of the world, and the large number of objects to be simulated were unprecedented at the time. More than a decade after its original release, StarPeace worlds continue to amuse players with the depth and intricacy of their virtual reality.
The engine was successful in modelling both local and global effects. Not only nearby facilities would affect each other, very often crisis in one city would be felt in a distant city.
The ability of grouping many apparently different phenomena into generic groups that could be quickly simulated proved the key of the speed and scalability of the system.
.png){kind=link}
.png){kind=link}