A* Pathfinding Java не работает должным образом

Question

Я создаю игру "Лабиринт" в Java и хочу добавить хитрого призрака (такого как Пакман), который двигается в сторону пользователя, чтобы поймать его. Для Smarty Ghost я выбрал алгоритм A* PathFinding и нашел ниже ссылки для реализации этого алгоритма:

https://code.google.com/p/a-star/source/browse/trunk/java/PathFinder.java?r=8

https://code.google.com/p/a-star/source/browse/trunk/java/AStar.java?r=8

Но код работает не совсем правильно, я имею в виду, что код, кажется, только находит пути, идущие сверху вниз слева направо, а не, например, слева направо слева направо вниз.

например:

если

 source = (0,0)
 Destination = (8,8)     // works perfectly..

если

  source = (8,8)
  Destination = (0,0)     // doesn't  work :(

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

Answer 1

Я думаю, что проблема в этой части кода:

protected List<Node> generateSuccessors(Node node){
                List<Node> ret = new LinkedList<Node>();
                int x = node.x;
                int y = node.y;
                if(y < map.length - 1 && map[y+1][x] == 1)
                                ret.add(new Node(x, y+1));

                if(x < map[0].length - 1 && map[y][x+1] == 1)
                                ret.add(new Node(x+1, y));

                return ret;
}

Этот код возвращает список соседей для текущего узла, однако он только пытается вниз и в правильном направлении. Попробуйте добавить соответствующий код для любых других направлений, которым вы хотите следовать, например,

if(y > 0 && map[y-1][x] == 1)
                ret.add(new Node(x, y-1));
if(x > 0 && map[y][x-1] == 1)
                ret.add(new Node(x-1, y));