path: root/src/cargodest.cpp

/* $Id$ */

/*
 * This file is part of OpenTTD.
 * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
 * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
 */

/** @file cargodest.cpp Implementation of cargo destinations. */

#include "stdafx.h"
#include "cargodest_type.h"
#include "cargodest_base.h"
#include "cargodest_func.h"
#include "core/bitmath_func.hpp"
#include "core/random_func.hpp"
#include "core/pool_func.hpp"
#include "cargotype.h"
#include "settings_type.h"
#include "town.h"
#include "industry.h"
#include "window_func.h"
#include "vehicle_base.h"
#include "station_base.h"
#include "pathfinder/yapf/yapf.h"
#include "company_base.h"


/* Possible link weight modifiers. */
static const byte LWM_ANYWHERE      = 1; ///< Weight modifier for undetermined destinations.
static const byte LWM_TONY_ANY      = 2; ///< Default weight modifier for towns.
static const byte LWM_TONY_BIG      = 3; ///< Weight modifier for big towns.
static const byte LWM_TONY_CITY     = 4; ///< Weight modifier for cities.
static const byte LWM_TONY_NEARBY   = 5; ///< Weight modifier for nearby towns.
static const byte LWM_INTOWN        = 8; ///< Weight modifier for in-town links.
static const byte LWM_IND_ANY       = 2; ///< Default weight modifier for industries.
static const byte LWM_IND_NEARBY    = 3; ///< Weight modifier for nearby industries.
static const byte LWM_IND_PRODUCING = 4; ///< Weight modifier for producing industries.

static const uint MAX_EXTRA_LINKS       = 2; ///< Number of extra links allowed.
static const uint MAX_IND_STOCKPILE     = 1000; ///< Maximum stockpile to consider for industry link weight.

static const uint BASE_TOWN_LINKS       = 0; ///< Index into _settings_game.economy.cargodest.base_town_links for normal cargo
static const uint BASE_TOWN_LINKS_SYMM  = 1; ///< Index into _settings_game.economy.cargodest.base_town_links for symmteric cargoes
static const uint BASE_IND_LINKS        = 0; ///< Index into _settings_game.economy.cargodest.base_ind_links for normal cargo
static const uint BASE_IND_LINKS_TOWN   = 1; ///< Index into _settings_game.economy.cargodest.base_ind_links for town cargoes
static const uint BASE_IND_LINKS_SYMM   = 2; ///< Index into _settings_game.economy.cargodest.base_ind_links for symmetric cargoes
static const uint BIG_TOWN_POP_MAIL     = 0; ///< Index into _settings_game.economy.cargodest.big_town_pop for mail
static const uint BIG_TOWN_POP_PAX      = 1; ///< Index into _settings_game.economy.cargodest.big_town_pop for passengers
static const uint SCALE_TOWN            = 0; ///< Index into _settings_game.economy.cargodest.pop_scale_town/weight_scale_town for normal cargo
static const uint SCALE_TOWN_BIG        = 1; ///< Index into _settings_game.economy.cargodest.pop_scale_town/weight_scale_town for normal cargo of big towns
static const uint SCALE_TOWN_PAX        = 2; ///< Index into _settings_game.economy.cargodest.pop_scale_town/weight_scale_town for passengers
static const uint SCALE_TOWN_BIG_PAX    = 3; ///< Index into _settings_game.economy.cargodest.pop_scale_town/weight_scale_town for passengers of big towns
static const uint CARGO_SCALE_IND       = 0; ///< Index into _settings_game.economy.cargodest.cargo_scale_ind for normal cargo
static const uint CARGO_SCALE_IND_TOWN  = 1; ///< Index into _settings_game.economy.cargodest.cargo_scale_ind for town cargoes
static const uint MIN_WEIGHT_TOWN       = 0; ///< Index into _settings_game.economy.cargodest.min_weight_town for normal cargo
static const uint MIN_WEIGHT_TOWN_PAX   = 1; ///< Index into _settings_game.economy.cargodest.min_weight_town for passengers
static const uint WEIGHT_SCALE_IND_PROD = 0; ///< Index into _settings_game.economy.cargodest.weight_scale_ind for produced cargo
static const uint WEIGHT_SCALE_IND_PILE = 1; ///< Index into _settings_game.economy.cargodest.weight_scale_ind for stockpiled cargo

/** Are cargo destinations for this cargo type enabled? */
bool CargoHasDestinations(CargoID cid)
{
	const CargoSpec *spec = CargoSpec::Get(cid);
	switch (spec->town_effect) {
		case TE_PASSENGERS:
		case TE_MAIL:
			return _settings_game.economy.cargodest.mode_pax_mail != CRM_OFF;

		case TE_GOODS:
		case TE_WATER:
		case TE_FOOD:
			return _settings_game.economy.cargodest.mode_town_cargo != CRM_OFF;

		default:
			return _settings_game.economy.cargodest.mode_others != CRM_OFF;
	}
}

/** Are cargo destinations for all cargo types disabled? */
bool CargoDestinationsDisabled()
{
	return _settings_game.economy.cargodest.mode_pax_mail == CRM_OFF && _settings_game.economy.cargodest.mode_town_cargo == CRM_OFF && _settings_game.economy.cargodest.mode_others == CRM_OFF;
}

/** Should this cargo type primarily have towns as a destination? */
static bool IsTownCargo(CargoID cid)
{
	const CargoSpec *spec = CargoSpec::Get(cid);
	return spec->town_effect != TE_NONE;
}

/** Does this cargo have a symmetric demand?  */
static bool IsSymmetricCargo(CargoID cid)
{
	const CargoSpec *spec = CargoSpec::Get(cid);
	return spec->town_effect == TE_PASSENGERS;
}

/** Is this a passenger cargo. */
static bool IsPassengerCargo(CargoID cid)
{
	const CargoSpec *spec = CargoSpec::Get(cid);
	return spec->town_effect == TE_PASSENGERS;
}


/** Information for the town/industry enumerators. */
struct EnumRandomData {
	CargoSourceSink *source;
	TileIndex       source_xy;
	CargoID         cid;
	bool            limit_links;
};

/**
 * Test whether two tiles are nearby with map-size scaling.
 * @param t1 First tile.
 * @param t2 Second tile.
 * @param dist_square Allowed squared distance between the tiles.
 * @return True if the tiles are nearby.
 */
static bool IsNearby(TileIndex t1, TileIndex t2, uint32 dist_square)
{
	/* Scale distance by 1D map size to make sure that there are still
	 * candidates left on larger maps with few towns, but don't scale
	 * by 2D map size so the map still feels bigger. */
	return DistanceSquare(t1, t2) < ScaleByMapSize1D(dist_square);
}

/**
 * Test whether a tiles is near a town.
 * @param t The town.
 * @param ti The tile to test.
 * @return True if the tiles is near the town.
 */
