Routing algorithm for goods/passenger (with route changeing)

Development discussion about Transport Empire. Other discussion to General forum please.

Moderator: Transport Empire Moderators

Locked
User avatar
Zuu
OpenTTD Developer
OpenTTD Developer
Posts: 4553
Joined: 09 Jun 2003 18:21
Location: /home/sweden

Routing algorithm for goods/passenger (with route changeing)

Post by Zuu » 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:

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.
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)
Last edited by Zuu on 07 Oct 2004 10:41, edited 1 time in total.
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)

User avatar
Arathorn
Tycoon
Tycoon
Posts: 6939
Joined: 30 Nov 2002 17:10

Post by Arathorn » 07 Oct 2004 10:33

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. ;)

User avatar
Hyronymus
Tycoon
Tycoon
Posts: 13189
Joined: 03 Dec 2002 10:36
Location: The Netherlands
Contact:

Post by Hyronymus » 14 Nov 2006 14:43

Do we still support the view expressed by Zuu or should this topic be archived? The Design Document doesn't offer a clue.

User avatar
aarona
Traffic Manager
Traffic Manager
Posts: 221
Joined: 26 May 2006 15:54
Location: Perth, Australia
Contact:

Post by aarona » 14 Nov 2006 16:28

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.

User avatar
Zuu
OpenTTD Developer
OpenTTD Developer
Posts: 4553
Joined: 09 Jun 2003 18:21
Location: /home/sweden

Post by Zuu » 14 Nov 2006 23:31

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. )
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)

m4rek
Chairman
Chairman
Posts: 801
Joined: 03 Sep 2006 08:06
Location: Plymouth, England

Post by m4rek » 14 Nov 2006 23:45

i agree with aarona

although passengers might need it


Locked until the DD discussion arrives at this issue.
Toyland isn't a climate, it's a mistake.
Everyone has a photographic memory - Some just don't have film
No matter how hard life gets, remember there is always light at the end of the tunnel. Let's just hope it's not a train.

Locked

Return to “Transport Empire Development”

Who is online

Users browsing this forum: No registered users and 1 guest