私はrtsゲームのボットを書いています（グリッドマップ上の別の村に対する1つの村、また、交差可能なセル - 草、森 - および交差不可能なセル - 水、丘）があります。これらの 2 つのセル間のパスで最も狭いポイントを見つける方法は? アルゴリズムの提案はありますか? (私は A* を使用して最も近いパスを見つけており、タワー (強力な防御建物) を配置する場所をボットで決定し、敵が横切ることができないように最も狭いポイントに配置したいと考えています - おそらく可能です。マップによって異なりますが、可能性は低くなります) .
質問する
275 次
2 に答える
4
いくつかのアイデア。
X が交差不可能な細胞 . A は crossable を表し、A は村を表し、B は別の村を表します。
XXXA.XXXXX
XXX..XXXXX
XX.....XXX
XXX....XXX
XXX...XXXX
XXX.....XX
XXXX....XX
XXXX.BXXXX
2 つの村を結ぶ道路には「分岐」がないため、マップを次の場所に転送できます。
000A100000
0001100000
0011111000
0001111000
C0001110000D
0001111100
0000111100
00001B0000
0 と 1 は、セルを移動するためのコストを意味します。道路の最も狭いポイントは、C から D への移動に最小のコストがかかる経路です。この経路は、次のマップで # で示されています。
000A100000
##########
#01111100#
#00111100#
C#00111000#D
0001111100
0000111100
00001B0000
元のマップの「道路」上のセルのみが 0 より大きいため、C と D の間のコストを最小化する最短経路は、道路上の「最も狭い点」の位置の手がかりを実際に与えます。
2 つの村を結ぶ「幹線道路」は 1 つしかないため、これは単純化したバージョンにすぎません。しかし、それが何らかの形で解決策の正しい方向を示してくれることを願っています.
于 2012-10-29T00:53:34.270 に答える
2
これは必ずしもあなたが望むものではないことに注意してください。T攻撃範囲のあるタワーを考えるt
..t..
.ttt.
ttTtt
.ttt.
..t..
Aそして、ポイントからポイントへの 1 つの狭い直接パスと 1 つの広い間接パスがある分岐マップ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
この場合のより良い配置は、少なくとも 1 つのヒットを保証する配置です。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に計算される最小コスト パスのコストを最大化する の配置が必要になる場合があります。maximin (minimax) アルゴリズムを調べます。もちろん、タワー自体の防御性など、配置に関して考慮すべき点は他にもあります。T
于 2012-10-29T15:27:42.867 に答える