java - 在2d char数组中生成随机路径的算法

Question

我正在尝试在二维char数组中生成从一个点到另一个点的随机路径,但是它遵循以下规则:

• 唯一允许的字符是:
  • O =开放路径
  • -=接受来自左侧或右侧的路径
  • |=接受来自顶部或底部的路径
  • \=接受来自路径:顶部到左,左到顶部,底部,以右和右至底部.
  • /=接受来自路径:底部到左,左到底,右到顶部,并且顶部到右
  • "接受路径"意味着其他路径(/-|\)只能从特定的边连接.

这是一个了解字符及其作用的图像:( -红色,\蓝色,/绿色,|橙色)

• 路径不能跨越自己 - 它只能进入开放的地方(开放路径:) O.想象一下结果路径就像蛇,这个心爱的游戏 - 它无法通过它自己.
• 2d阵列可以是任何大小
• 结尾可以在任何地方引导 - 它没有标记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

或者(地图大小为6):

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

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

提前致谢!

PS:在你问之前,不,这不是一个功课问题.

编辑:我更新了我的代码,现在该方法确实返回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();
    }

我可以在输出中看到它到达它的最终destenation,但它没有显示开始.这是为什么？

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

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已经包含xand y，即你在 , 中添加and x2y次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;