Determining a choke point

[Dom Pedro II]

I'm trying to develop code that will determine whether a tile serves as a chokepoint to block movement from one part of a continent to another. I've tried to figure out a bunch of different ways to do this, but I can't think of any way to do this that won't involve a lot of code comparing all possible combinations of the adjacent plots.

But before I went and coded all of that, I figured I'd put the question to the people on the forum.

 

[Trojan Sheep]

This is the kind of challenge many AI programmers decide aren't worth the effort due to the amount of brute force programming it often requires.

A lot of how you implement this depends on the context you intend to use it in, but given a generic "AIs use defensive choke points" example, I would do the following.

Find/Run stock functions to pathfind routes from the AI in question's capital to each of their rivals on the same land mass.

Narrow down the selection to tiles that are past their outer most cities (relative to the rival being checked), but still within their cultural borders.

Check each of the remaining tiles for "chokepoint" status (look for barricades surrounding the tile that would prevent movement). How far out you extend this "chokepoint" verification will determine how effective they are, but by doing the first steps you are at the very least blocking the path most AIs would take. I don't know how frequently the AIs would find suitable chokepoints using this logic, but it might be worth a try.

Just my two pennies

 

[ClassicThunder]

Also if you do what Trojan is suggesting make sure it doesn't run every turn. Perhaps when a city is captured, destroyed, or created. Such a function will take a noticeable amount of time.

Also balancing them with the other weight pulling the AI would be horrible. A algorithm to do this would be difficult but possible. Fitting it into the game without breaking anything will be very difficult though.

 

[Dom Pedro II]

Hmm... I hadn't considered the more expanded view of determining the best chokepoints. I was merely looking to test whether a particular tile was the only way to pass from a tile on one side of it to a tile on the other side.

What I decided on was a system whereby the program looks at five tiles at a time:

OX
XO

##?
XOX

These, from my jotting down of numerous combinations, seem to be the only instances where there is a choke point.

If the upper left is passable and the tiles below it (the left tile) and the tile to the right of it (the upper tile) are impassable, that central tile we're checking must be a choke point, or if the upper tile is passable and the tile to the left and right of the central tile are impassable, it's a choke point.

Then you rotate the direction of your check for each of the cardinal directions, and it should catch any instances of a choke point.

Looking for choke points on a more strategic level sounds like it'd be much harder to do, and I think it's probably going to require more processing time than it's worth.

 

[Dom Pedro II]

I'm basically looking to improve how the AI places forts and cities. I wasn't terribly concerned with how the AI moves its armies.

That I think would require a lot of processing time. And ultimately, I think it would be unnecessary because since the tiles ARE choke points, the units are going to tend in that direction anyway.

 

[Trojan Sheep]

Well my point wasn't so much finding the "best" chokepoint, but rather finding one that will actually do something. If you just do a reading on every tile to determine if it is a chokepoint you'll end up with AIs blockading off their own peninsulas all over the place (even though they control all the land on either side of the blockade) and creating forts in the middle of their lands just because they happened to have a few mountains there.

For the purposes of just determining whether or not something is a chokepoint what you propose should work, although I would scan out at least two squares in every direction. If you assign each square relative to the target square a unique identifier it shouldn't be too difficult to hardcode in all the viable "chokepoint" combinations.

 

[Dom Pedro II]

Well my point wasn't so much finding the "best" chokepoint, but rather finding one that will actually do something. If you just do a reading on every tile to determine if it is a chokepoint you'll end up with AIs blockading off their own peninsulas all over the place (even though they control all the land on either side of the blockade) and creating forts in the middle of their lands just because they happened to have a few mountains there.

For the purposes of just determining whether or not something is a chokepoint what you propose should work, although I would scan out at least two squares in every direction. If you assign each square relative to the target square a unique identifier it shouldn't be too difficult to hardcode in all the viable "chokepoint" combinations.

Well, I'm not going to make choke points the only criteria for building forts. It will be one factor. So might it occasionally result in oddly placed forts on peninsulas? Yes. But never on a tile that would be very useful with some other improvement on it. Proximity to enemy borders will be very important to determining fort placement as well as the AreaAI type.

 