static bool IsTownNearby(const Town *t, TileIndex ti)
{
	return IsNearby(t->xy, ti, _settings_game.economy.cargodest.town_nearby_dist);
}

/**
 * Test whether a tiles is near an industry.
 * @param ind The industry.
 * @param ti The tile to test.
 * @return True if the tiles is near the town.
 */
static bool IsIndustryNearby(const Industry *ind, TileIndex ti)
{
	return IsNearby(ind->location.tile, ti, _settings_game.economy.cargodest.ind_nearby_dist);
}

/** Common helper for town/industry enumeration. */
static bool EnumAnyDest(const CargoSourceSink *dest, EnumRandomData *erd)
{
	/* Already a destination? */
	if (erd->source->HasLinkTo(erd->cid, dest)) return false;

	/* Destination already has too many links? */
	if (erd->limit_links && dest->cargo_links[erd->cid].Length() > dest->num_links_expected[erd->cid] + MAX_EXTRA_LINKS) return false;

	return true;
}

/** Enumerate any town not already a destination and accepting a specific cargo.*/
static bool EnumAnyTown(const Town *t, void *data)
{
	EnumRandomData *erd = (EnumRandomData *)data;
	return EnumAnyDest(t, erd) && t->AcceptsCargo(erd->cid);
}

/** Enumerate cities. */
static bool EnumCity(const Town *t, void *data)
{
	return EnumAnyTown(t, data) && t->larger_town;
}

/** Enumerate towns with a big population. */
static bool EnumBigTown(const Town *t, void *data)
{
	EnumRandomData *erd = (EnumRandomData *)data;
	return EnumAnyTown(t, erd) && (IsPassengerCargo(erd->cid) ? t->supplied[CT_PASSENGERS].old_max > _settings_game.economy.cargodest.big_town_pop[BIG_TOWN_POP_PAX] : t->supplied[CT_MAIL].old_max > _settings_game.economy.cargodest.big_town_pop[BIG_TOWN_POP_MAIL]);
}

/** Enumerate nearby towns. */
static bool EnumNearbyTown(const Town *t, void *data)
{
	EnumRandomData *erd = (EnumRandomData *)data;
	return EnumAnyTown(t, data) && IsTownNearby(t, erd->source_xy);
}

/** Enumerate any industry not already a destination and accepting a specific cargo. */
static bool EnumAnyIndustry(const Industry *ind, void *data)
{
	EnumRandomData *erd = (EnumRandomData *)data;
	return EnumAnyDest(ind, erd) && ind->AcceptsCargo(erd->cid);
}

/** Enumerate nearby industries. */
static bool EnumNearbyIndustry(const Industry *ind, void *data)
{
	EnumRandomData *erd = (EnumRandomData *)data;
	return EnumAnyIndustry(ind, data) && IsIndustryNearby(ind, erd->source_xy);
}

/** Enumerate industries that are producing cargo. */
static bool EnumProducingIndustry(const Industry *ind, void *data)
{
	return EnumAnyIndustry(ind, data) && (ind->produced_cargo[0] != CT_INVALID || ind->produced_cargo[1] != CT_INVALID);
}

/** Enumerate cargo sources supplying a specific cargo. */
template <typename T>
static bool EnumAnySupplier(const T *css, void *data)
{
	return css->SuppliesCargo(((EnumRandomData *)data)->cid);
}

/** Enumerate nearby cargo sources supplying a specific cargo. */
static bool EnumNearbySupplier(const Industry *ind, void *data)
{
	EnumRandomData *erd = (EnumRandomData *)data;
	return EnumAnySupplier(ind, data) && IsIndustryNearby(ind, erd->source_xy);
}

/** Enumerate nearby cargo sources supplying a specific cargo. */
static bool EnumNearbySupplier(const Town *t, void *data)
{
	EnumRandomData *erd = (EnumRandomData *)data;
	return EnumAnySupplier(t, data) && IsTownNearby(t, erd->source_xy);
}


/** Find a town as a destination. */
static CargoSourceSink *FindTownDestination(byte &weight_mod, CargoSourceSink *source, TileIndex source_xy, CargoID cid, const uint8 destclass_chance[4], TownID skip = INVALID_TOWN)
{
	/* Enum functions for: nearby town, city, big town, and any town. */
	static const Town::EnumTownProc destclass_enum[] = {
		&EnumNearbyTown, &EnumCity, &EnumBigTown, &EnumAnyTown
	};
	static const byte weight_mods[] = {LWM_TONY_NEARBY, LWM_TONY_CITY, LWM_TONY_BIG, LWM_TONY_ANY};
	assert_compile(lengthof(destclass_enum) == lengthof(weight_mods));

	EnumRandomData erd = {source, source_xy, cid, IsSymmetricCargo(cid)};

	/* Determine destination class. If no town is found in this class,
	 * the search falls through to the following classes. */
	byte destclass = RandomRange(destclass_chance[3]);

	weight_mod = LWM_ANYWHERE;
	Town *dest = NULL;
	for (uint i = 0; i < lengthof(destclass_enum) && dest == NULL; i++) {
		/* Skip if destination class not reached. */
		if (destclass > destclass_chance[i]) continue;

		dest = Town::GetRandom(destclass_enum[i], skip, &erd);
		weight_mod = weight_mods[i];
	}

	return dest;
}

/** Find an industry as a destination. */
static CargoSourceSink *FindIndustryDestination(byte &weight_mod, CargoSourceSink *source, TileIndex source_xy, CargoID cid, IndustryID skip = INVALID_INDUSTRY)
{
	/* Enum functions for: nearby industry, producing industry, and any industry. */
	static const Industry::EnumIndustryProc destclass_enum[] = {
		&EnumNearbyIndustry, &EnumProducingIndustry, &EnumAnyIndustry
	};
	static const byte weight_mods[] = {LWM_IND_NEARBY, LWM_IND_PRODUCING, LWM_IND_ANY};
	assert_compile(lengthof(destclass_enum) == lengthof(_settings_game.economy.cargodest.ind_chances));

	EnumRandomData erd = {source, source_xy, cid, IsSymmetricCargo(cid)};

	/* Determine destination class. If no industry is found in this class,
	 * the search falls through to the following classes. */
	byte destclass = RandomRange(*lastof(_settings_game.economy.cargodest.ind_chances));

	weight_mod = LWM_ANYWHERE;
	Industry *dest = NULL;
	for (uint i = 0; i < lengthof(destclass_enum) && dest == NULL; i++) {
		/* Skip if destination class not reached. */
		if (destclass > _settings_game.economy.cargodest.ind_chances[i]) continue;

		dest = Industry::GetRandom(destclass_enum[i], skip, &erd);
		weight_mod = weight_mods[i];
	}

	return dest;
}

