• Welcome to SC4 Devotion Forum Archives.

NAM Traffic Simulator Development and Theory

Started by z, August 02, 2008, 05:07:50 PM

Previous topic - Next topic

0 Members and 4 Guests are viewing this topic.

ldog

Really excellent thinking on the streets.  :thumbsup:
I've been wondering what to do with them myself.

About the avenues vs owr. Since the topic came up I've been observing them more closely myself.
I hadn't realized the capacity for ave and highway was per tile.
The ave really is a pair of owr. So equalizing them is not such a bad thing.
Being as the ave is a bit more expensive, just making it the "higher speed limit" equivalent of a pair of owr seems balanced enough.

All that being said I am completely ignorant of NWM needs, but in the end I hope you find values that work both with and without it.

z

#381
Challenge and the Traffic Simulator

Most people want their traffic simulator to provide at least some challenge to their game play, and of course different people desire different levels of challenge.  In order to pick a traffic simulator that supplies the proper amount of challenge for your city, it's necessary to understand what makes a traffic simulator challenging.  This is not as obvious as it may seem, which is why I'm making this post.

On one hand, the original Maxis traffic simulator could be seen as very challenging.  But it made it impossible to build large, healthy cities.  In such cities, one of the biggest problems was that a fair amount of residential abandonment due to commute time was unavoidable, even when there were suitable jobs within easy commuting distance for the Sims who eventually left the city.  So the type of challenge that makes it impossible to create a healthy city, no matter what you do, is not very desirable.  Being a little more specific, having abandonment due to commute time when appropriate jobs are within easy commuting distance is not desirable, because it is not something that can be fixed by the player, no matter what is done.  In the real world, some abandonment is normal, and as an extreme case, half the city of Detroit is currently abandoned.  Yet if you look at these real-world cases, all of this abandonment is due to lack of demand, not commute time.  SC4 has plenty of mechanisms that can result in abandonment due to lack of demand, which in those cases is quite appropriate.  So the traffic simulator doesn't need to add spurious abandonment here.  If there aren't proper jobs available to the residents, you might get abandonment due to commute time from the simulator, but that's a mislabeling; it's really abandonment due to lack of demand that's encountered by the traffic simulator instead of other parts of the game.  That type of abandonment is quite reasonable, especially since the player has the ability to take actions to fix it.

What other forms of challenge are there?  Obviously, there's traffic congestion, and in fact most of the other forms of challenge in the traffic simulator stem from congestion.  In Simulator Z, at first glance it seems that the only effect of congestion is to have yellow, orange, and red lines appear on your congestion data view.  And then there's what Lenny so colorfully described as "advisor spam":  Your transportation advisor constantly nags you about "Traffic Jam On Side Street Has Local Sims Stewing," or "Local Road Reaches Limit - A Chaos of Cars," or "Big-Time Traffic Problems Hit Local Avenue."  (Many long-time players have these messages burned into their brains.)  For many players, the combination of these two factors is enough of a challenge to encourage them to improve their transportation systems.  But in reality, a lot more is going on behind the scenes, and congestion is a lot more damaging to the city in all traffic simulators than it appears at first glance.  Understanding how this works can be very helpful in choosing a traffic simulator and in planning your city.

I described a lot of the effects of congestion in an earlier post, but that was a very long post, and the part about congestion may have gotten lost in it for many people.  So I am reproducing that part here (edited slightly), so that all the material regarding traffic simulator challenge can be found in a single place.  The part that I am reproducing is between the two solid lines, so if you did read this before, you can skip it now.




Excessive traffic congestion can result in an increase in noise levels that makes residential areas less desirable, an increase in pollution, and a decrease of up to 14 points from neutral in the local Mayor Rating, or much as a 28 decrease from optimal in the local Mayor Rating.  Furthermore, these effects all have side effects themselves.  For example the lower Mayor Rating can be a contributing cause to riots in your city; this effect has actually been observed in Simulator Z Classic, which has the very low network capacities of the original Maxis simulator.  If your congestion is widespread, this can have a significant effect on your global Mayor Rating, which affects which rewards you can get.  To quote the Prima Guide regarding the awards:

QuoteIn addition... they improve your city in myriad other ways (enhancing desirability, boosting EQ or HQ, further increasing Mayor Rating, to name a few).

Note the last point.  This means that bad traffic can eventually cost you a lot more than 14 to 28 points in your Mayor Rating, ending up having a very major effect on the game, even with no abandonment due to commute time.  And abandonment due to demand may still happen, of course, and if you look at the above quote, you can see how bad traffic can start a cycle than can result in exactly that.  So depending on the level of congestion, any number of bad things can happen to your city.




There's one other important way that congestion can have a major effect on the difficulty of game play, and that's in commute time.  A lack of suitable transportation networks in a city may also cause the same problem, even if no congestion is present.  You may remember from earlier in this thread that in experiments to test the effect of the pathfinding heuristic, we found that in large cities, a higher pathfinding heuristic made the city less attractive to high-wealth Sims.  A short form of putting this causal relationship would be the following:

Pathfinding Heuristic => Desirability

We knew there had to be more intervening steps, but we didn't know what they were at the time.  I have since done some more research, and discovered the details of how this mechanism works.  It's not that much more complicated than the above statement, and can be stated as such:

Pathfinding Heuristic => Commute Time => Desirability

By definition, the higher the pathfinding heuristic, the higher the commute time.  Yet as I have stated many times, the maximum commute time in Simulator Z is effectively unlimited.  However, I'm sure you're all familiar with the short, medium, and long commute times that can be displayed when you query a residence.  And long commute times specifically reduce the desirability of the residences of the Sims who are commuting.  Reduced desirability in can be a big factor in why a building downgrades in wealth status.  So this is how a higher pathfinding heuristic can make a city less attractive to high-wealth Sims.

As for how this applies to congestion, congestion lengthens commute times.  Depending on the level of congestion, this can increase the number of long commute times a little or a lot.  When it increases them significantly, you get reduction in desirability, and you may start to see your high- and mid-wealth Sims leave town, replaced by low-wealth Sims.  On the other hand, a short commute time results in higher residential desirability, essentially helping to attract high-wealth Sims to your city.

So I hope I have shown that there is a lot more to the effects of traffic congestion than meets the eye, and I hope that this information will be useful in selecting a traffic simulator for your city that provides the level of challenge that you want.

b22rian

very well written and quite informative..

I never really considered the relationship between congestion, longer commutes times
and desirability very closely..

thanks for this Steve  &apls

brian

z

The Curious Case of Capitalis
- and -
More News on the Destination Finder

Regular readers of this thread may recall that last month, sumwonyuno posted a description of certain problems he was having with his region of Capitalis that appeared at the time to be related to Simulator Z.  At my request, he performed a number of tests, which produced some rather confusing results.  I then asked him to send me a copy of his city with its plugins so that I could do some more intensive testing here.  I have now done these tests, and I believe that the questions raised about Simulator Z have been answered.  I have also gained a bit of insight about what's actually happening in sumwonyuno's region.  Finally, this whole exercise has cast more light on how the Destination Finder works.

For those who like to know just the basics, I'll post a quick summary of my findings first, and then I'll post the details.  Here's the summary:

1. After extensive testing, I could find no evidence of any malfunction in Simulator Z.  Specifically, Perfect Pathfinding was not causing any problems, and was performing as expected and desired.  Simulator Z and Simulator A produced essentially identical results in all the cities I tested.  Although this is contrary to sumwonyuno's findings, I can show how the larger scope of my tests include his observations without contradiction.

2.  As you may gather from the previous point, there is no traffic simulator problem of any kind in the region.  Furthermore, the game appears to be operating properly.  The extent to which Capitalis behaves differently from the real region upon which it's based appears to be due solely to the fact that SC4 is not a perfect real-world simulator.  Within the rules of SC4, everything appears to be working properly.


When I received Capitalis from sumwonyuno, the Downtown city had been running Simulator A for some time.  I switched it to Simulator Z and ran it for 33 years, much longer than sumwonyuno's tests.  A summary of what I found can be seen in the following RCI graph:


There is no significant change in any of the three populations over time.  If you just look at the graph, it's very hard to tell where I switched simulators.  The importance of this graph is that it shows that Sims had no more trouble getting to local jobs under Simulator Z than they did under Simulator A.  And as we saw when testing the pathfinding heuristic, some downgrading or abandonment would happen within a few years of using a higher PH, even if everything was running fine before.

But you might say, "Well, that's a different situation.  Here it's not the paths that are changing; it's the destinations."  There's an easy way to test that out.  I stop the game, find the local Sims going to local jobs, and in the middle of the night, I bulldoze their residences.  (Caught them Sims napping!  ;D)  Now there are no workers at those far-flung jobs.  What happens now?  Here's the answer:


Look at the point where the population takes a little plunge.  The job count doesn't even budge.  That's just what you would hope.  The Sims passing through town now see open jobs here, and take them instead of continuing to the next tile.  That's the only place those workers can be coming from.  Meanwhile, the population slowly edges back upward, but the jobs don't increase.  Why?  Tax rates for R$ and R$$ are set to zero here.  But the local jobs are filled to the point that they can be.  The newly-arrived Sims start going to work in the next tile, but gradually over time, they take over some of the local jobs as vacancies appear.  Yet some of these jobs have been taken over permanently by the Sims commuting in from the western suburbs, which is why the population doesn't rebound all the way to its previous level.

Of course, this implies that the supply of accessible jobs is a major limiting factor in this city.  How can we verify this?  Looking at the zoning, I verified what is pretty obvious:  the small commercial buildings are all in low-density zones.  In fact, all the commercial zoning is low-density.  The large commercial buildings are ploppables with jobs.  I figured that if jobs were the limiting factor, rezoning a few of these areas to high-density should produce at least some growth.  This is what happened when I rezoned:


You can see that the Sims didn't waste any time with medium-sized buildings.  They went straight for the skyscrapers.  Here's what it looked like when they finished:


All the skyscrapers above the graph are new.  And sure enough, as you can see, there's an immediate increase of about 20% in jobs.  Here's what happens to the traffic pattern:


About 30,000 Sims are now getting off the expressway to go to the new jobs.  So that's why they just sped through downtown before - all the jobs were filled.

But sumwonyuno reported seeing a similar pattern with Simulator A, and no one getting off the highway when he ran Simulator Z.  How do I explain that?  Actually, I saw the same thing.  But because I ran the simulators for a much longer time (33 years for Simulator Z and 40 years for Simulator A), I saw many other things as well.  In both simulators, the highway traffic would fluctuate greatly, although in somewhat different patterns.  Although at some times, there were a constant 30,000 or so Sims traveling the whole highway in Simulator Z, at other times there were 65,000 entering the city, and 30,000 getting off at the main downtown exit.  At still other times, there were 35,000 Sims entering the city, with 30,000 getting off at the main downtown exit, leaving only 5000 on the highway after that point.  It all depended on when I looked.  But throughout all of this, the number of jobs stayed constant.  This means that the jobs were simply being traded off between the Sims coming in on the highway and the Sims living in town.  Whichever group of Sims didn't get the local jobs would go to the next tile, looking for work.  And in both simulators, there was never any residential abandonment or downgrading.  In general, what I observed simply reinforced what theory had told me:  The smaller the city, the more Simulators A and Z should behave similarly.

As for why sumwonyuno saw some of the southern jobs be filled when running Simulator A that weren't when running Simulator Z, this I can't say for sure, as I observed no difference there myself.  It could be timing, or the effect of running other cities, or almost anything.  But I was unable to reproduce any trace of this problem.

Sumwonyuno also reported that in the eastern suburbs, traffic was flowing the wrong way on the highway - away from downtown in the morning and toward downtown in the evening.  I agree with him that that makes no sense, and furthermore, it is not consistent with the morning traffic entering the city from the east that we both saw in the downtown city.  So I took a look in a couple of the suburbs that he mentioned.  I examined the traffic at the point where he gave the cities to me, and then ran both simulators on the cities from that point to see what changed.  In all cases, I found traffic flowing west toward downtown in the morning, and east back to the suburbs in the evening, just as it should.  I suspect a measurement error by sumwonyuno here.  It's easy to get the commute periods out of synch between the route query tool and the volume data display; I suspect that that's what happened here.

How does this all relate to the Destination Finder and the Nearest Destination Attractiveness property that I described in a previous post?  I believe that this investigation led me to the correct conclusions there; the only difference is that it now appears that Maxis implemented the Nearest Destination Attractiveness property properly, so that it does not interfere with perfect pathfinding.  However, I did realize something else about the Destination Finder (which must exist in some form, whatever Maxis calls it).  I have observed that in very large cities, it is usually impossible to get rid of abandonment due to commute time completely.  In Simulator Z, the only way this can be happening is if suitable jobs aren't being found for the Sims.  Yet such suitable jobs do exist in these cities.  Since it is the Destination Finder whose job it is to find them, it is the Destination Finder that must be failing here.  Furthermore, I noticed that with the introduction of Simulator Z v1.2, the number of such abandoned residences decreased by at least half.  In that version of Simulator Z, for all capacity levels I reduced the rail speeds, and increased the "Trip Starting Cost by travel type for Mass Transit" property for cars from 1 to 1.2.  So it would seem that one or both of these properties has an effect on the Destination Finder.  More research is needed here.  But for now, at least, I think that the questions raised in the Curious Case of Capitalis has been answered.

RippleJet

Quote from: z on December 06, 2009, 01:30:15 AM
I stop the game, find the local Sims going to local jobs, and in the middle of the night, I bulldoze their residences.  (Caught them Sims napping!  ;D)  Now there are no workers at those far-flung jobs.  What happens now?  Here's the answer:


Look at the point where the population takes a little plunge.  The job count doesn't even budge.  That's just what you would hope.  The Sims passing through town now see open jobs here, and take them instead of continuing to the next tile.  That's the only place those workers can be coming from.

You're probably right about that this is what happened... :thumbsup:

However the RCI graphs only show the capacities.
They do not show the population or number of workers.

The reason the capacities fluctuate a little over time is due to desirability.
It's the sum of all the first numbers seen in the queries...
those change every time the desirability factors are updated.

Thus, the constant commercial capacity in your graph cannot be used to verify your theory! $%Grinno$%
It doesn't tell you if sims are actually taking all jobs available,
it only tells you that the job capacity is still there to be taken.

z

Quote from: RippleJet on December 06, 2009, 02:12:17 AM
However the RCI graphs only show the capacities.
They do not show the population or number of workers.

Well, this is certainly good to know.  I remember when you explained what the numbers in the queries meant; I didn't realize it applied to the graph as well.

Fortunately, I also went around the city with the route query tool at the point that I took a picture of the graph, and I saw building by building how many jobs were actually filled.  What I saw also remained essentially constant.

sumwonyuno

#386
Well there goes 30 years of planning for the Kaka'ako area.  $%Grinno$%  The Capitalis City Council and Citizens Against Virtually Everything are in an uproar  :bomb:  In addition, wow the city looks nice at that resolution (and with shadows!). :P

Back to serious talk, z, I thank you for taking the time to look at my region.  I haven't been able to look at it since I mailed you the DVD.  I think you may remember back a while ago about the lack of jobs in the early stages of my region.  Yes, I understand the game has its limits, and I've done every trick I can think of to get Capitalis as close to Honolulu as possible.  Your explanations answered a lot.

It's an important point you raised, about the number of available jobs vs the number of jobs been sought in the Downtown city tile.  There obviously isn't enough available (and appropriate) jobs in that tile.  I didn't know what to make of the occasional fluctuations in the number of commuters from the east.  I really do think it's timing, as I always try to stop 10 years after on an October (I have a terrain texture issue in region view for saving during summer months).

The commuters "trading" jobs is a fascinating to think about.  Jobs in Kaka'ako (as of today) is primarily in low-rise buildings.  When you demolished the low-rise commercial buildings by the Capitol District, skyscrapers replaced them, giving tens of thousands of available jobs.  That is certainly enough jobs satisfy the 30,000+ westbound commuters.  The jobs closer to the shoreline are not taken because they're simply further away than almost all of the other potential jobs in the city tile.  You might want to try rezoning the commercial areas in Obama's neighborhood to high density to see what traffic patterns occur for Makiki residents and westbound freeway commuters.  Same thing for the Waikiki city tile.  (I'm assuming you know the places I'm talking about  ;)).

As for the eastern suburbs, I'm talking about Sector 24, 25, 26.  All commuters should be going west.  I don't believe it's me mistaking the morning/evening route query.  Assuming you haven't resaved the city tiles, try Sector 25, and don't unpause.  Query the avenue and it should say ~11000 cars westbound and ~7000 eastbound.  Those 7000 eastbound shouldn't be going to Sector 26, because there's isn't that many jobs out there.  It probably has to do with some legacy issue in my region.

Sector 22 <- 23 <- 24 <- 25 <- 26 <- 18 is the general pattern I'm aiming for, but it's not what is happening in the game.

I think some commuters from Sector 23 are going to Sector 24 because of commercial jobs in Sector 24.  From the perspective of those Sims, a Sector 24 neighbor connection is closer than jobs in Waikiki or a Sector 22 neighbor connection.  Now that I think about the order that jobs are taken, I think I know why.  The Sims in Sector 24 took the jobs within the same city tile.  The commuters from Sector 23 saw that there were no jobs available in Sector 24, but they see jobs in Sector 25.  In addition, there obviously isn't enough jobs in Sector 23, so some Sims in Sector 24 aren't willing to go there, and they see the jobs in Sector 25... and this pattern continues for Sector 25 and 26.  From Sector 26, the only place to go is Sector 18, but from Sector 18, the "next" tile would be Sector 10, and Sector 10 is undeveloped.  Sector 18 doesn't have the issue of wrong-peak-direction commuters, because the commuters from 24/25/26 don't have anywhere else to go, and "disappear".  Sector 24, 25, 26 do have the issue because they are in a chain, and these city tiles have jobs that are attractive to the commuters of other city tiles, but the jobs are already taken by Sims living in the respective city tiles.

Feel free to do testing on the one-way road modifications on my region.  I don't think I have time until after the 10th to do any SimCity-ing.  ()sad()  IMO, the game's original speeds better reflect the standard speed designations for Hawaii roadways.  15mph streets, 25mph roads and OWR, 35-45mph avenue, 55-60mph Maxis Highway.


The City & County of Honolulu, a Mayor Diary based on Honolulu, Hawai'i.

mark's memory address - I've created a blog!

z

Headlines from today's edition of the Sim City News:

PH Finally Convicted in the Case of Nate's City Abandonment
All SC4 Networks Discovered to Have Infinite Capacity

I'd like to discuss the second point first, as it lays the groundwork for the first point.

In RL, the capacity of a network is generally defined as the number of vehicles that can travel on the network without causing a noticeable delay in travel times.  In practice, this means that a in a network at full capacity in RL, vehicles are generally traveling slightly below the speed limit.

In SC4, there is no speed limit as such; there is simply a network speed at which all vehicles travel.  Also, unlike RL, all vehicles in SC4 are single-passenger.

In RL, as a network carries more and more vehicles beyond its capacity, traffic slows down.  There is effectively a lower limit for network speeds, after which people will simply find other routes, or those on the network will leave it.  For highways, as an example, this speed is about 5% of the speed limit.  If no other routes are available, traffic may come to a complete halt, and network capacity temporarily drops to zero.

Things work very differently in SC4.  The Congestion vs. Speed Curve (which as Alex pointed out should be more appropriately named the Traffic Volume vs. Speed Curve) slows down traffic as traffic volume increases, simulating to some extent the congestion process that happens in RL.  But unlike RL, there is a lower limit on the speed of a congested network, and that limit is 30% of the network's nominal speed.  As the speed of a network drops, the pathfinder will automatically try to find a faster route for the Sims, and the efficiency with which it does so is governed by the value of the pathfinding heuristic (PH).  But sometimes there is no faster route.  In that case, more and more Sims may be added to the existing route.  Once the network speed drops to 30% of the nominal speed, adding more Sims doesn't slow down traffic any further, because it's already going at the slowest possible speed for that network.  So the pathfinder can keep adding Sims to that network indefinitely, and the speed will not drop any further.  (One reason this doesn't work in RL is that unlike SC4, in RL, vehicles take up physical space.)  This is how networks actually have infinite capacity in SC4.  This applies to all networks and all traffic simulators.

The infinite capacity of SC4 networks also explains why Simulator Z Classic (which has the capacity levels of the original Maxis simulator) can be used on a city of any size without causing abandonment due to commute time.  Other problems may result from extreme congestion, but the networks will carry as many Sims as they're asked to.

