Passenger intelligence

[unmerged(496283)]

I was thinking of buying this game since it is on sale on Steam, but I think this thread convinced me to hold off. I played the first CIM, but it was awhile ago. From what I remember is that it all felt too gamey for me. Not a bad game, but one that I don't need to add to my backlog at this time.

I was thinking of writing the same post. Reading this topic and realizing how incredibly bad the AI is in this game...
And we're not talking about some useless or unintresting part of the AI here. How the passengers decide what type of transport is adequate\better for them, It's the freaking core of the whole game ffs..

 

[kensternation]

I was thinking of writing the same post. Reading this topic and realizing how incredibly bad the AI is in this game...
And we're not talking about some useless or unintresting part of the AI here. How the passengers decide what type of transport is adequate\better for them, It's the freaking core of the whole game ffs..

+1,000,000

 

[timfrombriz]

Here's my idea of a fix, which covers a few other suggestions;

Game engine changes
For each route's schedule, create a list of departure times for each stop and store them permanently in a list [Create List A].

Example:
[List for Stop 1]
12:00 - Route 1
4:00 Route 1
5:00 Route 2
6:00 Route 1
7:00 Route 1
..
23:00 Route 1


For each stop, store a list of connecting Routes available within the radius of that stop [Create List B]

Example:
[List for Stop 1]
Route 1 - 0 metres walk (same stop)
Route 2 - 0 metres walk (same stop)
Route 5 - 100metres walk
Route 13 - 300metres walk

Pathfinding algorithm (for when a CIM calculates a trip)
Create a list [Create List C] of all possible routes to begin on for stops within the CIM's starting point walking limit radius.

Example List C:
[List of Possible Starting Stops]
Route 1 @ Stop 64, 100m walk
Route 2 @ Stop 64, 100m walk
Route 5 @ Stop 109, 300m walk


Examine these routes[use List C] along with connecting routes for each stop available[use List B] and create a list of route combinations that permit Start Point to End Point delivery of the CIM. [Create List D]

Example of List D:
[List of Possible Routes for A-B to travel]
Walk to Startint Point[100m] -> Route 1, Enter Stop 64[0 m], Exit Stop 65[600 m] -> Route 6, Enter Stop 65[0 m], Exit Stop 66[900m] -> Route 7, Enter Stop 154[100m], Exit Stop 160[1600m] -> Walk to destination point.[50m] ,
etc ...


Using [use List D] sorted from shortest-longest traveled distance, examine the [use List A] list of times to move between each route and calculate the total time of travel for each [create list E].


Using [List E] , find the shortest time to travel, and set the CIM to travel this way.


Points to note

[List A] would only need created once, and updated when a stop is added to a route or removed, or when the scheduele is modified.

[List B] would also need to be created once and updated when a stop is added or removed from a route.

[List A] would enable the game to have the feature of scheduled departure times added to the game, as request by other users.

[List C-E] would be calculated each time a CIM's trip needed to be calculated. Considering it uses a majority of a permanently kept List A & List B, computations should be reduced.

List C & D] I presume would be part of the current pathfinding algorithm used in the game.

[List D] would need to be coded to prevent reusing a route in its pathfinding list to prevent an infinite loop if it ends up placing the CIM at a stop where the CIM has already travelled past.