/** Find a supply for a cargo type. */
static CargoSourceSink *FindSupplySource(Industry *dest, CargoID cid)
{
	EnumRandomData erd = {dest, dest->location.tile, cid, false};

	CargoSourceSink *source = NULL;

	/* Even chance for industry source first, town second and vice versa.
	 * Try a nearby supplier first, then check all suppliers. */
	if (Chance16(1, 2)) {
		source = Industry::GetRandom(&EnumNearbySupplier, dest->index, &erd);
		if (source == NULL) source = Town::GetRandom(&EnumNearbySupplier, INVALID_TOWN, &erd);
		if (source == NULL) source = Industry::GetRandom(&EnumAnySupplier, dest->index, &erd);
		if (source == NULL) source = Town::GetRandom(&EnumAnySupplier, INVALID_TOWN, &erd);
	} else {
		source = Town::GetRandom(&EnumNearbySupplier, INVALID_TOWN, &erd);
		if (source == NULL) source = Industry::GetRandom(&EnumNearbySupplier, dest->index, &erd);
		if (source == NULL) source = Town::GetRandom(&EnumAnySupplier, INVALID_TOWN, &erd);
		if (source == NULL) source = Industry::GetRandom(&EnumAnySupplier, dest->index, &erd);
	}

	return source;
}

/* virtual */ void CargoSourceSink::CreateSpecialLinks(CargoID cid)
{
	/* First link is for undetermined destinations. */
	if (this->cargo_links[cid].Length() == 0) {
		*this->cargo_links[cid].Append() = CargoLink(NULL, LWM_ANYWHERE);
	}
	if (this->cargo_links[cid].Get(0)->dest != NULL) {
		/* Insert link at first place. */
		*this->cargo_links[cid].Append() = *this->cargo_links[cid].Get(0);
		*this->cargo_links[cid].Get(0) = CargoLink(NULL, LWM_ANYWHERE);
	}
}

/* virtual */ void Town::CreateSpecialLinks(CargoID cid)
{
	CargoSourceSink::CreateSpecialLinks(cid);

	if (this->AcceptsCargo(cid)) {
		/* Add special link for town-local demand if not already present. */
		if (this->cargo_links[cid].Length() < 2) *this->cargo_links[cid].Append() = CargoLink(this, LWM_INTOWN);
		if (this->cargo_links[cid].Get(1)->dest != this) {
			/* Insert link at second place. */
			*this->cargo_links[cid].Append() = *this->cargo_links[cid].Get(1);
			*this->cargo_links[cid].Get(1) = CargoLink(this, LWM_INTOWN);
		}
	} else {
		/* Remove link for town-local demand if present. */
		if (this->cargo_links[cid].Length() > 1 && this->cargo_links[cid].Get(1)->dest == this) {
			this->cargo_links[cid].Erase(this->cargo_links[cid].Get(1));
		}
	}
}

/**
 * Remove the link with the lowest weight from a cargo source. The
 * reverse link is removed as well if the cargo has symmetric demand.
 * @param source Remove the link from this cargo source.
 * @param cid Cargo type of the link to remove.
 */
static void RemoveLowestLink(CargoSourceSink *source, CargoID cid)
{
	uint lowest_weight = UINT_MAX;
	CargoLink *lowest_link = NULL;

	for (CargoLink *l = source->cargo_links[cid].Begin(); l != source->cargo_links[cid].End(); l++) {
		/* Don't remove special links. */
		if (l->dest == NULL || l->dest == source) continue;

		if (l->weight < lowest_weight) {
			lowest_weight = l->weight;
			lowest_link = l;
		}
	}

	if (lowest_link != NULL) {
		/* If this is a symmetric cargo, also remove the reverse link. */
		if (IsSymmetricCargo(cid) && lowest_link->dest->HasLinkTo(cid, source)) {
			source->num_incoming_links[cid]--;
			lowest_link->dest->cargo_links[cid].Erase(lowest_link->dest->cargo_links[cid].Find(CargoLink(source, LWM_ANYWHERE)));
		}
		lowest_link->dest->num_incoming_links[cid]--;
		source->cargo_links[cid].Erase(lowest_link);
	}
}

/** Create missing cargo links for a source. */
static void CreateNewLinks(CargoSourceSink *source, TileIndex source_xy, CargoID cid, uint chance_a, uint chance_b, const uint8 town_chance[], TownID skip_town, IndustryID skip_ind)
{
	uint num_links = source->num_links_expected[cid];

	/* Remove the link with the lowest weight if the
	 * town has more than links more than expected. */
	if (source->cargo_links[cid].Length() > num_links + MAX_EXTRA_LINKS) {
		RemoveLowestLink(source, cid);
	}

	/* Add new links until the expected link count is reached. */
	while (source->cargo_links[cid].Length() < num_links) {
		CargoSourceSink *dest = NULL;
		byte weight_mod = LWM_ANYWHERE;

		/* Chance for town/industry is chance_a/chance_b, otherwise try industry/town. */
		if (Chance16(chance_a, chance_b)) {
			dest = FindTownDestination(weight_mod, source, source_xy, cid, town_chance, skip_town);
			/* No town found? Try an industry. */
			if (dest == NULL) dest = FindIndustryDestination(weight_mod, source, source_xy, cid, skip_ind);
		} else {
			dest = FindIndustryDestination(weight_mod, source, source_xy, cid, skip_ind);
			/* No industry found? Try a town. */
			if (dest == NULL) dest = FindTownDestination(weight_mod, source, source_xy, cid, town_chance, skip_town);
		}

		/* If we didn't find a destination, break out of the loop because no
		 * more destinations are left on the map. */
		if (dest == NULL) break;

		/* If this is a symmetric cargo and we accept it as well, create a back link. */
		if (IsSymmetricCargo(cid) && dest->SuppliesCargo(cid) && source->AcceptsCargo(cid)) {
			*dest->cargo_links[cid].Append() = CargoLink(source, weight_mod);
			source->num_incoming_links[cid]++;
		}

		*source->cargo_links[cid].Append() = CargoLink(dest, weight_mod);
		dest->num_incoming_links[cid]++;
	}
}

/** Remove invalid links from a cargo source/sink. */
static void RemoveInvalidLinks(CargoSourceSink *css)
{
	for (CargoID cid = 0; cid < NUM_CARGO; cid++) {
		/* Remove outgoing links if cargo isn't supplied anymore. */
		if (!css->SuppliesCargo(cid)) {
			for (CargoLink *l = css->cargo_links[cid].Begin(); l != css->cargo_links[cid].End(); l++) {
				if (l->dest != NULL && l->dest != css) l->dest->num_incoming_links[cid]--;
			}
			css->cargo_links[cid].Clear();
			css->cargo_links_weight[cid] = 0;
		}

		/* Remove outgoing links if the dest doesn't accept the cargo anymore. */
		for (CargoLink *l = css->cargo_links[cid].Begin(); l != css->cargo_links[cid].End(); ) {
			if (l->dest != NULL && !l->dest->AcceptsCargo(cid)) {
				if (l->dest != css) l->dest->num_incoming_links[cid]--;
				css->cargo_links[cid].Erase(l);
			} else {
				l++;
			}
		}
	}
}

