我在使用探路器时遇到了问题(这是我的第一个,所以这是意料之中的):它并不总是采用最短路线。例如,如果我想向下走一格,路径将是:左一格,下一格,右一格。
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 是 map 大小。 getSquares2 以起点调用,绘制每一个距离为 6 步的方格,并将每个值为“11”的情况视为障碍。
你能帮我找出我做错了什么吗?
结果截图如下: http://img808.imageshack.us/img808/96/screen.gif 红色方 block 是可能的目标。只有当玩家点击一个方 block 时才会定义真正的方 block (MouseListener 是 SquareListener,它应该知道要走的路径)。房屋是值为“11”的案例,即障碍物。
最佳答案
您的算法看起来几乎正确。几乎是因为当找到到节点的第二条路径时您忘记分配 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)
为了获得灵感,我建议查看 Dijkstra's algorithm (A* 的前身),当路径长度是小整数时,它设法仅访问最短路径并在 O(可达节点数)中得出结论。
关于java - 我的探路者在寻找最短路径时遇到问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3144822/