[Gaius Octavius]

Here's a similar take on the same idea, though a little outside your aim: what about assigning higher values to specific plots or cities like in the Civ 2 "objective" status? The idea is to get the AI to target these plots for attack/defense more readily than others.

This would have applications in scenarios where you could set chokepoints, major objectives, and fleet destinations as prime targets. The AI would resist letting them fall into enemy hands and would devote a greater portion of its attacking force to securing those plots first.

 

[Dom Pedro II]

Well, I could add in code for adding value to a plot. Unfortunately, my AI experience is limited, so I'm not really sure how to actually have the AI factor in a value into its decisions to move units, place cities, etc.

 

[cephalo]

Keep in mind that the map doesn't change a whole lot, so all the processing time you take to identify choke points only has to happen once.

What you can do is find basic choke points and mark them on a separate bitmap, then do seed fills on the bitmap to figure out how large each of the two regions that are blocked by the choke point.

Theres a seed fill algorithm in PerfectWorld that allows wrapping in the X direction. You can modify it for different criteria for blocking the fill. In this case you block water and chokpoints. A chokepoint touching two larger regions will be the more valuable, while chokepoints touching only one region aren't actually a chokepoint.

Then just keep the bitmap around for referencing.

 

[Dom Pedro II]

Thanks for the tip, cephalo.

I think that's the best way to go about this.

The only problem is that I think that different regions, even if they're only connected by one tile, are still considered part of the same continent. It would be fairly difficult then to calculate whether a choke point connects two different regions then as opposed to one since both would have the same Area.

 

[cephalo]

If you are implimenting your own seed filler, it is you who determines what an 'area' is or isn't. The reason I needed to write my own scheme was because I needed to include coast as part of a continent to determine which landmasses were separated by ocean.

Check out the Areamap class in PerfectWorld.py, it will do what you want with very little modification. It will fill a map with a different integer on each contiguous area it finds (not related to the 'Areas' in Civ), and also maintain a list of each area and it's size and whether it's land or water or in your case, also chokepoints and peaks. So if you set the map filler to block both chokepoints and water, the continent containing the chokepoint will be divided into two areas as far as the Areamap class knows. There are also some print functions useful for debugging so you can see how it's dividing up the map.

Here is the process you would use:

First you make your best guess on where the chokepoints are using your method above and mark them on the map array inside an Areamap class.

Then with the blocking criteria set you fill the map with what regions it finds, I think the function is called 'fillAreas' or something like that. It will use 4 connected neighbors for water and 8 connected neighbors for land.

Then for each of your guessed chokepoints, check what land areas they are touching and look up the sizes from the list in Areamap. If two of the areas are of acceptable size, then that's a good chokepoint. The other cases are that the chokepoint might be connected to zero land areas, one land area, or one large land area and other land areas that are only 3 or 4 tiles large, all of those cases can probably be discarded.

All of the information that you need will be in the Areamap class.

 

[EmperorFool]

It looks like cephalo has you covered once you have found the chokepoints, so I'll ramble a bit about finding them.

First, let's cover the crazy corner cases of triple- and quadruple-chokepoints (O is passable, X is impassable, which I think is what you used above, and # is the chokepoint):

XOX ... OXO
X#X ... X#X
OXO ... OXO​

This has the standard four rotational versions, and it doesn't happen very often. I see it mostly in the little crab-like peninsulas that SmartMap likes to generate -- even when you choose "Very Round; No Fragments" for the continent shape. Bah!

Because you can move diagonally, the 45 degree rotation of the above is not a triple-chokepoint, though it is a chokepoint.

OXX
X#O
XOX​

* I realized further down that there are more triple cases, but it doesn't matter in the end.

So the main thing I see is that if you start with one "side" of the bridge, there are two places for the tile: the corner or the side

O?? ... ?O?
?#? ... ?#?
??? ... ???​

As you rotate around the # from the O starting tile, corners require only one impassable tile before the other end of the bridge while sides require at least two. If the starting end of the bridge is "wider" than 1 tile, simply start from either edge of it.

OOX ... OXA ... A or B can be passable,
O#X ... O#O ... but the Xs cannot
OXO ... BXO​

While premature optimization is the root of all evil, it often helps to start there for ideas. If I were going to be testing a lot of map tiles for chokepointedness, I would consider building a table of possible layouts up front.

Conveniently, each tile has 8 adjacent tiles, each being either passable (1) or impassable (0). This gives a table of 256 8-bit adjacent tile passability values. Label the adjacent tile positions 0 through 7 and use them as the bit positions, for example:

012 ... XOO --> 01100010
7#3 ... X#X
654 ... OXX​

I went clockwise rather than row-wise so they would be easier to see visually, but it doesn't matter as long as you pick a way and stick with it. Also, I put 0 as the high bit which is backwards but unimportant.

Here you can see that 01100010 is obviously a chokepoint because both impassable runs have at least 2 tiles. In the case where you have a run of a single 0, you'll need to know if it separates two corner tiles (can be a chokepoint) or two side tiles (isn't). In fact, two side tiles with an impassable corner in between can be considered to be a single run of 3 passable tiles.

I did say "ramble" didn't I?

Now you have a way to turn a set of adjacent tiles into a table position by forming a binary number as above, you just need a way to evaluate the 1s and 0s to determine if it's a chokepoint. You could either do this manually (yuck!) for the 32 or so unique cases (32 * 2 mirrors * 4 rotations, total guess) or write an algorithm to do it.

The key is that you only have to build the table once. Then to test a tile, just convert the adjacent tiles' passability to an 8-bit index into the table. The table will simply be an array of 256 booleans.

Wow, I need to get out more. I hope that was helpful.

 

[Dom Pedro II]

Thank god this has sparked some interest because I'd hate to have to devote valuable brain power to figure out the math of this on my own!

 

[Red Key]

*Resurrect*

Did any solid code ever come from this? I want to improve the AI's use of choke points for my mod... I already asked in Kmod.

Google helped me find this thread and also this old choke point mini mod.

 

[Cruel]

*Resurrect*

Did any solid code ever come from this? I want to improve the AI's use of choke points for my mod... I already asked in Kmod.

Google helped me find this thread and also this old choke point mini mod.

The mini mod "choke point" sounds promising! A good point of start...

 

[Red Key]

Ok I have finished writing a code to determine choke and canal points and even taught the AI to use them for forts. There is one hurdle left to get it working - determine where to call the function. My code should only have to run once at the start of the game (unless the map is regenerated). Here are some places I have tried and the results:

CvMap::calculateAreas() - Bad place for random maps. The map isn't fully constructed when this runs. Impassable features are inserted later and don't get included in the choke point calculations.
CvMapGenerator::afterGeneration() - Bad place for scenarios and pre-made maps because they don't use this function. Great for random maps.
CvGame::setInitialItems() - Same as above.

Does anyone know a place in the SDK I could put my function call? If not then I'm thinking I need to expose it to python and call it from onGameStart() in CvEventManager, but putting it there might not work with map regeneration so I would also have to include it in one of those places that worked fine for random maps.

edit: I must not have been thinking. I could call my function from calculateAreas() for pre-made maps, and from one of the other spots for random maps. If someone knows a better spot I would still like to know.

edit2: Nevermind calculateAreas() does not work for pre-made maps either. So what I really need is a place that works for pre-made maps.

 

[embryodead]

CvGame::doTurn() with a condition that getElapsedGameTurns() == 0 ?
CvMap::doTurn() for a more logical place with same effect.

(that actually happens at the end of the first turn though)

 

[Red Key]

Thanks embryo! That way does work, but I would prefer if the calculations were done at the very beginning. I think I will call it from onGameStart in python.

 

[Tholal]

Thanks embryo! That way does work, but I would prefer if the calculations were done at the very beginning. I think I will call it from onGameStart in python.

Where is onGameStart called from the DLL? Looks like its called from regenerateMap(). Is there some reason to not put the chokepoint call there? I would think that regenerateMap() wouldn't be called for scenarios, but if that were the case, then onGameStart wouldn't be called either.