(svn r26646) -Fix [FS#6041]: Save locations instead of distances in link graphs to reduce size.

7 files changed, 71 insertions, 52 deletions

diff --git a/src/linkgraph/demands.cpp b/src/linkgraph/demands.cpp
index c16288123..2c88778ab 100644
--- a/src/linkgraph/demands.cpp
+++ b/src/linkgraph/demands.cpp
@@ -210,7 +210,8 @@ void DemandCalculator::CalcDemand(LinkGraphJob &job, Tscaler scaler)
 
 			/* Scale the distance by mod_dist around max_distance */
 			int32 distance = this->max_distance - (this->max_distance -
-					(int32)job[from_id][to_id].Distance()) * this->mod_dist / 100;
+					(int32)DistanceMaxPlusManhattan(job[from_id].XY(), job[to_id].XY())) *
+					this->mod_dist / 100;
 
 			/* Scale the accuracy by distance around accuracy / 2 */
 			int32 divisor = this->accuracy * (this->mod_dist - 50) / 100 +
diff --git a/src/linkgraph/linkgraph.cpp b/src/linkgraph/linkgraph.cpp
index 01b3d1ee2..50945d361 100644
--- a/src/linkgraph/linkgraph.cpp
+++ b/src/linkgraph/linkgraph.cpp
@@ -21,11 +21,13 @@ INSTANTIATE_POOL_METHODS(LinkGraph)
 
 /**
  * Create a node or clear it.
+ * @param xy Location of the associated station.
  * @param st ID of the associated station.
  * @param demand Demand for cargo at the station.
  */
-inline void LinkGraph::BaseNode::Init(StationID st, uint demand)
+inline void LinkGraph::BaseNode::Init(TileIndex xy, StationID st, uint demand)
 {
+	this->xy = xy;
 	this->supply = 0;
 	this->demand = demand;
 	this->station = st;
@@ -34,11 +36,9 @@ inline void LinkGraph::BaseNode::Init(StationID st, uint demand)
 
 /**
  * Create an edge.
- * @param distance Length of the link as manhattan distance.
  */
-inline void LinkGraph::BaseEdge::Init(uint distance)
+inline void LinkGraph::BaseEdge::Init()
 {
-	this->distance = distance;
 	this->capacity = 0;
 	this->usage = 0;
 	this->last_unrestricted_update = INVALID_DATE;
@@ -147,21 +147,6 @@ void LinkGraph::RemoveNode(NodeID id)
 }
 
 /**
- * Update distances between the given node and all others.
- * @param id Node that changed position.
- * @param xy New position of the node.
- */
-void LinkGraph::UpdateDistances(NodeID id, TileIndex xy)
-{
-	assert(id < this->Size());
-	for (NodeID other = 0; other < this->Size(); ++other) {
-		if (other == id) continue;
-		this->edges[id][other].distance = this->edges[other][id].distance =
-				DistanceMaxPlusManhattan(xy, Station::Get(this->nodes[other].station)->xy);
-	}
-}
-
-/**
  * Add a node to the component and create empty edges associated with it. Set
  * the station's last_component to this component. Calculate the distances to all
  * other nodes. The distances to _all_ nodes are important as the demand
@@ -180,7 +165,7 @@ NodeID LinkGraph::AddNode(const Station *st)
 	this->edges.Resize(new_node + 1U,
 			max(new_node + 1U, this->edges.Height()));
 
-	this->nodes[new_node].Init(st->index,
+	this->nodes[new_node].Init(st->xy, st->index,
 			HasBit(good.status, GoodsEntry::GES_ACCEPTANCE));
 
 	BaseEdge *new_edges = this->edges[new_node];
@@ -189,9 +174,8 @@ NodeID LinkGraph::AddNode(const Station *st)
 	new_edges[new_node].next_edge = INVALID_NODE;
 
 	for (NodeID i = 0; i <= new_node; ++i) {
-		uint distance = DistanceMaxPlusManhattan(st->xy, Station::Get(this->nodes[i].station)->xy);
-		new_edges[i].Init(distance);
-		this->edges[i][new_node].Init(distance);
+		new_edges[i].Init();
+		this->edges[i][new_node].Init();
 	}
 	return new_node;
 }
diff --git a/src/linkgraph/linkgraph.h b/src/linkgraph/linkgraph.h
index 7aaa1901d..799f22c78 100644
--- a/src/linkgraph/linkgraph.h
+++ b/src/linkgraph/linkgraph.h
@@ -49,8 +49,9 @@ public:
 		uint supply;             ///< Supply at the station.
 		uint demand;             ///< Acceptance at the station.
 		StationID station;       ///< Station ID.
+		TileIndex xy;            ///< Location of the station referred to by the node.
 		Date last_update;        ///< When the supply was last updated.
-		void Init(StationID st = INVALID_STATION, uint demand = 0);
+		void Init(TileIndex xy = INVALID_TILE, StationID st = INVALID_STATION, uint demand = 0);
 	};
 
 	/**
@@ -60,13 +61,12 @@ public:
 	 * the column as next_edge.
 	 */
 	struct BaseEdge {
-		uint distance;                 ///< Length of the link.
 		uint capacity;                 ///< Capacity of the link.
 		uint usage;                    ///< Usage of the link.
 		Date last_unrestricted_update; ///< When the unrestricted part of the link was last updated.
 		Date last_restricted_update;   ///< When the restricted part of the link was last updated.
 		NodeID next_edge;              ///< Destination of next valid edge starting at the same source node.
-		void Init(uint distance = 0);
+		void Init();
 	};
 
 	/**
@@ -99,12 +99,6 @@ public:
 		uint Usage() const { return this->edge.usage; }
 
 		/**
-		 * Get edge's distance.
-		 * @return Distance.
-		 */
-		uint Distance() const { return this->edge.distance; }
-
-		/**
 		 * Get the date of the last update to the edge's unrestricted capacity.
 		 * @return Last update.
 		 */
@@ -169,6 +163,12 @@ public:
 		 * @return Last update.
 		 */
 		Date LastUpdate() const { return this->node.last_update; }
+
+		/**
+		 * Get the location of the station associated with the node.
+		 * @return Location of the station.
+		 */
+		TileIndex XY() const { return this->node.xy; }
 	};
 
 	/**
@@ -413,6 +413,15 @@ public:
 		}
 
 		/**
+		 * Update the node's location on the map.
+		 * @param xy New location.
+		 */
+		void UpdateLocation(TileIndex xy)
+		{
+			this->node.xy = xy;
+		}
+
+		/**
 		 * Set the node's demand.
 		 * @param demand New demand for the node.
 		 */