/** Updated the desired link count for each cargo. */
void UpdateExpectedLinks(Town *t)
{
	CargoID cid;

	FOR_EACH_SET_CARGO_ID(cid, t->cargo_produced) {
		if (CargoHasDestinations(cid)) {
			t->CreateSpecialLinks(cid);

			uint max_amt = IsPassengerCargo(cid) ? t->supplied[CT_PASSENGERS].old_max : t->supplied[CT_MAIL].old_max;
			uint big_amt = _settings_game.economy.cargodest.big_town_pop[IsPassengerCargo(cid) ? BIG_TOWN_POP_PAX : BIG_TOWN_POP_MAIL];

			uint num_links = _settings_game.economy.cargodest.base_town_links[IsSymmetricCargo(cid) ? BASE_TOWN_LINKS_SYMM : BASE_TOWN_LINKS];
			/* Add links based on the available cargo amount. */
			num_links += min(max_amt, big_amt) / _settings_game.economy.cargodest.pop_scale_town[IsPassengerCargo(cid) ? SCALE_TOWN_PAX : SCALE_TOWN];
			if (max_amt > big_amt) num_links += (max_amt - big_amt) / _settings_game.economy.cargodest.pop_scale_town[IsPassengerCargo(cid) ? SCALE_TOWN_BIG_PAX : SCALE_TOWN_BIG];
			/* Ensure a city has at least city_town_links more than the base value.
			 * This improves the link distribution at the beginning of a game when
			 * the towns are still small. */
			if (t->larger_town) num_links = max<uint>(num_links, _settings_game.economy.cargodest.city_town_links + _settings_game.economy.cargodest.base_town_links[IsSymmetricCargo(cid) ? BASE_TOWN_LINKS_SYMM : BASE_TOWN_LINKS]);

			/* Account for the two special links. */
			num_links++;
			if (t->cargo_links[cid].Length() > 1 && t->cargo_links[cid].Get(1)->dest == t) num_links++;

			t->num_links_expected[cid] = ClampToU16(num_links);
		}
	}
}

/** Updated the desired link count for each cargo. */
void UpdateExpectedLinks(Industry *ind)
{
	for (uint i = 0; i < lengthof(ind->produced_cargo); i++) {
		CargoID cid = ind->produced_cargo[i];
		if (cid == INVALID_CARGO) continue;

		if (CargoHasDestinations(cid)) {
			ind->CreateSpecialLinks(cid);

			uint num_links;
			/* Use different base values for symmetric cargoes, cargoes
			 * with a town effect and all other cargoes. */
			num_links = _settings_game.economy.cargodest.base_ind_links[IsSymmetricCargo(cid) ? BASE_IND_LINKS_SYMM : (IsTownCargo(cid) ? BASE_IND_LINKS_TOWN : BASE_IND_LINKS)];
			/* Add links based on the average industry production. */
			num_links += ind->average_production[i] / _settings_game.economy.cargodest.cargo_scale_ind[IsTownCargo(cid) ? CARGO_SCALE_IND_TOWN : CARGO_SCALE_IND];

			/* Account for the one special link. */
			num_links++;

			ind->num_links_expected[cid] = ClampToU16(num_links);
		}
	}
}

/** Make sure an industry has at least one incoming link for each accepted cargo. */
void AddMissingIndustryLinks(Industry *ind)
{
	for (uint i = 0; i < lengthof(ind->accepts_cargo); i++) {
		CargoID cid = ind->accepts_cargo[i];
		if (cid == INVALID_CARGO) continue;

		/* Do we already have at least one cargo source? */
		if (ind->num_incoming_links[cid] > 0) continue;

		CargoSourceSink *source = FindSupplySource(ind, cid);
		if (source == NULL) continue; // Too bad...

		if (source->cargo_links[cid].Length() >= source->num_links_expected[cid] + MAX_EXTRA_LINKS) {
			/* Increase the expected link count if adding another link would
			 * exceed the count, as otherwise this (or another) link would
			 * get removed right again. */
			source->num_links_expected[cid]++;
		}

		*source->cargo_links[cid].Append() = CargoLink(ind, LWM_IND_ANY);
		ind->num_incoming_links[cid]++;

		/* If this is a symmetric cargo and we produce it as well, create a back link. */
		if (IsSymmetricCargo(cid) && ind->SuppliesCargo(cid) && source->AcceptsCargo(cid)) {
			*ind->cargo_links[cid].Append() = CargoLink(source, LWM_IND_ANY);
			source->num_incoming_links[cid]++;
		}
	}
}

/** Update the demand links. */
void UpdateCargoLinks(Town *t)
{
	CargoID cid;

	FOR_EACH_SET_CARGO_ID(cid, t->cargo_produced) {
		if (CargoHasDestinations(cid)) {
			/* If this is a town cargo, 95% chance for town/industry destination and
			 * 5% for industry/town. The reverse chance otherwise. */
			CreateNewLinks(t, t->xy, cid, IsTownCargo(cid) ? 19 : 1, 20, t->larger_town ? _settings_game.economy.cargodest.town_chances_city : _settings_game.economy.cargodest.town_chances_town, t->index, INVALID_INDUSTRY);
		}
	}
}

/** Update the demand links. */
void UpdateCargoLinks(Industry *ind)
{
	for (uint i = 0; i < lengthof(ind->produced_cargo); i++) {
		CargoID cid = ind->produced_cargo[i];
		if (cid == INVALID_CARGO) continue;

		if (CargoHasDestinations(cid)) {
			/* If this is a town cargo, 75% chance for town/industry destination and
			 * 25% for industry/town. The reverse chance otherwise. */
			CreateNewLinks(ind, ind->location.tile, cid, IsTownCargo(cid) ? 3 : 1, 4, _settings_game.economy.cargodest.town_chances_town, INVALID_TOWN, ind->index);
		}
	}
}

/* virtual */ uint Town::GetDestinationWeight(CargoID cid, byte weight_mod) const
{
	uint max_amt = IsPassengerCargo(cid) ? this->supplied[CT_PASSENGERS].old_max : this->supplied[CT_PASSENGERS].old_max;
	uint big_amt = _settings_game.economy.cargodest.big_town_pop[IsPassengerCargo(cid) ? BIG_TOWN_POP_PAX : BIG_TOWN_POP_MAIL];

	/* The weight is calculated by a piecewise function. We start with a predefined
	 * minimum weight and then add the weight for the cargo amount up to the big
	 * town amount. If the amount is more than the big town amount, this is also
	 * added to the weight with a different scale factor to make sure that big towns
	 * don't siphon the cargo away too much from the smaller destinations. */
	uint weight = _settings_game.economy.cargodest.min_weight_town[IsPassengerCargo(cid) ? MIN_WEIGHT_TOWN_PAX : MIN_WEIGHT_TOWN];
	weight += min(max_amt, big_amt) * weight_mod / _settings_game.economy.cargodest.weight_scale_town[IsPassengerCargo(cid) ? SCALE_TOWN_PAX : SCALE_TOWN];
	if (max_amt > big_amt) weight += (max_amt - big_amt) * weight_mod / _settings_game.economy.cargodest.weight_scale_town[IsPassengerCargo(cid) ? SCALE_TOWN_BIG_PAX : SCALE_TOWN_BIG];

	return weight;
}

