Mott did a fantastic job at the beginning of this thread illuminating points that many of us did not know, and doing so in a very clear and logical manner. In effect, he peeled back a few layers of the game to let us see what was going on underneath. However, he also understood the limits of his knowledge; at one point, he said, "I'm a math major, not a programmer," and he ended his series of posts with the following:

That's all I have. If anyone can correct/contradict any of the above, maybe a programmer knows more specifics about A* CPU/RAM use than I do, then fantastic. I should be pretty close though.

So I would like to use this post to essentially continue from where mott left off. Specifically, I'd like to take a closer look at the game from a programmer's point of view and peel back a few more layers. Mott certainly was pretty close, as he said, but if you apply certain technical aspects of programming knowledge to the observed behavior of the game, it's possible to understand the game a bit more accurately than he described it. I want to stress that this is in no way a criticism of mott, or anything he did; it is simply building on his understanding to go deeper. This post is intended for everyone from knowledgable players to advanced developers. As a result, what I say in the earlier parts of this post may be familiar to many people. But by the time you get past the first few paragraphs that start in boldface, I think I will be entering new territory for the vast majority of readers.

I really liked the way mott started his posts by listing a number of important but nonobvious points, so I will do the same here. As in mott's posts, the connection of these points to TE lots may not be immediately obvious, but an understanding of them is necessary in order to build up to the part of this post that directly deals with TE lots. So here are some more points that are important to understand:

**Sims don't commute to and from work every day.** Not even every weekday. This is easy to demonstrate. Run your city at whatever speed you like. While it's running, use the Route Query Tool (shortcut key Alt-/) on a network tile such as a road tile. Note the various totals for the different travel types; these are the morning commute totals. Note that they don't change with the time of day (nor the commute period), nor do they change as the calendar advances. If you switch to Evening Commute on the Route Query legend, you'll get the totals for the evening commute, but these don't change over time either. Switch to the Traffic Congestion View or the Traffic Volume View, and you'll see that these are static as well. As far as traffic is concerned, nothing at all happens in Sim City until the next time the traffic simulator runs, which is every four months or so. And even then, all that happens is that Sims' routes are recalculated. When this happens, all the signs of traffic mentioned above change essentially instantaneously. Which brings us to the next point:

**There is no traffic.** If the Sims don't ever commute, and the traffic simulator merely recalculates routes, then where is the traffic? There are the cute little automata, but most people know that they have only a very slight connection with what's happening in the game. But what about the numbers on the roads, in the MT stations, in the residences, at the jobs? And what about the two different traffic views, Congestion and Volume? These are all results from the last traffic simulator run, and they remain static until the next traffic simulator run, months away. They show a summary of the routes the Sims would follow on the day immediately after the last run of the traffic simulator. But the Sims don't actual travel these routes; for the game's purposes, they don't need to. The game just needs to know where these routes are so it can make it look to the players like the Sims are commuting. It's as if the traffic simulator constructs a detailed photograph of all aspects of traffic in the city whenever it runs, and whenever you enquire about anything having to do with traffic, it shows you the relevant part of the static photograph, which may have been taken months before. But since the Sims aren't really commuting, and there isn't really any traffic, then...

**There are no accidents.** No, this is not some grand philosophical statement; I'm talking about vehicular accidents here. Now those who are familiar with the traffic simulator exemplar might say, "Wait a minute! There are four different properties referring to accidents. What are those all about?" Internally, accidents are simply another form of congestion, added to the main congestion figures. The amount that is added is based on the settings of the Congestion to Accident Probability and Capacity to Accident Probability properties in the exemplar. But accidents don't actually occur in the traffic simulator, because the traffic simulator does not manage dynamic traffic flow. There is no dynamic traffic to flow. (This all gets a little Zen-like after a while.) However, there are the cute little automata, and the Accident Duration and Accident Check Period properties govern how accidents appear to the player. Since the automata accidents are tied to the accident probability, which in turn is tied to congestion, accidents are still a good indication of how congested a road is getting. This is true even through accidents don't actually "happen" in the traffic simulator. So when you see an accident happening with the automata, nothing is actually happening at that moment on any deeper level in the game.

