У моего путеводителя проблемы с поиском кратчайшего пути

У меня проблемы с путеводителем (это мой первый, так что этого следовало ожидать): он не всегда выбирает кратчайший путь. Например, если я хочу перейти на один квадрат вниз, путь будет таким: один квадрат влево, один вниз, один вправо.

public void getSquares(){
        actPath = new String[Map.x][Map.y];
        isDone = new boolean[Map.x][Map.y];
        squareListener = new SquareListener[Map.x][Map.y];
        getSquares2(x,y,0,new String());
    }
    public void getSquares2(int x, int y, int movesused, String path){
        boolean test1 = false;
        boolean test2 = false;
        test1 = (x < 0 || y < 0 || x > Map.x || y > Map.y);
        if(!test1){
            test2 = Map.landTile[y][x].masterID != 11;
        }
        if(movesused <= 6 && (test1 || test2)){
            addMoveSquare2(x,y, path);
            getSquares2(x+1,y,movesused+1,path+"r");
            getSquares2(x,y+1,movesused+1,path+"d");
            getSquares2(x,y-1,movesused+1,path+"u");
            getSquares2(x-1,y,movesused+1,path+"l");
        }
    }
    public void addMoveSquare2(int x, int y, String path){
        if(x >= 0 && y>=0 && x < Map.x && y < Map.y && (actPath[x][y] == null || actPath[x][y].length() > path.length())){
            if(squareListener[x][y] == null){
                actPath[x][y] = new String();
                actPath[x][y] = path;
                JLabel square = new JLabel();
                square.setBounds(x*16,y*16,16,16);
                square.setIcon(moveSquare);
                squareListener[x][y] = new SquareListener(x,y,path);
                square.addMouseListener(squareListener[x][y]);
                Map.cases.add(square);
            }
            else{
                squareListener[x][y].path = path;
            }
        }
    }

SquareListener — это простой MouseListener, который печатает местоположение квадрата и путь к нему. Map.x, Map.y — размер карты. getSquares2 вызывается с начальной точкой и рисует все квадраты, которые находятся на расстоянии 6 шагов, и рассматривает каждый случай со значением «11» как препятствие.

Не могли бы вы помочь мне найти, что я сделал неправильно?

Вот скриншот результата: http://img808.imageshack.us/img808/96/screen.gif Возможная цель — красные квадраты. Настоящий будет определен только тогда, когда игрок нажмет на один квадрат (MouseListener является SquareListener, он должен знать путь). Дома - это ящики со значением «11», препятствия.


java recursion path-finding
person Cheshire    schedule 29.06.2010    source источник
comment
Если это домашнее задание в классе, принято добавлять тег «домашнее задание».   -  person Jim Garrison    schedule 30.06.2010
comment
Выложите исходники всей программы.   -  person Fredrick Pennachi    schedule 30.06.2010
comment
Это не домашнее задание. Навигатор — это всего лишь часть программы. Что мне нужно добавить?   -  person Cheshire    schedule 30.06.2010

Ответы (3)


arrow_upward
2
arrow_downward

Ваш алгоритм выглядит почти правильным. Почти потому, что вы забываете назначить actPath[x][y] при обнаружении второго пути к узлу, что делает вашу проверку длины неверной с actPath[x][y]. Ты должен сделать:

        else{
            actPath[x][y] = path;             
            squareListener[x][y].path = path;
        }

Ваш алгоритм также имеет отвратительную временную сложность, так как он будет перебирать все пути длиной 6 (все 4 ^ 6 = 4096 из них) вместо самых коротких (6 * 6 + 5 * 5 = 61)

Для вдохновения я рекомендую взглянуть на алгоритм Дейкстры (предшественник A*), который удается посетить только самые короткие пути и завершается в O (количество достижимых узлов), когда длины пути являются небольшими целыми числами, как здесь.

person meriton    schedule 29.06.2010
comment
Большое спасибо ! Это действительно было проблемой. Я постараюсь сделать это лучше. - person Cheshire; 30.06.2010

arrow_upward
0
arrow_downward

Вас может заинтересовать этот руководство на Алгоритм поиска A*.

person Daniel Pryden    schedule 29.06.2010
comment
Спасибо за ссылку, однако у меня не 1 гол, а несколько ходов, что дает много возможных голов. Разве это не делает H of F = G + H непригодным для использования? - person Cheshire; 30.06.2010
comment
@Cheshire: я не уверен, что понимаю, но если у вас есть несколько возможных целей и вы просто хотите найти ближайшую, похоже, вам может понадобиться алгоритм Дейкстры (по сути, где H = 0). В нижней части этого руководства есть немного информации, или вы можете найти страницу Википедии полезной: en.wikipedia .org/wiki/Dijkstras_algorithm - person Daniel Pryden; 30.06.2010
comment
Я добавил изображение, чтобы сделать его более понятным. - person Cheshire; 30.06.2010
comment
Ссылка сейчас не работает, есть резервная копия? - person Travis; 12.02.2020

arrow_upward
0
arrow_downward

Вы можете посмотреть здесь мой ответ с примером кода для A-Star, а не прямым ответ, но код читаем, и он указывает вам на хорошую книгу, которая посвящена (среди прочего) поиску пути. Я так и не удосужился прокомментировать код...

Не уверен, что вы имеете в виду в комментарии для Даниэля: «Спасибо за ссылку, однако у меня не 1 гол, а несколько ходов, что делает много возможных голов».

person TofuBeer    schedule 29.06.2010