/* virtual */ uint Industry::GetDestinationWeight(CargoID cid, byte weight_mod) const
{
	uint weight = _settings_game.economy.cargodest.min_weight_ind;

	for (uint i = 0; i < lengthof(this->accepts_cargo); i++) {
		if (this->accepts_cargo[i] != cid) continue;
		/* Empty stockpile means more weight for the link. Stockpiles
		 * above a fixed maximum have no further effect. */
		uint stockpile = ClampU(this->incoming_cargo_waiting[i], 0, MAX_IND_STOCKPILE);
		weight += (MAX_IND_STOCKPILE - stockpile) * weight_mod / _settings_game.economy.cargodest.weight_scale_ind[WEIGHT_SCALE_IND_PILE];
	}

	/* Add a weight for the produced cargo. Use the average production
	 * here so the weight isn't fluctuating that much when the input
	 * cargo isn't delivered regularly. */
	weight += (this->average_production[0] + this->average_production[1]) * weight_mod / _settings_game.economy.cargodest.weight_scale_ind[WEIGHT_SCALE_IND_PROD];

	return weight;
}

/** Recalculate the link weights. */
void UpdateLinkWeights(Town *t)
{
	for (CargoID cid = 0; cid < NUM_CARGO; cid++) {
		uint weight_sum = 0;

		if (t->cargo_links[cid].Length() == 0) continue;

		t->cargo_links[cid].Begin()->amount.NewMonth();

		/* Skip the special link for undetermined destinations. */
		for (CargoLink *l = t->cargo_links[cid].Begin() + 1; l != t->cargo_links[cid].End(); l++) {
			l->weight = l->dest->GetDestinationWeight(cid, l->weight_mod);
			weight_sum += l->weight;

			l->amount.NewMonth();
		}

		/* Limit the weight of the in-town link to at most 1/3 of the total weight. */
		if (t->cargo_links[cid].Length() > 1 && t->cargo_links[cid].Get(1)->dest == t) {
			uint new_weight = min(t->cargo_links[cid].Get(1)->weight, weight_sum / 3);
			weight_sum -= t->cargo_links[cid].Get(1)->weight - new_weight;
			t->cargo_links[cid].Get(1)->weight = new_weight;
		}

		/* Set weight for the undetermined destination link to random_dest_chance%. */
		t->cargo_links[cid].Begin()->weight = weight_sum == 0 ? 1 : (weight_sum * _settings_game.economy.cargodest.random_dest_chance) / (100 - _settings_game.economy.cargodest.random_dest_chance);

		t->cargo_links_weight[cid] = weight_sum + t->cargo_links[cid].Begin()->weight;
	}
}

/** Recalculate the link weights. */
void UpdateLinkWeights(CargoSourceSink *css)
{
	for (uint cid = 0; cid < NUM_CARGO; cid++) {
		uint weight_sum = 0;

		if (css->cargo_links[cid].Length() == 0) continue;

		css->cargo_links[cid].Begin()->amount.NewMonth();

		for (CargoLink *l = css->cargo_links[cid].Begin() + 1; l != css->cargo_links[cid].End(); l++) {
			l->weight = l->dest->GetDestinationWeight(cid, l->weight_mod);
			weight_sum += l->weight;

			l->amount.NewMonth();
		}

		/* Set weight for the undetermined destination link to random_dest_chance%. */
		css->cargo_links[cid].Begin()->weight = weight_sum == 0 ? 1 : (weight_sum * _settings_game.economy.cargodest.random_dest_chance) / (100 - _settings_game.economy.cargodest.random_dest_chance);

		css->cargo_links_weight[cid] = weight_sum + css->cargo_links[cid].Begin()->weight;
	}
}

/* virtual */ CargoSourceSink::~CargoSourceSink()
{
	if (Town::CleaningPool() || Industry::CleaningPool()) return;

	/* Remove all demand links having us as a destination. */
	Town *t;
	FOR_ALL_TOWNS(t) {
		for (CargoID cid = 0; cid < NUM_CARGO; cid++) {
			if (t->HasLinkTo(cid, this)) {
				t->cargo_links[cid].Erase(t->cargo_links[cid].Find(CargoLink(this, LWM_ANYWHERE)));
				InvalidateWindowData(WC_TOWN_VIEW, t->index, 1);
			}
		}
	}

	Industry *ind;
	FOR_ALL_INDUSTRIES(ind) {
		for (CargoID cid = 0; cid < NUM_CARGO; cid++) {
			if (ind->HasLinkTo(cid, this)) {
				ind->cargo_links[cid].Erase(ind->cargo_links[cid].Find(CargoLink(this, LWM_ANYWHERE)));
				InvalidateWindowData(WC_INDUSTRY_VIEW, ind->index, 1);
			}
		}
	}

	/* Decrement incoming link count for all link destinations. */
	for (CargoID cid = 0; cid < NUM_CARGO; cid++) {
		for (CargoLink *l = this->cargo_links[cid].Begin(); l != this->cargo_links[cid].End(); l++) {
			if (l->dest != NULL) l->dest->num_incoming_links[cid]--;
		}
	}
}

/** Rebuild the cached count of incoming cargo links. */
void RebuildCargoLinkCounts()
{
	/* Clear incoming link count of all towns and industries. */
	CargoSourceSink *source;
	FOR_ALL_TOWNS(source) MemSetT(source->num_incoming_links, 0, lengthof(source->num_incoming_links));
	FOR_ALL_INDUSTRIES(source) MemSetT(source->num_incoming_links, 0, lengthof(source->num_incoming_links));

	/* Count all incoming links. */
	FOR_ALL_TOWNS(source) {
		for (CargoID cid = 0; cid < NUM_CARGO; cid++) {
			for (CargoLink *l = source->cargo_links[cid].Begin(); l != source->cargo_links[cid].End(); l++) {
				if (l->dest != NULL && l->dest != source) l->dest->num_incoming_links[cid]++;
			}
		}
	}
	FOR_ALL_INDUSTRIES(source) {
		for (CargoID cid = 0; cid < NUM_CARGO; cid++) {
			for (CargoLink *l = source->cargo_links[cid].Begin(); l != source->cargo_links[cid].End(); l++) {
				if (l->dest != NULL && l->dest != source) l->dest->num_incoming_links[cid]++;
			}
		}
	}
}

