SimCity Traffic, Under the Hood – Explained
The offcial SimCity blog just made a post explaining the internals of the traffic routing system:
It’s pretty simplified, but I suspect that it might still be hard for people to understand so I figured that I would try to distill it even further. I’ve done work with pathfinding systems in the past, and for the last couple of weeks I’ve been studying D*Lite, which is the pathfinding algorithm used in SimCity, and also playing with road networks and such in Unity (hence the latest tutorial on quill18creates).
There are two ways in which the pathfinding system in SimCity differs from how most people “think” of pathfinding in real life.
- The pathfinding system works backwards. It starts from the “goal” and works its way to the “start” location.
- The pathfinding system is about intersections, not roads. (NOTE: This doesn’t necessarily mean ACTUAL multi-way intersections — sometimes road segments can get split depending on how they were laid out. You can see this in game when you are upgrading roads or CTRL-bulldozing them. Sometimes only a certain amount will get selected. This will look like a single road, but is actually several road segments.)
Basically, here’s how it works:
When a vehicle is at an intersection, it looks at all other connected intersections and asks: How close are you to (this thing I want). Each intersection then replies and the car picks the one with the lowest number.
Note that at NO POINT does the vehicle have any idea what the cost of travelling to that next intersection is.
A car leaves the green residential area in the morning, trying to get to work at the yellow industry.
It will turn NORTH onto segment 5, because the north intersection has a lower number than the south intersection.
It will then go NORTH onto segment 6, because the next intersection on that route has a lower number (60) than the one on segment 4 (110). It doesn’t matter how much traffic is on segment 6, because the next intersection Is truly and correctly 60 away from the industry.
Now let’s look at the next example, in which segment 6 is split into two by the addition of a little dirt road intersection:
The previous intersection still has a weight of 60 (which is correct). However now, because of the traffic, the mini-intersection in between 6 and 7 has a very high weight, which means that our car will now take segment 4 (I am 110 away from industry) instead of segment 7 (I am 560 away from industry).
Using this information, we can DRAMATICALLY improve our traffic. Again, as mentioned above, this doesn’t mean that we literally need to add intersections (which slow down traffic in their own way) as long as we can force road segments to split.
Expect a video soon!