@@ -513,7 +522,6 @@ public:
 
 	NodeID AddNode(const Station *st);
 	void RemoveNode(NodeID id);
-	void UpdateDistances(NodeID id, TileIndex xy);
 
 protected:
 	friend class LinkGraph::ConstNode;
diff --git a/src/linkgraph/mcf.cpp b/src/linkgraph/mcf.cpp
index 3163ec9e3..81d4d6d38 100644
--- a/src/linkgraph/mcf.cpp
+++ b/src/linkgraph/mcf.cpp
@@ -259,7 +259,6 @@ void MultiCommodityFlow::Dijkstra(NodeID source_node, PathVector &paths)
 		for (NodeID to = iter.Next(); to != INVALID_NODE; to = iter.Next()) {
 			if (to == from) continue; // Not a real edge but a consumption sign.
 			Edge edge = this->job[from][to];
-			assert(edge.Distance() < UINT_MAX);
 			uint capacity = edge.Capacity();
 			if (this->max_saturation != UINT_MAX) {
 				capacity *= this->max_saturation;
@@ -267,7 +266,7 @@ void MultiCommodityFlow::Dijkstra(NodeID source_node, PathVector &paths)
 				if (capacity == 0) capacity = 1;
 			}
 			/* punish in-between stops a little */
-			uint distance = edge.Distance() + 1;
+			uint distance = DistanceMaxPlusManhattan(this->job[from].XY(), this->job[to].XY()) + 1;
 			Tannotation *dest = static_cast<Tannotation *>(paths[to]);
 			if (dest->IsBetter(source, capacity, capacity - edge.Flow(), distance)) {
 				annos.erase(dest);
diff --git a/src/saveload/linkgraph_sl.cpp b/src/saveload/linkgraph_sl.cpp
index 4988eb2ed..20a3f4498 100644
--- a/src/saveload/linkgraph_sl.cpp
+++ b/src/saveload/linkgraph_sl.cpp
@@ -109,24 +109,25 @@ const SaveLoad *GetLinkGraphScheduleDesc()
  * SaveLoad desc for a link graph node.
  */
 static const SaveLoad _node_desc[] = {
-	SLE_VAR(Node, supply,      SLE_UINT32),
-	SLE_VAR(Node, demand,      SLE_UINT32),
-	SLE_VAR(Node, station,     SLE_UINT16),
-	SLE_VAR(Node, last_update, SLE_INT32),
-	SLE_END()
+	SLE_CONDVAR(Node, xy,          SLE_UINT32, 191, SL_MAX_VERSION),
+	    SLE_VAR(Node, supply,      SLE_UINT32),
+	    SLE_VAR(Node, demand,      SLE_UINT32),
+	    SLE_VAR(Node, station,     SLE_UINT16),
+	    SLE_VAR(Node, last_update, SLE_INT32),
+	    SLE_END()
 };
 
 /**
  * SaveLoad desc for a link graph edge.
  */
 static const SaveLoad _edge_desc[] = {
-	    SLE_VAR(Edge, distance,                 SLE_UINT32),
-	    SLE_VAR(Edge, capacity,                 SLE_UINT32),
-	    SLE_VAR(Edge, usage,                    SLE_UINT32),
-	    SLE_VAR(Edge, last_unrestricted_update, SLE_INT32),
-	SLE_CONDVAR(Edge, last_restricted_update,   SLE_INT32, 187, SL_MAX_VERSION),
-	    SLE_VAR(Edge, next_edge,                SLE_UINT16),
-	    SLE_END()
+	SLE_CONDNULL(4, 0, 190), // distance
+	     SLE_VAR(Edge, capacity,                 SLE_UINT32),
+	     SLE_VAR(Edge, usage,                    SLE_UINT32),
+	     SLE_VAR(Edge, last_unrestricted_update, SLE_INT32),
+	 SLE_CONDVAR(Edge, last_restricted_update,   SLE_INT32, 187, SL_MAX_VERSION),
+	     SLE_VAR(Edge, next_edge,                SLE_UINT16),
+	     SLE_END()
 };
 
 /**
@@ -139,8 +140,16 @@ void SaveLoad_LinkGraph(LinkGraph &lg)
 	for (NodeID from = 0; from < size; ++from) {
 		Node *node = &lg.nodes[from];
 		SlObject(node, _node_desc);
-		for (NodeID to = 0; to < size; ++to) {
-			SlObject(&lg.edges[from][to], _edge_desc);
+		if (IsSavegameVersionBefore(191)) {
+			/* We used to save the full matrix ... */
+			for (NodeID to = 0; to < size; ++to) {
+				SlObject(&lg.edges[from][to], _edge_desc);
+			}
+		} else {
+			/* ... but as that wasted a lot of space we save a sparse matrix now. */
+			for (NodeID to = from; to != INVALID_NODE; to = lg.edges[from][to].next_edge) {
+				SlObject(&lg.edges[from][to], _edge_desc);
+			}
 		}
 	}
 }
