Generate random path on a 5x5

Newbie & Debugging Questions
#1

Well.
I have a 5x5 matrix, like this one


0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Or maybe like this one (doesn’t matter)


1  2  3  4 5
6  7  8  9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

I want to generate a random path of a length. ( 3>length>22 lets say)
You can only go left right up and down. You can’t cross the path, or go back.

Examples


// random path of length 5
0 0 0 1 0
0 0 0 2 0
0 0 4 3 0
0 0 5 0 0
0 0 0 0 0



// random path of length 9
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
8 7 4 3 2
9 6 5 0 1



// random path of length 6
1 2 3 0 0
0 5 4 0 0
0 6 0 3 0
0 0 0 0 0
0 0 0 0 0

Something like

public List CreateRandomPath(int length)
{
// magic
return the list.
}

The list could be something like 1 2 3 4 (list of numbers)
This would represent the ‘cell’ of the matrix like here


1  2  3  4 5
6  7  8  9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

ex: 1 would be the first one, 25 the last one, like in that matrix above
Or a Vector2 list, where every point in the path would have the x and y position.
ex: 1,1 would be the first cell, 4,4 the last one…

I hope someone understand :smiley:

#2

This sort of a problem can be approached in many ways.
Not sure how much thought you gave to this but essentially there will be times when you can’t step as much as you would like to because you get trapped.
Getting trapped happens because you will be surrounded by tiles that you have used before and since you can’t step on them again there will be no tile to move to.
You can handle this problem 2 ways: Allow in these situations to to move on a tile where you have already been, or stop movement. :point:

Other than that the other thing that requires a bit of thought is that when you generate random movement you should only be able to move to valid tiles (aka, you shouldn’t move outside of your matrix’s length because you’ll get IndexOutOfBoundsException).

Both of these problem are easily solvable and here’s an implementation that stops movement when getting trapped, in less than a 100 lines:

package your.package.here;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class RandomPath {
	
	public enum Movement{
		LEFT, RIGHT, UP, DOWN
	}
	
	public static class Vector2{
		public Vector2(int x, int y){
			this.x = x;
			this.y = y;
		}
		public int x;
		public int y;
	}
	
	private static final int MIN_PATH_LENGTH = 4;
	private static final int MAX_PATH_LENGTH = 21;
	private static final int yourMatrix[][] = new int[5][5];
	private static final Random random = new Random();
	private static final List<Vector2> path = new ArrayList<Vector2>();
	private static int x = 0;
	private static int y = 0;
	
	public static void main(String[] args){
		// Gives a random value between MIN_PATH_LENGTH and MAX_PATH_LENGTH
		int pathLength = MIN_PATH_LENGTH + random.nextInt(MAX_PATH_LENGTH-MIN_PATH_LENGTH+1);
		// Add the starting position to the path
		path.add(new Vector2(x, y));
		// Generate a random path
		for(int i = 0; i < pathLength-1; i++){
			Movement movement = randomMovement();
			if(movement == null) break;
			switch(movement){
				case UP:
					y += 1;
					break;
				case DOWN:
					y -= 1;
					break;
				case LEFT:
					x -= 1;
					break;
				case RIGHT:
					x += 1;
					break;
			}
			path.add(new Vector2(x, y));
		}
		// Print out our path
		System.out.println("Path length: "+pathLength);
		System.out.println("Real path length: "+path.size());
		System.out.print("Path: ");
		for(int i = 0; i < path.size(); i++){
			Vector2 v = path.get(i);
			System.out.print("["+v.x+", "+v.y+"]");
			if(i < path.size()-1) System.out.print(", ");
		}
	}
	
	// Checks if the tile has not been used before
	private static boolean isUntouched(int x, int y){
		for(Vector2 v : path){
			if(v.x == x && v.y == y) return false;
		}
		return true;
	}
	
	// Generate a VALID random movement
	private static Movement randomMovement(){
		List<Movement> movementSet = new ArrayList<Movement>();
		if(x > 0 && isUntouched(x-1, y))
			movementSet.add(Movement.LEFT);
		if(x < yourMatrix.length-1 && isUntouched(x+1, y))
			movementSet.add(Movement.RIGHT);
		if(y > 0 && isUntouched(x, y-1))
			movementSet.add(Movement.DOWN);
		if(y < yourMatrix[0].length-1 && isUntouched(x, y+1))
			movementSet.add(Movement.UP);
		if(movementSet.size() == 0) return null;
		return movementSet.get(random.nextInt(movementSet.size()));
	}
	
}

