java - 在二维字符数组中生成随机路径的算法

Question

我试图在二维字符数组中生成从一个点到另一个点的随机路径，但它会遵循以下规则:

• 唯一允许的字符是:
  • O = 开放路径
  • - = 接受来自左边或右边的路径
  • | = 接受来自顶部或底部的路径
  • \ = 接受从以下路径:top to left, left to top，底部到右边，右边到底部。
  • / = 接受从以下路径:bottom to left, left to bottom，右到上，上到右
  • “接受路径”意味着其他路径 (/-|\) 只能从指定的边连接。

这是一张图片来理解字符及其作用:(- 红色，\ 蓝色，/ 绿色，| 橙色)

• 路径不能跨越自身——它只能在空旷的地方(开放路径:O)。将结果路径想象成贪吃蛇，它无法通过自己。
• 二维数组可以是任意大小
• 结尾可以通往任何地方 - 它没有标有 X 或任何类似的字符，但它必须到达合乎逻辑的地方。

正确的输出:

开始:(0, 0)，结束:(3, 3)

START-> - - \ O
        O O \ \
        O / - /
        O \ - \ <- END

第一个例子基本上是这样的:

开始:(1, 0)，结束:(1, 4)

START v
    O - \ O O
    / - / O O
    \ - - - \
    O O O O |
    O - - - / 
      ^ END

第二个例子基本上是这样的:

我正在尝试使用这段代码来完成此操作，但由于某种原因，它无法正常工作:

代码:

int x, y, mapsize;
char[][] map;
public Random rand = new Random();
public boolean findPath(int x, int y, int xGoal, int yGoal){
    if(x==xGoal&&y==yGoal)return true;
    int[] avilableMovement = avilableMovement(x, y);
    if(avilableMovement==null)return false;
    int moveX = avilableMovement[0];
    int moveY = avilableMovement[1];
    map[moveX][moveY]=mark(x, y, moveX, moveY);
    if(findPath(moveX, moveY, xGoal, yGoal))return true;
    return false;
}
public char mark(int fromX, int fromY, int toX, int toY){
    //If moved to up/down and <>, mark |
    //If moved to <> and left/right, mark -
    //If moved to up and left, or to down and right, mark \
    //If moved to up and right, or to down and left, mark /
    boolean toUp = fromY<toY;
    boolean toDown = fromY>toY;
    boolean toRight = fromX<toX;
    boolean toLeft = fromX>toX;
    if((toUp||toDown)&&!(toLeft||toRight)){
        return '|';
    }
    if((toLeft||toRight)&&!(toUp||toDown)){
        return '-';
    }
    if((toUp&&toLeft)||(toDown&&toRight)){
        return '\\';
    }
    if((toUp&&toRight)||(toDown&&toLeft)){
        return '/';
    }
    return '?';
}
private boolean onMap(int x, int y){
    return x>0&&y>0&&x<mapsize&&y<mapsize;
}
private int[] avilableMovement(int x, int y){
    ArrayList<Integer> numsX = new ArrayList<>(Arrays.asList(-1+x, 0+x, 1+x));
    ArrayList<Integer> numsY = new ArrayList<>(Arrays.asList(-1+y, 0+y, 1+y));
    Collections.shuffle(numsX);
    Collections.shuffle(numsY);
    //^^ Making it random instead of going in same order every timee
    for(int lx : numsX){
        for(int ly : numsY){
            if(onMap(y+ly, x+lx)&&map[y+ly][x+lx]=='O'){
                return new int[]{x+lx, y+ly};
            }
        }
    }
    return null;
}

当我使用这段代码运行代码时，

private void initMap(int mapsize){
    this.mapsize=mapsize;
     map = new char[mapsize][mapsize];
    for(int i = 0; i<mapsize; i++){
        for(int j = 0; j<mapsize; j++){
            map[i][j]='O';
        }
    }
}
public static void main(String[] args){
    Main main = new Main();
    main.initMap(4);
    System.out.println(main.findPath(0, 0, 3, 3));
    for(char[] ch : main.map){
        System.out.println(ch);
    }
}

它不断输出错误和不合逻辑的路径，例如:

OOOO
O/OO
O-OO
O-OO

或者( map 大小为 6):

OOOOOO
O/OOOO
O-OOOO
OOO/OO
OOOOOO
OOOOOO

我不知道为什么会这样。谁能告诉我我的代码有什么问题并帮助我解决这个问题？

