Databases
StackOverflow2013
Postsdbo
POA* can't find path in AI game
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POA* can't find path in AI game
    text
    copied!<p>I want to ask an assignment question. I know some people hesitate to give answers for this kind of questions, but believe me, I have spent a <em>lot</em> of time on this assignment and have tried everything I could. So please help if you could.</p> <p>The question is a rogue-like AI game in a grid format, one of the test cases is a map like the following:</p> <pre><code>~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~ ~~ g** d *~~ ~~ ** * * ~~ ~~ ** *** ~~ ~~ ** d ~~ ~~ ** &lt; ~~ ~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~ </code></pre> <p>g=gold, d=dynamite, ~=water, *=wall, &lt; is our agent, facing left.</p> <p>The rules are that the agent cannot move into the water nor the wall. It can only move to an empty square or to a d square to pick up a dynamite. It can then blast a wall with the dynamite. Once the dynamite is used, it can't be used again. The ultimate goal is to find the gold and pick it up. Agent can only move up and down or left and right. No diagonal moves.</p> <p>Due to the text formatting, there may appear some extra spaces between the walls in the diagonal direction, but there aren't any.</p> <p>So far I've used Depth First Search to explore the map. (This example map is quite small, there are some that are big). I've also used A* search to plan for paths, with manhattan distance as the heuristics. </p> <p>What's tricky about this map is that, A* search can't find a path to the goal, and the only solution is to first pick up the dynamite near the agent, and then blast the second wall to the right of the gold, then go right to pick up the second dynamite, and then go back to blast the last wall to the right of the gold, and then get the gold.</p> <p>I'm stuck with the following issues:</p> <ol> <li>A* search only gives me a path to the goal if it finds one. It doesn't give a "almost-there" path.</li> <li>I can use A* to search for the path either for the gold or the dynamite, but not both at the same time. It seems that, in this case, I need to search the best path for getting the dynamite first and then the gold, in one routine. That sounds tooo hard..Please tell me if that is the wrong direction.</li> </ol> <p>If anyone has any suggestions or good advice, please enlighten me. I haven't slept for two days...</p> <p>Thanks for reading.</p> <p>[EDITED 30/05] Well, I managed to use a trick to solve the above map. Basically search backwards from the gold, and assume if the first level neighbouring walls are clear and see if the agent can move there and also can pick up any dynamite from there. if both, then it's a through path.</p> <p>But, looking at the following maps, I'm speechless.....can anyone help?</p> <p>A.</p> <pre><code>~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~ ~g*** *** ~~ ~*** d**~~ ~** *d~~ ~* ^ *~~ ~** **~~ ~d** **d~~ ~ d** **d ~~ ~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~ </code></pre> <p>B.</p> <pre><code>~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~ ~~ ~~ ~~ ^ ~~ ~~ *** ~~ ~~ ***** ~~ ~~ ***g*** ~~ ~~ ******** ~~ ~~ ***dd*** ~~ ~~ *****d** ~~ ~~ ***d*d** ~~ ~~ ******d* ~~ ~~ ******** ~~ ~~ ******** ~~ ~~ d*d**d* ~~ ~~ **d** ~~ ~~ *** ~~ ~~ * ~~ ~~ ~~ ~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~ </code></pre> <p>Can anyone shed some light?, appreciated...</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload