パスは、Linuxで「ニブル」ゲームに似ているヘビのゲームがある

Question

（私の弱い英語のための最初で、申し訳ありません）

Javaでの2Dゲームのために見つけます。

ゲーム機能の一部!:

-theボードが壁に囲ま60 * 60のフィールドであり、そしていくつかの壁はあまりにもボードにあります。

は、（1蛇のための各プログラム）

-timeは、次の動きは0.1秒であるかを決定する。4人のプログラマはそれらの移動方法を見つけるためのプログラムを記述する必要があります4匹のヘビを-thereあるので、我々は見つける必要がありますそれは0.1秒前です。さもなければ、ヘビは前の方向に行くでしょう。

-Snake's headは、壁や他のヘビに当たってはいけません。

-Snakeが後方に移動してはいけません（それは反則だと持っているマイナスポイント）

...............

壁のcoordiationが私たちに与えられている

ゲーム（x、y）で。ゲーム

の その他のヘビのcooardiationは、すべてのサイクルで私たちに与えられている（0.1秒）...............

今の質問は次のとおりです。どのように最良の動きを見つけるか？

アルゴリズムを提案して助けてもらえますか？

ありがとうございます。

あなたはここでゲームのスクリーンショットを見ることができます：

Answer 1

ほとんどの人は非常によく、ウェブ上で文書化されているA *パス発見アルゴリズムのようなものを提案しようとしていると私はあなたが行く提案をこれらの提案のいずれかを検索します。あなたがしなければならないことは、与えられた制約内でうまく働くように、これらのアルゴリズムを変更することです。 （A *を提案し、0.1秒の制限を無視することはそれほど役に立ちません）。

もその潜在的な次の移動があり、私はあなたが

• あなたがパスを探している、あなたは障害物として他の蛇や壁だけでなく、検討すべき検討すべきだと思ういくつかのポイントがありますが、 。あなたは次の動きで蛇の頭が衝突するのを望んでいません。これは頭​​を追跡する必要があります。

• 時間がなくならないように、パス検索を特定の深さまで制限する必要があります。 A *アルゴリズムを使用する場合は、ヒューリスティック要素によってほとんどのパスが移動先の方向に移動することになります。あなたが近づくと、次の検索が潜在的に簡単になります。

• ポイントの選択はそれほど簡単ではありません。たとえば、他のヘビにレースをしているので、最も近いポイントを選択するだけではいけません。知っているか、最初に得ることができると思うポイントを選んでみてください。あなたは単にヘビとすべてのポイントとの間の距離を測定することができます。お互いのヘビが彼らに最も近いポイントを探していて、あなたが近くにいるので、あなたがそれらを打つことができるかどうかを見ていると考えてください。あなたが勝つことができると思うポイントを選びなさい。

• 障害物があると、後方への動きを防ぐことができます。