提前致谢!

P.S:在你问之前，不，这不是作业问题。

编辑:我更新了我的代码，现在该方法确实返回了 true 并且它到达了结尾，但是有一个问题。我更新的代码:

public Random rand = new Random();
public boolean findPath(int x, int y, int xGoal, int yGoal){
    if(x==xGoal&&y==yGoal)return true;
    int[] avilableMovement = avilableMovement(x, y);
    if(avilableMovement==null)return false;
    int moveX = avilableMovement[0];
    int moveY = avilableMovement[1];
    map[moveX][moveY]=mark(x, y, moveX, moveY);
    if(findPath(moveX, moveY, xGoal, yGoal))return true;
    return false;
}
public char mark(int fromX, int fromY, int toX, int toY){
    //If moved to up/down and <>, mark |
    //If moved to <> and left/right, mark -
    //If moved to up and left, or to down and right, mark \
    //If moved to up and right, or to down and left, mark /
    boolean toUp = fromY<toY;
    boolean toDown = fromY>toY;
    boolean toRight = fromX<toX;
    boolean toLeft = fromX>toX;
    if((toUp||toDown)&&!(toLeft||toRight)){
        return '|';
    }
    if((toLeft||toRight)&&!(toUp||toDown)){
        return '-';
    }
    if((toUp&&toLeft)||(toDown&&toRight)){
        return '\\';
    }
    if((toUp&&toRight)||(toDown&&toLeft)){
        return '/';
    }
    return 'O';
}
private boolean onMap(int x, int y){
    return x>0&&y>0&&x<mapsize&&y<mapsize;
}
private int[] avilableMovement(int x, int y){
    ArrayList<Integer> numsX = new ArrayList<>(Arrays.asList(-1+x, x, 1+x));
    ArrayList<Integer> numsY = new ArrayList<>(Arrays.asList(-1+y, y, 1+y));
    Collections.shuffle(numsX);
    Collections.shuffle(numsY);
    //^^ Making it random instead of going in same order every timee
    for(int lx : numsX){
        for(int ly : numsY){
            if(onMap(ly, lx)&&map[ly][lx]=='O'){
                return new int[]{lx, ly};
            }
        }
    }
    return null;
}

我的主要代码:

Main main = new Main();
    main.initMap(4);
    boolean b = main.findPath(0, 0, 3, 3);
    while(!b)b = main.findPath(0, 0, 3, 3);
    for(int i = 0; i<main.mapsize; i++){
        for(int j = 0; j<main.mapsize; j++){
            System.out.print(main.map[j][i]);
        }
        System.out.println();
    }

我可以在输出中看到它到达了最终目的地，但没有显示开始。这是为什么？

以下是新的更新代码的一些示例输出:

OOOO
O/OO
O/OO
O---

OOOO
O//-
OO/O
OOO|

如您所见，输出仍然没有意义，但它比以前更接近了 :P 它没有完全遵循规则，也没有显示开头。这是为什么？

Answer 1

我发现了几个错误(我没有运行你的代码)。

1.主要问题是您可能在逻辑和输出到屏幕中混合了 x 和 y 坐标，尝试更改

for(char[] ch : main.map){
    System.out.println(ch);
}

类似于

for(int i = 0; i<mapsize; i++){
    for(int j = 0; j<mapsize; j++){
        System.out.print(map[j][i]);
    }
    System.out.println();
}

即改变输出的 x 和 y 坐标循环

2.您可能错误地从函数 avilableMovement 中的 x,y 计算了下一个坐标。 lx 和 ly 已经包含 x 和 y，即您添加 x 和 y 2 次 x+lx, y+ly:

ArrayList<Integer> numsX = new ArrayList<>(Arrays.asList(-1+x, 0+x, 1+x));
ArrayList<Integer> numsY = new ArrayList<>(Arrays.asList(-1+y, 0+y, 1+y));
Collections.shuffle(numsX);
Collections.shuffle(numsY);
for(int lx : numsX){
    for(int ly : numsY){
        if(onMap(y+ly, x+lx)&&map[y+ly][x+lx]=='O'){
            return new int[]{x+lx, y+ly};

3.如果在当前单元格中找不到路径，则不会为单元格返回“O”标记，并且不会检查下一个可能的移动:

map[moveX][moveY]=mark(x, y, moveX, moveY);
if(findPath(moveX, moveY, xGoal, yGoal))return true;
return false;