Perhaps Colossal Order could advise what style of pathfinding (A*, Dijkstra's etc) they are using, or what limitations exist with their pathfinding that may prevent, or even release that portion of code,along with some information about how these things (stops, Routes, Schedules) are stored that may pose limitations. I for one as a programmer, and with experience in Unity (using C#), would certainly tinker with it and speed profile a solution that may fix this.

 

[gebbiz]

The problem there is that it's very easy to create a situation where list D would require terabytes of RAM (+insane amount of CPU power and that is only for one citizen). That wouldn't even solve the issue, our algorithm already finds the optimal solution in terms of travel time / comfort and cost. However, it uses average times for waiting, not the actual timetable. This would make the calculation much more complex (You need to realize that on a large city at max speed we are doing several thousand pathfind requests per second).

 

[asaphxxx]

if you want a realistic transportation game, it's not this one.

I recommend the experimental branch of simutrans - 90's graphics and limited construction options - but very realistic approach to passenger behavior. also it's free.

 

[timfrombriz]

The problem there is that it's very easy to create a situation where list D would require terabytes of RAM (+insane amount of CPU power and that is only for one citizen). That wouldn't even solve the issue, our algorithm already finds the optimal solution in terms of travel time / comfort and cost. However, it uses average times for waiting, not the actual timetable. This would make the calculation much more complex (You need to realize that on a large city at max speed we are doing several thousand pathfind requests per second).

First, thanks for replying. Its good to see the programmer(s) are aware of this discussion.

I can see your argument about the CPU/RAM overheads with generating list D. Your pathfinder currently would do something similar to List D currently, so what about this...


With the method of pathfinding you are using, I presume you are traversing a node tree thats permanently stored (each node represents a stop and branches between nodes represent walk/mode of travel to adjacent stops). The weightings used in the node tree you say are for travel time/comfort/cost. The algorithm finds a single solution based on the best outcome on these weightings.

So how about this;

1. Weighting should solely be on travel distance (aka, walk distance, the distance between two stops which are stored permanently in the node tree), not travel time, comfort or cost.

2. Modify the pathfinder to find the first '5' best weighted paths, and then doing a more detailed lookup on these top 5 paths that analyse the travel time using the other permanently stored lists I suggested against these paths, they could also track the comfort and zones traversed in this process. The quickest delivery (based on schedueling) is selected from this top 5, and if conditions are met (cost, comfort if you feel it a must, travel time vs avg car travel distance between start-end) the CIM is spawned to travel.

Note that I say top 5, and the argument on this would be, you may not find the appropriate route. How about storing this variable in a advanced setting so users that are willing to sacrifice more cpu/memory can increase this value appropriate to their system speed. You could also have your standard pathfinding set by default and let users change to this style of pathfinding if they elect and with a 'use at your own risk' that it may slow/crash the game (out of memory) if used.

I dont see huge amounts of memory required for this suggestion, only some additional permanent lists to be used as lookup tables.
The CPU overhead is dependant on how far you want to dig in route path possibilities.
The only obstacle I see is creating the implementation and doing it efficiently. Thats why I suggested letting the community brainstorm on the code/obstacles in the code that may present limitations.

The other thing is I am active with other open source game communities, and know some coders that actively work on Pathfinding AI, such as OpenTTD. If you were to share that portion of code and what interfaces existed external to that code (ie the classes and exposed variables/functions) with other objects in the game world, they would jump at the opportunity to use their skill to propagate a solution.

Let us know your thoughts.

 

[Alex_brunius]

our algorithm already finds the optimal solution in terms of travel time / comfort and cost. However, it uses average times for waiting, not the actual timetable.

Not last time I played the game.

As far as I have seen, your algorithm also does not factor in walking time, which can end up adding many hours to the travel that staying on the same line would not have done.

The most common complaint here is that CiMs get off at the station before the actual interchange and walk for hours, just because it's the first opportunity to switch lines within the radius (often just on the edge of radius).

This is especially devastating with line interchanges using the same station where the walking time for switching at the interchange station would be zero.

(You need to realize that on a large city at max speed we are doing several thousand pathfind requests per second).

This sounds very sub-optimal.

Path could be calculated one time and stored, updates or new requests are only needed if:

* New CiM moves into the town.
* CiM switches home/work/favorite leisure/shop. (optional, the simulation could work with this almost never happening)
* A new line that is within the radius of these visited locations is activated.
* A line that is used for commute is shut down.
* A line that is within the radius of these visited locations lowers it's service frequency (reducing average wait time).

I don't have to solve the question of how I can commute optimally to work every morning, because I have stored the optimal path in my memory

If your goal is to model a realistic city you don't have to worry about complex situations with 3-5 or more interchanges because these are so un-attractive in a realistic city that they are never used. Normally if you can't find a path with 1 or maximum 2 changes of line you will use another method of travel then commute.


Another result of this is that citizens in reality that can't afford a car will normally chose their work/leisure/shop (or home) so that they are within range of commute or walking.

 

[timfrombriz]

If your goal is to model a realistic city you don't have to worry about complex situations with 3-5 or more interchanges because these are so un-attractive in a realistic city that they are never used. Normally if you can't find a path with 1 or maximum 2 changes of line you will use another method of travel then commute.

If the pathfinding could limit the number of nodes traversed, the amount of calculations could be reduced. Certainly another valid weighting argument to add to the mix (number of service transfers). Could also abort the current node traverse if travel distance is greater than the static start point to end point car travel distance weighting.

 

[kensternation]

... our algorithm already finds the optimal solution in terms of travel time / comfort and cost. However, it uses average times for waiting, not the actual timetable. This would make the calculation much more complex (You need to realize that on a large city at max speed we are doing several thousand pathfind requests per second).

Obviously, considering the plethora of complaints, your algorithm does NOT find the optimal solution. How would using next departure be so much more complex than average wait time? First you have to calculate average wait time and that is really difficult to do with no data when a line opens- sounds like division by 0 to me. Then you have to recalculate that EVERY time the poor CIM switches lines. How is it NOT simpler to find a train that starts where I live and goes relatively close to where I work that is leaving in the next few minutes? Then you figure routes out down the list of comfort/speed.

Average wait time? Really? Raise your hand if you use a service based on average wait time. Anyone?

Average and optimal are mutually exclusive. Also there should in no way be thousands of pathfinds/second. Anyone already on a vehicle does not need to calculate anything. Anyone already at work does not need to calculate anything. Once a route is taken, unless one or more schedule is changed, need not be repeated.

This is a quote from http://www.citiesinmotion2.com/ "Organize timetables to bring order out of chaos." Now you are telling us that from the beginning this was not about timetables but about average wait time. What is the point of schedules if people (read CIMs) don't read them? There is none. This is nonsense and needs to be addressed or you need to refund our money as the sale was based on false advertising.

 

[timfrombriz]

Average wait time? Really? Raise your hand if you use a service based on average wait time. Anyone?

In Brisbane Australia, timetables are being adapted to a turn up and go for some high frequency services. In this instance, they say at a particular stop between x time and y time then run every 5 to 10 minutes, without a list of individual times.
In this instance, it could be considered average wait time for the passenger.

This is a quote from http://www.citiesinmotion2.com/ "Organize timetables to bring order out of chaos." Now you are telling us that from the beginning this was not about timetables but about average wait time. What is the point of schedules if people (read CIMs) don't read them? There is none. This is nonsense and needs to be addressed or you need to refund our money as the sale was based on false advertising.

Mate, no one owes you anything. I for one will say the way your presenting your criticism of the game mechanics is like a child throwing a tantrem. If you don't like the game as it stands, don't play it, if you want to be involved in the community, be constructive.

This is a simulation game and the developers I'm confident didn't set out to mislead you. There are constraints with the design in regards to how much depth you can go before performance is impacted. Also this is new territory, they are not rehashing an existing game mechanic, they are inventing the wheel here with these ideas and will do so with how they see them working best. They are the painters so to speak.

Obviously, as you say, the complaints here are merely yours. The rest of us are engaging in constructive discussion about how this could be implemented, it was great to see CO respond, which indicates they are aware of this discussion and it may progress to improvement in the future, be it within CIM2 or maybe one day in a CIM3. CIM2 was built upon with the ideas from the community from CIM1.

 

[kensternation]

In Brisbane Australia, timetables are being adapted to a turn up and go for some high frequency services. In this instance, they say at a particular stop between x time and y time then run every 5 to 10 minutes, without a list of individual times.
In this instance, it could be considered average wait time for the passenger.



Mate, no one owes you anything. I for one will say the way your presenting your criticism of the game mechanics is like a child throwing a tantrem. If you don't like the game as it stands, don't play it, if you want to be involved in the community, be constructive.

This is a simulation game and the developers I'm confident didn't set out to mislead you. There are constraints with the design in regards to how much depth you can go before performance is impacted. Also this is new territory, they are not rehashing an existing game mechanic, they are inventing the wheel here with these ideas and will do so with how they see them working best. They are the painters so to speak.

Obviously, as you say, the complaints here are merely yours. The rest of us are engaging in constructive discussion about how this could be implemented, it was great to see CO respond, which indicates they are aware of this discussion and it may progress to improvement in the future, be it within CIM2 or maybe one day in a CIM3. CIM2 was built upon with the ideas from the community from CIM1.

First, that is NOT average wait time. Several transit agencies in the New York Metropolitan area also use every 2-4 minutes or every 5 minutes. That does not mean the average wit time is 5 minutes. That is how often the train comes. If it is every half hour, there is usually a train as a reference point that arrives at the station at say 8:36 every half hour would mean the next train is at 9:06 and the one after is at 9:36.

Second, obviously, as I say the complaints are NOT merely mine because if they were, no one would be trying to solve the issue, they would be too busy playing the game.

Third I have tried the calm approach but when a company, I had faith in, starts telling customers, sorry, we are not going to fix the number one issue it is time to up the ante of complaining. Obviously, you have an issue with the scheduling or you would not be in the forum. You would be playing. Read the threads that I have started and have posted replies in before using one sample of my rhetoric to assume that I am a whiny brat. I notice you edited what I actually posted. I may not have worded it the way you like it, but I did offer some help. Next time make sure to include things like this "First you have to calculate average wait time and that is really difficult to do with no data when a line opens- sounds like division by 0 to me. Then you have to recalculate that EVERY time the poor CIM switches lines. How is it NOT simpler to find a train that starts where I live and goes relatively close to where I work that is leaving in the next few minutes? Then you figure routes out down the list of comfort/speed."

 

[unmerged(607757)]

Would it help (to reduce the number of possible and calculated routes) if we could/should put in the connections between stops/lines manually.
It would be fun to do and give a bit more control of the passenger streams.
It is also not unusual to show the connections (and corresponding possibilities) between the differnt lines and forms of transport.

Greets,
Skelter

 

[kensternation]

Would it help (to reduce the number of possible and calculated routes) if we could/should put in the connections between stops/lines manually.
It would be fun to do and give a bit more control of the passenger streams.
It is also not unusual to show the connections (and corresponding possibilities) between the differnt lines and forms of transport.

Greets,
Skelter

+1

There could be 'official' transfer points, this way the CIM would not have to calculate and re-calculate for every single stop on the line.

 

[C40LFR]

I really hope there is some way to fix this. I would LOVE to add a peak hour only limited stop service.

Here in Los Angeles, buses use the "Rapid" branding for limited stop. Stops are only at busy stops(ie. major intersections, or employment centers), and they bypass typically time costly deviations that local buses use. (For example, a local bus deviates from the main highway to serve a small neighborhood to maximize catch area)

This game is getting there. Just need to add/fix a few things and this simulation would be almost perfect.

 

[kensternation]

I really hope there is some way to fix this. I would LOVE to add a peak hour only limited stop service.

Here in Los Angeles, buses use the "Rapid" branding for limited stop. Stops are only at busy stops(ie. major intersections, or employment centers), and they bypass typically time costly deviations that local buses use. (For example, a local bus deviates from the main highway to serve a small neighborhood to maximize catch area)

This game is getting there. Just need to add/fix a few things and this simulation would be almost perfect.

+1,000,000

We also have limited stop rush hour service and would love to implement it. It seems that despite all the complaints and suggestions CO is dropping the matter. Unfortunately this turns what could have been a top notch game into a bargain bin game in a month. I bought this game for scheduling and while co claims there is they then contradict themselves by saying the AI uses average wait time. Sighhhhhhhhhhhh

A quote from CO Dev gebbiz "our algorithm already finds the optimal solution in terms of travel time / comfort and cost." Obviously it does NOT or we would not all be yelling and screaming to have it fixed. What is the point of schedules if "it uses average times for waiting, not the actual timetable." And there you have it ladies and gentlemen- scheduling by average wait time. Sure because that's how scheduling works. I mean I actually had to read that several times when gebbiz posted that as I simply could not believe it. They also are telling us that is a much simpler way of of calculating pathfinding because as we know division by zero is so uber efficient.

 

[Tinyboss]

The problem there is that it's very easy to create a situation where list D would require terabytes of RAM (+insane amount of CPU power and that is only for one citizen). That wouldn't even solve the issue, our algorithm already finds the optimal solution in terms of travel time / comfort and cost. However, it uses average times for waiting, not the actual timetable. This would make the calculation much more complex (You need to realize that on a large city at max speed we are doing several thousand pathfind requests per second).

What if you maintained separate "average wait" data for each hour in the day? Twenty-four times as much data sounds like a lot, but certainly wouldn't put you in the "terabyte" range.

 

[wada314]

I understand what gebbiz saying. It's really "difficult" problem to calculate the route in a large city network, and they need to balance between the computation cost and the cims' realistic behavior. Alex's "cache" mechanism seems work well in a first glance, but to do that they need to memory hundreds of users who will potentially using the stations/stops per every stations/stops (remember, cims will going to the fixed work place, but going randomely for the leisure places), and need to maintain the station-users list in a thread safe manner (gebbiz, you're computing the cims' commute route in multithread, right?). So this method is not scaling for large problem.
And also some people are mentioning to make cims refer the timetable in more detail, but it's also difficult problem -- What will happen if a bus got stuck in a traffic jam and got delayed, and could not reach the stop within the time? The cim's trip plan will become completely useless, and he need to re-calculate his trip plan. And what happen if the next line is already "closed"? Only he can do is to wait until next morning or just disappear at that point. Also, I won't describe a detail in this limited space, but it's essential to use an "average waiting time" instead of an "actual timetable" is very very core factor for the algorithm to compute the cims' route with cheap computation cost.

To make the timetable system work perfectly, we need more and more system updates. For example, we need a system to make a bus "wait" for the arrival of a train at a nearby train station. For example, we need a system to "synchronize" two crossing lines, which vehicles wait each other in a crossing station, and leave after the all cims have done the transfer. Both need a complete re-design of the game system, and I think we cannot see that function in CiM2.

So my suggestion is: let's forget about the complex timetable options. What we can do in this version of CiM is only something like "This line runs every 30 mins, but in midnight, it runs only every 1 hour.". All I want is if I can do the timetable setting in more easy way, not the current "click copy-from-another-line button for 5 times" way.

 

[timfrombriz]

This falls under the Pathfinding AI argument that's been thoroughly debated with the developers.

If you can't fathom the complexity of calculations this game currently is performing every second, then just consider that every spot on the landscape that has a moving vehicle and walking person, regardless visible on screen or not, is navigating a path and recalculating on demand in addition to the pathfinding of the player's buses/trains/ferries etc. Just consider how well this game performs on this scale alone, and then try to consider the limitations Colossal Order may be bound to.

What I did is variate my style of game play, heres two examples:


1. A line that runs from the city centre to the west and vice versa, has an inbound/outbound stop on the same round throughout the trip.

Instead of running a full loop route covering depot->city centre->west->city centre->depot, I break it into 2 routes, an inbound (west to city centre) & outbound (city centre to west). Both run from the same depot, roughly half way. This gives me greater control on the inbound times (residential to city centre) and outbound times (city centre to residential) timetables, and the balance of vehicles disributed from the one depot varies from 50%/50% to 10%/90%. This works really well and adds a gameplay dynamic of balancing vehicle demands vs patronage.

2. A train line may run A-B-C-D- etc .... to X-Y-Z . Have one train run all stations from A-K , then express to Z. Have another train run express from A to K, then all stations K to Z. You'll find there many variations of this style of pattern stopping, and the idea is to move people faster to their destination. This seems to work as expected with the pathfinding from my experience.

I guess the idea is try to understand what's going on with the pathfinding behaviour and think of strategies that can achieve your intended goals (passenger numbers, delivery speed, operation costs, least vehicles in service)

 

[thestoon]

I'm not really convinced there is a problem with the AI the way it is. Yes, its imperfect - if your idea of perfection is an AI that will always pick the most logical and optimal journey. The problem with that is, its simply not a real representation of how people use public transport. Just like the AI, real people are often seemingly illogical, taking seemingly suboptimal routes, strange detours etc. Imagine you're a traffic planner in a big city, you're analysing someones usage, and you can see that everyday they travel from point A to point B in the morning, and point B to point A at night. The quickest, most comfortable route is a single tram journey. However, you notice that 1 day of the week the person uses the tram for one stop, before changing onto a bus, then another bus before going back onto the tram further down the line. It looks utterly bizarre, why would anyone do this? Well, what you don't know is that every Tuesday this person picks up a newspaper they order that they can only get at one particular newsagent in town. The detour takes them right past that newsagents. You, as a traffic planner, will never know this motivation, you just see a bizarre journey. Maybe you have a tourist, who for 3 days just gets on a tram, goes somewhere and then goes straight back to his hotel. One day 4 he takes a tram, then a bus, then a tram, then a bus, and another bus, and a tram before spending 5 minutes in a shop and repeating the whole journey in reverse. Crazy eh? Not really, its the last day of his holiday and he wants to explore a bit of the city. What better way than with a travelcard?

Big cities are chaotic, and public transport systems are too. Not every journey is perfect, for various reasons. People don't know the system so they make mistakes, people who change lines to travel part of a journey with their friends, if you can think of it, there will probably be someone, somewhere who will do it. The imperfections in the AI go some way to representing this kind of chaos. We see as much about our citizens as a traffic planner would in real life, we can't do surveys to find out why people use the system the way the do, so its up to us to fill in the gaps using our own imaginations. Try it, its fun.

 

[Lord Vetinari]

Try it, its fun.

Not fun anymore when customers are unhappy and unsatisfied because of the stupid stunts they themselves pull off.