search

Return-To-The-Roots / s25client

Return To The Roots (Settlers II(R) Clone)
http://www.rttr.info
GNU General Public License v2.0
476 stars 75 forks source link

Road network identifiers #164

Open MarcusSt opened 9 years ago

MarcusSt commented 9 years ago

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 commented 9 years ago

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

Flow86 commented 9 years ago

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