A* can't find path in AI game

Question

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 lot of time on this assignment and have tried everything I could. So please help if you could.

The question is a rogue-like AI game in a grid format, one of the test cases is a map like the following:

~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~
~~   g**   d *~~
~~   ** *   * ~~
~~   **  ***  ~~
~~   **  d    ~~
~~   **    <  ~~
~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~

g=gold, d=dynamite, ~=water, *=wall, < is our agent, facing left.

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.

Due to the text formatting, there may appear some extra spaces between the walls in the diagonal direction, but there aren't any.

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.

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.

I'm stuck with the following issues:

1. A* search only gives me a path to the goal if it finds one. It doesn't give a "almost-there" path.
2. 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.

If anyone has any suggestions or good advice, please enlighten me. I haven't slept for two days...

Thanks for reading.

[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.

But, looking at the following maps, I'm speechless.....can anyone help?

A.

~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~
~g***       *** ~~
~***         d**~~
~**           *d~~
~*      ^      *~~
~**           **~~
~d**         **d~~
~ d**       **d ~~
~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~

B.

~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~
~~                  ~~
~~     ^            ~~
~~    ***           ~~
~~   *****          ~~
~~  ***g***         ~~
~~  ********        ~~
~~   ***dd***       ~~
~~    *****d**      ~~
~~     ***d*d**     ~~
~~      ******d*    ~~
~~       ********   ~~
~~        ********  ~~
~~         d*d**d*  ~~
~~          **d**   ~~
~~           ***    ~~
~~            *     ~~
~~                  ~~
~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~

Can anyone shed some light?, appreciated...

Answer 1

This is more than a path-finding problem, but it sounds like you are trying to use A* just for path finding. That's why it is failing.

Your A* search space needs to include state changes that involve picking up dynamite and using dynamite on a wall (which changes the connectivity of the map). In other words, you need to search the space of game states generated by all possible agent actions, not just agent movement.

To elaborate a tiny bit: the game state that A* uses should be the current map, the positions of all objects (including the agent), and the agent's dynamite inventory. State changes can include agent movement and (if the agent has dynamite) blowing up any wall segment the agent might be next to. The latter actions will result in successor states having a different map (as well as one less dynamite).

You can probably get fancy about saving space (and making state generation more efficient) by storing in each state only the changes to the map that resulted from using dynamite, rather than a copy of the entire map. Depending on how you represent the map, this could be as simple as storing additional edges representing additional connectivity between map locations resulting from the blast.