There is one other important piece of information here before we look at Nate's city.  Until recently, it had been generally believed (including by me) that the Commute Trip Max Time property was the maximum time that a round-trip could take, measured in minutes.  However, in this post, Lenny showed that this property actually sets a limit on the one-way maximum commute time.  In other words, Sims can commute twice as far as we thought they could.

This result was quite surprising to me, and you may have noticed that I have been using half of the Commute Trip Max Time value until now in this thread to describe the one-way commute time.  So I constructed a very simple experiment, described in this post, to test Lenny's results.  I got the same result that he did.  Furthermore, Lenny discovered that Chris (CLR1S4D) had performed experiments himself to answer this very question, and also found that this property measured the one-way commute time limit in minutes.  So we have three different sets of experiments, all independently constructed and performed, coming to the exact same conclusion.  I think that we can take this conclusion as fact from now on.

Now we're ready to look at Nate's city.  You can find a description of his experiences here and here, but I'll include all the relevant information in this post so that looking at the originals is optional.

Nate started on a medium tile with a healthy city of two million Sims.  He switched to a newer traffic simulator to test it out, and twenty years later, his population had dropped 60%, to about 800,000.  Although this city started out with about a population almost identical to that of my Near South Side city that I've used in numerous examples, the devastation in Nate's city was far worse.  As you may recall, the population actually increased slightly in the Near South Side when the PH was raised, as the effects of downgrading (resulting in more Sims per building) were far greater than the results of abandonment.  In Nate's city, though, abandonment overwhelms everything.  The only way a traffic simulator can cause that to happen is abandonment due to commute time, and this part has never been disputed.  However, there are three ways that the traffic simulator can cause abandonment due to commute time:


  • The traffic simulator is unable to find suitable jobs for the Sims.
  • The traffic simulator is able to find suitable jobs for the Sims, but to reach them would exceed the Commute Trip Max Time.
  • The traffic simulator is able to find suitable jobs for the Sims and they can theoretically reach them within the Commute Trip Max Time, but the pathfinding heuristic is set too high, and the pathfinder can't find a suitable route.

We know that the first possibility is not the problem, since Nate's Sims had no trouble finding jobs with his previous traffic simulator.  It has been generally assumed until now that the second possibility accounted for the problem, and that the lower commute time limit of the new simulator, combined with the slower travel through congested areas due to lower network capacities, prevented the Sims from reaching suitable jobs within Commute Trip Max Time.  However, given the information derived in the first part of this post, it is now possible to disprove this, and show that all the abandonment was caused by the third possibility - a pathfinding heuristic that was too high for that city.  In fact, given the information derived above, surprisingly little information about the city is needed to show this.  We don't need to know the capacities of the networks involved, we don't need to know how much congestion there was, and we don't even need to look at the mass transit networks.  All we need is a basic map of the city, the speed limits of the streets and roads, and the value of Commute Trip Max Time.  From the following Traffic Volume Data view, and other pictures in the original thread, we can derive a basic map of the city roads:


The dark blue lines are roads and avenues, while the lighter lines are streets.  The speed on the streets is 40 kph, while on the roads and avenues it is 60 kph.  The Commute Trip Max Time is 17 minutes.  This differs from the previous simulator used in this city in that the Commute Trip Max Time there was 60 minutes, and network capacities were between 50% and 100% higher.  So it's easy to see why the lower Commute Trip Max Time and network capacities were suspected as the causes of abandonment.  But it's also easy to prove that they're not.

Given a speed of 60 kph for roads and avenues, a car can cover 62.5 tiles in one minute.  That means that the maximum range of a one-way commute is 17 times that, or 1062 tiles.  For the sake of argument, let's assume that all streets and roads are at maximum congestion.  (It can be shown that they weren't, but it's unnecessary to do so for this example.)  That means that a car's actual range would be 30% of 1062, or 318 tiles.  This is regardless of what the road and avenue capacities are.  This city exists on a medium-sized tile, which is 128 tiles in length.  This means that the maximum length of any trip is 255 tiles, and the vast majority of trips must be shorter than that.  So any trip that uses only roads and avenues has more than enough time to be completed, even at maximum congestion, since 318 tiles can be covered.  When you consider that some trips must use streets, you have to take into account that the Sims can cover 213 street tiles by car in 17 minutes - less than the longest possible trip.  But with perfect pathfinding, which always finds the fastest path, Sims would use streets only when necessary, and use roads or avenues for the rest of the trip.  For such mixed cases, as long as the street portion is less than half of maximum possible trip, or about 128 tiles, the trip can always be completed, even with maximum congestion.  And looking at the map above, it should be obvious that for a path between any two points on the map, only a very small fraction of that number of street tiles is ever necessary in any trip; the fastest trip always uses roads or avenues whenever doing so shortens the trip time.

So given the properties of the traffic simulator involved, the Commute Trip Max Time is not a limiting factor - trips by car can always be completed within that time to any square on the map.  And we didn't even have to consider the availability of bus or subway routes, which are present.  Therefore, we can eliminate the second of the three possible causes of abandonment for this city.  Since we already eliminated the first possible cause, that leaves us with the third possibility as the only explanation for the abandonment seen in this city.  The pathfinding heuristic used in the new simulator was .009, while perfect pathfinding uses a value of .003.  From the facts present, there can be no doubt that it was the higher value of the pathfinding heuristic, and that alone, that was the cause of all the abandonment in the city.

The point of all of this is not merely to see what happened in one city long ago.  Instead, it's to demonstrate even more clearly than any other example to date the importance of the pathfinding heuristic.  While a higher PH caused some abandonment and a fair amount of downgrading in the Near South Side, the overall population figures were not affected adversely.  In contrast, the population here declined by 60%.  For reasons such as this, I have gradually come to the conclusion that the PH is the single most important parameter in the traffic simulator.

This is not a new conclusion.  Recent research has found that the first modified traffic simulator was created by the7trumpets even before the Rush Hour pack was released, and was essentially what we now call Simulator E Standard.  This simulator is identical to the original Maxis simulator with one exception:  The PH has been lowered from the original Maxis value of .09 to the perfect pathfinding value of .003.  So I have merely rediscovered what was known more than six years ago.  I would simply like to request that simulator builders consider this and other examples when deciding which values to use for their simulator.

wouanagaine

speaking of PH, please take a look at this

I've once seen a java applet where you can see the actual effect of changing PH in realtime, but I can't find it anymore

New Horizons Productions
Berethor ♦ beskhu3epnm ♦ blade2k5 ♦ dmscopio ♦ dedgren ♦ emilin ♦ Ennedi ♦ Heblem ♦ jplumbley
M4346 ♦ moganite ♦ Papab2000 ♦ Shadow Assassin ♦ Tarkus ♦ wouanagaine
Divide wouanagaine by zero and you will in fact get one...one bad-ass that is - Alek King of SC4

z

Quote from: wouanagaine on December 07, 2009, 01:27:08 AM
speaking of PH, please take a look at this

Ah yes, Amit Patel's Web site!  This is where I learned basically all I know about A*.  Was there something in specific that you wanted me to look at here?

It's funny how things go full circle.  The way I first found that place was with a post that started with the following, addressed to Mott:

Quote from: wouanagaine on October 17, 2007, 12:15:09 AM
Seems you've been to Amit Patel webpage :)

sumwonyuno

QuoteThe infinite capacity of SC4 networks also explains why Simulator Z Classic (which has the capacity levels of the original Maxis simulator) can be used on a city of any size without causing abandonment due to commute time.

:D

Now that explains why whenever I changed the capacities for Simulator Z, there wasn't any abandonment of existing development my region.


The City & County of Honolulu, a Mayor Diary based on Honolulu, Hawai'i.

mark's memory address - I've created a blog!

wouanagaine

Quote from: z on December 07, 2009, 02:37:15 AM
Ah yes, Amit Patel's Web site!  This is where I learned basically all I know about A*.  Was there something in specific that you wanted me to look at here?

It's funny how things go full circle.  The way I first found that place was with a post that started with the following, addressed to Mott:

On that specific page, it explains how the PH influences the search
That was a quick reminder

New Horizons Productions
Berethor ♦ beskhu3epnm ♦ blade2k5 ♦ dmscopio ♦ dedgren ♦ emilin ♦ Ennedi ♦ Heblem ♦ jplumbley
M4346 ♦ moganite ♦ Papab2000 ♦ Shadow Assassin ♦ Tarkus ♦ wouanagaine
Divide wouanagaine by zero and you will in fact get one...one bad-ass that is - Alek King of SC4

RippleJet

Regarding the naming of property 0x4a678060... ::)




The original source is Ingred.ini, made by Maxis and located in SimCity 4's Apps folder:


  • PropID = 0x4a678060
  • VarType = Float32
  • VarCount = 1
  • DefaultValue = 0.75
  • Filter = SimulatorFilter
  • Prop Name = "Nearest Destination Attractiveness"
  • HelpText = "Lower scores means more side explorations but also more CPU time"
  • EditorCLSID = Float32TextEditor
  • FormatCLSID = 0
  • CheckCLSID = 0




DarkMatter copied all the data from Ingred.ini into properties.xml,
which most people who have downloaded Reader from STEX would have.
He made a slight change regarding this particular property (see the desc):

<property
   num="0x4a678060"
   type="Float32"
   name="Nearest Destination Attractiveness"
   desc="Lower scores means more side explorations but also more CPU time (Pathfinding Heuristic)">
</property>




The latest version is the one that Tropod made, tropod_properties.xml.
That is the one included in the Reader that's available on LEX:

<property
   num="0x4a678060"
   type="Float32"
   name="Pathfinding Heuristic"
   desc="Lower value means more accurate Pathfinding, but at a cost of more CPU time/usage">
</property>

daeley

#393
regarding the value of PH, do we have any idea where this is used in the calculation of SC4's A* algorithm?

