(svn r25259) -Codechange: track capacities and usage of links

18 files changed, 447 insertions, 14 deletions

diff --git a/src/aircraft_cmd.cpp b/src/aircraft_cmd.cpp
index 18d284dbb..e0eb3558e 100644
--- a/src/aircraft_cmd.cpp
+++ b/src/aircraft_cmd.cpp
@@ -271,13 +271,16 @@ CommandCost CmdBuildAircraft(TileIndex tile, DoCommandFlag flags, const Engine *
 		v->spritenum = avi->image_index;
 
 		v->cargo_cap = avi->passenger_capacity;
+		v->refit_cap = 0;
 		u->cargo_cap = avi->mail_capacity;
+		u->refit_cap = 0;
 
 		v->cargo_type = e->GetDefaultCargoType();
 		u->cargo_type = CT_MAIL;
 
 		v->name = NULL;
 		v->last_station_visited = INVALID_STATION;
+		v->last_loading_station = INVALID_STATION;
 
 		v->acceleration = avi->acceleration;
 		v->engine_type = e->index;
diff --git a/src/articulated_vehicles.cpp b/src/articulated_vehicles.cpp
index 9c9a1ba39..501af719d 100644
--- a/src/articulated_vehicles.cpp
+++ b/src/articulated_vehicles.cpp
@@ -355,6 +355,7 @@ void AddArticulatedParts(Vehicle *first)
 					t->cargo_type = front->cargo_type; // Needed for livery selection
 					t->cargo_cap = 0;
 				}
+				t->refit_cap = 0;
 
 				t->SetArticulatedPart();
 				break;
@@ -381,6 +382,7 @@ void AddArticulatedParts(Vehicle *first)
 					rv->cargo_type = front->cargo_type; // Needed for livery selection
 					rv->cargo_cap = 0;
 				}
+				rv->refit_cap = 0;
 
 				rv->SetArticulatedPart();
 				break;
diff --git a/src/economy.cpp b/src/economy.cpp
index 9c599dafc..aa7d94ce3 100644
--- a/src/economy.cpp
+++ b/src/economy.cpp
@@ -1615,6 +1615,13 @@ static void LoadUnloadVehicle(Vehicle *front)
 			} else if (cargo_not_full != 0) {
 				finished_loading = false;
 			}
+
+			/* Refresh next hop stats if we're full loading to make the links
+			 * known to the distribution algorithm and allow cargo to be sent
+			 * along them. Otherwise the vehicle could wait for cargo
+			 * indefinitely if it hasn't visited the other links yet, or if the
+			 * links die while it's loading. */
+			if (!finished_loading) front->RefreshNextHopsStats();
 		}
 		unloading_time = 20;
 
diff --git a/src/order_base.h b/src/order_base.h
index 5054a315b..d361ce67d 100644
--- a/src/order_base.h
+++ b/src/order_base.h
@@ -168,6 +168,9 @@ public:
 	inline void SetConditionValue(uint16 value) { SB(this->dest, 0, 11, value); }
 
 	bool ShouldStopAtStation(const Vehicle *v, StationID station) const;
+	bool CanLoadOrUnload() const;
+	bool CanLeaveWithCargo(bool has_cargo) const;
+
 	TileIndex GetLocation(const Vehicle *v, bool airport = false) const;
 
 	/** Checks if this order has travel_time and if needed wait_time set. */
@@ -239,6 +242,14 @@ public:
 	inline Order *GetLastOrder() const { return this->GetOrderAt(this->num_orders - 1); }
 
 	/**
+	 * Get the order after the given one or the first one, if the given one is the
+	 * last one.
+	 * @param curr Order to find the next one for.
+	 * @return Next order.
+	 */
+	inline const Order *GetNext(const Order *curr) const { return (curr->next == NULL) ? this->GetFirstOrder() : curr->next; }
+
+	/**
 	 * Get number of orders in the order list.
 	 * @return number of orders in the chain.
 	 */
@@ -250,6 +261,9 @@ public:
 	 */
 	inline VehicleOrderID GetNumManualOrders() const { return this->num_manual_orders; }
 
+	StationID GetNextStoppingStation(const Vehicle *v) const;
+	const Order *GetNextStoppingOrder(const Vehicle *v, const Order *next, uint hops) const;
+
 	void InsertOrderAt(Order *new_order, int index);
 	void DeleteOrderAt(int index);
 	void MoveOrder(int from, int to);
diff --git a/src/order_cmd.cpp b/src/order_cmd.cpp
index e44447f7c..833d23ff3 100644
--- a/src/order_cmd.cpp
+++ b/src/order_cmd.cpp
@@ -20,6 +20,7 @@
 #include "vehicle_func.h"
 #include "depot_base.h"
 #include "core/pool_func.hpp"
+#include "core/random_func.hpp"
 #include "aircraft.h"
 #include "roadveh.h"
 #include "station_base.h"
@@ -350,6 +351,87 @@ Order *OrderList::GetOrderAt(int index) const
 }
 
 /**
+ * Get the next order which will make the given vehicle stop at a station
+ * or refit at a depot if its state doesn't change.
+ * @param v The vehicle in question.
+ * @param next The order to start looking at.
+ * @param hops The number of orders we have already looked at.
+ * @return Either an order or NULL if the vehicle won't stop anymore.
+ */
+const Order *OrderList::GetNextStoppingOrder(const Vehicle *v, const Order *next, uint hops) const
+{
+	if (hops > this->GetNumOrders() || next == NULL) return NULL;
+
+	if (next->IsType(OT_CONDITIONAL)) {
+		if (next->GetConditionVariable() == OCV_LOAD_PERCENTAGE) {
+			/* If the condition is based on load percentage we can't
+			 * tell what it will do. So we choose randomly. */
+			const Order *skip_to = this->GetNextStoppingOrder(v,
+					this->GetOrderAt(next->GetConditionSkipToOrder()),
+					hops + 1);
+			const Order *advance = this->GetNextStoppingOrder(v,
+					this->GetNext(next), hops + 1);
+			if (advance == NULL) return skip_to;
+			if (skip_to == NULL) return advance;
+			return RandomRange(2) == 0 ? skip_to : advance;
+		}
+		/* Otherwise we're optimistic and expect that the
+		 * condition value won't change until it's evaluated. */
+		VehicleOrderID skip_to = ProcessConditionalOrder(next, v);
+		if (skip_to != INVALID_VEH_ORDER_ID) {
+			return this->GetNextStoppingOrder(v, this->GetOrderAt(skip_to),
+					hops + 1);
+		}
+		return this->GetNextStoppingOrder(v, this->GetNext(next), hops + 1);
+	}
+
+	if (next->IsType(OT_GOTO_DEPOT)) {
+		if (next->GetDepotActionType() == ODATFB_HALT) return NULL;
+		if (next->IsRefit()) return next;
+	}
+
+	if (!next->CanLoadOrUnload()) {
+		return this->GetNextStoppingOrder(v, this->GetNext(next), hops + 1);
+	}
+
+	return next;
+}
+
+/**
+ * Recursively determine the next deterministic station to stop at.
+ * @param v The vehicle we're looking at.
+ * @return Next stoppping station or INVALID_STATION.
+ */
+StationID OrderList::GetNextStoppingStation(const Vehicle *v) const
+{
+
+	const Order *next = this->GetOrderAt(v->cur_implicit_order_index);
+	if (next == NULL) {
+		next = this->GetFirstOrder();
+		if (next == NULL) return INVALID_STATION;
+	} else {
+		/* GetNext never returns NULL if there is a valid station in the list.
+		 * As the given "next" is already valid and a station in the list, we
+		 * don't have to check for NULL here.
+		 */
+		next = this->GetNext(next);
+		assert(next != NULL);
+	}
+
+	uint hops = 0;
+	do {
+		next = this->GetNextStoppingOrder(v, next, ++hops);
+		/* Don't return a next stop if the vehicle has to unload everything. */
+		if (next == NULL || (next->GetDestination() == v->last_station_visited &&
+				(next->GetUnloadType() & (OUFB_TRANSFER | OUFB_UNLOAD)) == 0)) {
+			return INVALID_STATION;
+		}
+	} while (next->IsType(OT_GOTO_DEPOT) || next->GetDestination() == v->last_station_visited);
+
+	return next->GetDestination();
+}
+
+/**
  * Insert a new order into the order chain.
  * @param new_order is the order to insert into the chain.
  * @param index is the position where the order is supposed to be inserted.
@@ -1044,11 +1126,11 @@ CommandCost CmdSkipToOrder(TileIndex tile, DoCommandFlag flags, uint32 p1, uint3
 	if (ret.Failed()) return ret;
 
 	if (flags & DC_EXEC) {
+		if (v->current_order.IsType(OT_LOADING)) v->LeaveStation();
+
 		v->cur_implicit_order_index = v->cur_real_order_index = sel_ord;
 		v->UpdateRealOrderIndex();
 
-		if (v->current_order.IsType(OT_LOADING)) v->LeaveStation();
-
 		InvalidateVehicleOrder(v, VIWD_MODIFY_ORDERS);
 	}
 
@@ -2122,3 +2204,23 @@ bool Order::ShouldStopAtStation(const Vehicle *v, StationID station) const
 			/* Finally do stop when there is no non-stop flag set for this type of station. */
 			!(this->GetNonStopType() & (is_dest_station ? ONSF_NO_STOP_AT_DESTINATION_STATION : ONSF_NO_STOP_AT_INTERMEDIATE_STATIONS));
 }
+
+bool Order::CanLoadOrUnload() const
+{
+	return (this->IsType(OT_GOTO_STATION) || this->IsType(OT_IMPLICIT)) &&
+			(this->GetNonStopType() & ONSF_NO_STOP_AT_DESTINATION_STATION) == 0 &&
+			((this->GetLoadType() & OLFB_NO_LOAD) == 0 ||
+			(this->GetUnloadType() & OUFB_NO_UNLOAD) == 0);
+}
+
+/**
+ * A vehicle can leave the current station with cargo if:
+ * 1. it can load cargo here OR
+ * 2a. it could leave the last station with cargo AND
+ * 2b. it doesn't have to unload all cargo here.
+ */
+bool Order::CanLeaveWithCargo(bool has_cargo) const
+{
+	return (this->GetLoadType() & OLFB_NO_LOAD) == 0 || (has_cargo &&
+			(this->GetUnloadType() & (OUFB_UNLOAD | OUFB_TRANSFER)) == 0);
+}
diff --git a/src/roadveh_cmd.cpp b/src/roadveh_cmd.cpp
index 44336ac45..77b82a420 100644
--- a/src/roadveh_cmd.cpp
+++ b/src/roadveh_cmd.cpp
@@ -279,8 +279,10 @@ CommandCost CmdBuildRoadVehicle(TileIndex tile, DoCommandFlag flags, const Engin
 		v->spritenum = rvi->image_index;
 		v->cargo_type = e->GetDefaultCargoType();
 		v->cargo_cap = rvi->capacity;
+		v->refit_cap = 0;
 
 		v->last_station_visited = INVALID_STATION;
+		v->last_loading_station = INVALID_STATION;
 		v->engine_type = e->index;
 		v->gcache.first_engine = INVALID_ENGINE; // needs to be set before first callback
 
@@ -311,6 +313,7 @@ CommandCost CmdBuildRoadVehicle(TileIndex tile, DoCommandFlag flags, const Engin
 		/* Call various callbacks after the whole consist has been constructed */
 		for (RoadVehicle *u = v; u != NULL; u = u->Next()) {
 			u->cargo_cap = u->GetEngine()->DetermineCapacity(u);
+			u->refit_cap = 0;
 			v->InvalidateNewGRFCache();
 			u->InvalidateNewGRFCache();
 		}
diff --git a/src/saveload/oldloader_sl.cpp b/src/saveload/oldloader_sl.cpp
index 8cc670d23..987af757a 100644
--- a/src/saveload/oldloader_sl.cpp
+++ b/src/saveload/oldloader_sl.cpp
@@ -1252,6 +1252,7 @@ bool LoadOldVehicle(LoadgameState *ls, int num)
 
 			if (!LoadChunk(ls, v, vehicle_chunk)) return false;
 			if (v == NULL) continue;
+			v->refit_cap = v->cargo_cap;
 
 			SpriteID sprite = v->cur_image;
 			/* no need to override other sprites */
diff --git a/src/saveload/saveload.cpp b/src/saveload/saveload.cpp
index 61ab52656..8b0ee1109 100644
--- a/src/saveload/saveload.cpp
+++ b/src/saveload/saveload.cpp
@@ -246,6 +246,7 @@
  *  179   24810
  *  180   24998   1.3.x
  *  181   25012
+ *  182   25259
  */
 extern const uint16 SAVEGAME_VERSION = 181; ///< Current savegame version of OpenTTD.
 
diff --git a/src/saveload/vehicle_sl.cpp b/src/saveload/vehicle_sl.cpp
index bc1edebb8..3ee6ce99c 100644
--- a/src/saveload/vehicle_sl.cpp
+++ b/src/saveload/vehicle_sl.cpp
@@ -604,6 +604,7 @@ const SaveLoad *GetVehicleDescription(VehicleType vt)
 		     SLE_VAR(Vehicle, vehstatus,             SLE_UINT8),
 		 SLE_CONDVAR(Vehicle, last_station_visited,  SLE_FILE_U8  | SLE_VAR_U16,   0,   4),
 		 SLE_CONDVAR(Vehicle, last_station_visited,  SLE_UINT16,                   5, SL_MAX_VERSION),
+		 SLE_CONDVAR(Vehicle, last_loading_station,  SLE_UINT16,                 182, SL_MAX_VERSION),
 
 		     SLE_VAR(Vehicle, cargo_type,            SLE_UINT8),
 		 SLE_CONDVAR(Vehicle, cargo_subtype,         SLE_UINT8,                   35, SL_MAX_VERSION),
@@ -612,6 +613,7 @@ const SaveLoad *GetVehicleDescription(VehicleType vt)
 		SLEG_CONDVAR(         _cargo_source,         SLE_UINT16,                   7,  67),
 		SLEG_CONDVAR(         _cargo_source_xy,      SLE_UINT32,                  44,  67),
 		     SLE_VAR(Vehicle, cargo_cap,             SLE_UINT16),
+		 SLE_CONDVAR(Vehicle, refit_cap,             SLE_UINT16,                 182, SL_MAX_VERSION),
 		SLEG_CONDVAR(         _cargo_count,          SLE_UINT16,                   0,  67),
 		 SLE_CONDLST(Vehicle, cargo.packets,         REF_CARGO_PACKET,            68, SL_MAX_VERSION),
 		 SLE_CONDARR(Vehicle, cargo.action_counts,   SLE_UINT, VehicleCargoList::NUM_MOVE_TO_ACTION, 181, SL_MAX_VERSION),
@@ -903,6 +905,8 @@ void Load_VEHS()
 			v->last_station_visited = INVALID_STATION;
 		}
 
+		if (IsSavegameVersionBefore(182)) v->last_loading_station = INVALID_STATION;
+
 		if (IsSavegameVersionBefore(5)) {
 			/* Convert the current_order.type (which is a mix of type and flags, because
 			 *  in those versions, they both were 4 bits big) to type and flags */
diff --git a/src/ship_cmd.cpp b/src/ship_cmd.cpp
index 55c695603..ea1233da4 100644
--- a/src/ship_cmd.cpp
+++ b/src/ship_cmd.cpp
@@ -681,8 +681,10 @@ CommandCost CmdBuildShip(TileIndex tile, DoCommandFlag flags, const Engine *e, u
 		v->spritenum = svi->image_index;
 		v->cargo_type = e->GetDefaultCargoType();
 		v->cargo_cap = svi->capacity;
+		v->refit_cap = 0;
 
 		v->last_station_visited = INVALID_STATION;
+		v->last_loading_station = INVALID_STATION;
 		v->engine_type = e->index;
 
 		v->reliability = e->reliability;
diff --git a/src/station.cpp b/src/station.cpp
index 7fb6e1916..da5f09025 100644
--- a/src/station.cpp
+++ b/src/station.cpp
@@ -24,6 +24,7 @@
 #include "roadstop_base.h"
 #include "industry.h"
 #include "core/random_func.hpp"
+#include "linkgraph/linkgraph.h"
 
 #include "table/strings.h"
 
@@ -63,7 +64,8 @@ Station::Station(TileIndex tile) :
 }
 
 /**
- * Clean up a station by clearing vehicle orders and invalidating windows.
+ * Clean up a station by clearing vehicle orders, invalidating windows and
+ * removing link stats.
  * Aircraft-Hangar orders need special treatment here, as the hangars are
  * actually part of a station (tiletype is STATION), but the order type
  * is OT_GOTO_DEPOT.
@@ -87,12 +89,25 @@ Station::~Station()
 		if (a->targetairport == this->index) a->targetairport = INVALID_STATION;
 	}
 
+	for (CargoID c = 0; c < NUM_CARGO; ++c) {
+		LinkGraph *lg = LinkGraph::GetIfValid(this->goods[c].link_graph);
+		if (lg != NULL) {
+			lg->RemoveNode(this->goods[c].node);
+			if (lg->Size() == 0) {
+				delete lg;
+			}
+		}
+	}
+
 	Vehicle *v;
 	FOR_ALL_VEHICLES(v) {
 		/* Forget about this station if this station is removed */
 		if (v->last_station_visited == this->index) {
 			v->last_station_visited = INVALID_STATION;
 		}
+		if (v->last_loading_station == this->index) {
+			v->last_loading_station = INVALID_STATION;
+		}
 	}
 
 	/* Clear the persistent storage. */
diff --git a/src/station_base.h b/src/station_base.h
index 7a3d3a885..974caa063 100644
--- a/src/station_base.h
+++ b/src/station_base.h
@@ -334,6 +334,8 @@ public:
 	/* virtual */ uint32 GetNewGRFVariable(const ResolverObject *object, byte variable, byte parameter, bool *available) const;
 
 	/* virtual */ void GetTileArea(TileArea *ta, StationType type) const;
+
+	void RunAverages();
 };
 
 #define FOR_ALL_STATIONS(var) FOR_ALL_BASE_STATIONS_OF_TYPE(Station, var)
