**Release of Simulator Z v2.1**

**Perfect Pathfinding Revised**

This new release of Simulator Z contains a much more accurate perfect pathfinding value for the pathfinding heuristic. Most of this post is somewhat technical; if you just want to see what this means for users and possibly download the new version of Simulator Z, skip down to the part just below the horizontal line. Watch out for elephants along the way, though...

I was thinking more about

**woodb3kmaster**'s situation, and while I believe that what I said to him was correct, I was disappointed that the traffic simulator couldn't be tuned better to address his problem. Yet before posting my possible solutions, I had tried tuning all the parameters in the traffic simulator that I could think of, with no effect.

Revisiting the problem, I started thinking more about the pathfinding heuristic (PH). The perfect pathfinding value for the PH is defined to be the highest value of this constant where the fastest path is always found. Lower values will still give the fastest path, but they will take longer to compute. Higher values become less and less likely to give the fastest path, although the pathfinder will run faster. This means that although values for the PH that are lower than the perfect value will take more time, the results should be identical to using the perfect pathfinding value.

At least that's how it works in standard A* pathfinding. Unfortunately, SC4 uses a modified version of A*, in which due to the interactions with the destination finder, pathfinding deteriorates with values of the PH that are lower than the "perfect" value. Furthermore, since one of the duties of the destination finder is to throttle the CPU usage of the pathfinder, even the perfect pathfinding value of the PH may not always find the perfect paths - in fact, sometimes it may not even find paths at all, even when valid ones exist. Nevertheless, the perfect pathfinding value of the PH will always find the best paths possible, compared to other values of the PH. I'll be going more into the details of the way SC4's variation of pathfinding works in my post on the destination finder, which is in preparation.

In any case, it's still important to know the value of the PH that results in perfect pathfinding, even if it's SC4's version of perfect pathfinding. The main previous record we have of what this value is comes from Tropod, who used the value of .003 consistently; it still appears today in Simulator E. We know that the7trumpets was the first person to come up with a perfect pathfinding version of the traffic simulator, but I have been unable to find what value he used for the PH. In the lack of evidence to the contrary, I have been assuming that it is the same .003 that Tropod used.

When I first built Simulator Z, I wanted it to use perfect pathfinding from the start. I figured that Tropod's value was probably correct, but I thought it was important to do a fair amount of testing to verify it. Unfortunately, I did not understand the workings of the traffic simulator as well as I do today, and so my tests were less precise. To be completely sure that one had found the perfect PH, one would have to check every path in the city and verify that it was the fastest path possible. Even to do this for a single path is a lot of work, and must be done manually; to do it for the thousands of paths that exist in a large city would be impossibly time consuming. However, values of the PH that are significantly higher than the perfect value produce many paths that are less than optimal, and this is easy to see in the traffic volume view. Furthermore, in SC4, such values can produce abandonment, as we have seen in earlier tests in this thread. And in general, the health of a city improves as the PH approaches its perfect value.

Using this understanding and doing a number of tests, I was able to determine that the perfect PH lay somewhere between .003 and .006. Below .003, there were definitely no improvements to the paths, and CPU time started rising rapidly. There also seemed to be some other subtle signs that .003 was the correct value, but they were somewhat ambiguous, and I ended up settling on .003 because it was both consistent with my tests and it was the number that Tropod claimed was the perfect value. Recently, I have also done other experiments showing that values below .003 gain nothing.

In considering

**woodb3kmaster**'s situation, I decided to re-examine the area between .003 and .006. This time, I had much more precise tools available. Specifically, there's the following relationship, which I outlined a while ago:

Pathfinding Heuristic => Commute time => Desirability

To spell it out, the better the PH, the shorter the commute time, which results in higher desirability for residences. This has shown up again and again in the tests that I have displayed here, with graphs showing the residential population migrating to higher wealth levels as the PH approached its optimum, and migrating to lower levels as the PH moved away from its optimum. If desirability becomes too low, this results in outright abandonment of residences.

