[RFD] Finding routes and services

[Hellfire]

In last sunday's meeting, I promised to put my comments on route/service finding on the forums and try to explain them a bit more clear.

PLEASE KEEP THIS THREAD ON-TOPIC

---

Let's make some definitions first so we know what we're talking about.

• Route: Two connected stations. (i.e. two railway stations with track between them or two harbours which are reachable over water. All airports are connected.)
• Connected: Two stations s and t are directly connected, if there is a piece of track between them on which vehicles can get from the one station to the other. Two stations s and t are indirectly connected if there is a station r for which the following holds:
  • s is connected (directly or indirectly) to r and r is connected to t.
  Please notice that it may take several recursive steps to get a path of directly connected stations between two indirectly connected stations. Also, if the word (in)directly is ommited, we mean "directly or indirectly connected".
• Service: A route on which some type of cargo is transported. (e.g. a passenger service between two busstops in a city.)

The following picture shows an example:

Strange people in Locomotion. Eventhough there is nothing in the catchment area's of the stations, people manage to find them.
In the picture:

• There is a route from A to B.
• A is directly connected to B.
• B is directly connected to C.
• C is directly connected to D.
• A is indirectly connected to C and D. (and vice-versa)
• There is a passenger service from B to C and there is a passenger service from C to D.

Note that some have been ommitted.

Obviously, we could search for routes or for services. I propose the setup given in the following subsections. Feel free to give comments.

Finding services

I chose this one first, because it's the most obvious. Consider a graph G=(V,E,L), where V is a set of vertices, which will be all stations. E is the set of edges, where an edge e=(v1,v2), a directed connection between two stations. L is a labelling function over the set E of edges where L(e) is a subset of all track types.

The following image shows an example:


There is a piece of bidirectional railroad track with two stations, "A" and "B". Then, we have:

• V = {A, B}
  V is the set of vertices, vertices represent the stations.
• E = {(A, B), (B, A)}
  E is the set of edges, edges represent routes. Because the piece of track is bidirectional, there are two edges: one from A to B and one from B to A.
• L(A, B) = {Rail}, L(B, A) = {Rail}
  L assigns a set of labels to each edge. Each label represents a track type. In this case, both edges represent a piece of railroad track.

Now, we also consider another labelling function S over set E, where S(e) is a subset of cargo types. So if between A and B is a coal service, S would look like this:

• S(A, B) = {Coal}, S(B, A) = {Coal}

Using this graph, we can use a greedy algorithm, for example Dijkstra's shortest path algorithm, to calculate for a given station and cargo type, a set of stations which have a service of the given cargo type between them. Even better, if two stations are selected, the shortest path between them can be calculated using some heuristic algorithm like A*.

So now we have a list of reachable stations using the current services. This way, cargo can be offered for destinations that do not have direct services, but do have services with several transfers.

Finding routes

Consider the same graph G=(V,E,L) as in the Finding services section.

An industry x wants to transport cargo to another industry y.

In addition to stations connected with services, we now also consider stations that are connected, but do not have a service for the desired cargo type between them.

In the same way as described for services, a route can be found between two stations or a list of all reachable stations for a given station. Now, suppose industry x is in the catchmentarea of station A and industry y is in the catchmentarea of station B. Industry x will check the list of station A and notice that there is a route to station B, which has industry y in its catchment area. However, there is no service for the desired cargo type between them.

Perhaps Finding routes should be an optional feature, but what if industry a asks the player to provide a service of the desired cargo type between A and B? This can lead to more subsidies/contracts which are more interesting.

[Zuu]

Thanks, this was more clear than your previous post in the wiki. Althroght I won't be able to code the pathfinding algoritm for your model. But thats not becues of you, but becuse I'm not good enoght on maths and graps (yet).

Edit: Nice examples.

[PJayTycy]

If I use your terminology (eg: a route is only a direct connection), then why do you restrict the second part to "routes" ?

Why shouldn't an industry close by station A be able to propose a new service to station C ?

Maybe you didn't want routes to be restricted to direct connections? So a route would be any 2 stations that are (in)directly connected, while a service would be a route + transport for a certain cargo is provided between the 2 stations.

[Hellfire]

Maybe you didn't want routes to be restricted to direct connections? So a route would be any 2 stations that are (in)directly connected, while a service would be a route + transport for a certain cargo is provided between the 2 stations.

I think that was what I meant. The industry should be able to find routes between directly OR indirectly connected stations. Obviously, the definition of "route" is wrong. I'll fix it.

[Steve]

Meeting Decisions:

- Needs more discussion.

Status: Open to discussion.

[Hellfire]

