@jplumbley: Had a look at the file you posted. One important point: Never let the speed of a network drop to zero with congestion. It can trap Sims coming in from off-map with no way to route around the blockage, and there's no way to convey that information back in to the originating city. This throws the pathfinder into panic-mode and confuses the demand and desirability simulators. Make congestion slower than walking, and that should be enough to avoid the problem. I loved the congestion/speed curve; that should work wonderfully for what you're trying to do with the TLA.. I'm modding your file right now to make a few adjustments that you'd asked for. It'll be up in a few hours... but first...

---

I took a crash-course in A* pathfinding last night, courtesy of the Stanford Math Department Website.

Here's what I learned:

First off, the conventional wisdom of "higher heuristic = less CPU/RAM, lower = more CPU/RAM" is true only in a very general sense. The whole point of the heuristic approach is that if you get the heuristic close enough, the algorithm ceases to be exponential. It becomes linear, and it can actually use less CPU and RAM than a dumber algorithm would, while finding better routes too. It's not about "bigger" or "smaller," but about "closer."

Here's what's going on inside the pathfinder (I hope this is comprehensible...):

Suppose a Sim is at point A and wants to go to point B. The pathfinding engine computes the Manhattan distance between the two points (E/W tiles traversed + N/S tiles traversed). This number of tiles is then multiplied by the "heuristic," to obtain the "expected" time cost of the A-B trip. So, the heuristic is what you think the total step cost of an arbirtary trip will really be on the real map, divided by the number of tiles that would be traversed on a direct Manhattan path between the two points.

The best-case is that you get it exactly right: The actual per-tile step cost of reaching the goal by the most time-efficient route, is exactly the time you had guessed it would take to traverse the "Manhattan Distance" between the two points, at a per-tile step cost of the heuristic. In this case, only the very best route was traced by the pathfniding engine, it was found on the very first try, and comparison against the heuristic told the algorithm not to bother trying to beat it. Bulls-eye.

The odds of being exactly right on an arbitrary map with variable speeds, are much smaller than the odds of being struck by lightning. We can only hope to be close enough, most of the time, for things to work as well as possible considering that we cannot know the layout of a user-drawn transportation system in advance, or how much of the trip will be accomplished at what speed.

So, the better question is, "how close is close enough?" It turns out that there's a formula for this:

First, pick an arbirtary trip on the map, and compute the total error between the heuristic guess and the cost of the real optimum path. That is, the difference between the (Manhattan Distance * Heuristic) estimate, and the actual total step cost of the best route for that trip. (Remember that "step cost" is (1/speed) on networks, or the "Transit Switch Entry Cost" of transit switches). Just subtract actual total step cost of a trip from the "expected" step cost, and ignore the negative sign if there is one. Or vice-versa. It doesn't matter since we only care about the absolute value. That's your total accumulated error for the trip. If the error is exactly zero, you need to consider a less perfect test case.

Assuming error is not zero, look at the actual trip cost and the accumulated error. If either of these are less than 1, slide the decimal point over on both numbers, until they are both greater than 1. Scaling them like this is OK, just make sure that it's done the same for both. We'll call these "adjusted error" and "adjusted actual cost." [We're doing this to avoid inequality-reversal confusion in the next step.]

Now set your calculator on "scientific mode," key in that "adjusted error" amount, and then hit the (e^x) button. If the result is smaller than the "adjusted actual" trip cost, the algorithm may have tried a few bad turns here and there, but it realized it had done so at the next intersection encountered, and did not expand those paths any further. You again found the perfect fastest route, and CPU/RAM use remained linear (*not* exponential). In the worst-case, you matched the default Maxis setting's performance, you may have improved on it, and you likely found a better path too.

To put it another way, as long as the error between the (heuristic * manhattan-distance) prediction and the actual trip cost is between zero and the natuiral logarithm of the actual trip cost, you get "perfect pathfinding," AND optimal CPU/RAM use also. [Again, it's OK to just slide the decimals over on both numbers until they're both above 1, to avoid the inequality-reversal confusion that can occur when using fractions with log() and exp().]

Now, what if you guess wrong? What if (e^|adjusted error|) > adjusted actual cost? That depends on whether you guessed too high or too low, but CPU use will probably increase either way, compared to a "good" guess.

If you guessed too high (actual trip was much faster than predicted), the algorithm starts taking a straight line toward the destination for as far as it can regardless of network speeds, and will start to detour around obstacles at the last possible opportunity. If the "bad" over-guess was high enough, a zig-zag becomes indistinguishable from a straight line, as long as it's heading generally toward the destination. CPU use increases a bit compared to a smaller heuristic, because every perceived "equivalent" choice at every intersection along every dumb zig-zag has to be expanded and examined, and that eats CPU and RAM in an exponential manner. The algorithm will find *a* path to the destination. It is not guaranteed to be an optimal path, it may be a ridiculous one, and it may take more CPU and RAM to discover than a better path would have, given a smaller heuristic.

The default Maxis heuristic of 0.09 assumes that any given trip will take the same amount of time as a direct path would at a speed of 11. Anything faster than that, and you start seeing zig-zags and dumb choices because how much faster than 11 a route averages does not matter - it's considered the same as any other route that beats a direct route at speed 11.

If you guessed too low (there is no route as fast as the predicted one), the algorithm ends up re-tracing the map in search of the better route that it expects to exist. It's like a tiebreaking situation again, except this time, all of the known "good" routes are re-considered and it will, worst-case, check every possible path on the map trying to improve on the best route known. The algorithm does this as efficiently as it can be done, and it will always find the optimal route, but it's exponentially-growing in terms of CPU and RAM use as the estimate gets farther from reality.

The NAM's "perfect pathfinding" valiue of 0.003 will pretty much always find the best route on a large city tile, no matter what. It will use a lot of RAM and CPU if there are many equivalent routes, though. Interestingly, making the very first Sim to use a road start slowing it down immediately (like the "speeding" mod does) tends to reduce the number of potentially equivalent routes on the map at any given moment, resulting in less CPU and RAM use in the most common cases, not more.

Conclusion:

The "better" pathfinding version of the NAM plugins still allows some zig-zagging in my experience. The "perfect" version (heuristic 0.003) doesn't inherently use nearly as much CPU or RAM as it's advertised to in most cases, finds the optimal path in just about every case possible, and will actually receive a performance improvement from the "speeding mod" whereas the default Maxis value would not. It may actually exceed Maxis's performance in many common cases with that mod. Stick with the 0.003 heuristic for now, I'd say. Especially if you want to see the true results of any speed/congestion mods. Or anything else that's usually faster than 11.