the reason I'm asking is that it's obviously a fraction or a multiplier to some parameter in A*'s calculations. Considering the same definitions on Amit Patel's site of f(n) = g(n) + h(n) where h(n) is related to the estimate of distance to the goal, I would think that the "nearest destination attractiveness" is a multiplier to this distance which would probably mean that h(n) is defined somewhat along the lines of h(n) = ph * d(n,dest) where d(n,dest) is a distance measure (euclidian or manhattan, but I'd guess manhattan as this avoids calculating a root) between square n and the destination square.

If this is true - and from what I read this seems to be implied, but I haven't seen anyone specify it so explicitly - you would need to guess the scale of both g(n) and dist(x,y) to correctly find the "true" value for perfect pathfinding. If g(n) is scaled in time (distance/speed) and dist(x,y) is scaled in distance, according to the same distance scale used to calculate g(n), then it makes sense to calculate ph as 1/speed (as mott concluded?). If in this formula speed is the highest achievable speed, then pathfinding should be "perfect". If speed is lower, the A* algorithm may produce routes that are sub-optimal: shorter in distance, but longer in travel time since a sub-optimal travel strategy is used.

Again, following the same reasoning, if ph is much too high (i.e. 0.09, which equals a speed of 11, units not specified) the simulator will show a strong preference for routes that follow the shortest-distance route. In other words, such a simulator does actually work, but you will need to build your road system in such a way to take this into account and you should, for example, avoid building low-capacity links on a direct path between residential zones and jobs.

Is this a correct synthesis of all the "discoveries" regarding the PH value?

If so, a higher-than-perfect behaviour does not strike me as awefully unrealistic for a pathfinder, as in real life people will often pick the shortest route, even if it's not the best. But I guess that's a discussion for somewhere else...
1. Install SC4+RH
2. Install LEX (CD&DVD helps) and latest NAM + updates
3. Play the game
4. ? ? ? ?
5. Profit!

wouanagaine

#394
based on the fact that the much higher heuristic is ( h(n) part of the equation ), the much nodes in the graph will be explored, I can guess in SC4 the formula is
f(n) = g(n) + h(n)/ph
The more nodes explored = the more cpu usage = the more chance to find the exact best path
if ph < 1 then h(n)/ph > h(n) which results in an overestimate which is the only way to find the best path ( one of the hypothesis of A* )
and I guess h(n) is using manhattan distance as the graph is 4-arity based in SC4 ( given how .SC4Path are described )
given that a big difference is shown when going from 0.09 to 0.03 I also expect that g(n) and h(n) don't use the same units at all.
g(n) might be expressed in trip time, whereas h(n) might be in distance

This is so far the biggest ( or smallest depending POV ) ph I ever seen ( and I used a lot of A* )


New Horizons Productions
Berethor ♦ beskhu3epnm ♦ blade2k5 ♦ dmscopio ♦ dedgren ♦ emilin ♦ Ennedi ♦ Heblem ♦ jplumbley
M4346 ♦ moganite ♦ Papab2000 ♦ Shadow Assassin ♦ Tarkus ♦ wouanagaine
Divide wouanagaine by zero and you will in fact get one...one bad-ass that is - Alek King of SC4

daeley

#395
Quote from: wouanagaine on December 07, 2009, 07:48:46 AM
if ph < 1 then h(n)/ph > h(n) which results in an overestimate which is the only way to find the best path ( one of the hypothesis of A* )

quick comment: As I understood from below quote from Amit Patels site, a higher h(n) (or lower ph in case of h(n)/ph) would cause less exploration while a lower h(n) (which could be generated by increasing ph in h(n)/ph) increases exploration and makes the search more like a dijkstra algorithm. This seems to contradict your quote?

Quote
- At one extreme, if h(n) is 0, then only g(n) plays a role, and A* turns into Dijkstra's algorithm, which is guaranteed to find a shortest path.
- If h(n) is always lower than (or equal to) the cost of moving from n to the goal, then A* is guaranteed to find a shortest path. The lower h(n) is, the more node A* expands, making it slower.
- If h(n) is exactly equal to the cost of moving from n to the goal, then A* will only follow the best path and never expand anything else, making it very fast. Although you can't make this happen in all cases, you can make it exact in some special cases. It's nice to know that given perfect information, A* will behave perfectly.
- If h(n) is sometimes greater than the cost of moving from n to the goal, then A* is not guaranteed to find a shortest path, but it can run faster.
- At the other extreme, if h(n) is very high relative to g(n), then only h(n) plays a role, and A* turns into BFS.

or do I mix different concepts here?

very confusing, all of this...
1. Install SC4+RH
2. Install LEX (CD&DVD helps) and latest NAM + updates
3. Play the game
4. ? ? ? ?
5. Profit!

ldog

My understanding of A* in a nutshell, is that the PH is used as a placeholder for the terrain entry cost (or .96/speed in our case).
So we take the trip length (the distance is Manhattan because that is what we are using), and we calculate it as if we can find a route there in that time.
Then we keep looking until we either find a route that is that fast or we have exhausted all possible routes.
My sources of study include but are not limited to the aforementioned Amit Patel.
I am also by no means an expert or even close; I only began learning about A* because of SC4.
In theory, as best as I can ascertain this is how it should all work.
In SC4 apparently it does not; or at least there is much more to it.

wouanagaine

Quote from: daeley on December 07, 2009, 08:28:43 AM
quick comment: As I understood from below quote from Amit Patels site, a higher h(n) (or lower ph in case of h(n)/ph) would cause less exploration while a lower h(n) (which could be generated by increasing ph in h(n)/ph) increases exploration and makes the search more like a dijkstra algorithm. This seems to contradict your quote?

or do I mix different concepts here?

very confusing, all of this...
No I mixed it myself
your quote from Amit resumes it perfectly, as now I remember using value from 1.5 to 2 to speed up search in my last project ( I have the f(n) = g(n) + h(n)*PH )

So if in SC4 reducing PH cause more CPU usage ( it should be verify if not yet, as we can't blindy believe what is in the ingred.ini ), then the formula should be
f(n) = g(n) + h(n)*k(ph)
I introduce a k() function because I don't expect f(n) = g(n) + h(n)*ph as it with such a low value, it will make h(n) almost inexistant in the total
It can still be the case if the g(n) and h(n) are not using the same units

and I also mix it up, because A* need to use an underestimate to be guaranted to find the best path ( hence why almost all A* implementation either use the L1 or L2 distance function as heuristic )


BTW Did someone already test with PH = 0  and PH = 1 ?




New Horizons Productions
Berethor ♦ beskhu3epnm ♦ blade2k5 ♦ dmscopio ♦ dedgren ♦ emilin ♦ Ennedi ♦ Heblem ♦ jplumbley
M4346 ♦ moganite ♦ Papab2000 ♦ Shadow Assassin ♦ Tarkus ♦ wouanagaine
Divide wouanagaine by zero and you will in fact get one...one bad-ass that is - Alek King of SC4

z

#398
Quote from: RippleJet on December 07, 2009, 06:23:14 AM
Regarding the naming of property 0x4a678060... ::)

This would certainly explain what we've been seeing, and is consistent with the timeline I inferred for the naming of this property.  The actual historical details you provide are quite informative.

Quote from: daeley on December 07, 2009, 07:23:33 AM
regarding the value of PH, do we have any idea where this is used in the calculation of SC4's A* algorithm?

I don't believe so.  We do have a quote from Maxis that they are using a "modified" version of A*, but they don't define what "modified" is.  But the PH visible to us appears to be a normalized version, in that it isn't dependent on speed.  This normalization would explain why it's much lower than anything wouanagaine has seen before; I would guess that there's something inside the simulator that translates it into a more traditional PH, which would be within the bounds with which wouanagaine is familiar.

Quote
the reason I'm asking is that it's obviously a fraction or a multiplier to some parameter in A*'s calculations. Considering the same definitions on Amit Patel's site of f(n) = g(n) + h(n) where h(n) is related to the estimate of distance to the goal, I would think that the "nearest destination attractiveness" is a multiplier to this distance which would probably mean that h(n) is defined somewhat along the lines of h(n) = ph * d(n,dest) where d(n,dest) is a distance measure (euclidian or manhattan, but I'd guess manhattan as this avoids calculating a root) between square n and the destination square.

I agree with you here, and I also think in retrospect that the Manhattan distance makes more sense than the Euclidean distance, for exactly the reason you mentioned.  Maxis was very big on efficiency in the traffic simulator, and mentioned this point explicitly.

Quote
If this is true - and from what I read this seems to be implied, but I haven't seen anyone specify it so explicitly - you would need to guess the scale of both g(n) and dist(x,y) to correctly find the "true" value for perfect pathfinding. If g(n) is scaled in time (distance/speed) and dist(x,y) is scaled in distance, according to the same distance scale used to calculate g(n), then it makes sense to calculate ph as 1/speed (as mott concluded?). If in this formula speed is the highest achievable speed, then pathfinding should be "perfect". If speed is lower, the A* algorithm may produce routes that are sub-optimal: shorter in distance, but longer in travel time since a sub-optimal travel strategy is used.

Again, following the same reasoning, if ph is much too high (i.e. 0.09, which equals a speed of 11, units not specified) the simulator will show a strong preference for routes that follow the shortest-distance route. In other words, such a simulator does actually work, but you will need to build your road system in such a way to take this into account and you should, for example, avoid building low-capacity links on a direct path between residential zones and jobs.

Is this a correct synthesis of all the "discoveries" regarding the PH value?

Yes and no.  Experimental observations all point to the normalization that I referred to having removed the dependence of PH on speed; the value of .003 appears to give perfect pathfinding regardless of the speed of the networks present or used.  And although Mott believed in using perfect pathfinding, by calculating the PH as 1/speed, he came up with a PH of .025 for his traffic simulator, which is much higher than the actual perfect PH in this game.

QuoteIf so, a higher-than-perfect behaviour does not strike me as awefully unrealistic for a pathfinder, as in real life people will often pick the shortest route, even if it's not the best.

This would be quite reasonable, except for the fact that Maxis' pathfinding contains an additional limitation, namely the time allowed to calculate the path.  This limit is completely different from the Commute Trip Max Time.  In standard A*, a valid path is always found, regardless of how long it is.  But in SC4, the pathfinder is allotted only a specific amount of time to find a path.  (An exception appears to be made for perfect pathfinding.)  If the pathfinder doesn't find a path in the allotted time, it gives up, and that's how all the abandonment happens.

Quote from: wouanagaine on December 07, 2009, 11:40:57 AM
BTW Did someone already test with PH = 0  and PH = 1 ?

I assume you mean .001?

I tested with values of 0, .001, .002, and .0025.  As you would expect, the only thing that changed with the lower values was that the lower the value, the longer the time it took to run the pathfinder.

mightygoose

ive been looking at this CvS quotient.... and asuming it causes glitches beneath 0.3..... is the following true?

NAM + CAM + RAM + SAM, that's how I roll....