내 경로 찾기에서 최단 경로를 찾는 데 문제가 있습니다

Question

경로 찾기에 문제가 있습니다 (내 첫 번째 경로이므로 예상 한 것입니다.) 항상 최단 경로를 차지하지는 않습니다. 예를 들어 하나의 정사각형을 아래로 이동하려면 경로가 왼쪽에 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가 시작점과 함께 호출되고 여섯 개의 이동 거리 인 모든 사각형을 그립니다. 값 "11"인 모든 경우를 장애물로 간주합니다.

내가 잘못한 것을 찾는 것을 도와 줄 수 있습니까?

다음은 결과 스크린 샷입니다. http://img808.imageshack.us/img808/96/screen.gif 빨간색 사각형이 가능한 목표입니다. 실제 하나는 플레이어가 하나의 사각형을 클릭 할 때 정의됩니다 (MouseListener는 SquareListener이므로 걸릴 경로를 알고 있어야합니다). 주택은 장애물 인 "11"값을 가진 경우입니다.

Answer 1

알고리즘이 거의 비슷합니다. 거의 노드의 두 번째 경로가 발견되면 actPath[x][y]을 지정하는 것을 잊었 기 때문에 actPath[x][y]으로 길이를 확인하는 것이 잘못되었습니다. 당신이해야 할 :

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

알고리즘이 대신 단지 짧은 것들 (6 * 6의 (모두 4^6 = 4096) 길이 6의 모든 경로를 반복하므로 또한, 가증스러운 시간 복잡도를 가지고 + 5 * 5 = 61)

영감을 얻으려면 경로 길이가 작은 정수일 때 최단 경로 만 방문하고 도달 가능한 노드 수를 결론 짓는 Dijkstra's algorithm (A *의 전조)을 살펴 보는 것이 좋습니다. 여기의 경우처럼.

Answer 2

tutorialA* search algorithm에 관심이 있으실 것입니다.

Answer 3

당신은 A-Star의 예제 코드로 직접 대답이 아니지만 코드가 읽기 쉽고 (다른 많은 것들 중에서) 경로 찾기를 다루는 좋은 책을 가리킨다 고 생각하면 here을 볼 수 있습니다. 코드에 대한 주석 달기를 결코 잊지 못했습니다.

Daniel에 대한 코멘트에서 "링크 고마워."라는 말에 무슨 뜻인지 확실하지 않지만 1 점을 얻지 만 여러 가지 움직임이 있습니다. 가능한 많은 목표를 세우고 있습니다. "