How to find the narrowest point in the path between two cells in a grid

Question

I am writing a bot for the rts game (one village against another on the grid map, there are also intersecting cells - grass, forests and disjoint cells - water, hills). How to find the narrowest point on the path between these two cells? Any suggestion for an algorithm? (I use A * to find the nearest path, and I want the bot to decide where to put the Tower (a strong defensive building) to put on the narrowest point that the enemy cannot cross against - maybe it depends on the map, but less possible).

Answer 1

Some ideas.

Think of a (possibly too large) simplified version on which X stands for disjoint cells. means cross, A denotes a village, and B means another.

XXXA.XXXXX XXX..XXXXX XX.....XXX XXX....XXX XXX...XXXX XXX.....XX XXXX....XX XXXX.BXXXX 

Since there is no “branch” on the road connecting the two villages, we can transfer the map to

  000A100000 0001100000 0011111000 0001111000 C0001110000D 0001111100 0000111100 00001B0000 

on which 0 and 1 means the cost of moving around the cell. The narrowest point on the road is the path that costs the minimum to move from C to D. The path is indicated by the # symbol on the next map.

  000A100000 ########## #01111100# #00111100# C#00111000#D 0001111100 0000111100 00001B0000 

Since only the cells on the “road” of the original map cost more than 0, the shortest path that minimizes the cost between C and D will really give the key to determining the location of the “narrowest point” on the road.

Well, this is just a simplified version, as there is only one “main road” connecting the two villages. But I hope that this can somehow point in the right direction to the solution.

Answer 2

Keep in mind that this is not even what you want. Consider a tower T with an attack range T

 ..t.. .ttt. ttTtt .ttt. ..t.. 

and a branching map, where there is one narrow direct path and one wide indirect path from point A to point B Suppose that the closest points around A marked by n are accessible, but not capable of building towers.

 xBxxxxxxx x.......x x.......x x.......x x..xx...x x..xx...x x..xx...x x.......x xnnn....x xnnn....x xAnxxxxxx 

Initially, the characters will follow the path p

 xBxxxxxxx xp......x xp......x xp......x xp.xx...x xp.xx...x xp.xx...x xp......x xp......x xp......x xA.xxxxxx 

Placing T at the narrowest point will result in 3 beats if the characters continue along the same path. But this is not what happens if the tower pain is high relative to the speed goal, for example. Of course if fatal. Instead, characters will be redirected to a longer path.

 xBxxxxxxx xp......x xppppp..x xt.p..x xttxxp..x xtTxxp..x xttxxp..x xt.p..x x....p..x xppppp..x xA.xxxxxx 

The best placement in this case is one that guarantees at least one hit. (Keep in mind that the best placements T closer to A are considered unremovable.)

 xBxxxxxxx x.......x x.......x x.......x x..xx...x x..xx...x x.txx...x xttTtt..x x.ttt...x x..t....x xA.xxxxxx 

So, you may need a T placement that maximizes the cost of the minimum cost path that will be calculated after the T placement. Look at the maximin (minimax) algorithms. Of course, there are other things that should be considered when placing, for example, the security of the tower itself.