I'd like to add here that this topic is mostly about implementation details. This does not need to be in the design document.

[Steve]

I disagree. We need to discuss how passengers will wait at stations and be taken on trains as such,

My suggestions.
As a base, used in all below solutions, i think it would be best if passengers only visit stations when routes have been set up. So, as soon as you finish setting a route for a train from London to Paris and the trains start rolling, people will go to the station and wait for the train. The amount of passengers would depend on the size of the start and end cities.
Notes: Trains DON'T need to visit the station to start the service, there just need to a be a route and a train moving. To avoid TTDPatch style first runs, where no cargo is transported. Number of trains may or may not affect passenger turn out. If we leave the numbers higher than can be transported, it'll just encourage players to build more trains (which isn't bad).

Then, either:
(A) Passengers are picked up on a first come, first serve basis. This is the simplist method to use and the simplist to implement. But can be exploited by connecting up routes to major cities with low numbers of trains, then setting up lots of other trains to easier, more profitable (in some cases) routes, that are designed to soak up all the passengers. Slight changes to the main section can be changed to fix that.

(B) Passengers can look ahead 3 or so journeys from connected stations. So if a train goes from Paris to Madrid, then a person in London will go to the station for the Paris train. Then, in the station window, you can make a list, sorted by number of passengers to a place or by place, to see where people are going. London Station may say something like:
Madrid: 78 Passengers
Paris: 12 Passengers
Swindon: 3 Passengers.
This will be mostly to locate popular routes that aren't being serviced properly as passengers, with their specific destinations, will only board trains which will one eventually get to their destination. So passengers going to Madrid will take a train to Paris or if there is also a detour through Swindon, it'll take the train to go there instead.
I'm not sure whether we should make passengers wait for specific routes, as maybe that's a bit too much micromanagement, as long as they get to where they want to go.

(B) Notes: Places can be defined by cities, or in cases of big cities, specific areas of cities. Such as Downtown London or Heathrow. Could also have 'regions' for areas of countryside with many small villages.
Because of this route based system, building an effective bus network will greatly increase your passenger base as passengers will know of other stations they can get to from the other Bus Stop. So it's quite realistic for someone to go:
Stockport Bus Stop -> Manchester Airport -> LA Airport -> Hollywood
Which, i think, is pretty damn cool!

[Arathorn]

I like option B.
Not sure about the parts of cities though, if we go for TTD size cities or perhaps a bit larger, we won;t have clear regions.

[Hyronymus]

I like option B too but I want to know if it's possible too. Any devs who can shed a light on it?

[Steve]

Well, Locomotion cities got really big. They turned to a Metropolis. It would be hard to isolate areas realistic areas, but it should be fairly simply to make North, Central, East etc divides. Over time these divides would change, when that happened, we'd have to update all routes and passenger destinations automatically, in order to keep everything flowing smoothly. Perhaps add a simple "London announces new transport system".

I agree that it depends a lot on the size of maps, the scale and everything that we choose, but the proposed grid systems may be able to compact the map more than a normal TTD town, so roads don't look as huge. I suppose for the time being, we should just concentrate on the general system, and refine it as we go.

[Hyronymus]

I wondered if the 'smart passenger logarithm' is possible at all .

[Hellfire]

Any devs who can shed a light on it?

Actually, I explained how to implement such a system in the first post of this topic.

I think it's very possible to do this. In fact, if programmed in a clever way, we could even show the individual destinations of passengers in a vehicle-detail display.

For example:

Vehicle info, cargo:
* 50 passengers from station A to station B
* 30 passengers from station C to station B
* 1 passenger from station A to station D

Or perhaps a bit simpler:

Vehicle info, cargo:
* 50 passengers from city A to city B
* 1 passenger from city A to city D
* 30 passengers from city C to city B

I think I prefer the former over the latter. The former will allow people to continue travelling after they've reached the city they "wanted" to go to.

Edit:
If it wasn't clear from this post, I prefer option B

[PJayTycy]

I would like the passengers to choose a actual route rather than just a destination. People that appear at a station should already have decided which train/route they'll take.

How to implement (trying to use Hellfire's connected-route-service naming convention) :
We have a list of services provided by all companies.
When a passenger is created, give him some desirable destinations.
Elect all routes he can choose (to any of his destinations, by any company, by any method).
Give those routes points based on {order in his destination-list, company rating, speed, cost , waiting-line , ... }
Assign the passenger to the route with the most points, increase the corresponding waiting line, put the person visible on the right station.


Option A is completely unacceptable. You only divide passengers between companies and don't care about destinations. We decided our passengers would have destinations.

Option B is desirable, only you didn't specify how to divide the passengers between the stations if there are multiple stations (maybe competing companies) and how to give the passengers destinations.

[PJayTycy]

In last meeting, there was decided to keep discussing this more thoroughly. I agree we have mostly been talking next to each other, without interaction.

There are some real basic things we need to decide on for this topic. I'll try to list them here, perhaps as a basis for voting later on, but first as a basis for more discussion. I also would ask, if we vote, to vote point-by-point, and not a vote for all points at once, because votes on some points will depend on the outcome of other points. The best order is not the order they appear here btw.

I'll start with making an assumption, I hope we agree on this one:

0) Cities/buildings generate a certain amount of passengers / month or year. (How this amount is calculated is still to be decided)

This raises the first 2 questions, an easy one:
1) At what frequency should new passengers be created?

