Road network identifiers

[MarcusSt]

Every road node (noRoadNode) gets an id of the unique network (as in connected nodes) it is attached to.

Advantages

1. Eliminates the worst case for pathfinding, which would visit all nodes, putting them into a tree structure etc. and happens a lot while fighting or for new buildings that are not yet connected. Also the well-known strategy of disconnecting military buildings from the network is problematic.
2. Possibility to implement a "reachable" check to replace pathfinding in many cases. May be used as heuristics together with CalcDistance() when there's no exact walking distance needed.

Implementation

1. New road between n1 and n2 gets built.
   • Different id? (happens way less often than worst case pathfinding, mostly only by user interaction)
     • Flood-fill (non-recursive!) part with lower id with higher id.
     • Re-calculate transport (buildings in net 1 may need wares from storehouses in 2 etc.)
2. Road between two nodes n1 and n2 gets destroyed
   • No other path from n1 to n2? (should also not happen that often)
     • flood-fill n2 with new id
3. Seafaring
   • Ids stop at harbors
   • set of pairs (low, high) to look up connections
4. Pathfinding
   • Different id? Check harbors, otherwise no path possible.

[Flow86]

sounds good, I think the old s2 has done something similar, since they had unique ids for the "seas"

[Flow86]

Branch: road-network-id: https://github.com/Return-To-The-Roots/s25client/compare/master...road-network-id