The code is not heavily documented but there are some comments here and there.
If you have any questions feel free to ask me. :slight_smile:

#3

Why sometimes the real path length is smaller than the length i’ve choosen?
Because it gets stuck?

I got an ideea but i’m not sure how to implement it and if it works.

If you get stuck, you will need to go back, and choose not go go on the position that didn’t worked…

Maybe something like an backtracking version?

#4

Backtracking is way too advanced for such a simple problem.

You should simply discard the path, and attempt a new one.

#5

The real path length is smaller than the chosen path length when the path generator gets “trapped”.
I’ve explained that in my previous comment:

As Riven said for such a simple thing you probably don’t need backtracking, it’s enough if you discard the track if it gets trapped and generate a new one.

#6

You definitely need backtracking if the path is much longer then 5.
e.g. Try to find a random path of length 25 on a 5x5 board. If you always discard the entire path once you reach a dead end, it’s gonna take forever to get a solution.
Backtracking only discards as much of the path as necessary and is therefore much faster.
Here is the most simple backtracking algorithm I could come up with to solve your problem.


import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class RandomPath {
  static int[][] matrix = new int[5][5];
  static List<int[]> movements = Arrays.asList(
    new int[] {1, 0}, //right
    new int[] {-1, 0}, //left
    new int[] {0, 1}, //down
    new int[] {0, -1}); //up
  
  public static void main(String[] args) {
    //a list of all the possible start positions
    ArrayList<int[]> startPositions = new ArrayList<>();
    for(int x = 0; x < matrix.length; x++) {
      for(int y = 0; y < matrix[0].length; y++) {
        startPositions.add(new int[] {x, y});
      }
    }
    Collections.shuffle(startPositions);
    for(int[] pos: startPositions) {
      if(findPath(pos[0], pos[1], 25, 1)) break;
    }
    printMatrix();
  }
  
  static void printMatrix() {
    for(int y = 0; y < matrix[0].length; y++) {
      for(int x = 0; x < matrix.length; x++) {
        if(x > 0) System.out.print(",");
        if(matrix[x][y] < 10) System.out.print(" ");
        System.out.print(matrix[x][y]);
      }
      System.out.println();
    }
  }
  
  //recursive method that uses backtracking to find a path
  //x, y: where to go next
  //maxN: target length of path
  //n: current length (actually the length of the path once x,y has been set to n)
  //returns true if a path has been found
  static boolean findPath(int x, int y, int maxN, int n) {
    //if x,y is outside the matrix or it's already part of the path we can return false
    if(x < 0 || x >= matrix.length ||
       y < 0 || y >= matrix[0].length || matrix[x][y] != 0) return false;
    matrix[x][y] = n;
    if(n == maxN) return true; // target length reached
    Collections.shuffle(movements);
    for(int[] move: movements) {
      if(findPath(x + move[0], y + move[1], maxN, n+1)) return true;
    }
    //if no path was found we backtack
    //i.e. we remove x, y from the path and return false
    matrix[x][y] = 0;
    return false;
  }
}
#7

Thank you it works perfectly, but can you add some explications to it ? :smiley:

#8

I think this problem would be quite interesting on a slightly larger grid than 5x5, so heuristics to avoid getting stuck in corners would became worthwhile.

But would it break the requirement to be a “random” path if it played the percentages to aim for faster completion? :stuck_out_tongue:

#9

I added some comments to the code.
You could also read this to help you understand backtracking better.

#10

Thank you, I already understand backtracking, and some algorithms like Prim’s algorithm, and more, i’ve learned in school like 1 year ago.