/** Update the demand links of all towns and industries. */
void UpdateCargoLinks()
{
	if (CargoDestinationsDisabled()) return;

	Town *t;
	Industry *ind;

	/* Remove links that have become invalid. */
	FOR_ALL_TOWNS(t) RemoveInvalidLinks(t);
	FOR_ALL_INDUSTRIES(ind) RemoveInvalidLinks(ind);

	/* Recalculate the number of expected links. */
	FOR_ALL_TOWNS(t) UpdateExpectedLinks(t);
	FOR_ALL_INDUSTRIES(ind) UpdateExpectedLinks(ind);

	/* Make sure each industry gets at at least some input cargo. */
	FOR_ALL_INDUSTRIES(ind) AddMissingIndustryLinks(ind);

	/* Update the demand link list. */
	FOR_ALL_TOWNS(t) UpdateCargoLinks(t);
	FOR_ALL_INDUSTRIES(ind) UpdateCargoLinks(ind);

	/* Recalculate links weights. */
	FOR_ALL_TOWNS(t) UpdateLinkWeights(t);
	FOR_ALL_INDUSTRIES(ind) UpdateLinkWeights(ind);

	InvalidateWindowClassesData(WC_TOWN_VIEW, 1);
	InvalidateWindowClassesData(WC_INDUSTRY_VIEW, 1);
}

/**
 * Get a random demand link.
 * @param cid Cargo type
 * @param allow_self Indicates if the local link is acceptable as a result.
 * @return Pointer to a demand link or this->cargo_links[cid].End() if no link found.
 */
CargoLink *CargoSourceSink::GetRandomLink(CargoID cid, bool allow_self)
{
	/* Randomly choose a cargo link. */
	uint weight = RandomRange(this->cargo_links_weight[cid] - 1);
	uint cur_sum = 0;

	CargoLink *l;
	for (l = this->cargo_links[cid].Begin(); l != this->cargo_links[cid].End(); ++l) {
		cur_sum += l->weight;
		if (weight < cur_sum) {
			/* Link is valid if it is random destination or only the
			 * local link if allowed and accepts the cargo. */
			if (l->dest == NULL || ((allow_self || l->dest != this) && l->dest->AcceptsCargo(cid))) break;
		}
	}

	return l;
}


/** Get a random destination tile index for this cargo. */
/* virtual */ TileArea Town::GetTileForDestination(CargoID cid)
{
	assert(this->cargo_accepted_weights[cid] != 0);

	/* Randomly choose a target square. */
	uint32 weight = RandomRange(this->cargo_accepted_weights[cid] - 1);

	/* Iterate over all grid squares till the chosen square is found. */
	uint32 weight_sum = 0;
	const TileArea &area = this->cargo_accepted.GetArea();
	TILE_AREA_LOOP(tile, area) {
		if (TileX(tile) % AcceptanceMatrix::GRID == 0 && TileY(tile) % AcceptanceMatrix::GRID == 0) {
			weight_sum += this->cargo_accepted_max_weight - (DistanceMax(this->xy_aligned, tile) / AcceptanceMatrix::GRID) * 2;
			/* Return tile area inside the grid square if this is the chosen square. */
			if (weight < weight_sum) return TileArea(tile + TileDiffXY(1, 1), 2, 2);
		}
	}

	/* Something went wrong here... */
	NOT_REACHED();
}

/** Enumerate all towns accepting a specific cargo. */
static bool EnumAcceptingTown(const Town *t, void *data)
{
	return t->AcceptsCargo((CargoID)(size_t)data);
}

/** Enumerate all industries accepting a specific cargo. */
static bool EnumAcceptingIndustry(const Industry *ind, void *data)
{
	return ind->AcceptsCargo((CargoID)(size_t)data);
}

/**
 * Move a single packet of cargo to a station with destination information.
 * @param cid Cargo type.
 * @param amount[in,out] Cargo amount, return is actually moved cargo.
 * @param source_type Type of the cargo source.
 * @param source_id ID of the cargo source.
 * @param all_stations List of possible target stations.
 * @param src_tile Source tile.
 * @return True if the cargo was handled has having destinations.
 */
bool MoveCargoWithDestinationToStationWorker(CargoID cid, uint *amount, SourceType source_type, SourceID source_id, const StationList *all_stations, TileIndex src_tile)
{
	CargoSourceSink *source = NULL;
	CargoSourceSink *dest = NULL;
	CargoLink *l = NULL;

	/* Company HQ doesn't have cargo links. */
	if (source_type != ST_HEADQUARTERS) {
		source = (source_type == ST_TOWN) ? static_cast<CargoSourceSink *>(Town::Get(source_id)) : static_cast<CargoSourceSink *>(Industry::Get(source_id));
		/* No links yet? Create cargo without destination. */
		if (source->cargo_links[cid].Length() == 0) return false;

		/* Randomly choose a cargo link. */
		l = source->GetRandomLink(cid, true);

		if (l != source->cargo_links[cid].End()) {
			l->amount.new_max += *amount;
			dest = l->dest;
		}
	}

	/* No destination or random destination? Try a random town. */
	if (dest == NULL) dest = Town::GetRandom(&EnumAcceptingTown, INVALID_TOWN, (void *)(size_t)cid);
	/* No luck? Try a random industry. */
	if (dest == NULL) dest = Industry::GetRandom(&EnumAcceptingIndustry, INVALID_INDUSTRY, (void *)(size_t)cid);
	/* Still no luck, nothing left to try. */
	if (dest == NULL) return false;

	/* Pick a tile that belongs to the destination. */
	TileArea dest_area = dest->GetTileForDestination(cid);

	/* Maximum pathfinder penalty based on distance. */
	uint r = RandomRange(_settings_game.economy.cargodest.max_route_penalty[1]);
	uint max_cost = _settings_game.economy.cargodest.max_route_penalty[0] + r;
	max_cost *= DistanceSquare(src_tile, dest_area.tile);

	/* Randomly determine the routing flags for the packet.
	 * Right now only the two lowest bits are defined. */
	byte flags = r & 0x3;

	/* Find a route to the destination. */
	StationID st, st_unload;
	bool found = false;
	RouteLink *route_link = YapfChooseRouteLink(cid, all_stations, src_tile, dest_area, &st, &st_unload, flags, &found, INVALID_ORDER, max_cost);

	if (route_link == NULL) {
		/* No suitable link found (or direct delivery), nothing is
		 * moved to the station, but count it as transported anyway. */
		if (found && l != NULL) l->amount.new_act += *amount;
		*amount = 0;
		return true;
	}

	/* Move cargo to the station. */
	Station *from = Station::Get(st);
	*amount = UpdateStationWaiting(from, cid, *amount * from->goods[cid].rating, source_type, source_id, dest_area.tile, dest->GetType(), dest->GetID(), route_link->GetOriginOrderId(), st_unload, flags);
	if (found && l != NULL) l->amount.new_act += *amount;

	/* If this is a symmetric cargo type, try to generate some cargo going from
	 * destination to source as well. It's no error if that is not possible. */
	if (IsSymmetricCargo(cid)) {
		/* Try to find the matching cargo link back to the source. If no
		 * link is found, don't generate return traffic. */
		CargoLink *back_link = dest->cargo_links[cid].Find(CargoLink(source, LWM_ANYWHERE));
		if (back_link == dest->cargo_links[cid].End()) return true;

		back_link->amount.new_max += *amount;

		/* Find stations around the new source area. */
		StationFinder stf(dest_area);
		TileIndex tile = dest_area.tile;

		/* The the new destination area. */
		switch (source_type) {
			case ST_INDUSTRY:
				dest_area = static_cast<Industry *>(source)->location;
				break;
			case ST_TOWN:
				dest_area = TileArea(src_tile, 2, 2);
				break;
			case ST_HEADQUARTERS:
				dest_area = TileArea(Company::Get(source_id)->location_of_HQ, 2, 2);
				break;
		}

		/* Find a route and update transported amount if found. */
		route_link = YapfChooseRouteLink(cid, stf.GetStations(), tile, dest_area, &st, &st_unload, flags, &found, INVALID_ORDER, max_cost);
		if (found) back_link->amount.new_act += *amount;

		if (route_link != NULL) {
			/* Found a back link, move to station. */
			UpdateStationWaiting(Station::Get(st), cid, *amount * 256, dest->GetType(), dest->GetID(), dest_area.tile, source_type, source_id, route_link->GetOriginOrderId(), st_unload, flags);
		}
	}

	return true;
}