**The building query numbers are often misinterpreted.** I have to plead guilty to this one myself. However, at this point, it's possible to say definitively what they are. The second figure in the Current Occupancy (for residences) or Current Jobs (for commercial or industrial buildings) is the maximum potential occupancy of the building. I think this has been pretty obvious to everybody. For residences, the first figure in this field refers to the actual potential occupancy; this means the maximum number of Sims who are currently able to live in the building. Normally, in a thriving city where the population is constantly growing, every residential building is fully occupied, and this first number corresponds to the population of the building. However, in cities where the population is static or declining, the actual population of the building may be less than this first figure. It is the actual population number that is used when determining a city's total population. Unfortunately, there is no way to exactly determine what it is for a particular residential building. Meanwhile, for commercial and industrial buildings, the first figure refers to the actual number of jobs available in the building; it does not indicate how many Sims are actually working there. The first figure in all cases tends to be fairly close to the second number, unless the building is abandoned, in which case it is zero. The Prima manual is incorrect in describing what these numbers mean.

To determine the actual number of workers in a residence, you need to use the Route Query Tool, which lists commuters by travel type. However, you can't simply add up all the numbers here to get the total number of commuters, as those Sims who take multiple travel types to work will be listed multiple times. For example, a Sim who takes a bus to a subway stop and then takes the subway the rest of the way to work will be listed under both Bus and Subway categories. So finding the actual number of commuters may take a little work, including looking at the actual routes that the Sims take. Jobs for commercial and industrial buildings work in a similar way. It is this hidden number of commuters or jobs that determines whether a building becomes abandoned; only the actual workers count in this decision.

