SelfAvoidingWalk.java

Below is the syntax highlighted version of SelfAvoidingWalk.java from §2.4 Case Study: Percolation.

/*************************************************************************
 *  Compilation:  javac SelfAvoidingWalk.java
 *  Execution:    java SelfAvoidingWalk N
 *  Dependencies: StdDraw.java
 *
 *  Simulate and animate a self-avoiding walk in two dimensions. Follow
 *  trajectory of 2D random walk until it walks back in on itself or
 *  reaches the boundary. Always choose a direction that won't hit itself
 *  if possible.
 *
 *  This random process produces a biased SAW. To produce an unbiased
 *  SAW, need to generate a 2D random walk (choosing each of the 4
 *  directions with equal likelihood) and start over from scratch
 *  if it self-intersects.
 *
 *  % java SelfAvoidingWalk 16
 *
 *  % java SelfAvoidingWalk 32
 *
 *************************************************************************/

public class SelfAvoidingWalk { 

    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);

        StdDraw.setXscale(0, N);
        StdDraw.setYscale(0, N);

        // draw many self-avoiding random walks
        while (true) {
           StdDraw.clear();
           boolean[][] visited = new boolean[N][N];

           // starting position
           int x = N / 2;
           int y = N / 2;
           visited[x][y] = true;


           // make a random move as long as particle is not boxed in
           while (!visited[x-1][y] || !visited[x+1][y] || !visited[x][y-1] || !visited[x][y+1]) {
     

               // try until you find an available move
               while (true) {
                   double r = Math.random();
                   if      (r < 0.25 && !visited[x-1][y]) { x--; break; }
                   else if (r < 0.50 && !visited[x+1][y]) { x++; break; }
                   else if (r < 0.75 && !visited[x][y-1]) { y--; break; }
                   else if (r < 1.00 && !visited[x][y+1]) { y++; break; }
                }
                visited[x][y] = true;

                // draw
                StdDraw.filledSquare(x + 0.5, y + 0.5, .45);
                StdDraw.show(25);

                if (x <= 0 || x >= N-1 || y <= 0 || y >= N-1) break;    // hit outside boundary
            }
            StdDraw.show(1000);
        }
    }
}