diff --git a/src/station_cmd.cpp b/src/station_cmd.cpp
index c2b4cf410..10af5519e 100644
--- a/src/station_cmd.cpp
+++ b/src/station_cmd.cpp
@@ -50,6 +50,7 @@
 #include "order_backup.h"
 #include "newgrf_house.h"
 #include "company_gui.h"
+#include "linkgraph/linkgraph_base.h"
 #include "widgets/station_widget.h"
 
 #include "table/strings.h"
@@ -559,7 +560,7 @@ void UpdateStationAcceptance(Station *st, bool show_msg)
 
 	/* Adjust in case our station only accepts fewer kinds of goods */
 	for (CargoID i = 0; i < NUM_CARGO; i++) {
-		uint amt = min(acceptance[i], 15);
+		uint amt = acceptance[i];
 
 		/* Make sure the station can accept the goods type. */
 		bool is_passengers = IsCargoInClass(i, CC_PASSENGERS);
@@ -568,7 +569,11 @@ void UpdateStationAcceptance(Station *st, bool show_msg)
 			amt = 0;
 		}
 
-		SB(st->goods[i].acceptance_pickup, GoodsEntry::GES_ACCEPTANCE, 1, amt >= 8);
+		GoodsEntry &ge = st->goods[i];
+		SB(ge.acceptance_pickup, GoodsEntry::GES_ACCEPTANCE, 1, amt >= 8);
+		if (LinkGraph::IsValidID(ge.link_graph)) {
+			(*LinkGraph::Get(ge.link_graph))[ge.node].SetDemand(amt / 8);
+		}
 	}
 
 	/* Only show a message in case the acceptance was actually changed. */
