Traderoute calculations should be done per player rather than per unit

[Nightinggale]

I just had an inspiration regarding how to improve fully automated transports.

Right now whenever an automated transport needs a new task, it will loop all possible routes to find "the best" and then do that one.

What we should do instead is once automated transports needs a new task, they add themselves to a list. Once CvPlayer::doTurn is done with units, it will generate a sorted list of routes (sorted according to AI value of getting them done). It will then go from the top and assign it to the nearest transport, then the next to the nearest etc and continue until there are no transports left or no valid routes.

The benefits of doing it this way is that the time consuming task of figuring out all valid routes and sort them will be done once per turn rather than once per unit, or if the unit finishes during the same turn, more than once for a single unit. This is a not insignificant timer saver.

The other benefit is getting the closest transport. That will reduce the amount of times a transport has to travel many turns to reach the other end of the empire while other transports spend time moving empty in the other direction.

[Schmiddie1979]

Sounds great! I used the automated transport system for the first time in my current game (after so many years!) and I'm very impressed. I should have done that earlier. I assume it would be a great advantage to get this done as you describe.

[MrZorG33]

After implementation, it will be interesting to see whether auto-transport will begin to deliver goods for the domestic market. they don't do that now.

[devolution79]

This code block is likely the culprit to be blamed for poor performance.

By iterating over routes rather than city source/destination pairs, it ends up issuing redundant pathfinding calls.

Since there are two pathfinding calls in sequence with different source nodes, the pathfinding cache is discarded. Therefore, we won't benefit from caching at all, and the pathfinder will have to start from scratch every time.

Summary: Not only are there redundant calls to the pathfinder, but they are also executed in the most inefficient way possible.

	for (uint i = 0; i < routes.size(); ++i)
	{
		CvCity* pSourceCity = ::getCity(routes[i]->getSourceCity());

		if ((pSourceCity != NULL) && (bNoCargo || (cityValues[routes[i]->getSourceCity()] > 0)))
		{
			CvCity* pDestinationCity = ::getCity(routes[i]->getDestinationCity());
			YieldTypes eYield = routes[i]->getYield();

			// transport feeder - start - Nightinggale
			//int iAmount = pSourceCity->getYieldStored(eYield) - pSourceCity->getMaintainLevel(eYield);
			int iAmount = pSourceCity->getYieldStored(eYield) - pSourceCity->getAutoMaintainThreshold(eYield);
			// transport feeder - end - Nightinggale
			// R&R mod, vetiarvind, max yield import limit - start
			if(pDestinationCity != NULL &&   pDestinationCity->getMaxImportAmount(eYield) > 0)
			{
				int turnsToReachToSource = 0, turnsToReachFromSourceToDest = 0;
				const bool bSourceOk = generatePath(plot(), pSourceCity->plot(), (bIgnoreDanger ? MOVE_IGNORE_DANGER : MOVE_NO_ENEMY_TERRITORY), true, &turnsToReachToSource);
				const bool bDestOk = generatePath(pSourceCity->plot(), pDestinationCity->plot(), (bIgnoreDanger ? MOVE_IGNORE_DANGER : MOVE_NO_ENEMY_TERRITORY), true, &turnsToReachFromSourceToDest);

				if (!(bSourceOk && bDestOk))
					// We require both of these paths to be valid. If not, we skip this route
					continue;

				// At least one destination is reachable
				bNoRoute = false;

				// Erik: If we can travel from the current plot to the source, and then from source to destination in the same turn,
				// we have to make sure that we don't overestimate the amount that we should load
				int turnsRequired;
				if (turnsToReachToSource == turnsToReachFromSourceToDest)
				{
					// No need to add both legs of the journey since that would have the transport load too much cargo for the destination city
					turnsRequired = turnsToReachToSource + turnsToReachFromSourceToDest - 2;
					// In case generatePath could ever return 0
					turnsRequired = std::max(0, turnsRequired);
				}
				else
				{
					// Slightly underestimate the cargo we should carry (we cannot get this 100% correct since it depends on fractional movement,
					// other transports, consumption changes at the destination etc.
					turnsRequired = std::max(turnsToReachToSource, turnsToReachFromSourceToDest);
				}

				iAmount = estimateYieldsToLoad(pDestinationCity, iAmount, eYield, turnsRequired, aiYieldsLoaded[eYield]);
			}
			// Note that Europe has no import limit!
			else if (pDestinationCity == NULL && routes[i]->getDestinationCity() == kEurope)
			{
				// This is a Europe trade-route, exempt it from the reachability criteria
				// TODO: Check that there is actually a route to Europe!
				bNoRoute = false;
			}

			// R&R mod, vetiarvind, max yield import limit - end
			if (iAmount > 0)
			{

				int iExportValue = kOwner.AI_transferYieldValue(routes[i]->getSourceCity(), routes[i]->getYield(), -iAmount);
				int iImportValue = kOwner.AI_transferYieldValue(routes[i]->getDestinationCity(), routes[i]->getYield(), iAmount);
				int iRouteValue = (iExportValue + iImportValue + 2 * std::min(iExportValue, iImportValue)) / 4;


				if (pSourceCity == pPlotCity)
				{
					cityValues[routes[i]->getDestinationCity()] += 2 * iRouteValue;
				}
				else
				{
					cityValues[routes[i]->getSourceCity()] += iRouteValue;
				}

				routeValues[i] = iRouteValue;
			}
		}