Как найти самую узкую точку на пути между двумя ячейками в сетке
Я пишу бота для игры rts (одна деревня против другой на сетке, есть также перекрестные ячейки — трава, лесные и некроссируемые ячейки — вода, холмы). Как найти самую узкую точку на пути между этими двумя клетками? Любое предложение для алгоритма? (Я использую A *, чтобы найти ближайший путь, и я хочу, чтобы бот решал, куда поставить Башню (сильное оборонительное сооружение), чтобы поставить самую узкую точку, чтобы противник не мог пересечь — вероятно, может, зависит от карты, но менее возможно) ,
Решение
Некоторые идеи.
Подумайте о (может быть, слишком) упрощенной версии, в которой X обозначает не пересекающиеся ячейки. обозначает крестообразный, A обозначает деревню, а B обозначает другую.
XXXA.XXXXX
XXX..XXXXX
XX.....XXX
XXX....XXX
XXX...XXXX
XXX.....XX
XXXX....XX
XXXX.BXXXX
Поскольку на дороге, соединяющей две деревни, нет «ветки», мы можем перенести карту в
000A100000
0001100000
0011111000
0001111000
C0001110000D
0001111100
0000111100
00001B0000
на котором 0 и 1 означает стоимость проезда на сотовую связь. Самая узкая точка на дороге — это путь, который стоит минимум, чтобы добраться от C до D. Путь обозначен # на следующей карте
000A100000
##########
#01111100#
#00111100#
C#00111000#D
0001111100
0000111100
00001B0000
Поскольку только ячейки на «дороге» исходной карты стоят больше 0, кратчайший путь, сводящий к минимуму затраты между C и D, действительно даст подсказку о местонахождении «самой узкой точки» на дороге.
Ну, это просто упрощенная версия, так как есть только одна «главная дорога», соединяющая две деревни. Но я надеюсь, что это может как-то указывать правильное направление решения.
Другие решения
Имейте в виду, что это даже не обязательно то, что вы хотите. Рассмотрим башню T с дальностью атаки t
..t..
.ttt.
ttTtt
.ttt.
..t..
и карта ветвления, где есть один узкий прямой путь и один широкий косвенный путь от точки A В точку B, Предположим, непосредственные точки вокруг A отмеченный n можно ходить, но не для сборки башен.
xBxxxxxxx
x.......x
x.......x
x.......x
x..xx...x
x..xx...x
x..xx...x
x.......x
xnnn....x
xnnn....x
xAnxxxxxx
Изначально персонажи будут следовать по пути 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
размещение T в самой узкой точке вызовет 3 удара, если персонажи продолжат в том же пути. Но это не то, что произойдет, если боль в башне велика по отношению к цели скорости, например конечно если фатально. Вместо этого персонажи будут перенаправлены на более длинный путь.
xBxxxxxxx
xp......x
xppppp..x
x.t..p..x
xttxxp..x
xtTxxp..x
xttxxp..x
x.t..p..x
x....p..x
xppppp..x
xA.xxxxxx
Лучшее размещение в этом случае — это то, которое гарантирует как минимум один удар. (Имейте в виду, что самые лучшие места размещения T ближе к A предполагается, что не может быть построен.)
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
Итак, что вы можете захотеть, это размещение T что максимизирует стоимость пути минимальной стоимости, которая будет рассчитана после размещение T, Посмотрите на максимин (минимакс) алгоритмы. Конечно, есть и другие вещи, которые следует учитывать при размещении, такие как защита самой башни.