/**
 * Move cargo to a station with destination information.
 * @param cid Cargo type.
 * @param amount[in,out] Cargo amount, return is actually moved cargo.
 * @param source_type Type of the cargo source.
 * @param source_id ID of the cargo source.
 * @param all_stations List of possible target stations.
 * @param src_tile Source tile.
 * @return True if the cargo was handled has having destinations.
 */
bool MoveCargoWithDestinationToStation(CargoID cid, uint *amount, SourceType source_type, SourceID source_id, const StationList *all_stations, TileIndex src_tile)
{
	if (!CargoHasDestinations(cid)) return false;

	/* Split the cargo into multiple destinations for industries. */
	int num_packets = 1;
	if (source_type == ST_INDUSTRY) {
		if (*amount > 5) num_packets++;
		if (*amount > 50) num_packets += 2;
	}

	/* Generate num_packets different destinations while making
	 * sure no cargo is lost due to rounding. */
	uint amount_packet = *amount / num_packets;
	uint last_packet = *amount - (num_packets - 1) * amount_packet;
	uint moved = 0;
	for (; num_packets > 0; num_packets--) {
		uint cur_amount = (num_packets == 1) ? last_packet : amount_packet;

		/* If we fail once, we will fail always. */
		if (!MoveCargoWithDestinationToStationWorker(cid, &cur_amount, source_type, source_id, all_stations, src_tile)) return false;
		moved += cur_amount;
	}

	*amount = moved;
	return true;
}

/**
 * Get the current best route link for a cargo packet at a station.
 * @param st Station the route starts at.
 * @param cid Cargo type.
 * @param cp Cargo packet with destination information.
 * @param order Incoming order of the cargo packet.
 * @param[out] found Set to true if a route was found.
 * @return The preferred route link or NULL if either no suitable link found or the station is the final destination.
 */
RouteLink *FindRouteLinkForCargo(Station *st, CargoID cid, const CargoPacket *cp, StationID *next_unload, OrderID order, bool *found)
{
	if (cp->DestinationID() == INVALID_SOURCE) return NULL;

	StationList sl;
	*sl.Append() = st;

	TileArea area = (cp->DestinationType() == ST_INDUSTRY) ? Industry::Get(cp->DestinationID())->location : TileArea(cp->DestinationXY(), 2, 2);
	return YapfChooseRouteLink(cid, &sl, st->xy, area, NULL, next_unload, cp->Flags(), found, order);
}


/* Initialize the RouteLink-pool */
RouteLinkPool _routelink_pool("RouteLink");
INSTANTIATE_POOL_METHODS(RouteLink)

/**
 * Invalidate some stuff on destruction.
 */
RouteLink::~RouteLink()
{
	if (RouteLink::CleaningPool()) return;

	if (this->GetOriginOrderId() != INVALID_ORDER) StationCargoList::InvalidateAllTo(this->GetOriginOrderId(), this->GetDestination());
}

/**
 * Update or create a single route link for a specific vehicle and cargo.
 * @param v The vehicle.
 * @param cargoes Create links for the cargo types whose bit is set.
 * @param clear_others Should route links for cargo types nor carried be cleared?
 * @param from Originating station.
 * @param from_oid Originating order.
 * @param to_id Destination station ID.
 * @param to_oid Destination order.
 * @param travel_time Travel time for the route.
 */
void UpdateVehicleRouteLinks(const Vehicle *v, uint32 cargoes, bool clear_others, Station *from, OrderID from_oid, StationID to_id, OrderID to_oid, uint32 travel_time)
{
	for (CargoID cid = 0; cid < NUM_CARGO; cid++) {
		bool has_cargo = HasBit(cargoes, cid);
		/* Skip if cargo not carried and we aren't supposed to clear other links. */
		if (!clear_others && !has_cargo) continue;
		/* Skip cargo types that don't have destinations enabled. */
		if (!CargoHasDestinations(cid)) continue;

		RouteLinkList::iterator link;
		for (link = from->goods[cid].routes.begin(); link != from->goods[cid].routes.end(); ++link) {
			if ((*link)->GetOriginOrderId() == from_oid) {
				if (has_cargo) {
					/* Update destination if necessary. */
					(*link)->SetDestination(to_id, to_oid);
					(*link)->UpdateTravelTime(travel_time);
				} else {
					/* Remove link. */
					delete *link;
					from->goods[cid].routes.erase(link);
				}
				break;
			}
		}

		/* No link found? Append a new one. */
		if (has_cargo && link == from->goods[cid].routes.end() && RouteLink::CanAllocateItem()) {
			from->goods[cid].routes.push_back(new RouteLink(to_id, from_oid, to_oid, v->owner, travel_time, v->type));
		}
	}
}

/**
 * Update route links after a vehicle has arrived at a station.
 * @param v The vehicle.
 * @param arrived_at The station the vehicle arrived at.
 */