@@ -220,6 +229,23 @@ static void Load_LGRS()
  */
 void AfterLoadLinkGraphs()
 {
+	if (IsSavegameVersionBefore(191)) {
+		LinkGraph *lg;
+		FOR_ALL_LINK_GRAPHS(lg) {
+			for (NodeID node_id = 0; node_id < lg->Size(); ++node_id) {
+				(*lg)[node_id].UpdateLocation(Station::Get((*lg)[node_id].Station())->xy);
+			}
+		}
+
+		LinkGraphJob *lgj;
+		FOR_ALL_LINK_GRAPH_JOBS(lgj) {
+			lg = &(const_cast<LinkGraph &>(lgj->Graph()));
+			for (NodeID node_id = 0; node_id < lg->Size(); ++node_id) {
+				(*lg)[node_id].UpdateLocation(Station::Get((*lg)[node_id].Station())->xy);
+			}
+		}
+	}
+
 	LinkGraphSchedule::Instance()->SpawnAll();
 }
 
diff --git a/src/saveload/saveload.cpp b/src/saveload/saveload.cpp
index f3d2f6205..958ed46ac 100644
--- a/src/saveload/saveload.cpp
+++ b/src/saveload/saveload.cpp
@@ -258,8 +258,9 @@
  *  188   26169   1.4.x
  *  189   26450
  *  190   26547
+ *  191   26646
  */
-extern const uint16 SAVEGAME_VERSION = 190; ///< Current savegame version of OpenTTD.
+extern const uint16 SAVEGAME_VERSION = 191; ///< Current savegame version of OpenTTD.
 
 SavegameType _savegame_type; ///< type of savegame we are loading
 
diff --git a/src/station_cmd.cpp b/src/station_cmd.cpp
index 99bb4225e..91d65ad87 100644
--- a/src/station_cmd.cpp
+++ b/src/station_cmd.cpp
@@ -649,7 +649,7 @@ static void UpdateStationSignCoord(BaseStation *st)
 	for (CargoID c = 0; c < NUM_CARGO; ++c) {
 		LinkGraphID lg = full_station->goods[c].link_graph;
 		if (!LinkGraph::IsValidID(lg)) continue;
-		LinkGraph::Get(lg)->UpdateDistances(full_station->goods[c].node, st->xy);
+		(*LinkGraph::Get(lg))[full_station->goods[c].node].UpdateLocation(st->xy);
 	}
 }