A Guide to the Operation of the Traffic Simulator
The traffic simulator is one of the least understood components of SC4. This is partly because understanding of how it works is not required for modding other parts of the game, and partly because many of its effects are fairly subtle, and are often second- or third-order. This guide will attempt to summarize our current knowledge about the traffic simulator, both in terms of how it works as a whole, and also in terms of what each of its individual properties do. Since it is the properties of the traffic simulator that are accessible to us, and that allow us to tune it in various ways, these properties will form a central part of this description, and will be boldfaced whenever they are used. This post contains some material from other places; I have gathered it all together here for ease of reference, and also to make this description more coherent. There are undoubtedly some errors in here, and some omissions; if people spot these, please post in this thread, and such errors or omissions can then be corrected.
This guide has not been written in isolation, and in fact relies to a very large extent on previous work done in this field. Specifically, much of our current understanding of the traffic simulator has come from work done by the7trumpets, Tropod, jplumbley, and Mott, among others; what I have done has merely been to build upon the excellent work done by these gentlemen, and would not have been possible without their efforts.
Most people are aware that changes various parameters in the traffic simulator can have a significant effect on their game, but it's often not obvious how significant that effect is. Consider the following Pop & Jobs graph:
This is a graph of the Lakeview neighborhood in the city of Chicago. Lakeview was originally built with a pre-alpha version of Simulator Z; it had the large capacities and long commute time of today's Simulator Z, but it still had the pathfinding heuristic (PH) of its CAM Simulator predecessor. (The pathfinding heuristic will be discussed in detail later.) It was quite stable in this state, which you can see at the beginning of the graph, where all lines are basically flat.
The city in general looked pretty good and seemed to to function rather well. At this point there were just a couple of city blocks where there was a lot of abandonment and rebuilding going on. I eventually realized that I needed to adjust the PH, which I lowered to the value of .003, which was thought to be the perfect pathfinding value at the time. This is the point where the R$$ starts to rise rapidly and the R$ begins to fall rapidly; there is also a slight upward movement in the CS$$$. All this represents upgrading; either buildings that were originally R$$ but downgraded to R$ were upgraded back to R$$, or new R$$ buildings replaced existing R$ buildings. Throughout all this, total population remains steady at around 835K.
A very important point to note here is that though the population of the city was changing significantly, as evidenced by the graph, I was unaware of the extent of the change at the time. Only since the end of October, when I began doing the PH experiments that are illustrated in the Traffic Simulator Z Development and Theory thread starting with this post, have I even been aware of these population changes. And yet their significance is obviously great; the difference in residential desirability that they represent has a profound effect on the game. But these changes aren't always accompanied by abandonment, and are therefore easily missed. Similarly, if a player uses a traffic simulator that is not properly tuned, there are no changes to see; there is just a general lack of desirability and its attendant effects that are difficult to explain. Rarely is the traffic simulator thought of as the cause of these problems.
Returning to the graph, look at the point where the red arrows are pointing. This is where I switched the city from Simulator Z v1.0 to v1.2. The changes in v1.2 included reducing rapid transit speeds, adjusting the Customers/Traffic Noise Coefficient, and strengthening the travel strategy preferences of the Sims. The changes in the graph here are more subtle; some take a while to kick in, while others are immediate. The general trend of the R$ and R$$ lines does not change immediately. However, within a decade the trends accelerate until they cross at a point where they are both close to the vertical. Major changes are clearly happening in the city here, yet without seeing this graph, they would not be obvious. At this point, both the PH change and the changes introduced in v1.2 are working together constructively to produce these steep trend lines. From experiments in the thread referenced above, it was shown that a PH change tends to work itself out in about 30 years. In the graph, that's right where the top two trend lines angle sharply toward the horizontal. The R$$ remains fairly constant through the remainder of the run, while the R$ continues to decline; the population as a whole remains steady. From here on out, low-wealth Sims are being replaced by high-wealth Sims.
Meanwhile, the changes in the R$$$ line begin right at the simulator switch; there's an immediate little bump that quickly turns into a steady upward trend that lasts through the remaining 60 years of this graph. The net result of the movement of all three populations is that in just a few years following the change in simulators, the city's overall population jumps by about 7%, from 835K to 894K, a level at which it remains at for the rest of the graph.
There are significant changes in the commercial capacity as well. (The city has no industrial population to speak of.) The third red arrow shows the CO$$$ capacity, which has been flat until now, but immediately increases during the few years after the switch. It settles back a little bit, and then maintains roughly the same level for the remainder of the run. Meanwhile, directly below the red arrow is the CS$$$ line, which has been slowly rising since the introduction of perfect pathfinding. But with the changeover to v1.2, the rise accelerates noticeably for a few years, and then slows down, though it continues to rise through the end of the test.
Changes like these are much easier to see in a small graph like this than by eyeballing the city for a century. Some of the most dramatic changes come with the introduction of v1.2, well after the PH has been lowered, so there are clearly other factors at work here. Later, the perfect pathfinding heuristic was changed to the more accurate value described in this post; this caused the previous changes to continue on for a little longer. To understand what these changes are and what their importance is, we have to really understand how the traffic simulator works, and that is the subject of the rest of this post.
First of all, it is important to note that despite its name, the traffic simulator isn't actually the part of the game that simulates traffic, at least as it is visible to the players. Visible traffic is generated by the automata controller, which is only loosely influenced by the traffic simulator. Aside from the automata, there is no actual traffic in the game. Instead, the traffic simulator runs about once every four game months, and calculates routes for the Sims to take to and from work. This is why if you use the Route Query Tool on various networks, the numbers will always remain constant for months at a time. No one travels the morning commute routes in the morning, and no one travels the evening commute routes in the evening (other than the automata). These routes are calculated mainly for their side effects, which are used by many other aspects of the game. Most importantly, they are a key factor in determining desirability, which is one of the most important factors in deciding how the growth of cities will proceed. To a very large extent, then, the traffic simulator is actually a desirability generator.
The functionality of the traffic simulator can be divided into six parts:
- The destination finder, which locates suitable jobs for working Sims.
- The pathfinder, which calculates paths from the Sims' homes to their jobs.
- The automata support, which provides data that allows the automata to reflect something of what is happening in the game.
- Properties that affect only the city's budget.
- Properties that are either unused, or serve a purpose that is currently unknown.
- Properties that are known to be nonfunctional.
The first two of these functions are the main reasons for the traffic simulator's existence: to find jobs for the Sims, and to calculate paths to these jobs. As mentioned, these functions run about every four months, with the destination finder first finding all the jobs for Sims who need them, and then the pathfinder calculating the necessary paths. The reason that the destination finder must run first, and not in parallel with the pathfinder, is simply for efficiency reasons. As will become clear as this guide progresses, both of these functions need a large amount of memory to run. The minimum system requirements for SC4 are a Pentium III 500 with 128 MB of memory. It is difficult enough running this game at all in such an environment. If the destination finder and the pathfinder ran in parallel, the amount of memory required would be greatly increased, and a lot of paging would result on minimal systems, resulting in the game's running several times slower, essentially becoming unplayable for all but the smallest cities. For this reason, and because running the two functions in parallel doesn't gain anything, we can assume that they are run sequentially.
The Destination Finder
In every traffic simulator run, the destination finder systematically goes through all the residences in the city and sees which Sims need new jobs. RippleJet discovered the default movement pattern of the destination finder:
Quote from: RippleJet on December 13, 2009, 03:03:56 AM
From what I've seen in a couple of my cities, the destination finder works from the west to the east,
probably picking the tracts (which are 4×4 tiles) in consecutive order, starting in the northwest corner,
going down south, and then up to the next column of tracts.
How the destination finder decides that a Sim needs a new job is somewhat more complex. The Prima Guide claims that as of Rush Hour, "the Sims hold their jobs until something forces them to find another." But extensive testing in mature cities seems to show a lot more job changing than this statement would imply. Further research is needed here.
What is known at this point is that there are many different properties that can affect the destination finder's choice of a job for a Sim. Depending on the values of these properties, the destination finder may decide that no suitable job exists for a particular Sim, and the pathfinder won't even be run for that Sim. It has become clear that the destination finder has been tuned aggressively by Maxis in ways that we cannot access in order to minimize how much the pathfinder must run, since finding paths is one of the most expensive operations (in terms of CPU time and memory) in SC4. The destination finder will make an educated guess as to whether a path is even possible between a Sim's residence and a prospective job. Presumably, if it decides that such a path is not possible, it will look for other open jobs. Ideally, it would check all open jobs until it finds one it thinks would work, but at this point, we don't know if it does that, or if there's a limit on the number of jobs it checks. We do know that there are various properties that influence where it looks for jobs, and those are discussed below.
The destination finder also knows a little bit about how the pathfinder works, and uses this knowledge to help decide whether or not it thinks a job is reachable from a residence. In determining a more precise value for the perfect pathfinding heuristic, I found out something very interesting: In deciding whether a job is reachable from a residence with the current traffic simulator settings, the destination finder weighs the presence of subways very heavily, especially subways that go very near the residence, and presumably, those that go near the job as well. It's not just subways, though - any rail network will do, and highways will work almost as well. It's just easier to place a large network of subways than any other type of network, since they don't take up surface real estate. At first glance, this whole behavior seems very strange indeed. It seems even stranger when you discover that this holds true even when the traffic simulator uses perfect pathfinding, and even when Commute Trip Max Time is set to many times the amount required for a successful trip. Even in such circumstances, buildings can be abandoned due to commute time when perfectly good jobs are available in the city. But add a few subways in the right places, and abandonment disappears.
To understand what's happening here, it's important to remember that in the original Maxis traffic simulator, Commute Trip Max Time is set to six minutes. And in the original Maxis simulator, using the subway speed of 150 kph, you can get from one corner of a large tile to the opposite corner in 3.28 minutes via subway. In other words, you can get from anywhere to anywhere else on a large tile via subway in the original Maxis simulator, and still have enough time left over to walk a little ways to and from the stations. I think this helps explain why the six minutes was originally chosen for Commute Trip Max Time. It also allows the destination finder to make a quick and dirty test. If there are enough subways around, and the subways go close enough to the businesses and residences, then with perfect pathfinding (or something close to it), the Sims can probably make it to such a job within six minutes, and the destination finder hands off the source/destination pair to the pathfinder. But without enough subways or other high-speed networks, they may not, and further tests have to be done.
This only makes sense if we use the six minute figure. But this behavior persists even when Commute Trip Max Time is set much higher - even a hundred times as high. The only way I can think to explain this is that the six minute figure is hardwired into parts of the destination finder.
There's another interesting implication here. Sims can be guaranteed to reach anywhere on a large tile only if perfect pathfinding is used. Without perfect pathfinding, the destination finder will preemptively discard many otherwise valid trips, as has been shown in the experiments mentioned above. This would tend to support the theory that the Maxis programmers originally intended that the traffic simulator be used with perfect pathfinding, and indeed used it themselves; it was likely only the constraints of having to run a Pentium III 500 with 128 MB of memory that resulted in perfect pathfinding being abandoned for the commercial product. This issue is discussed in more detail in the Appendix.
The destination finder also uses a time limit in deciding what trips are feasible. Based on the various properties described below, if it thinks that calculating a valid path is going to take more than a certain amount of time, it declares that path as being invalid. In standard A* pathfinding (described below), values for the heuristic lower than the perfect value should still produce perfect paths; they just take longer. But in SC4, values lower than the perfect value can result in additional abandonment or downgrading. This is due to the time limit imposed by the destination finder.
The properties that are known to affect the operation of the destination finder are as follows, in approximate order of importance. When optimum values for these properties have been through experimentation, these optimum values are noted after the property's description.
Pathfinding Heuristic (a.k.a. Nearest Destination Attractiveness) Even before Rush Hour was released the7trumpets and many others recognized this as the most important property in the whole traffic simulator. And even back then, when Maxis was still talking to the SC4 community, they referred to this property by both of its names. Both aspects of this property come into play in the destination finder.
The traffic simulator's pathfinder uses a modified version of the A* algorithm, which is described very well in Amit’s A* Pages. Basically, the number and complexity of the possible paths between Sims and their jobs grows exponentially with the size of a city. The A* algorithm is designed so that it will always find a path between its source and destination points if one exists. The pathfinding heuristic is a constant that determines how close to perfect these paths are; i.e., how close they are to the fastest possible path. In perfect pathfinding, the value of the pathfinding heuristic is such that the fastest possible path is always found. In SC4, this number has been experimentally determined to be approximately .005797. The behavior of A* is generally exponential, in that as the pathfinding heuristic approaches the perfect number, the time to compute paths rises exponentially. However, as the pathfinding heuristic gets close to the perfect number, the exponential behavior gradually decreases, and it costs less and less to approach perfection. Below the perfect number, the paths produced are still the fastest, but the time to compute them increases again. In Amit's words:
So we have an interesting situation in that we can decide what we want to get out of A*. At exactly the right point, we’ll get shortest paths really quickly. If we’re too low, then we’ll continue to get shortest paths, but it’ll slow down. If we’re too high, then we give up shortest paths, but A* will run faster.
In a game, this property of A* can be very useful. For example, you may find that in some situations, you would rather have a “good” path than a “perfect” path...
That's how standard A* pathfinding works. However, in SC4, much of the destination finder has been designed to cripple the activities of the A* pathfinder for the sake of efficiency. Whereas the standard A* algorithm is designed to always find a valid path if one exists, regardless of the value of the pathfinding heuristic, in SC4 the probability of finding a valid path declines as the pathfinding heuristic moves away from its theoretically perfect value, which is approximately .005797. So while in standard A* pathfinding, the worst penalty for not using perfect pathfinding is having longer paths, in SC4 the worst penalty for not using perfect pathfinding is not finding valid paths at all. This is a big difference, and is where most of the "Abandonment due to commute time" comes from. Furthermore, if some residents of a building aren't able to find valid paths to jobs, but others are, the pathfinding failures of the unemployed residents is averaged in with the commute time of the employed residents. This can result in the commute time that is associated with the residence being designated "Long," which reduces the desirability of the residence. This can happen even when all the employed residents of the building have short commutes.
It was mentioned above that in the traffic simulator, the Pathfinding Heuristic property is also known as Nearest Destination Attractiveness. The reasoning behind this is very simple. Although the distance a Sim can travel during a commute is theoretically limited only by the Commute Trip Max Time property, in practice the Pathfinding Heuristic plays a big part as well. The higher the Pathfinding Heuristic, the more likely it is that the Sims will not take the fastest path, and instead will take the most direct path. In other words, a higher Pathfinding Heuristic effectively reduces their range of travel. The destination finder takes this into account, as it figures that there's no point in setting a destination that the Sims can't reach, and the higher the Pathfinding Heuristic, the more the destination finder steers the Sims to nearer destinations. Unfortunately, the destination finder appears to be overly conservative in estimating the limiting effects of the Pathfinding Heuristic. The result is that the destination finder draws a line beyond which the Sims cannot go in their travels, based on the values of the Pathfinding Heuristic and the Commute Trip Max Time. This line has been observed by multiple people; for example, in this post by jplumbley:
Although what is intriguing is your roads are not over capacity. There seems to be an invisible "line" that is stopping Sims from going further, I have a feeling this is where the maximum distance of the travel is.
That is exactly what was happening. The destination finder figures that the pathfinder will never find a valid path to points beyond that line within the time available, so why spend the extra CPU time and memory letting the pathfinder try to solve what is probably a hopeless task? So the pathfinder never runs for those Sims for whom a destination cannot be found on their side of the line.
This entire strategy accomplishes what it sets out to do - it gives a basic implementation of A* pathfinding while limiting the amount of CPU time and memory spent in these expensive calculations. But it does so at great cost. Instead of having a pathfinder that always finds valid paths, we have one that finds valid paths most of the time, the exact percentage depending on the value of the Pathfinding Heuristic, Commute Trip Max Time, how close zones are, and the size of the cities in question. Fortunately, if we use perfect pathfinding and follow the guidelines about using high-speed networks, realistic cities of almost any size (along with many not so realistic ones) can be built.
What about traffic simulators that don't use perfect pathfinding? If zones are intermixed closely, than large cities can still be built quite successfully. For smaller cities, the complexity of paths declines exponentially, and the traffic simulators all begin to behave quite similarly in terms of pathfinding. But there is no downside at all to using perfect pathfinding; even the supposed performance disadvantage is minimal at best. For example, SC4 using the Simulator Z v2.2 has been measured to run from 0% to 10% slower than SC4 using the standard Maxis simulator - not a big difference considering the difference in results. This advantage of perfect pathfinding was known to the SC4 community even before the release of the Rush Hour pack; this is documented in the Appendix below. Optimum value: .005797
As this guide is too big for a single post, it will be continued in succeeding posts.