void UpdateVehicleRouteLinks(const Vehicle *v, StationID arrived_at)
{
	/* Only update links if we have valid previous station and orders. */
	if (v->last_station_loaded == INVALID_STATION || v->last_order_id == INVALID_ORDER || v->current_order.index == INVALID_ORDER) return;
	/* Loop? Not good. */
	if (v->last_station_loaded == arrived_at) return;

	Station *from = Station::Get(v->last_station_loaded);
	Station *to = Station::Get(arrived_at);

	/* Update incoming route link. */
	UpdateVehicleRouteLinks(v, v->vcache.cached_cargo_mask, false, from, v->last_order_id, arrived_at, v->current_order.index, v->travel_time);

	/* Update outgoing links. */
	CargoID cid;
	FOR_EACH_SET_CARGO_ID(cid, v->vcache.cached_cargo_mask) {
		/* Skip cargo types that don't have destinations enabled. */
		if (!CargoHasDestinations(cid)) continue;

		for (RouteLinkList::iterator link = to->goods[cid].routes.begin(); link != to->goods[cid].routes.end(); ++link) {
			if ((*link)->GetOriginOrderId() == v->current_order.index) {
				(*link)->VehicleArrived();
				break;
			}
		}
	}
}

/**
 * Pre-fill the route links from the orders of a vehicle.
 * @param v The vehicle to get the orders from.
 */
void PrefillRouteLinks(const Vehicle *v)
{
	if (CargoDestinationsDisabled()) return;
	if (v->orders.list == NULL || v->orders.list->GetNumOrders() < 2) return;

	/* Can't pre-fill if the vehicle has refit or conditional orders. */
	uint count = 0;
	Order *order;
	FOR_VEHICLE_ORDERS(v, order) {
		if (order->IsType(OT_GOTO_DEPOT) && order->IsRefit()) return;
		if (order->IsType(OT_CONDITIONAL)) return;
		if ((order->IsType(OT_IMPLICIT) || order->IsType(OT_GOTO_STATION)) && (order->GetNonStopType() & ONSF_NO_STOP_AT_DESTINATION_STATION) == 0) count++;
	}

	/* Increment count by one to account for the circular nature of the order list. */
	if (count > 0) count++;

	/* Collect cargo types carried by all vehicles in the shared order list. */
	uint32 transported_cargoes = 0;
	for (Vehicle *u = v->FirstShared(); u != NULL; u = u->NextShared()) {
		transported_cargoes |= u->vcache.cached_cargo_mask;
	}

	/* Loop over all orders to update/pre-fill the route links. */
	order = v->orders.list->GetFirstOrder();
	Order *prev_order = NULL;
	do {
		/* Goto station or implicit order and not a go via-order, consider as destination. */
		if ((order->IsType(OT_IMPLICIT) || order->IsType(OT_GOTO_STATION)) && (order->GetNonStopType() & ONSF_NO_STOP_AT_DESTINATION_STATION) == 0) {
			/* Previous destination is set and the new destination is different, create/update route links. */
			if (prev_order != NULL && prev_order != order && prev_order->GetDestination() != order->GetDestination()) {
				Station *from = Station::Get(prev_order->GetDestination());
				Station *to = Station::Get(order->GetDestination());
				/* A vehicle with the speed of 128 km/h-ish would take one tick for each of the
				 * #TILE_SIZE steps per tile. For aircraft, the time needs to be scaled with the
				 * plane speed factor. */
				uint time = DistanceManhattan(from->xy, to->xy) * TILE_SIZE * 128 / v->GetDisplayMaxSpeed();
				if (v->type == VEH_AIRCRAFT) time *= _settings_game.vehicle.plane_speed;
				UpdateVehicleRouteLinks(v, transported_cargoes, true, from, prev_order->index, order->GetDestination(), order->index, time);
			}

			prev_order = order;
			count--;
		}

		/* Get next order, wrap around if necessary. */
		order = order->next;
		if (order == NULL) order = v->orders.list->GetFirstOrder();
	} while (count > 0);
}

/**
 * Remove all route links to and from a station.
 * @param station Station being removed.
 */
void InvalidateStationRouteLinks(Station *station)
{
	/* Delete all outgoing links. */
	for (CargoID cid = 0; cid < NUM_CARGO; cid++) {
		for (RouteLinkList::iterator link = station->goods[cid].routes.begin(); link != station->goods[cid].routes.end(); ++link) {
			delete *link;
		}
	}

	/* Delete all incoming link. */
	Station *st_from;
	FOR_ALL_STATIONS(st_from) {
		if (st_from == station) continue;

		for (CargoID cid = 0; cid < NUM_CARGO; cid++) {
			/* Don't increment the iterator directly in the for loop as we don't want to increment when deleting a link. */
			for (RouteLinkList::iterator link = st_from->goods[cid].routes.begin(); link != st_from->goods[cid].routes.end(); ) {
				if ((*link)->GetDestination() == station->index) {
					delete *link;
					link = st_from->goods[cid].routes.erase(link);
				} else {
					++link;
				}
			}
		}
	}
}

/**
 * Remove all route links referencing an order.
 * @param order The order being removed.
 */
void InvalidateOrderRouteLinks(OrderID order)
{
	Station *st;
	FOR_ALL_STATIONS(st) {
		for (CargoID cid = 0; cid < NUM_CARGO; cid++) {
			/* Don't increment the iterator directly in the for loop as we don't want to increment when deleting a link. */
			for (RouteLinkList::iterator link = st->goods[cid].routes.begin(); link != st->goods[cid].routes.end(); ) {
				if ((*link)->GetOriginOrderId() == order || (*link)->GetDestOrderId() == order) {
					delete *link;
					link = st->goods[cid].routes.erase(link);
				} else {
					++link;
				}
			}
		}
	}
}

/** Age and expire route links of a station. */
void AgeRouteLinks(Station *st)
{
	/* Reset waiting time for all vehicles currently loading. */
	for (std::list<Vehicle *>::const_iterator v_itr = st->loading_vehicles.begin(); v_itr != st->loading_vehicles.end(); ++v_itr) {
		CargoID cid;
		FOR_EACH_SET_CARGO_ID(cid, (*v_itr)->vcache.cached_cargo_mask) {
			for (RouteLinkList::iterator link = st->goods[cid].routes.begin(); link != st->goods[cid].routes.end(); ++link) {
				if ((*link)->GetOriginOrderId() == (*v_itr)->last_order_id) (*link)->wait_time = 0;
			}
		}
	}

	for (CargoID cid = 0; cid < NUM_CARGO; cid++) {
		/* Don't increment the iterator directly in the for loop as we don't want to increment when deleting a link. */
		for (RouteLinkList::iterator link = st->goods[cid].routes.begin(); link != st->goods[cid].routes.end(); ) {
			if ((*link)->wait_time++ > _settings_game.economy.cargodest.max_route_age) {
				delete *link;
				link = st->goods[cid].routes.erase(link);
			} else {
				++link;
			}
		}
	}
}