• 1a. once each month
• 1b. once each week
• 1c. each day
• 1d. more than once a day

and a more difficult one:
2) Should passengers be created & consumed by buildings or by cities?

• 2a. Buildings => They have a location in the city, and will start their journey there.
• 2b. Cities => They don't have a specific location in the city. They might still end up everywhere.
• 2c. Regions, probably "per cell" or something.

So, next, what do we need to do now with our people? This is where the real trouble (and I hope discussion will kick in):
3) Do we assign them their complete route from start => finish or just drop them at a certain station ? (the question on how this route/station is chosen, comes next, but the answer to this question will have a strong influence on it)

• 3a. complete route : The passenger knows which trains to catch, which busses to get, etc... to get to his destination.
• 3b. one piece at a time : The passenger will have to decide at each stop wheter to get off and which transport method to choose next, gradually trying to get closer to its destination.

When a passenger is assigned an unreachable destination, we will notice that in 3a, but not (necessarily) in 3b.
4) What about unreachable destinations ?

• 4a. Impossible, we will only give destinations that are reachable.
• 4b. Randomly give a destination, if it is unreachable, just "discard" the passenger and move on.
• 4c. Try a few times to give another random destination, then "discard" the passenger.

Before you vote on this question, please read our wiki (I'll probably have to repeat it anyway).

Now, together with question 3, what should we account for when choosing the route a passenger takes (either when created = option 3a or when he gradually progresses to its destination = option 3b)
5) What will influence the passenger when choosing a route.?

• 5a. company rating (-s)
• 5b. estimated travel time (not possible for option 3b)
• 5c. travel cost (not possible for option 3b)
• 5d. crowdiness of the route (-s)
• 5e. locomotive (-s) appeal
• 5f. more?

I know this will be a mess to discuss, but I tried to split up this complicated issue in the appropriate sub-issues as good as I could. Feel free to comment on this split-up approach and on the issues themselves of course..

[Zuu]

Please also read this: http://www.hajo.simutrans.com/pmwiki/pm ... uEn/Cities It iis about pathfinding and passengers in simutrans.

One thing that I think is important to remember, that Hajo have siad that he has to choice a quite simple destination and route selection algoritm, becuse else it would consume to much CPU time.

Evan thoght we begin a few years later (faster computers) I think we still have to remember that we will have LOTS of passengers, goods etc, and a fast algoritm is a must.

[jfs]

I would like passengers to travel from one building to one station. But of course only the destination is stored with the passenger. That way several passengers can be grouped into a "passenger group", which is treated as one entity for pathfinding purposes etc.

Passengers should be generated "all the time", ie. often enough that the player doesn't notice they're genearted at a specific interval. Perhaps make the interval somewhat random. I think approx. once a day should work well.

For simplicity I'll just write passenger from now on, when I mean a passenger group. Everything that applies to a single passenger also applies to any other passenger with the same destination.

Passengers will always want to get to their destination as quickly as possible. I think we should just assume that everyone has an infinite purse and will pay whatever, that should simplify calculations.
Unfortunately, it's hard to say anything about the time a travel will take, but making the basic assumption that longer route equals longer travel time should work in most cases.

I would like pathfinding to be somewhat dynamic. A passenger should take the first vehicle that brings him closer to his destination.
Now, I don't know if this will be too slow to calculate, but, my idea is:
Build a directed graph of all passenger traffic connections on the map. A passenger that wants to travel, runs an "all paths from single source to single destination" algorithm on this graph, using his current location and destination. If there are no paths, the passenger will just give up. Otherwise, the passenger will take any vehicle that follows a path that is at most 50% (number subject to change) longer than the shortest path. That should bring the passenger "closer".
When the passenger boards a vehicle, he selects one "midway destination", which is the place he will get off this vehicle. When the passenger reaches the midway destination, he will get off and run the algorithm again.
If the station the passenger is currently at is the same as the destination station, the travel is over and the passenger disappears.

