2

添付の画像を使用して問題を説明します。

グリッド

緑のブロックは、私のゲーム エンティティの開始位置です。次に、オレンジ色の四角でマークされた位置に移動したいと思います。しかし同時に、浮揚が不可能である、または/&このブロックが壁であると仮定します。いずれにせよそこに行くことは不可能です。そのため、エンティティが移動できる最初の場所 (オレンジ色の四角にできるだけ近い場所) を見つける方法を見つける必要があります (この場合は、灰色の列の一番上か、オレンジ色の 2 行下のいずれかになります)。四角）。

私はグリッドを記述する 2 次元配列を持っています。ここで1は壁で、0空きスペースです。

data = [
    [1,1,1,1,...],
    [1,0,0,0,0,...],
    [1,0,0,...],
    ...
]

私はこの方法で解決策を考えていました（たとえば1.、セルの下が床であるかどうかを確認してアルゴを終了するか、セルでない場合は続行する2.ことができます）が、これを効率的に（そして簡単に）行う方法を考えることができません）。

ここに画像の説明を入力

誰もこれに取り組む方法を知っていますか? Googleにどのアルゴリズムを依頼すればよいかよくわかりません:)

4

2 に答える 2

1

Q 学習アルゴリズムを探しています。これは強化学習の一形態です。これはhttp://en.wikipedia.org/wiki/SARSAの 1 つです。

基本的に、ソースと宛先の間でシミュレーションを複数回実行し、そのたびに目標の発見に近づきます。

于 2013-05-24T01:26:11.730 に答える
0

手間をかける価値がある場合は、Cellular Automata を使用できると思います。それ自体は AI ではなく、実装が簡単で、1 つのロジックを使用して A* と最終的な位置検出の問題を置き換えることができます。

ゲーム エンティティの周囲の 8 つの近傍セルを考えてみましょう。各セルは、フリーまたはブロック (0 または 1) にすることができます。近傍には 2^8 通りの組み合わせがありますが、CA にそれだけ多くのルールを使用する必要がある場合とそうでない場合があります。

これを調べてみてください: http://www.cs.sun.ac.za/rw711/2012term1/documents/CABehringPathPlanning.pdf 彼らはロボティクスの経路計画のために CA を実装しました。必要に応じて微調整できます。

利点は、適切なルール セットを使用すると、ゲーム エンティティがゴール周辺の適切な位置 (ゴールに最も近く、浮上していない) に到達した場合にのみ CA が終了することです。

システムに複数のルール セットを実装することもできるため、より堅牢になります。

于 2013-05-24T07:55:42.697 に答える