Building the road networks in SimCity 3000
In 1997 I started to work at Maxis, as General Manager. Our key product to release was SimCity 3000, for the PC.
I did some work on solving how the road network would work. Aware that I was using Mathematica, Flip Phillips editor of the Mathematica Journal interviewed me and published this in “The Mathematica Journal“:
In the Beginning, There Was Tetris
Back in my pre-academia days, I worked for a little start-up computer graphics company in Marin County, California. There were a lot of computers there capable of displaying graphics. We actually manufactured some ourselves: the now deceased Pixar Image Computer. With so many graphics machines around, it went without saying that we had a lot of nascent computer games on them. Tetris seemed to have basically taken over every Macintosh in E-Building by sometime in late 1987. Lunch hours (well, lunch two hours in some cases) were spent packing the falling Soma-cube-like boxes into little spaces in astonishing single-bit color resolution.
Tetris so inspired some of my colleagues that they went about the task of writing a faux Tetris program for the Pixar II and then for this strange black box that appeared one afternoon from NeXT. It was all good clean computer geek fun.
About the time the “Cube” appeared, a fellow addict brought in a virtual city planning program, created by Will Wright, entitled SimCity. This was not just a game in the traditional sense; it was one of the first true “System Simulator” programs for the personal computer. Introducing it to me, my friend unleashed the wrath of Godzilla upon a small, barely thriving metropolis he had created. The great mutant lizard tore a wide path through his downtown, leaving behind a fiery wake of virtual destruction. Godzilla, the digital planning commission, and the embezzleable finance system quickly displaced the suddenly coma-inspiring blocks game on my and most every personal computer in the company.
Virtual Destruction. Uncontrolled fires break out in an industrial zone, a more easily managed disaster than the aftermath of Godzilla’s fury.
For the uninitiated, SimCity allows you to model a virtual community, step by step, tax dollar by tax dollar. You have to include schools for learning, police and fire protection, hospitals for the wounded, office buildings, entertainment, housing areas, power plants, transportation, and utilities. These things all cost money, so you needed to tax your population, but if you overdo it you will be left with a ghost town when the citizenry flee for greener silicon the next town over. The simulation runs at a variable rate, allowing you to set up an initial model and speed through a few hundred years in a couple of minutes. Alternately, you can carefully monitor the situation, listen to your constituency, build stadia and airports when they complain, burn down slums when crime gets too frequent (Godzilla is quite useful for this purpose), react to other natural disasters, and in general try to keep the city afloat with the limited amount of tax-revenue you can squeeze from your virtual population.
Planning as Simulation
One of the really wonderful things about the Sim family of games is that they are complex simulation systems fitted with nice interfaces. Basically, any aspiring Pierre L’Enfant can whip up a little petri dish of a community and watch it develop without waiting for hundreds of years or facing criminal charges for tampering with the treasury.
Eastern New Jersey. Road networks presented a challenge for the isometric projection used in newer versions of the software.
SimCity utilizes a “tile” system for laying out utility and road networks. In the initial versions of the software these tiles existed in a plane, viewed from above. The introduction of SimCity 2000 brought with it a new rendering scheme, isometric rather than a strict plan view. Needless to say, this introduced a new set of challenges when laying out the various networks required to sustain a silicon city. Further complicating matters, newer versions allow for nonflat terrain, which strenuously challenges the layout algorithms.
Layout. Users lay out roads and utilities by drawing a path on the network tiles (here seen in blue), and the resulting graphical elements, a road here, are fit to the tiles. Mathematica code is used to define the replacement rules employed in selecting the proper graphical elements.
When laying out the networks, various graphical elements need to be placed on the terrain to indicate the use of that particular tile. Roadways, utility lines, subways, water pipes, and other networks have to be connected and visually represented in an æsthetically pleasing way. For simple linear structures this really is not much of a problem; graphical elements can be linked together much like pieces of model railroad track. Problems occur when curves, overpasses and underpasses, and intersections enter the picture. To handle these cases, earlier versions of SimCity employed a simple scheme that used the four adjacent (Greek-cross) neighbors to obtain a unique solution for almost all possible cases of intersections, curves, or terminations. For SimCity 3000 the art directors wanted more flexibility in the visual design of the networks’ graphical elements. As with most complex systems of this sort, some small additions and perturbations to the basic set of rules resulted in a large increase in the complexity of the resulting system. Coding all of the possible situations by hand was going to be a tedious task at best. The designers wanted a solution more data- than algorithm-driven so configural changes could be accomplished in a more straightforward and intuitive way.
Complicated Intersections. SimCity 3000 increases the complexity of the graphical elements of the various networks. Here we see a four-lane divided highway, complete with on and off ramps, exit signs, and underpasses.
Mathematica’s Solutions
Enter Luc Barthelet. Luc is the general manager of Maxis, the arm of Electronic Arts responsible for the Sim family of products. He is a long-time user of Mathematica and has found it invaluable for a variety of problems involved in the research and development of projects like SimCity.
Barthelet’s plan was to use Mathematica to develop a set of graphical replacement rules for “solving” the graphic-selection process based on the constraints present in the neighborhood of the target tile. The graphic design team developed a taxonomy of intersection graphics and Barthelet created Mathematica notebooks that would isolate some key features of the neighborhood and propagate a solution using a set of simple replacement rules.
Rule. A rule that finishes the connection of two diagonal roads using a diagonal curve.
Rule. A cleaned-up four-lane highway cur
Rule. A construction of one-half of an elevated highway and intersection; the second half is easily obtained via symmetry.
Barthelet’s rules consider the 4, 8, or 24 connected neighbors to a given tile to decide whether to leave some tiles’ graphics unchanged, add additional graphic elements, or replace them with other graphical elements. The illustrations above demonstrate a few of the rules used with road networks. Similar sets of rules exist for the various utilities and other transportation systems.
The Rules
Barthelet says that the contributions of Mathematica come in two primary areas: symmetry and testing. One convenience of using a symbolic computation package is that rules for each replacement need to be implemented only in one orientation. The remaining are easily calculated by taking advantage of symmetry. This “out of one, many” approach saves countless hours and guarantees the accuracy of the resulting rules.
The replacement rules take on the following form.
Text Form of a Rule. Human readable form of the highway rule for capping the end of a diagonal curve.
A nice, readable format, but difficult to visualize. Barthelet relies on Mathematica’s graphics capabilities to render each rule, using the actual game graphics; thus, he is able to visually validate them easily. A picture is indeed worth at least a couple of dozen symbols in this case!
Further Testing
While developing the replacement rules, Barthelet needed to test them against the encyclopedia of graphic elements provided by the art department. Furthermore, he needed to make sure that they all actually worked in combination with each other. Manually testing all possible combinations would have been a nightmarish task. Mathematica was called into action to test the huge variety of possible combinations of elements. As the replacement rules were modified, the entire collection of possible combinations were tested and visualized, generating several hundred-page notebooks in the process. Relying on the outstanding pattern matching system available in the human eye and brain, the constructions could easily be checked for accuracy and conformance with the art department’s wishes.
Rule Testing. Mathematica was used to test all of the possible replacement rules. These three rules are tested in the Mathematica code above. On the left, the rule instructs the present tile to show a terminus if there are no other road pieces connected. The middle rule places a “straight through” graphic, and the right-hand rule handles turns.
After all of the rules were tested, they were output to several text files that were readable by the game’s executable. (If you happen to own the game and are feeling adventurous check out the tilingrules folder on the CD-ROM.) This data-driven solution makes a lot of sense by easing changes and simplifying cross-platform issues. SimCity simply loads them in at run-time and builds the table of replacement rules that it uses to solve the network problem at a relatively brisk pace, a necessity in the computer gaming world.
According to Barthelet, by using this system they were able to implement more rules more easily and even implement new features feared to be too difficult to program directly. If you have played the new 3000 version you already know that the visual richness is greatly improved. If you have not, it is well worth a look. Check out www.simcity.com. While you are there, give the SimCity Classic simulator a try[LongDash]but be careful, you may become an addict.