To be used with #45945, the most difficult part of HRM879656. A requirement to see if a city is connected to a tile by a specific kind of terrain or infrastructure on the map (e.g.: roads; railroads; rivers, lakes and shallow ocean...). To reuse game elements that we have, we describe this infrastructure as a unit class (unit type specific things like ZoC or fuel are left out for simplicity). We probably also need ruleset parameters that specify minimal diplomatic relation for connectors with tile, city or unit owner (likely, for civ2 it should be "War", "War", "Alliance", may be hardcoded in first realization); that is not applied to the starting (target) tile that we get only out.
Since requirements should be flash fast, we won't calculate it in a regular path finder; we have no interest in travel time, our business here is to find an answer if there is any path at all or no and do it at minimal cost. Probably, a node map that we are to use here will consist of sole integer value for each tile that specifies its connectivity cluster. We should be able to reuse the map for given class and given player (with partially traversed data in the amount we needed before) until something on the main map renders it obsolete.
The cluster value specifies the index of a root growth point on an arena of growth points for the map; these points are left during tile traversing where there are unexplored enterable tiles left aside. The growth points of a cluster may form a list or a quadrotree, or both. A cluster that has no growth points left gets negative index, if we question a tile in it we can immediately say if any other tile belongs to the cluster by comparing its cluster index.
For traversing nodes, we can use BFS or DFS algorithms, but I would prefer to use something more optimized for lattice-like 4-, 6- or 8-connected graphs that we have. I have not found one in books yet, but what about this draft (supposed we start at unexplored map positions and the start point is passable):
1 Initialization: make the start and the finish points clusters.
2 Take closest pair of growth points from clusters.
3 Advance a point of the current pair in a way that brings the points as close as possible, but if there is an obstacle aside, don't diverge from it unless the step is on an angle that can be called "discrete tangential" and the approaching is positive. If we enter a "corridor", leave a growth point in the unexplored area left behind.
4 If we have run into another cluster, join the clusters and continue.
5 If we have run into a cluster of another path end, join the clusters and return "yes".
6 If we have run into a dead end, destroy the growth point and try to use another perspective point. If a cluster of one end has no perspective point left, return "no".
7 If we have run into explored territory (T-style), split the growth point to be able to search in both unexplored regions. Use ray tracing to say if the points we get are perspective (that may be not possible in a rare case when we have unmatching diagonally connecting roads on a 8-connected map)
8 If the approaching was not positive, try to find a closer pair
To be used with #45945, the most difficult part of HRM879656. A requirement to see if a city is connected to a tile by a specific kind of terrain or infrastructure on the map (e.g.: roads; railroads; rivers, lakes and shallow ocean...). To reuse game elements that we have, we describe this infrastructure as a unit class (unit type specific things like ZoC or fuel are left out for simplicity). We probably also need ruleset parameters that specify minimal diplomatic relation for connectors with tile, city or unit owner (likely, for civ2 it should be "War", "War", "Alliance", may be hardcoded in first realization); that is not applied to the starting (target) tile that we get only out.
Since requirements should be flash fast, we won't calculate it in a regular path finder; we have no interest in travel time, our business here is to find an answer if there is any path at all or no and do it at minimal cost. Probably, a node map that we are to use here will consist of sole integer value for each tile that specifies its connectivity cluster. We should be able to reuse the map for given class and given player (with partially traversed data in the amount we needed before) until something on the main map renders it obsolete.
The cluster value specifies the index of a root growth point on an arena of growth points for the map; these points are left during tile traversing where there are unexplored enterable tiles left aside. The growth points of a cluster may form a list or a quadrotree, or both. A cluster that has no growth points left gets negative index, if we question a tile in it we can immediately say if any other tile belongs to the cluster by comparing its cluster index.
For traversing nodes, we can use BFS or DFS algorithms, but I would prefer to use something more optimized for lattice-like 4-, 6- or 8-connected graphs that we have. I have not found one in books yet, but what about this draft (supposed we start at unexplored map positions and the start point is passable):