This all ties in to the previous points. When a new building grows, it initially shows zero for actual occupancy; when the building is completed, the zero briefly changes to the maximum occupancy, and then settles down to a slightly lower number. How does this fit in with my static description of traffic? If you use the Route Query Tool on a building that has just grown on an empty lot, you will find it has no commuters or no jobs, as the case may be. Only when the traffic simulator next runs are the Sims actually assigned jobs, and travel routes are created for them. Until then, they all sit at home watching SimTV, and newly built office buildings sit vacant, despite the occupancy number. There is one exception here: If a new building grows replacing an older building, and the wealth levels of the old and new buildings are compatibile, some Sims from the old building may decide to stick around. In such a case, while the building is under construction, even though the current occupancy shows as zero, the Route Query Tool will still show commuters for the building (while it's being constructed!) and routes for them. The same goes for commercial and industrial buildings under construction. This doesn't violate anything I've said above, as no new routes are calculated for the Sims who stay over. (At least not until the next run of the traffic simulator.)

So now you see a bit of what's really going on here. The traffic simulator itself is implemented as a finite state machine. This means that it starts out with the entire complex state of all traffic, which is static, processes it, and spits out a new state, which remains static until the next traffic simulator run. It's important to realize that the new state is based entirely on the old state, and does not take finished portions of the new state into account when calculating the rest of this state. This is essential if proper optimization is going to be done. So when mott refers to "making the very first Sim to use a road start slowing it down immediately," that's not quite what happens, since congestion is undefined for the current simulator run until the end of the run. (Again, this is necessary for optimization reasons.) Until then, the game uses the congestion figures from the previous simulator run. However, mott's conclusions still hold, although for different reasons than he states. Adding the extra congestion levels means that paths are going to be more differentiated in the previous state, which leads to more tiebreaking when calculating the current state, which leads to better simulator efficiency.

This type of model is called "finite state" because there are a finite number of states a city's traffic can be in when the simulator starts running, and there are a finite number of states that the traffic can be in when the simulator finishes with it, although both numbers are astronomically large. The alternative to a finite state implementation would be a traffic simulator that ran continuously, updating traffic in real Sim time. This would be a little harder to program, but the main problem with it is that it would take forever to run on anything less powerful than a supercomputer. So using a finite state machine implementation for the traffic simulator was not merely a wise choice; it was the only choice.

As has been noted elsewhere, the traffic simulator uses a Manhattan A* algorithm to do pathfinding calculations. But what hasn't been noted before are the optimizations that are being performed. The algorithm that mott describes is fairly complex; it has things like exponentials in it, and you don't want to use it any more than you have to. If you have a large tile with millions of Sims, if you had to apply this algorithm to find the path for each one of them, it would take far too long. Fortunately, there are well known optimizations that can be applied. For example, take the case where a new residential tower goes up and thousands of Sims move in. Now they aren't all going to be going to thousands of different buildings for their jobs, so some of them will be starting at the exact same place and ending up at the exact same destination. Suppose you've just used Manhatta A* to calculate the best path of one Sim to his or her job. Now you find that the next Sim is going to the exact same job. Do you use Manhattan A* to perform the same tedious calculations which give the exact same result to get the Sim to his or her job? Definitely not.

What you need is a way to remember routes that you've already calculated for the current run of the traffic simulator. The remembered routes are only good for the current run of the simulator because between runs, the user may have built new roads, torn others down, built or torn down MT stations, etc. Congestion may have changed, buildings may have grown or been demolished. So we have to stick to the current run.

The next question is, What do we remember? We could remember the entire path from start to finish. But there are an awful lot of these paths, and if we store them exactly, what do we do when Sims one building closer than our origin want to go to our destination job? Or perhaps to something along the way? We could store all possible subpaths of the path we calculated, but this starts eating up a huge amount of storage fast. Simply storing all the subpaths starts taking significant CPU time as well.

Instead, we store a useful subset of the paths - a "coarse grid," as it's technically termed. What we use for this coarse grid depends depends on what our main mode of travel is. There are two main travel modes - car and mass transit. (If pedestrian-only travel stores routes, as I would think they do, they would use the car grid.) The car grid consists of all road intersections, where here a "road" is anything a car is permitted to travel on, while the mass transit grid uses all the mass transit stations. So if a Sim car travel route is being calculated for the first time this simulator session, the route between the first intersection through the last intersection is stored in a hash table. (A hash table has the very useful property that no matter how big it is, storage and lookup times are essentially constant, on the order of nanoseconds.) All contiguous subpaths of the original path are also stored in the hash table; all eligible subpaths have intersections as end points. As further Sim car routes are calculated, each time the simulator reaches an intersection, it tries looking it up in the hash table to see if it is a waypoint - an intersection that is part of an already computed path. If any of these paths go through the intersection and also go in the direction that the Sim is trying to go, then rather than recompute the path over that segmented, the precomputed path is used. Precomputed paths may be used to calculate a new path that leads part way to the destination, while the remaining distance is then computed with a new path, which, along with the entire new path and any new subpaths, is then added to the database (which is actually the hash table) of precomputed paths. So very quickly, a set of precomputed paths is built up for the most commonly used routes, saving tremendous amounts of CPU time in calculation. And it's not even necessary for the simulator to check a path segment by segment; it can take the intersection closest to the origin along with the one closest to the destination, and see if a path has been computed for the entire route. Furthermore, such a precalculated path may exist even if it has not been calculated for any Sim up until this point, as it may be one of the subpaths that has been stored in previous calculations.

Mass transit paths are calculated in a similar way, again using intersections as a coarse grid. However, in this case, TE lots are also included in the coarse grid. Since transit switches can happen only at MT stations, only they serve as waypoints; intersections do not. Otherwise, things work similarly as for cars. And since everything is heavily optimized, the number of calculations of trips through TE lots is a small fraction of the actual number of trips through them. Essentially, only one calculation needs to be made for a TE lot for any given path, no matter how many Sims use that path. When a precalculated route is used, either for cars or mass transit, each square on the route is updated to account for travel by a new Sim. But since the route is precalculated, no new calculations are needed anywhere, including on those parts of the route that go through TE lots. Thus the impact of TE lots on the simulator is minimized.

None of the above is my invention; these are all standard programming techniques, and standard applications of the Manhattan A* algorithm. I used as my main reference the same resource that mott did, namely,

Amit Patel's paper. A fair understanding of math and programming is required for reading this paper, but everything's in there. Amit makes passing references to things like hash tables and waypoints; I've expanded on them a little bit here. And while what I've described is not guaranteed to be the exact implementation used in SC4, something very close to it, with essentially the same properties, must be. Any programmer who knows how to implement a Manhattan A* algorithm, as the Maxis programmers clearly did, will also know of all the methods I mentioned and more, and will use them to optimize the simulator as much as possible.

Now that the basic principles have been laid out, it is possible to use them to come to some very specific conclusions about the usage of TE lots in the game. Since these conclusions are in contradiction to some of the conventional wisdom about the workings of TE lots, I will state the mistaken beliefs in the form of myths, which is essentially what they are, and then show why they are not true.

**Myth #1: Whenever a Sim enters a TE lot, the Sim's commute time clock gets reset to zero.** Searching for the first appearance of this statement, I found it showing up on a forum here on January 31st. Since then, it has been repeated in a number of places by several different people, but never with any supporting evidence whatsoever, nor any indication of why it would make sense for the game to do this. Some people are under the impression that mott said this, but he didn't. What he did say was this:

Transit Switches were invented to solve a particular problem: Sometimes a Sim has to get off a bus, and then walk back the same way he had just come, on the same street.

The problem with that is, a simulated trip cannot backtrack. The pathfinding system does not allow the same route to be traveled twice during a trip.

The solution was adding the "Transit Switch" property to lots. Lot-makers may recognize this as the one that makes a lot function as a bus stop or train station, by converting traffic from one form of transit to another.

They also make the Sim "forget" how he got there.

When the pathfinder encounters a Transit Switch lot, it generates a new trip, from the lot to the destination. This "new" trip is free to try routes that were already tried by the "old" trip. That way, Sims can walk any direction when they get off the bus, and the backtracking problem is solved.

(I have included the whole quote because I will be referring to other parts of it later on.) So to sum up, what mott said was that for the sake of backtracking, the Sim must be able to (temporarily) forget how he got to the current point, as the A* algorithms do not allow backtracking. Nothing was said about forgetting commute time. And a little analysis will show that if a Sim actually did forget his commute time when entering a TE lot, it would break the pathfinder completely. For as mott described in

this post, paths are calculated by trying out different paths and seeing how the result (i.e., the commute time) compares to the ideal time, and sometimes to other possible paths. If the commute time is set to zero during the calculation of any single path,

*such a comparison becomes impossible*, as there is no longer a valid trip length to compare. So under these circumstances, pathfinding itself becomes impossible.

To me, that argument seems airtight. For anyone not convinced by that argument, there are equally convincing arguments. For example, I have about a dozen cities filled with RTMT stations. You can't walk a block without running into one. Which also means that you'll run into one wherever you drive, or ride the bus, or take the subway. Now if a Sim's commute time were reset to zero every time they entered one of these stations, it would be getting set to zero repeatedly, and they would never run out of commute time. But that's not the case at all. These cities are just as sensitive to the Commute Trip Max Time Property as any others; extensive testing has shown that there's no difference here. That simply couldn't be true if the commute time were constantly being reset.

So the bottom line is: A Sim's commute time is NEVER reset when entering a TE lot.

**Myth #2: Whenever a Sim enters a TE lot, the Sim forgets how he got there.** This may seem to be exactly what mott said in the long quote above, and in fact, it is. But if you recall from the beginning of this post, he also said, "I'm a math major, not a programmer." So his math and logic are basically correct here, but he was apparently unaware how good programming can completely eliminate this problem. I have no criticism of mott here whatsoever; he did a fantastic job, and simply made it clear where the limitations of his knowledge were.

So how do we allow backtracking without recalculating paths? Our main limitation is that we're not allowed to retrace paths we've already taken; this is slightly more generalized than simply forbidding backtracking. But the only time we would ever want to retrace paths is if we're using a different travel type than in the original traversal. To use mott's example, the Sim gets off the bus and then walks back along the same road the bus has come. So what we really want to do is to say that the path is different if the travel type is different. This is easily done by adding a third coordinate to each location in the Sim's path. In addition to the standard x and y coordinates, we add a z coordinate, which is a number representing the travel type in use at the time. Once we do that, the backtracking problem simply disappears, as the Sim is now seen as taking two different routes. For most of the Manhattan A* algorithm, the x and y coordinates are used in the usual way, and the z coordinate is ignored. But for seeing whether or not we have traversed a certain square, the z coordinate is examined. This is very easy to do using the implementation of A* that Amit describes on the second page of his paper.

Looking more closely, it turns out that not only is the method of recalculating paths at every TE lot entrance excessively costly, but it's also insufficient to prevent all backtracking problems. To take a simple case, look what happens at a standard highway cloverleaf when a Sim drives over the lower highway on the top highway, then takes a right turn (or left, depending on your country) onto the exit ramp leading to the lower highway, merges onto that highway, and then drives under the upper highway. This happens all the time. The problem is that

*it's not allowed by the standard A* implementation that mott references.* The reason is simple: "Backtracking" in this implementation actually means "traversing any square more than once." And when the Sim drives under the upper highway, he's actually traversing the same square a second time. Mott's solution doesn't help us here; the Sim remains on the same network and doesn't pass through any TE lot, so there's no opportunity to recalculate paths. You could special-case this situation, but unfortunately, there are too many others like it. You can have rail loops that cross themselves, monorail loops, el train loops, other types of highway interchanges, etc. You need some method that can handle all these cases automatically.

Fortunately, the coordinate system I described can be easily modified to handle all of these cases. It does need modification, because all the cases I just described happen with a single travel type. But what these cases also have in common is that the direction of travel the second time across the re-used square is orthogonal to the direction of travel the first time across it. So, one solution would be to add a fourth coordinate to the triplet, making this additional coordinate 1 for north-south travel and 0 for east-west travel, or something along those lines. But since the purpose of this fourth coordinate is identical to that of the third, z coordinate, it would be simpler to combine them. You could simply use the z coordinate in the way I first described, but use a positive sign for north-south travel and a negative sign for east-west travel. So then you still have your three dimensions, and all your backtracking problems are solved.

This three-dimensional coordinate system has other benefits as well, which make it a compelling choice for the SC4 implementation. For example, let's assume that a Sim is walking down the road and reaches a square with a bus stop on one side and a subway station on the other side, and that furthermore, both the bus and subway continue down the road on which the Sim is walking, with the subway running directly under the road. What route does the Sim take? In the classic Manhattan A* algorithm, all three forms of transportation - walking, bus, and subway - follow the same path (at least once you get beyond the transit station). With the standard two-dimensional coordinate system, extra work needs to be done to differentiate among the different travel types that follow the same path. With the three-dimensional system that I have described, no extra work is needed, as the travel types are all considered to take different paths, and the algorithm handles this case automatically. This three-dimensional implementation is both the simplest and most efficient that I can think of now, and it would be quite obvious to an experienced programmer.

So the bottom line here is: By choosing an appropriate coordinate system, a Sim's path NEVER needs to be recalculated, and backtracking is always handled properly.

**Myth #3: RTMT stations are bad for your traffic simulator and/or bad for the game.** This section assumes and build on the conclusions from the previous section. When cars travel through RTMT lots, they always emerge as cars. So as long as the Transit Switch Entry Cost is set properly for cars (which is not difficult), RTMT stations are essentially invisible to cars; they behave just like a road or street network tile. No extra decisions need to be made, and the cost of cars' going through these TE lots is not significantly different than having them travel over network tiles. Freight trucks are similar, although since their speed is typically a little lower than cars, they travel through the TE lot a little faster than they would over network tiles. But the difference is not very large, and as long as you don't have RTMT stations every other tile or so (which is a bad idea for many reasons), the average speed of freight trucks is hardly affected at all. As for pedestrians, generally when they enter an RTMT lot, they board a bus or subway so the Transit Switch Entry Cost works fine in such a case. In the few cases where they walk across the lot and keep on going, they do end up going much faster than they should across the lot. But this case is relatively rare, and even when it happens, it should have no significant larger repercussions, especially if the RTMT lot is a 1x1 lot.

As for mass transit, if the costs for passing through a roadside TE lot are usually almost nonexistent, they are almost nonexistent for buses and subways passing through RTMT lots as well. So RTMT stations are really no worse than other TE lots. There is one series of experiments that I did last year that provided powerful support for this statement. I had a half dozen fully developed, highly urbanized, dense CAM cities (five medium tiles and one large tile) which had all been played for a long time, and which contained no RTMT lots. Once I started using RTMT, I liked it so much that I went through each of these cities and replaced all roadside lots with RTMT lots wherever possible, which was almost everywhere. This is the only change I made to the cities. I continued playing each of the cities, and in no case did I notice the slightest difference in performance from before I made the change. If RTMT really did make the traffic simulator work a lot harder for each station, or even a bit harder, then I should have noticed a large drop in performance when I suddenly filled a whole city with these stations. But I didn't. This is also strong evidence that the programming techniques I described (or ones similiar to them), which are all very basic, are actually implemented in the game.

Finally, TE lots in general are a lot more benign than one would think from mott's description. The reason for this is not that mott is describing things inaccurately, but that there standard programming practices that are able to eliminate unnecessary costs. Some costs cannot be eliminated; every time you plop a TE lot, you've inserted more branch points into your map, which means more paths for the simulator to explore. So you don't want to supersaturate your city with TE lots (i.e., one every two or three squares), as this will definitely have an impact on performance. But as I've tried to demonstrate, and have found from experiments in my own cities, the performance hit from individual TE stations (be they RTMT or otherwise) is a lot less than mott describes. So having a reasonable number of TE lots in your cities is not going to be a noticeable drag on performance. And "a reasonable number" here means whatever you need to make your city run properly. If you find your TE lots are maxing out on capacity, don't just add more of them; use bigger capacity stations. This is much easier on the traffic simulator, and it's much more realistic. Also, it's very important to use high quality, properly built TE lots; all the optimization in the world won't help you if your TE lot is broken.

So I hope I've been able to clarify some points about TE lots from a programmer's point of view. It's not necessary to be miserly about using them; if you use them approximately the way they're used in real cities, or even a reasonable amount more, you'll be fine. And RTMT lots carry no significant disadvantages over other TE lots. They also look more realistic than most roadside lots, and make building your city a lot easier.

I have written this post based on my experience and understanding, which I believe to be correct. However, it is very possible that I have made some mistakes. I would be very happy to hear about them so that I can correct them. I would also be happy to elaborate on any points that are unclear. Thank you for reading this far, and for your patience with the length of this post.