Armed with this information, I began examining the values between .003 and .006, essentially using a binary search. When I got down to the final values, I repeated some tests to make sure I had exactly the right values. As I narrowed in on the final value, the change in the population lines between values in the Pop & Jobs graph became unnoticeable. At this point, I switched over to looking at the abandonment itself, which would still change significantly from one value to another. Finally, I got a value that consistently produced the lowest abandonment over time, test after test. I was also aware of when I had told Lenny that I was sure that the .003 value was correct to within a few percent; my tests until then didn't really provide enough data to state that with such confidence, and I was largely relying on Tropod's figure. This time, I relied on my tests alone, tests that were much more accurate and that gave a precise answer. And the number that they finally gave was...

What's especially interesting about this number (aside from the fact that it's surrounded by dancing elephants) is that instead of one significant digit, as the .003 value has, this value has four significant digits. The binary search method allowed me to get down to this level of detail quickly, and it was only at this level that adjacent values began to look at all similar. There are two effects that are in conflict across the entire range of PH values: the better pathfinding that comes with a lower PH, and the worsening of the pathfinding that results from the destination finder's trying to limit the time that the pathfinder spends finding paths. It would seem reasonable that these two trends would cross at the perfect PH, since lower values don't provide better pathfinding but do take more time. And in fact, the pattern of abandonment changes right at the number I have cited.

Is this truly the perfect PH in the terms that A* defines it, or is this simply the best PH for SC4? For the reasons I just mentioned, I believe that it is both. However, there's not enough data to prove the first part conclusively. Nevertheless, the second part definitely seems to be true, for reasons that I describe below, and that's enough to make this value "perfect" for SC4.

This value for the PH was sufficient to get rid of most, although not all, of the abandonment in my large city without subways, which seems to be having a problem similar to

**woodb3kmaster**'s. I went from a state of having a large neighborhood filled with abandoned buildings to a steady state where only two or three buildings were abandoned at a time. Many of the other buildings in the neighborhood were upgraded to their original wealth levels. I then tried out this value for the PH on all the rest of my cities. One city had no change, but the others had positive changes ranging from small to moderate. I also tried this out on

**sumwonyuno**'s main city, which is now a standard part of my test suite. Recently, I had done one test that was able to recreate his original problem. I bulldozed a large section of the low-density commercial buildings in the outlying areas of his capital city. Although the buildings came back fairly quickly, the number of workers did not return to its previous level. With the new PH, however, not only did the workers return, but a widespread building spree occurred in these areas, replacing smaller buildings with slightly larger ones; their size was limited by the low-density zoning.

How accurate is this number? Once I got down to this area, I tried out all values from .005793 to .005802, varying the tests by .000001 and repeating many of them. So this would imply a margin of error of no more than 0.017%. My tests of alternate numbers were not as extensive in other cities; since they did not suffer from abandonment, such a level of accuracy was not possible. But the tests that I did do and mentioned in the previous paragraph all supported this number as being the true perfect PH for SC4.

To summarize, using the new perfect PH value of .005797 has the following effects:

- Abandonment due to commute time, when due to limitations in the traffic simulator, is eliminated in all but the most difficult cases. Even in those cases, it almost all disappears.
- The desirability of all residences tends to increase; the exact amount of the increase depends on the city involved.
- Subway usage tends to increase, and in many cases, other mass transit usage as well. This is something that has been noted many times before when improving the PH, and is another sign that this value for the PH produces better pathfinding than what was previously considered perfect.
- The game as a whole will run somewhat faster; this a direct result of using a higher PH. The bigger the city, the bigger the speed increase.

I've attached a copy of Simulator Z v2.1 at the end of this post. Zack, please give this a try and let us know how this works for you. And

**sumwonyuno**, please give this a try on your downtown city - I think you'll like the results. Feedback from everyone else is welcome of course as well.