Routing algorithm for goods/passenger (with route changeing)
Posted: 07 Oct 2004 10:05
Introduction:
An algorism for letting goods change route. Goods will not have a final destination. So it will probably be more dynamical than by random(or via an algorithm) chose a destination when goods is generated.
Definitions:
Vehicles: Train, lorry, buss, airplane, helicopter, ship.
Goods: passengers, wood, cattle, food etc.
factory: anything that generates/accept goods. Including city houses.
My notes about optional things and possible improvements is between [ and ].
Algorithm:
Each lists element contain:
* Goods type
* Transport cost for closest station(that accept or delivery to another station) estimated by number of route changes and estimated distance.
Optional: [not necessary for the algorithm above, but can help to maintain the lists]
* How many route changes for the final destination.
* Estimated distance for the final destination.
* The estimated capacity of all vehicles that delivery from this station per year. [maybe we can use last years capacity as estimated capacity]
Positive:
* Goods can make changes to reach a destination, without that factories have to decide where to send goods. Freedom for player to chose where to send goods. (he might get better payed for some destinations)
Problems:
* To maintain the lists.
* Might be problems when deleting a line or changing a route. Goods might be left on a station where it cant get away from.
* The list will take some memory.
* To estimate the transport cost.
* Sometimes a player dont want that a station should delivery goods to a factory in its accept/supply zone. The payment might be to low. A possible solution can be to have a switch on the station GUI to allow the player to block the station from delivery a certain goods sort do nearby factories.
Notes:
* The consuming part of this algorithm is probably to maintain the lists. We have to figure out how it can be done.
Related topics in the past:
Passenger movement
Very flexible economy/industry system
EDIT: changed gods -> goods. (Emacs didn't complain. Stalman is to religious)
An algorism for letting goods change route. Goods will not have a final destination. So it will probably be more dynamical than by random(or via an algorithm) chose a destination when goods is generated.
Definitions:
Vehicles: Train, lorry, buss, airplane, helicopter, ship.
Goods: passengers, wood, cattle, food etc.
factory: anything that generates/accept goods. Including city houses.
My notes about optional things and possible improvements is between [ and ].
Algorithm:
Code: Select all
1. Goods(in this example Cattle) arrives to a station either from a vehicle or a factory.
2. A vehicle arrives to the station.
3. IF( any of the stations that the vehicle stops at accept cattle )
OR IF( any of the stations that the vehicle stops at(called ViaStation) have cattle in its list of goods sorts that can be delivered to a factory, via ViaStation. AND transport cost is lower via ViaStation than via this station. )
{
Add one of the stations which the above is true for. Which one can be selected by lowest number of changes and lowest estimated distance.
}
ELSE
{
Jump to 2.
}
4. The cattle arrives to a station.
5. If there is any factories that accept cattle, the cattle will be delivered to that factory. Else jump to 2.* Goods type
* Transport cost for closest station(that accept or delivery to another station) estimated by number of route changes and estimated distance.
Optional: [not necessary for the algorithm above, but can help to maintain the lists]
* How many route changes for the final destination.
* Estimated distance for the final destination.
* The estimated capacity of all vehicles that delivery from this station per year. [maybe we can use last years capacity as estimated capacity]
Positive:
* Goods can make changes to reach a destination, without that factories have to decide where to send goods. Freedom for player to chose where to send goods. (he might get better payed for some destinations)
Problems:
* To maintain the lists.
* Might be problems when deleting a line or changing a route. Goods might be left on a station where it cant get away from.
* The list will take some memory.
* To estimate the transport cost.
* Sometimes a player dont want that a station should delivery goods to a factory in its accept/supply zone. The payment might be to low. A possible solution can be to have a switch on the station GUI to allow the player to block the station from delivery a certain goods sort do nearby factories.
Notes:
* The consuming part of this algorithm is probably to maintain the lists. We have to figure out how it can be done.
Related topics in the past:
Passenger movement
Very flexible economy/industry system
EDIT: changed gods -> goods. (Emacs didn't complain. Stalman is to religious)
