2

パスファインダーに問題があります (これは私の初めてのことなので、当然のことでした) : 常に最短の道をたどるとは限りません。たとえば、1 マス下に移動したい場合、パスは 1 マス左、1 マス下、1 右になります。

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 赤い四角が可能な目標です。実際のものは、プレーヤーが 1 つの正方形をクリックしたときにのみ定義されます (MouseListener は SquareListener であり、たどるパスを知っているはずです)。家屋は、値が「11」のケースで、障害物です。

4

3 に答える 3

2

あなたのアルゴリズムはほぼ正しいようです。actPath[x][y]ほとんどの場合、ノードへの 2 番目のパスが見つかったときに割り当てを忘れたため、長さチェックがactPath[x][y]正しく表示されません。やったほうがいい：

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

あなたのアルゴリズムには、最短のパス (6*6 + 5*5 = 61) だけでなく、長さ 6 のすべてのパス (すべて 4^6 = 4096) を反復するため、時間の複雑さもありません。

インスピレーションを得るために、 Dijkstra のアルゴリズム(A* の前身) を参照することをお勧めします。このアルゴリズムは、パスの長さが小さい整数の場合、最短のパスのみを訪問し、O(到達可能なノードの数) で終了します。

于 2010-06-29T22:12:31.327 に答える
0

ここで、A-Starのサンプルコードを使用した私の回答を見ることができます。直接の回答ではありませんが、コードは読みやすく、（他の多くのことの中でも）パスファインディングを扱った優れた本を示しています。私はコードにコメントすることを決して回避しませんでした...

ダニエルへのコメントで、「リンクをありがとう。しかし、私には1つのゴールはありませんが、多くの可能性のあるゴールを作る多くの動きがあります」とあなたが何を意味するのかわかりません。

于 2010-06-29T21:55:54.780 に答える
0

A* 検索アルゴリズムに関するこのチュートリアルに興味があるかもしれません。

于 2010-06-29T21:23:57.210 に答える