Jump to content
  • Kevin
    Kevin

    Commute Time and Pathfinding Report by The Community

    Commute Time and Pathfinding Report
    Please PM STomnibus if you have any questions about this article. Thank you for taking the time to read this. This project is ongoing, and many people have contributed countless hours to figuring out exactly what is causing us problems with commutes in our cities. The information is fairly detailed, but we have tried to keep it from becoming tedious. Please understand that all of our testing and this report is an effort to help you make a great game better. There are serious issues here which degrade the playability and fun of an otherwise great game, and it is our sincere hope that these issues can be addressed. We would be very grateful if you would keep us posted on the progress of addressing these issues.


    This document details our findings on the following:
    Commute times ten bugPathfinding algorithm shortcomingsSuggestions to fix the Pathfinding algorithmUnrealistic Mass Transit SpeedsRequests for better tools to diagnose traffic problemsContact info and links
    Commute Times Ten Bug
    Tested speeds of roads, streets, and highways, are consistently 10 times greater than the speeds shown in the .dat file. There is a bug somewhere that is causing the total commute time, or the time cost for each type of transportation tile, to be multiplied by 10.


    Methodology:
    1 – Trips start any transportation tile adjacent to the residence and end at any transportation tile adjacent to the workplace (fig a). This was tested by placing a workplace directly across from a residence, and observing that there is always a zero commute time for this setup, because there are no “steps” being taken from tile to tile.

    //www.simtropolis.com/library/Omnibus/CommutePath/FigureA.jpg
    Figure a
    2 - The commute time graph shows twice the time it takes to get to work, simulating round trip time. A return route must be present for the sim to move into a residential zone, but its route and time cost is not calculated, and has no effect on commute times. In figure b and c, the sim can commute to work and back home. The commute time, however, is not affected by the length of the return trip. There just must be a possible return trip for the zone to develop. If there is no return trip (fig d), the residential zone will not develop.

    //www.simtropolis.com/library/Omnibus/CommutePath/FigureB.jpg
    Figure B
    //www.simtropolis.com/library/Omnibus/CommutePath/FigureC.jpg
    Figure C
    //www.simtropolis.com/library/Omnibus/CommutePath/FigureD.jpg
    Figure D

    3 – Next we tested commute times by having one path from home to work, and recording the commute time. There are two sources of inaccuracy. First, the inaccuracy caused by the commute engine rounding or truncating travel time at one or more steps along the way. Second is inaccuracy in the commute time graph. We found that it is rounded to the nearest minute on the graph, so accuracy is at best +/- 0.5 min, and probably worse because of rounding and truncating in the commute engine. The difference factor was calculated with values from the dat file before they were rounded.

    These times are adjusted for one way travel by dividing the observed commute time in the graph by 2. Below is the tested walking commute times with their respective speeds in min/tile compared to the min/tile times calculated from the kph speeds claimed by the prima manual and exemplar #23045:

    # Tiles
    Travel Time (minutes)
    Prima Time (minutes)
    Observed Speed (min/tile)
    Prima speed (min/tile)
    Difference Factor
    1





    2
    2.50
    0.27
    2.50
    0.27
    9.11
    3
    5.00
    0.55
    2.50
    0.27
    9.11
    4
    8.00
    0.82
    2.67
    0.27
    9.72
    5
    10.57
    1.10
    2.64
    0.27
    9.64
    6
    13.49
    1.37
    2.70
    0.27
    9.83
    7
    16.09
    1.65
    2.68
    0.27
    9.78
    8
    18.52
    1.92
    2.65
    0.27
    9.64
    9
    21.60
    2.19
    2.70
    0.27
    9.84
    10
    24.52
    2.47
    2.72
    0.27
    9.93
    As you can see, the difference is consistently about a factor of 10. This is clearer when looking at the street and road charts. The street values are:

    # Tiles
    Travel Time (minutes)
    Prima Time (minutes)
    Observed Speed (min/tile)
    Prima Speed (min/tile)
    Difference Factor
    11
    4.4
    0.46
    0.44
    0.046
    9.55
    12
    4.5
    0.50
    0.41
    0.046
    8.95
    13
    5.0
    0.55
    0.42
    0. 046
    9.11
    14
    5.5
    0.59
    0.42
    0. 046
    9.25
    15
    6.0
    0.64
    0.43
    0. 046
    9.38
    16
    6.5
    0.69
    0.43
    0. 046
    9.48
    17
    7.0
    0.73
    0.44
    0. 046
    9.57
    18
    7.5
    0.78
    0.44
    0. 046
    9.65
    19
    8.0
    0.82
    0.44
    0. 046
    9.72
    20
    8.5
    0.87
    0.45
    0. 046
    9.79
    21
    9.0
    0.91
    0.45
    0. 046
    9.84
    22
    9.5
    0.96
    0.45
    0. 046
    9.90
    23
    10.0
    1.01
    0.45
    0. 046
    9.94
    24
    10.5
    1.05
    0.46
    0. 046
    9.99
    25
    11.0
    1.10
    0.46
    0. 046
    10.03
    26
    11.5
    1.14
    0.46
    0. 046
    10.06
    27
    12.0
    1.19
    0.46
    0. 046
    10.10
    28
    12.5
    1.23
    0.46
    0. 046
    10.13
    29
    13.0
    1.28
    0.46
    0. 046
    10.16
    30
    13.5
    1.33
    0.47
    0. 046
    10.18
    40
    17.5
    1.78
    0.45
    0. 046
    9.82
    50
    21.6
    2.24
    0.44
    0. 046
    9.66
    60
    26.5
    2.70
    0.45
    0. 046
    9.83
    70
    31.5
    3.15
    0.46
    0. 046
    9.99
    80
    36.0
    3.61
    0.46
    0. 046
    9.98
    90
    40.6
    4.07
    0.46
    0. 046
    9.98

    100
    45.0
    4.53
    0.45
    0. 046
    9.94








    And the road values:

    # Tiles
    Travel Time (minutes)
    Prima Time (minutes)
    Observed Speed (min/tile)
    prima speed (min/tile)
    Difference Factor
    11
    3.0
    0.31
    0.30
    0.031
    9.69
    12
    3.0
    0.34
    0.27
    0. 031
    8.81
    13
    3.5
    0.37
    0.29
    0. 031
    9.42
    14
    4.0
    0.40
    0.31
    0. 031
    9.94
    15
    4.0
    0.43
    0.29
    0. 031
    9.23
    16
    4.5
    0.46
    0.30
    0. 031
    9.69
    17
    4.5
    0.50
    0.28
    0. 031
    9.08
    18
    5.0
    0.53
    0.29
    0. 031
    9.50
    19
    5.5
    0.56
    0.31
    0. 031
    9.87
    20
    5.5
    0.59
    0.29
    0. 031
    9.35
    21
    6.0
    0.62
    0.30
    0. 031
    9.69
    22
    6.0
    0.65
    0.29
    0. 031
    9.23
    23
    6.5
    0.68
    0.30
    0. 031
    9.54
    24
    6.5
    0.71
    0.28
    0. 031
    9.13
    25
    7.0
    0.74
    0.29
    0. 031
    9.42
    26
    7.5
    0.77
    0.30
    0. 031
    9.69
    27
    8.0
    0.81
    0.31
    0. 031
    9.94
    28
    8.0
    0.84
    0.30
    0. 031
    9.57
    29
    8.5
    0.87
    0.30
    0. 031
    9.80
    30
    8.5
    0.90
    0.29
    0. 031
    9.46
    40
    12.0
    1.21
    0.31
    0. 031
    9.94
    50
    15.0
    1.52
    0.31
    0. 031
    9.89
    60
    18.0
    1.83
    0.31
    0. 031
    9.85
    70
    21.0
    2.14
    0.30
    0. 031
    9.83
    80
    24.0
    2.45
    0.30
    0. 031
    9.81
    90
    27.5
    2.76
    0.31
    0. 031
    9.98
    100
    30.5
    3.07
    0.31
    0. 031
    9.95
    It has also been confirmed that Highways tiles fall victim to the commute times 10 bug, but we do not have specific data archived because it is more difficult to get specific data since we don't know what the speed of onramps is. Preliminary testing suggests that mass transit tiles also fall victim to the commute times ten bug.

    It is plain and clear that for some reason, the commute time is being multiplied by 10. Perhaps this was accidental, and perhaps it was on purpose. If it was on purpose, it was probably to account for the fact that not everyone in reality works at the closest workplace for their wealth level. This is understandable, but I believe this is a very poor way to account for that.


    Pathfinding Engine Shortcomings
    It has been shown that the sims do not use the fastest route in the vast majority of situations. To test this, we used test situations that do not resemble real-world cities, representations of real life cities that are to scale, as well as various cities people have created in the game. In general, the pathfinding engine is not willing to go far enough out of its way to find a faster path from the home to the workplace.

    In figure e, the sim preferred the slower road even though he could have gone just one tile out of his way to pick a faster street.

    //www.simtropolis.com/library/Omnibus/CommutePath/FigureE.jpg
    figure e
    In figure f, even when the street path is longer, the sim still prefers it to the road bypass since it starts out more direct toward the goal.

    //www.simtropolis.com/library/Omnibus/CommutePath/FigureF.jpg
    figure f
    It appears that the only instance where the sim will take the road over the street is when, especially near the beginning of the commute, the road and street path are equidistant from the workplace (fig g). Every once in a while when the road path is one tile out of the way, the sim will take the road. But it should take the road if it is faster, regardless of how far away from the straight line path it must go.

    //www.simtropolis.com/library/Omnibus/CommutePath/FigureG.jpg
    figure g
    In figure h, the sim continually switched between the two routes about every 6 months game time, showing that the beginning of the commute is the most important in determining which route the sim will take.

    //www.simtropolis.com/library/Omnibus/CommutePath/FigureH.jpg
    figure h
    In Figure i, j, and k, the route the sim took is in red while the faster more logical route is in green.
    //www.simtropolis.com/library/Omnibus/CommutePath/FigureI.jpg
    figure i
    //www.simtropolis.com/library/Omnibus/CommutePath/FigureJ.jpg
    figure j
    //www.simtropolis.com/library/Omnibus/CommutePath/FigureK.jpg
    figure k
    Another shortcoming that is difficult to test definitively, because of the limited tools we have, is that it appears the pathfinding engine does not take into account the lower travel speeds caused by congestion. This creates a situation where no sims are willing to take bypasses around high traffic areas to get to work quicker.


    Suggestions for Fixing the Path-Finding Algorithm
    While we do not know exactly what algorithm is being used in the game currently, it has been shown that it rarely finds the quickest route. We presume that the reason for this was to slim down processor time used by the pathfinding engine by limiting its search using an over-optimistic or inadmissible heuristic. We are not trying to tell you how to write the game, you have done an excellent job. We just want to do all we can to help you in fixing this pathfinding engine so that it is both efficient and finds the quickest route. The current code precludes the pathfinding engine from finding the most efficient routes, and makes planning an efficient traffic system impossible.

    Our suggestion is two fold. The easiest thing to do short term is to simply allow us to control how much processing power is used by the pathfinding engine, similar to the new graphics settings introduced in patch 2. If a variant of A* or other heuristic based pathfinding algorithm is used, this setting would simply change the heuristic as we chose to devote more computing power to the pathfinding engine. However, for a long term solution, and especially for the upcoming expansion pack to be of any use at all, the pathfinding algorithm needs to be rewritten and perfected. It simply will not matter how many new options we have for transportation if the sims still use the most direct route instead of the quickest route. We are trying to explore as many pathfinding algorithms we can find or create, to see which would be best suited for SimCity. You may be interested to follow along and check our progress. This project is currently going on at Simtropolis. Links to the threads and contact info for the people who have been working on this project are located at the end of this document.


    Unrealistic Mass Transit Speeds
    It occurs to us that the mass transit speeds may have been increased to faster than realistic speeds (before the commute times ten bug) for the purpose of encouraging mass transit usage. Here are the speeds in kph from the .dat file which I'm sure you're well familiar with:

    Street
    Road
    Highway
    Train track
    Subway tunnel
    Car

    21

    31

    82

    Bus

    31

    46

    100

    Train

    150

    Subway

    150

    It would be more realistic to switch the car and bus speeds, lower the subway speed to about 80kph, and lower the train speed to about 100kph. The new “commuter trains” in the expansion pack could then travel at 150kph.

    As mentioned before, these speeds were probably chosen to facilitate their commute times being shorter than driving, so that the sims who choose the “fastest” method of commute (car or mass transit) will choose mass transit.

    It would be far better to simply include new ordinances to increase mass transit usage. There could be “bus only lanes” which would put bus lanes on roads (and/or avenues when rush hour is released), and make them impervious to traffic congestion in the pathfinding algorithm. There could also be a “mass transit voucher program” which would lower the fares you receive from mass transit, but encourage higher usage by changing the “fastest” algorithm to require the driving route to be at least 30% faster than the mass transit route in order to use it over mass transit. Instead of an ordinance, this could also be achieved by using a continuously variable “fare setting” in the budget panel, which would adjust the preference value on mass transit over driving depending on how high you set your fares.


    Requests for Better Tools to Diagnose Traffic Problems
    The commute time in number of minutes instead of a “short, medium, long” indication in the query window of all residential buildings. Industrial buildings would include a numerical minute value as well, for their “freight trip” length.

    When we query a transportation tile, it should also give us its congestion and respective speed limit.A data view that shows commute time from a range of green to red, green being 0 minutes and red being 2 hours, or longest commute time allowed.An ability to select an area of residential and see where they are working. With these tools, we could zoom in on areas which have red commute times in the data view, query the residence to see how long it is, select it and surrounding residences to see what transportation routes need upgrading, and see what methods of upgrading the transportation are most effective at reducing commute time by querying the residence after upgrading is complete.


    Contact Info and Links
    We would welcome any communication from you. Any questions you have, or requests for further data will be gladly answered. If you want to check the progress of this project, the pathfinding engine thread is at http://www.simtropolis.com/idealbb/view.asp?topicID=33438

    The previous thread, where most of the information for this article was drawn from is at http://www.simtropolis.com/idealbb/view.asp?topicID=32788

    Also feel free to email any of us, the contributing authors about any issues raised here. These are two of the main contributors to this project:

    pruett@unt.edu

    cepha@hotmail.com

    Also, feel free to PM STomnibus about any questions regarding this article.

    Sign in to follow this  
    Sign in to follow this  

    User Feedback


    There are no comments to display.



    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an Account  

    Sign up to join our friendly community. It's easy!  

    Register a New Account

    Sign In  

    Already have an account? Sign in here.

    Sign In Now


  • Recently Browsing   0 members

    No registered users viewing this page.

×

Season's Greetings!

xmas popup.jpg

Thank You for the Continued Support!

Simtropolis relies mainly on member donations to continue operating. Without your support, we just would not be able to be entering our 15th year online!  You've really help make this a great community.

But we still need your support to stay online. If you're able to, please consider a donation to help us stay up and running, so that we can help keep bringing SimCity players together to share our creations.

Make a Donation, Get a Gift!

Expand your city with the best from the Simtropolis Echange.
Make a donation and get one or all three discs today!

stexcollection-header.png

By way of a "Thank You" gift, we'd like to send you our STEX Collector's DVD. It's some of the best buildings, lots, maps and mods collected for you over the years. Check out the STEX Collections for more info.

Each donation helps keep Simtropolis online, open and free!

Thank you for reading and enjoy the site!

More About STEX Collections