@@ -3341,6 +3346,79 @@ static void UpdateStationRating(Station *st)
 	}
 }
 
+/**
+ * Increase capacity for a link stat given by station cargo and next hop.
+ * @param st Station to get the link stats from.
+ * @param cargo Cargo to increase stat for.
+ * @param next_station_id Station the consist will be travelling to next.
+ * @param capacity Capacity to add to link stat.
+ * @param usage Usage to add to link stat. If UINT_MAX refresh the link instead of increasing.
+ */
+void IncreaseStats(Station *st, CargoID cargo, StationID next_station_id, uint capacity, uint usage)
+{
+	GoodsEntry &ge1 = st->goods[cargo];
+	Station *st2 = Station::Get(next_station_id);
+	GoodsEntry &ge2 = st2->goods[cargo];
+	LinkGraph *lg = NULL;
+	if (ge1.link_graph == INVALID_LINK_GRAPH) {
+		if (ge2.link_graph == INVALID_LINK_GRAPH) {
+			if (LinkGraph::CanAllocateItem()) {
+				lg = new LinkGraph(cargo);
+				ge2.link_graph = lg->index;
+				ge2.node = lg->AddNode(st2);
+			} else {
+				DEBUG(misc, 0, "Can't allocate link graph");
+			}
+		} else {
+			lg = LinkGraph::Get(ge2.link_graph);
+		}
+		if (lg) {
+			ge1.link_graph = lg->index;
+			ge1.node = lg->AddNode(st);
+		}
+	} else if (ge2.link_graph == INVALID_LINK_GRAPH) {
+		lg = LinkGraph::Get(ge1.link_graph);
+		ge2.link_graph = lg->index;
+		ge2.node = lg->AddNode(st2);
+	} else {
+		lg = LinkGraph::Get(ge1.link_graph);
+		if (ge1.link_graph != ge2.link_graph) {
+			LinkGraph *lg2 = LinkGraph::Get(ge2.link_graph);
+			if (lg->Size() < lg2->Size()) {
+				lg2->Merge(lg); // Updates GoodsEntries of lg
+				lg = lg2;
+			} else {
+				lg->Merge(lg2); // Updates GoodsEntries of lg2
+			}
+		}
+	}
+	if (lg != NULL) {
+		(*lg)[ge1.node].UpdateEdge(ge2.node, capacity, usage);
+	}
+}
+
+/**
+ * Increase capacity for all link stats associated with vehicles in the given consist.
+ * @param st Station to get the link stats from.
+ * @param front First vehicle in the consist.
+ * @param next_station_id Station the consist will be travelling to next.
+ */
+void IncreaseStats(Station *st, const Vehicle *front, StationID next_station_id)
+{
+	for (const Vehicle *v = front; v != NULL; v = v->Next()) {
+		if (v->refit_cap > 0) {
+			/* The cargo count can indeed be higher than the refit_cap if
+			 * wagons have been auto-replaced and subsequently auto-
+			 * refitted to a higher capacity. The cargo gets redistributed
+			 * among the wagons in that case.
+			 * As usage is not such an important figure anyway we just
+			 * ignore the additional cargo then.*/
+			IncreaseStats(st, v->cargo_type, next_station_id, v->refit_cap,
+				min(v->refit_cap, v->cargo.StoredCount()));
+		}
+	}
+}
+
 /* called for every station each tick */
 static void StationHandleSmallTick(BaseStation *st)
 {
@@ -3421,6 +3499,19 @@ static uint UpdateStationWaiting(Station *st, CargoID type, uint amount, SourceT
 	if (amount == 0) return 0;
 
 	ge.cargo.Append(new CargoPacket(st->index, st->xy, amount, source_type, source_id));
+	LinkGraph *lg = NULL;
+	if (ge.link_graph == INVALID_LINK_GRAPH) {
+		if (LinkGraph::CanAllocateItem()) {
+			lg = new LinkGraph(type);
+			ge.link_graph = lg->index;
+			ge.node = lg->AddNode(st);
+		} else {
+			DEBUG(misc, 0, "Can't allocate link graph");
+		}
+	} else {
+		lg = LinkGraph::Get(ge.link_graph);
+	}
+	if (lg != NULL) (*lg)[ge.node].UpdateSupply(amount);
 
 	if (!ge.HasRating()) {
 		InvalidateWindowData(WC_STATION_LIST, st->index);
diff --git a/src/station_func.h b/src/station_func.h
index 000bd19ba..8efa3c2f1 100644
--- a/src/station_func.h
+++ b/src/station_func.h
@@ -15,6 +15,7 @@
 #include "sprite.h"
 #include "rail_type.h"
 #include "road_type.h"
+#include "vehicle_type.h"
 #include "economy_func.h"
 #include "rail.h"
 
@@ -47,6 +48,9 @@ void UpdateAirportsNoise();
 
 bool SplitGroundSpriteForOverlay(const TileInfo *ti, SpriteID *ground, RailTrackOffset *overlay_offset);
 
+void IncreaseStats(Station *st, const Vehicle *v, StationID next_station_id);
+void IncreaseStats(Station *st, CargoID cargo, StationID next_station_id, uint capacity, uint usage);
+
 /**
  * Calculates the maintenance cost of a number of station tiles.
  * @param num Number of station tiles.
diff --git a/src/train_cmd.cpp b/src/train_cmd.cpp
index b3144207f..b8ed5596b 100644
--- a/src/train_cmd.cpp
+++ b/src/train_cmd.cpp
@@ -200,7 +200,9 @@ void Train::ConsistChanged(bool same_length)
 			}
 		}
 
-		u->cargo_cap = e_u->DetermineCapacity(u);
+		uint16 new_cap = e_u->DetermineCapacity(u);
+		u->refit_cap = min(new_cap, u->refit_cap);
+		u->cargo_cap = new_cap;
 		u->vcache.cached_cargo_age_period = GetVehicleProperty(u, PROP_TRAIN_CARGO_AGE_PERIOD, e_u->info.cargo_age_period);
 
 		/* check the vehicle length (callback) */
@@ -606,6 +608,7 @@ static CommandCost CmdBuildRailWagon(TileIndex tile, DoCommandFlag flags, const
 
 		v->cargo_type = e->GetDefaultCargoType();
 		v->cargo_cap = rvi->capacity;
+		v->refit_cap = 0;
 
 		v->railtype = rvi->railtype;
 
@@ -673,6 +676,7 @@ static void AddRearEngineToMultiheadedTrain(Train *v)
 	u->cargo_type = v->cargo_type;
 	u->cargo_subtype = v->cargo_subtype;
 	u->cargo_cap = v->cargo_cap;
+	u->refit_cap = v->refit_cap;
 	u->railtype = v->railtype;
 	u->engine_type = v->engine_type;
 	u->build_year = v->build_year;
@@ -725,7 +729,9 @@ CommandCost CmdBuildRailVehicle(TileIndex tile, DoCommandFlag flags, const Engin
 		v->spritenum = rvi->image_index;
 		v->cargo_type = e->GetDefaultCargoType();
 		v->cargo_cap = rvi->capacity;
+		v->refit_cap = 0;
 		v->last_station_visited = INVALID_STATION;
+		v->last_loading_station = INVALID_STATION;
 
 		v->engine_type = e->index;
 		v->gcache.first_engine = INVALID_ENGINE; // needs to be set before first callback
diff --git a/src/vehicle.cpp b/src/vehicle.cpp
index b209092fb..1a50a0241 100644
--- a/src/vehicle.cpp
+++ b/src/vehicle.cpp
@@ -2002,6 +2002,13 @@ void Vehicle::BeginLoading()
 
 	Station::Get(this->last_station_visited)->loading_vehicles.push_back(this);
 
+	if (this->last_loading_station != INVALID_STATION &&
+			this->last_loading_station != this->last_station_visited &&
+			((this->current_order.GetLoadType() & OLFB_NO_LOAD) == 0 ||
+			(this->current_order.GetUnloadType() & OUFB_NO_UNLOAD) == 0)) {
+		IncreaseStats(Station::Get(this->last_loading_station), this, this->last_station_visited);
+	}
+
 	PrepareUnload(this);
 
 	SetWindowDirty(GetWindowClassForVehicleType(this->type), this->owner);
@@ -2043,6 +2050,23 @@ void Vehicle::LeaveStation()
 	/* Only update the timetable if the vehicle was supposed to stop here. */
 	if (this->current_order.GetNonStopType() != ONSF_STOP_EVERYWHERE) UpdateVehicleTimetable(this, false);
 
+	if ((this->current_order.GetLoadType() & OLFB_NO_LOAD) == 0 ||
+			(this->current_order.GetUnloadType() & OUFB_NO_UNLOAD) == 0) {
+		if (this->current_order.CanLeaveWithCargo(this->last_loading_station != INVALID_STATION)) {
+			/* Refresh next hop stats to make sure we've done that at least once
+			 * during the stop and that refit_cap == cargo_cap for each vehicle in
+			 * the consist. */
+			this->RefreshNextHopsStats();
+
+			/* if the vehicle could load here or could stop with cargo loaded set the last loading station */
+			this->last_loading_station = this->last_station_visited;
+		} else {
+			/* if the vehicle couldn't load and had to unload or transfer everything
+			 * set the last loading station to invalid as it will leave empty. */
+			this->last_loading_station = INVALID_STATION;
+		}
+	}
+
 	this->current_order.MakeLeaveStation();
 	Station *st = Station::Get(this->last_station_visited);
 	this->CancelReservation(st);
@@ -2061,6 +2085,116 @@ void Vehicle::LeaveStation()
 	}
 }
 
+/**
+ * Predict a vehicle's course from its current state and refresh all links it
+ * will visit. As a side effect reset the refit_cap of all vehicles in the
+ * consist to the cargo_cap. This method is expected to be called when loading
+ * at a station so it's safe to do so.
+ */
+void Vehicle::RefreshNextHopsStats()
+{
+	/* Assemble list of capacities and set last loading stations to 0. */
+	SmallMap<CargoID, uint, 1> capacities;
+	for (Vehicle *v = this; v != NULL; v = v->Next()) {
+		v->refit_cap = v->cargo_cap;
+		if (v->refit_cap == 0) continue;
+
+		SmallPair<CargoID, uint> *i = capacities.Find(v->cargo_type);
+		if (i == capacities.End()) {
+			/* Braindead smallmap not providing a good method for that...
+			 * capacities[v->cargo_type] += v->cargo_cap won't do as that just
+			 * allocates the memory, but doesn't initialize it if the key isn't
+			 * there, yet. So we still have to check if the key exists and that
+			 * is best done with Find(). */
+			i = capacities.Append();
+			i->first = v->cargo_type;
+			i->second = v->refit_cap;
+		} else {
+			i->second += v->refit_cap;
+		}
+	}
+
+	/* If orders were deleted while loading, we're done here.*/
+	if (this->orders.list == NULL) return;
+
+	uint hops = 0;
+	const Order *first = this->GetOrder(this->cur_implicit_order_index);
+	do {
+		/* Make sure the first order is a station order. */
+		first = this->orders.list->GetNextStoppingOrder(this, first, hops++);
+		if (first == NULL) return;
+	} while (!first->IsType(OT_GOTO_STATION));
+	hops = 0;
+
+	const Order *cur = first;
+	const Order *next = first;
+	while (next != NULL && cur->CanLeaveWithCargo(true)) {
+		next = this->orders.list->GetNextStoppingOrder(this,
+				this->orders.list->GetNext(next), ++hops);
+		if (next == NULL) break;
+
+		/* If the refit cargo is CT_AUTO_REFIT, we're optimistic and assume the
+		 * cargo will stay the same. The point of this method is to avoid
+		 * deadlocks due to vehicles waiting for cargo that isn't being routed,
+		 * yet. That situation will not occur if the vehicle is actually
+		 * carrying a different cargo in the end. */
+		if (next->IsAutoRefit() && next->GetRefitCargo() != CT_AUTO_REFIT) {
+			/* Handle refit by dropping some vehicles. */
+			CargoID new_cid = next->GetRefitCargo();
+			for (Vehicle *v = this; v != NULL; v = v->Next()) {
+				const Engine *e = Engine::Get(v->engine_type);
+				if (!HasBit(e->info.refit_mask, new_cid)) continue;
+
+				/* Back up the vehicle's cargo type */
+				CargoID temp_cid = v->cargo_type;
+				byte temp_subtype = v->cargo_subtype;
+				v->cargo_type = new_cid;
+				v->cargo_subtype = GetBestFittingSubType(v, v, new_cid);
+
+				uint16 mail_capacity = 0;
+				uint amount = e->DetermineCapacity(v, &mail_capacity);
+
+				/* Restore the original cargo type */
+				v->cargo_type = temp_cid;
+				v->cargo_subtype = temp_subtype;
+
+				/* Skip on next refit. */
+				if (new_cid != v->cargo_type && v->refit_cap > 0) {
+					capacities[v->cargo_type] -= v->refit_cap;
+					v->refit_cap = 0;
+				} else if (amount < v->refit_cap) {
+					capacities[v->cargo_type] -= v->refit_cap - amount;
+					v->refit_cap = amount;
+				}
+
+				/* Special case for aircraft with mail. */
+				if (v->type == VEH_AIRCRAFT) {
+					Vehicle *u = v->Next();
+					if (mail_capacity < u->refit_cap) {
+						capacities[u->cargo_type] -= u->refit_cap - mail_capacity;
+						u->refit_cap = mail_capacity;
+					}
+					break; // aircraft have only one vehicle
+				}
+			}
+		}
+
+		if (next->IsType(OT_GOTO_STATION)) {
+			StationID next_station = next->GetDestination();
+			Station *st = Station::GetIfValid(cur->GetDestination());
+			if (st != NULL && next_station != INVALID_STATION && next_station != st->index) {
+				for (const SmallPair<CargoID, uint> *i = capacities.Begin(); i != capacities.End(); ++i) {
+					/* Refresh the link and give it a minimum capacity. */
+					if (i->second > 0) IncreaseStats(st, i->first, next_station, i->second, UINT_MAX);
+				}
+			}
+			cur = next;
+			if (cur == first) break;
+		}
+	}
+
+	for (Vehicle *v = this; v != NULL; v = v->Next()) v->refit_cap = v->cargo_cap;
+}
 
 /**
  * Handle the loading of the vehicle; when not it skips through dummy
@@ -2099,6 +2233,34 @@ void Vehicle::HandleLoading(bool mode)
 }
 
 /**
+ * Get a map of cargoes and free capacities in the consist.
+ * @param capacities Map to be filled with cargoes and capacities.
+ */
+void Vehicle::GetConsistFreeCapacities(SmallMap<CargoID, uint> &capacities) const
+{
+	for (const Vehicle *v = this; v != NULL; v = v->Next()) {
+		if (v->cargo_cap == 0) continue;
+		SmallPair<CargoID, uint> *pair = capacities.Find(v->cargo_type);
+		if (pair == capacities.End()) {
+			pair = capacities.Append();
+			pair->first = v->cargo_type;
+			pair->second = v->cargo_cap - v->cargo.StoredCount();
+		} else {
+			pair->second += v->cargo_cap - v->cargo.StoredCount();
+		}
+	}
+}
+
+uint Vehicle::GetConsistTotalCapacity() const
+{
+	uint result = 0;
+	for (const Vehicle *v = this; v != NULL; v = v->Next()) {
+		result += v->cargo_cap;
+	}
+	return result;
+}
+
+/**
  * Send this vehicle to the depot using the given command(s).
  * @param flags   the command flags (like execute and such).
  * @param command the command to execute.
diff --git a/src/vehicle_base.h b/src/vehicle_base.h
index 7b40d4819..62fcb24ab 100644
--- a/src/vehicle_base.h
+++ b/src/vehicle_base.h
@@ -12,6 +12,7 @@
 #ifndef VEHICLE_BASE_H
 #define VEHICLE_BASE_H
 
+#include "core/smallmap_type.hpp"
 #include "track_type.h"
 #include "command_type.h"
 #include "order_base.h"
@@ -211,10 +212,12 @@ public:
 	byte waiting_triggers;              ///< Triggers to be yet matched before rerandomizing the random bits.
 
 	StationID last_station_visited;     ///< The last station we stopped at.
+	StationID last_loading_station;     ///< Last station the vehicle has stopped at and could possibly leave from with any cargo loaded.
 
 	CargoID cargo_type;                 ///< type of cargo this vehicle is carrying
 	byte cargo_subtype;                 ///< Used for livery refits (NewGRF variations)
 	uint16 cargo_cap;                   ///< total capacity
+	uint16 refit_cap;                   ///< Capacity left over from before last refit.
 	VehicleCargoList cargo;             ///< The cargo this vehicle is carrying
 	uint16 cargo_age_counter;           ///< Ticks till cargo is aged next.
 
@@ -257,6 +260,10 @@ public:
 
 	void HandleLoading(bool mode = false);
 
+	void GetConsistFreeCapacities(SmallMap<CargoID, uint> &capacities) const;
+
+	uint GetConsistTotalCapacity() const;
+
 	/**
 	 * Marks the vehicles to be redrawn and updates cached variables
 	 *
@@ -598,6 +605,17 @@ public:
 	inline VehicleOrderID GetNumManualOrders() const { return (this->orders.list == NULL) ? 0 : this->orders.list->GetNumManualOrders(); }
 
 	/**
+	 * Get the next station the vehicle will stop at.
+	 * @return ID of the next station the vehicle will stop at or INVALID_STATION.
+	 */
+	inline StationID GetNextStoppingStation() const
+	{
+		return (this->orders.list == NULL) ? INVALID_STATION : this->orders.list->GetNextStoppingStation(this);
+	}
+
+	void RefreshNextHopsStats();
+
+	/**
 	 * Copy certain configurations and statistics of a vehicle after successful autoreplace/renew
 	 * The function shall copy everything that cannot be copied by a command (like orders / group etc),
 	 * and that shall not be resetted for the new vehicle.
diff --git a/src/vehicle_cmd.cpp b/src/vehicle_cmd.cpp
index 7cdb4eb49..a7e2f305b 100644
--- a/src/vehicle_cmd.cpp
+++ b/src/vehicle_cmd.cpp
@@ -397,20 +397,16 @@ static CommandCost RefitVehicle(Vehicle *v, bool only_this, uint8 num_vehicles,
 		/* Store the result */
 		for (RefitResult *result = refit_result.Begin(); result != refit_result.End(); result++) {
 			Vehicle *u = result->v;
-			if (u->cargo_type != new_cid) {
-				u->cargo.Truncate(u->cargo_cap);
-			} else if (u->cargo_cap > result->capacity) {
-				u->cargo.Truncate(u->cargo_cap - result->capacity);
-			}
+			u->refit_cap = (u->cargo_type == new_cid) ? min(result->capacity, u->refit_cap) : 0;
+			if (u->cargo.TotalCount() > u->refit_cap) u->cargo.Truncate(u->cargo.TotalCount() - u->refit_cap);
 			u->cargo_type = new_cid;
 			u->cargo_cap = result->capacity;
 			u->cargo_subtype = result->subtype;
 			if (u->type == VEH_AIRCRAFT) {
 				Vehicle *w = u->Next();
-				if (w->cargo_cap > result->mail_capacity) {
-					w->cargo.Truncate(w->cargo_cap - result->mail_capacity);
-				}
+				w->refit_cap = min(w->refit_cap, result->mail_capacity);
 				w->cargo_cap = result->mail_capacity;
+				if (w->cargo.TotalCount() > w->refit_cap) w->cargo.Truncate(w->cargo.TotalCount() - w->refit_cap);
 			}
 		}
 	}