Ведущий PacMan до точки

Question

Я пытаюсь создать AI PacMan. Последнее, что я отчаянно пытаюсь сделать, - это дать Pacman реальный путь от его текущей позиции к любой другой позиции. Сложность для меня в этом состоит в том, что, как вы все знаете, на его пути могут быть стены.

Вот пример (E= пустое поле, D= точка, P=Pacman, W= стена, X= путь):

Я получил эту карту Pacman в виде массива:

W-W-W-W-W-W-W
W-E-E-E-E-E-W
W-E-P-E-E-E-W
W-E-E-E-E-E-W
W-W-W-W-E-E-W
W-E-D-E-E-E-W
W-W-W-W-W-W-W

И я хочу иметь такой вывод:

W-W-W-W-W-W-W
W-E-E-E-E-E-W
W-E-P-E-E-E-W
W-E-X-X-X-E-W
W-W-W-W-X-E-W
W-E-D-X-X-E-W
W-W-W-W-W-W-W

Поэтому мне нужен массив, который показывает путь вокруг стен.

С помощью следующего кода я смог узнать расстояние до Манхэттена:

public static void ManhattanDist(int currentX, int currentY) {
    int[][] ratings = new int[5][5];
    int value = 0;
    for (int i = 0; i < ratings.length; i++) {
        value = Math.abs(i - currentX);
        for (int j = 0; j < ratings[i].length; j++) {
            ratings[i][j] = value + Math.abs(j - currentY);
            System.out.print("-" + ratings[i][j]);
        }
        System.out.println();
    }
}

Подобным образом я хочу найти реальный путь.

У кого-нибудь есть идеи? Я надеюсь, что вы, люди, можете мне помочь:D