Surprise me.
Ok.
First of all my definition of a chokepoint is the following:
A single walkable tile which is bordered by a minimum of two diagonally adjacent, non-walkable tiles. or two
non-walkable tiles on opposite sites with equal X or equal Y values.
When this chokepoint tile, when considered "non-walkable" causes a single land area zone to become split into two sub-land area zones (A and B), where the minimum pathing distance from a tile in sub-zone A that is adjacent
to the chokeponit tile. to a tile in subzone B that is also adjacent to the chokepoint tile, is greater than X
or when a walkable land path between sub-zone A and B no longer exists.
An Example:
1 = non-walkable tile
0 = walkable taile
X = chokepoint tile
001110
000100
000X00
000100
000100
Some caveats:
This was orignally envisioned before the mountaineering mod came into existance, so for now I am assuming
that mountians are considered as non-walkable tile. Chokepoints as determined thus therefore viable
for anyone not using the mountaineering mod. Even with the mountaineering mod, they remain viable pre-mountaineering tech
or in regards to cost, or if one wants to modify the mountaineering rules to further restrict what unit types can traverse them.
It is assumed that chokepoint locations will be calculated for land tiles only at the beginning of the game during inital map creation,
via a single scan pass of the map. Terrain type and features are irrelavent, only a tile's walkable or non-walkable states are considered.
The algorithm is for single tile chokepoints, but it could be expanded to cover two-tile chokepoints, but at more complication. (more on that later)
I am assuming that chokepoint blocking that require 3 or more tiles to "fill the gap" to be too complex to bother with for the AI.
The algorithm
For Y = 0 to MaxHeight //Note this Y scan could be reduce if it is known that the map type is a 'polar' ice cap type, to begin and end at a reduce latitude to skip the ice/ocean rows
For X = 0 to MaxWidth
tile = GetTile(x,y)
if (tile.IsWalkable()) //A walkable tile is != mountain and != water.
{
if (IsChokepoint(tile))
AddToChokePointList(tile)
}
IsChokePoint(tile)
How many possible ways are there to divide an 3x3 tile grid, into two sub-land zone if a choke point is
considered to be present at the center? Answer: 6
First lets ID our tiles as:
123
456
789
The tile passed into the function is at position 5. So position 3 = tile.X+1, tile.Y - 1, etc.
How can we subdivide the grid? A, B = walkable tiles, 1 = non-walkable tiles, X = center (potential chokepoint site)
A1B A1B A1B AAA AAA AAA
1XB AX1 AXB 1X1 1XA AX1
BBB AAA A1B BBB B1A A1B
Translate positions 1-8's walkable (0) /non-walkable (1) states into a bitmask and we'll do some bitwise operations
against the resultant 8-bit (8 because position 5 is ignored) byte to keep or throw away this candidate tile. I'm not going to explain bitwise ops here though,
it will take too long.
Notice that positions 2, 4, 6, and 8 are the primary positions we need to consider to determine if the tile is a chokepoint candidate
(checking other positions might eliminate candidacy, but if a minimum of 2 non walkable tiles do not exist in position 2,4,6,8 then the tile
is NOT a candidate chokepoint location, return false
First some general culling: sum your bitmask, if the sum >=7 them the tile is NOT a candidate (8 means its a boxed in tile, 7 means it's a cul-de-sac)
return false
So for now if you have gotten this far, then position 5 is walkable, and there are at least 2 non-walkable tiles (non-diagonally) adjacent to it.
Based on the calculated 8 bit number you are in 1 of the 6 states above.
We want to find the opposing walkable positions as belonging to tile set A and tile set B
(these represent walkable tiles in sub-zone A and B on opposite side of the chokepoint)
note that it is possible for there to be a set C if positions (2,4,6,8) have 3 non-walkable tiles or a set D if they have 4.
We want to divide the walkable tiles adjacent to the chokepoint into separate sets separated by non-walkable tiles.
The minimum size for a set is 0 and the maximum size for a set is 5.
We construct a list of positions 1,2,3,6,9,8,7.4 w/ values as their walkable states.
Add to set A, the first walkable position encountered from the list starting at 1 and keep adding tiles to set A
until a non-walkable tile is encountered at position 2,4,6 or 8 then stop. Each time a walkable tile is added to set A, remove it from the list.
If set A contains position 1 or 2, then
traverse the remaining list in backwards order starting from 4,
and each walkable tile to Set A until a non-walkable tile at position 4,6 or 8 is encountered then stop.
You have completed set A.
Add to Set B the first non-walkable position encountered from the list, starting from the beginning until a non-walkable tile at position 2,4,6, or 8 is encountered.
You have completed set B.
Repeat the above to construct set C and D until there are no more walkable tiles left in the list.
If Set B have no elements, then the tile is NOT a chokepoint candidate, return false.
We now need to determine if the minimum shortest path distance between walkable tile pairs in disparate sets is greater than the given threshold T, for each set pair.
The step will help eliminate extra unneeded chokepoints, but can be skipped. Calculating the shortest path because it will go outside the
original adjacent 8 position of the candidate tile to find out if Calculate these shortest path assuming the the chokepoint is blocked.
Note that there is a maximal limit to the compares based on the original prior determinations
There is at MOST 6 walkable tiles from the original tiles adjacent to the candidate choke point. (because 2 were known to be non-walkable)
There is a minimum of two different sets, the maximum elements of one set being 5, the minimum being 1 Therefore the max number of shortest path
calculations is 9 (Assuming max number of tiles in different sets)
(Set A tile 1 to Set B tile 1)
(Set A tile 1 to Set B tile 2)
(Set A tile 1 to Set B tile 3)
(Set A tile 2 to Set B tile 1)
(Set A tile 2 to Set B tile 2)
(Set A tile 2 to Set B tile 3)
(Set A tile 3 to Set B tile 1)
(Set A tile 3 to Set B tile 2)
(Set A tile 3 to Set B tile 3)
You will need to abort some path calculations when the primary shortest path chain gets longer than T * (some other cutoff threshold value which is >= 1)
T represents how far of an alternate path a unit must walk to bypass the chokepoint and get from sub-zone A to sub-zone B. (or from A to C, A to D, B to C, B to D or C to D)
For each pair of sets, you should have the minimum shortest path between them. If ALL of these shortest paths are less than T
then the candidate chokepoint is mostly useless, and should NOT be considered viable, return false.
The Minimum value of T should be 2. and the maximum should be 6. Larger values of T will eliminate more candidate chokepoints.
For example, assume all tiles with a Y position <= A.Y are walkable, and that tiles > A.Y continue to separate tiles A and B. The shortest bath form A to B would be 6.
111
AXB
111
The last check: Minimum Land zone size. M
We want to make sure the size of our land sub-zones are sufficientlly large enough for the choke point to be important.
For example, let say we had four sub-zone sets
A1B
1X1
C1D
Assume that this happens to be an 3x3 island. Placing a chokepoint at position X is rather useless in this case, because the size of each of our sub-zones is only 1 tile.
If we assume it was the tail end of a peninsula. it is still useless, One sub-zone would be large but the other 3 still small. So we want to make sure at least 2
sub-zones land sizes are greater than M.
For each set choose the first tile in the set.
Count all contiguous walkable tiles radiating out from the set's tile. You don't have to count them all, stop once you reach M.
Set this count result as the land size value for this set.
If there is not at least 2 sets with a land size value = to M then
this tile is NOT a chokepoint candidate, return false.
If you have gotten this far, then the tile is a chokepoint.
Ok now, how do you expand it to consider 2 tile length choke points?
First remember than we are scanning top to bottom left to right for Y and X in map height and width.
When we are preparing to construct our bitmask:
If position 2 or 4 has been previously added to the chokepoint list, consider it to be non-walkable.
If position 2 is a non-walkable tile, and position 3 is walkable, pretend position 3 is non-walkable if and only if
tile(candidate tile.X, candidate tile.Y + 2) is a non-walkable tile.
If position 4 is a non-walkable tile and position 6 is walkable, pretend position 6 is non-walkable if and only if
tile(candidate_tile.X + 2, candidate_tile.Y) is a non-walkable tile.
Construct your bitmask as normal and continue with the rest of the previously described function.
---------------------------
Construct this list at the beginning of the map setup. These choke points are not going to change (however some might get flagged as "unimportant" or removed but none will be added)
the only major kink I can think of is if any mod using rising sea levels this might create or wash away some chokepoints.
If is washes them away, remove them from the list. (this is the only time they should get removed)
Don't bother trying to determine new ones though, by the time a global warming mod raises sea levels chokepoints
will mostly be a minor speed bump to any civ that is powerful, and its not worth recalculating anyway..
When does a chokepoint become important or unimportant to a civ?
A chokepoint location becomes important to a civ when they expand to within R range of a choke point site, and the choke is in neutral territory or inside their borders.
A chokepoint becomes unimportant when the a civ culturally controls P percent of all tiles surrounding a chokepoint up to range R.
An important choke point needs to be controlled, by the nearby civ, and have defending units squatting on it (and workers sent to it to build forts).
An unimportant choke point does not need defenders on it anymore. (or at the least, less defended on it)
What values should R and P be? I don't know that requires testing.
Each civ should have a list of "important chokepoints" that changes over the course of the came.
A chokepoint is a candidate site for building a city. (it's priority and weight relative to other nearby city sites however, may vary)
It is possible to identify chokepoints on water, by swapping the "walkable/non-walkable" state w/ water tile/land tile and using the function, but I am not sure if
one would want to both tracking water chokepoints. I would advise against it.
This algorithm won't be perfect by any means, there will be much tweaking required I am sure, to get the right balance.
I can for see some issues along the lines of tile arrangements like this:
11111111111
00000000000
11111111111
Technically every one of the walkable 0 tiles would get flagged as a chokepoint, but there doesn't really need to be that many of them in a row.in that scenario
only a few on the best terrain., This is where more culling functions would need to be expanded on.