Java - Algorithm for generating random path in 2d char array

Question

I am trying to create a random path from point to another in a 2-dimensional char array, but therefore it will follow these rules:

• Only the following characters are allowed:
  • O = Open Path
  • - = accepts paths to the left or right of it
  • | = accepts paths above or below
  • \ = takes paths from: from top to bottom, from left to right, from bottom to right and from right to down.
  • / = takes paths from: bottom to left, left to right, right to top and top to bottom
  • "Accepts paths" means that other paths ( /-|\ ) can connect only from the sides associated with them.

Here is an image to understand the symbols and what they do: ( - in red, \ in blue, / green, | orange)

• A path cannot cross itself - it can only work in open places (Open paths: O ). Imagine that the path of the result is like a snake, your favorite game - it cannot go through itself.
• 2d array can be any size
• The final can be conducted anywhere - it is not marked with X or any other symbol, but it must go somewhere logical.

Correct outputs:

Start: (0, 0), End: (3, 3)

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

The first example is basically this:

Start: (1, 0), End: (1, 4)

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

The second example is basically this:

I am trying to execute this with this code, but for some reason it does not work:

Code:

 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; } 

When I run the code using this code,

 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); } } 

It displays incorrect and illogical paths, for example:

 OOOO O/OO O-OO O-OO 

Or (with card size 6):

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

I do not know why this is happening. Can someone tell me what is wrong with my code and help me solve this?

Thanks in advance!

PS: Before asking, no, this is not a homework question.

EDIT: I updated my code and now the method returns true and it reaches the end, but there is a problem. My updated code:

 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; } 

My main code is:

 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(); } 

I see in the output that he reaches the final definition, but does not show the beginning. Why is this?

Here are some examples from the new updated code:

 OOOO O/OO O/OO O--- OOOO O//- OO/O OOO| 

As you can see, the outputs still do not make sense, but they are closer than before: P This does not exactly comply with the rules and does not show the beginning. Why is this?

Answer 1

I see some errors (I did not run your code).

1. The main problem is that you probably mixed the x and y coordinates in your logic and displayed, try changing

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

to something like

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

those. loop change through x and y coordinates for output

2. Probably, you incorrectly calculated the following coordinates from x, y in the avilableMovement function. lx and ly already contain x and y , i.e. you add x and y 2 times in 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. You do not return the “O” sign for the cell if the path is not found in the current cell, and you do not check the following possible move:

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

Answer 2

Here is another idea for your consideration. Starting with a simple path, for example, right along the x axis, then right along the y axis (or vice versa) from start to finish,

 start--\ | | | \end 

we can change the path using a predefined options dictionary. For any cell that is between two others in the path (which excludes the start and end cells), we define 6 possibilities, each of which has two ways to change it. The following two examples only deal with a change in the middle cell, x :

 (1) cell is connected from west and east: oxo we can move x either north or south: / x \ oo or oo \ x / (2) cell is connected from west and south: ox o we can move x either north or east: / x o | or o - x oo / 

Since the cells cannot be connected diagonally, there are only 4 choose 2 = 6 configurations. We can easily create a dictionary of options for a random attempt, based on the delta configurations of the cells along the way. Two examples above:

 (dictionary key) (dictionary value) Δx1 Δy1 Δx2 Δy2 1 0 -1 0 => try north or south 1 0 0 -1 => try north or east