Algorithm to find shortest path through wall

Question

I am writing an AI for a text-based game and the problem I have is that I am stuck on how to determine the thinnest section of wall. For example the following represents the 2D map, where '^' is the character who wants to get through a wall represented by '*' characters to the location marked 'X':

------------------
|  X *           |
|*****           |
|****            |
|***             |
|**      ^       |
|                |
|                |
|                |
------------------

I've been thinking about this one for a couple days straight now and I've run out of ideas. I've tried using a* algorithm where when it tries to go through a wall character the g-cost made very high. Unfortunately the algorithm decides to never path-find through the wall.

The agent can only move left-right-up-down and not diagonally, one space at a time.

The shortest path in the above example through the wall is one, as it only has to travel through one '*' character.

I just need a couple simple ideas :)

Answer 1

All of the popular graph search algorithms are typically formulated with costs having some real number (i.e. float/double) cost. But this isn't a requirement. All you really need for the cost is something that has a strict ordering and operations like addition.

You could apply standard A* to this.

• Define the costs to have the form (a,b)
  • a is number of moves on wall cells
  • b is number of moves on normal cells.
• Define The ordering on these cells as follows:
  • [(a1,b1) < (a2,b2)] == [(a1<a2) || (a1==a2 && b1<b2)]
  • This is just a dictionary ordering where we always prefer less moves on walls before we prefer less moves on normal cells
• Define the addition operation on these costs as follows:
  • (a1,b1) + (a2,b2) == (a1+a2,b1+b2)
• Define the heuristic (i.e. the lower bound estimate on the remaining distance to goal) to be (0,b) where b is the Manhattan distance to the goal

---

One immediate objection might be "With that heuristic, the entire space outside of the wall will have to be explored before ever trying to pass through the wall!" -- But that's exactly what was asked for.

With the information and requirements you've given, that's actually the optimal A* heuristic.

---

A more complicated approach that could give significantly better best-case performance would be to combine the above with a bidirectional search. If your goal is inside of a tiny walled area, the bidirectional search can find some candidate "cheapest paths through the wall" very early on in the search.

Answer 2

Use Dijkstra.

Since you're dealing with a text-based game, I find it highly unlikely that you're talking about maps larger than 1000 by 1000 characters. This will give you the guaranteed best answer with a very low cost O(n*logn), and a very simple and straightforward code.

Basically, each search state will have to keep track of two things: How many walls have you stepped through so far, and how many regular empty spaces. This can be encoded into a single integer, for both the search and the mark matrix, by assuming for instance that each wall has a cost of 2^16 to be traversed. Thus, the natural ordering of Dijkstra will ensure the paths with the least walls get tried first, and that after traversing a wall, you do not repeat paths that you had already reached without going through as many walls.

Basically, assuming a 32-bit integer, a state that has passed through 5 empty spaces and 3 walls, will look like this: 0000000000000011 0000000000000101. If your maps are really huge, maze-like, tons of walls, few walls, or whatnot, you can tweak this representation to use more or less bits for each information, or even use a longer integers if you feel more comfortable with, as this specific encoding example would "overflow" if there existed a shortest path that required walking through more than 65 thousand empty spaces.

The main advantage of using a single integer rather than two (for walls/ empty spaces) is that you can have a single, simple int mark[MAXN][MAXM]; matrix to keep track of the search. If you have reached a specific square while walking through 5 walls, you do not have to check whether you could have reached it with 4, 3 or less walls to prevent the propagation of a useless state - this information will automatically be embedded into your integer, as long as you store the amount of walls into the higher bits, you will never repeat a path while having a higher "wall cost".

Here is a fully implemented algorithm in C++, consider it pseudo-code for better visualization and understanding of the idea presented above :)

int rx[4] = {1,0,-1,0};
int ry[4] = {0,1,0,-1};
int text[height][width]; // your map
int mark[height][width]; //set every position to "infinite" cost
int parent[height][width]; //to recover the final path

priority_queue<int64_t, vector<int64_t>, greater<int64_t> > q;
int64_t state = (initial_y<<16) + initial_x;
q.push(state);
while(!q.empty()){
    state = q.top(); q.pop();
    int x = state & 0xFF;
    int y = (state>>16) & 0xFF;
    int cost = state>>32;
    if(cost > mark[x][y]) continue;
    if(text[x][y] == 'X') break;
    for(int i = 0; i < 4; ++i){
        int xx = x+rx[i];
        int yy = y+ry[i];
        if(xx > -1 && xx < width && yy > -1 && yy < height){
            int newcost = cost;
            if(text[yy][xx] == ' ') newcost += 1;
            else newcost += 1<<16;
            if(newcost < mark[yy][xx]){
                mark[yy][xx] = newcost;
                parent[yy][xx] = i; //you know which direction you came from
                q.push( ((int64_t)newcost << 32) + (y<<16) + x);
            }
        }
    }
}
// The number of walls in the final answer:
// walls = state>>48;
// steps = (state>>32) & 0xFF; // (non walls)
// you can recover the exact path traversing back using the information in parent[][]

Answer 3

Just make it a weighted graph, and give all the "walls" an absurdly large weight.

Be careful not to overflow your integers.

Answer 4

Assuming any number of moves is always cheaper than going through the wall (meaning 10000000000 non-through-wall moves is cheaper than 1 through-wall move) (otherwise setting the cost appropriately would work), I can see a special case for any algorithm I can think of that does not involve searching practically the whole map, so...

• Do an exhaustive A* from the source, stopping at walls, recording the shortest path at each position.
• For each explored position next to a wall, step though the wall. Then do a combined A* of all of them (where applicable), again stopping at walls.
• For each of these new explored positions next to walls, step though the wall and continue the A*.
• And so on... until we find the target.

Skip already explored positions - the new path should always be longer than the one already there.

The only reason you really want to do an A* instead of a BFS is because this will allow for less exploring as soon when you reach the area containing the target. Whether this is more efficient will depend on the map.

As Sint mentioned, if the start is always in a wide open area and the finish is in a small area, reversing this search would be more efficient. But this is only really applicable if you know whether it is. Detecting it is unlikely to be efficient, and once you have, you've done most of the work already and you would've lost out if both are in reasonably-sized areas.

An example:

X** |
**  |
**  |
** ^|

Initial BFS:

X**3
**32
**21
**10

Step through the wall and BFS (no BFS happens since they have nowhere to go but through walls):
(the ones we can ignore are marked with %)

X*4%
*4%%
*3%%
*2%%

Step into wall and BFS (BFS onto target):

65%%
5%%%
4%%%
3%%%