課題の質問をしたいです。この種の質問に答えるのをためらう人がいることは知っていますが、信じてください。私はこの任務に多くの時間を費やし、できる限りのことをしてきました。それで、できれば助けてください。
問題はグリッド形式のローグライク AI ゲームで、テスト ケースの 1 つは次のようなマップです。
~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~
~~ g** d *~~
~~ ** * * ~~
~~ ** *** ~~
~~ ** d ~~
~~ ** < ~~
~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~
g=金、d=ダイナマイト、~=水、*=壁、< は左向きのエージェントです。
ルールは、エージェントが水や壁に移動できないことです。ダイナマイトを拾うために移動できるのは、空いているマスまたはアド スクエアだけです。その後、ダイナマイトで壁を爆破することができます。ダイナマイトは一度使うと二度と使えません。最終的な目標は、金を見つけて拾うことです。エージェントは上下左右にしか移動できません。斜め移動はありません。
テキストのフォーマットにより、斜め方向の壁の間に余分なスペースが表示される場合がありますが、ありません。
ここまでは、Depth First Search を使用してマップを探索してきました。(この例のマップは非常に小さく、大きいものもあります)。また、ヒューリスティックとしてマンハッタン距離を使用して、A* 検索を使用してパスを計画しました。
このマップの厄介な点は、A* 検索ではゴールへの道が見つからないということです。唯一の解決策は、最初にエージェントの近くにあるダイナマイトを拾い、次にゴールドの右側にある 2 番目の壁を爆破することです。右に行って 2 番目のダイナマイトを拾い、次に戻って金の右側にある最後の壁を爆破し、金を手に入れます。
私は次の問題で立ち往生しています：
- * 検索は、ゴールが見つかった場合にのみ、ゴールへのパスを提供します。「ほぼそこにある」パスはありません。
- A* を使用して、金またはダイナマイトのパスを検索できますが、両方を同時に検索することはできません。この場合、最初にダイナマイトを取得し、次に金を取得するための最適なパスを 1 つのルーチンで検索する必要があるようです。それは難しすぎるように聞こえます..それが間違った方向であるかどうか教えてください.
誰か提案や良いアドバイスがあれば、私に教えてください。二日寝てない…
読んでくれてありがとう。
[2005 年 30 月 30 日編集] さて、私は上記のマップを解決するためにトリックを使用することができました。基本的にはゴールドから逆方向に検索し、最初のレベルの隣接する壁が空いているかどうかを想定し、エージェントがそこに移動できるかどうか、そこからダイナマイトを拾うことができるかどうかを確認します。両方の場合、それは通過パスです。
でも、以下の地図を見て言葉が出ません……誰か助けてくれませんか？
A.
~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~
~g*** *** ~~
~*** d**~~
~** *d~~
~* ^ *~~
~** **~~
~d** **d~~
~ d** **d ~~
~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~
B.
~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~
~~ ~~
~~ ^ ~~
~~ *** ~~
~~ ***** ~~
~~ ***g*** ~~
~~ ******** ~~
~~ ***dd*** ~~
~~ *****d** ~~
~~ ***d*d** ~~
~~ ******d* ~~
~~ ******** ~~
~~ ******** ~~
~~ d*d**d* ~~
~~ **d** ~~
~~ *** ~~
~~ * ~~
~~ ~~
~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~
誰か光を当てることができますか？