One weakness of this algorithm: It can't take many of the things under PJay's point 5 into account. It does take travel time (5b) into account, but the rest of the points can't be properly taken into the calculation. I would like to see 5a and 5e taken into account too. (Idea: They could modify the cost of the individual edges in the graph?)

(This is an elaboration of what I said during the IRC meeting yesterday.)

[Zuu]

Otherwise, the passenger will take any vehicle that follows a path that is at most 50% (number subject to change) longer than the shortest path. That should bring the passenger "closer".

...

One weakness of this algorithm: It can't take many of the things under PJay's point 5 into account. It does take travel time (5b) into account, but the rest of the points can't be properly taken into the calculation. I would like to see 5a and 5e taken into account too. (Idea: They could modify the cost of the individual edges in the graph?)

Could you have a base of 50% and multiplcy (or add/subbtract (faster)) a factor that depend on the company rating and other things that we want to take into acount.

If we only use company rating which would not differ frome train to train, we can calculate the vale once a day and save it in memory. This way we will take 5a into acount without making the game significant slower.

[Steve]

0) Calculation is irrelevant at this stage.

This raises the first 2 questions, an easy one:
1) At what frequency should new passengers be created?
Also irrelevant, depends on things like time scale, as doesn't really matter right now.

and a more difficult one:
2) Should passengers be created & consumed by buildings or by cities?
By buildings/regions or it doesn't make sense. If a passenger can be anywhere in a city, then he has no need to catch a bus to the other side!

3) Do we assign them their complete route from start => finish or just drop them at a certain station ?
I want to say 3b, but that would be a problem. I think jfs's solution is best, where the passenger has many possible routes and as he works through the stations, the amount would get smaller. So, he wouldn't be making new routes at each station, or he could just go round and round.. never getting to his destination.

4) What about unreachable destinations ?
If we have percentages of passengers that want to go to the major towns, etc, then only the passengers which have a route, go to the station. We don't want lists of "Passenger to London" when there is no route to London.. it would be long, overwhelming and probaly of little use.

5) What will influence the passenger when choosing a route.?
Ratings would choose which station he goes to first, but then, with jfs's idea, he'd just follow the best routes to his destination. I think that's the most realistic model too. If your catching a train somewhere, you just get the first train that your ticket works on. Often the one that leaves first. I think that's the simpliest way to handle it.

[Zuu]

from this thread in the Simutrans forum (here at tt-forums):

Zuu, I wanted to post a message to the Transport Empire forum. You talked about passenger pathfinding and the CPU load it cuases in Simutrans. But I'm not allowede to post there. So I write it here:

In big games there can be several tenth of thousands passengers in the game. The network can change often becuase the player keeps building. So passenger pathfinding is called fairly often, for each created passenger and for every passenger who leaves a vehicle to transfer to another vehicle. In large games this are a lot of calls due to the high number of passengers.

But since 3GHz CPUs become more and more common nowadays, the problem may no longer exist until Transport Empire is done. So you might keep an eye on the issue but I assume it's not worth spending a lot of thought in this early stage of TE development.

[PJayTycy]

In big games there can be several tenth of thousands passengers in the game. The network can change often becuase the player keeps building. So passenger pathfinding is called fairly often, for each created passenger and for every passenger who leaves a vehicle to transfer to another vehicle.

If we establish the complete route when the passenger is created, this would reduce the overhead of re-calculating it at every stop. I don't know how the increased complexity in calculating it all at once compares to the reduction in overhead at the transfer stops.

As it is friday evening, and almost no discussion has come up, I'll just vote here because I won't be at the meeting. Please take these votes in account at the meeting:

1) At what frequency should new passengers be created?
=> first choice : 1b. once each week
=> backup choices : more frequent (1c, 1d)

2) Should passengers be created & consumed by buildings or by cities?
=> first choice : 2a. Buildings
=> backup choice : 2c. Regions, probably "per cell" or something.

3) Do we assign them their complete route from start => finish or just drop them at a certain station ?
=> 3a. complete route : The passenger knows which trains to catch, which busses to get, etc... to get to his destination.

4) What about unreachable destinations ?
=> 4c. Try a few times to give another random destination, then "discard" the passenger. (no backup vote : reason : see the wiki)

5) What will influence the passenger when choosing a route.?
I'd like all of them to have an influence, I'll list them by how important I think they are...
=> 1 : 5b. estimated travel time
=> 1 : 5c. travel cost
=> 2 : 5a. company rating (-s)
=> 3 : 5d. crowdiness of the route (-s)
=> 3 : 5e. locomotive (-s) appeal