Page 1 of 1

Routing algorithm for goods/passenger (with route changeing)

Posted: 07 Oct 2004 10:05
by Zuu
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.

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 ].


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.
     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.
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]

* 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)

* 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.

* 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)

Posted: 07 Oct 2004 10:33
by Arathorn
We gods don't really need transport, as we're almighty. ;)

But this is a good topic, I also think the passenger movement topic should be revived, we weren't done discussing I believe. ;)

Posted: 14 Nov 2006 14:43
by Hyronymus
Do we still support the view expressed by Zuu or should this topic be archived? The Design Document doesn't offer a clue.

Posted: 14 Nov 2006 16:28
by aarona
Seeing as though we give the player the option to load and unload at will, this is now redundant?

It may affect passengers who have destinations, but really I think this should be archived.

Posted: 14 Nov 2006 23:31
by Zuu
Having reread my old post, I think it reflects a way to implement some kind of routing for goods. Where goods don't have any specific destination other than anything that accepts that kind of goods.

It lend some ideas from A* which I was working with at the time I wrote that algoritm.

If you choose to have goods destinations in the sens that goods from source A must reach factory B, then my algoritm would be of none use. But if goods from any source you got contract with is allowed to reach any factory you got a contract with then the algoritm can be used.

( I'd rather not give you the answer if it should be archived or not, that's all up to you. )

Posted: 14 Nov 2006 23:45
by m4rek
i agree with aarona

although passengers might need it

Locked until the DD discussion arrives at this issue.