Converting coding challenge 'Self-avoiding walk backtracing' from p5.js to Processing (Java)

Hi my friends,
I am trying to learn coding challenge Self-avoiding walk backtracing from Denial’s video 26:40 ; And converting the P5.js code to processing(java) code. But my code seems it is struggling on getting the array right and null pointer. Can anyone help me to figure out the problem?

Step[] allOptions = 
{
  new Step(1, 0), new Step(-1, 0), new Step(0, 1), new Step(0, -1)
};

Spot spot;

ArrayList<Spot> path = new ArrayList<Spot>();

Spot[][] grid;
int spacing = 20;
int cols, rows;

boolean isValid(int i, int j)
{
  if(i < 0 || i >= cols || j < 0 || j >= rows)
  {
    return false;
  }
  return !grid[i][j].visited;
}

void setup()
{
  size(400, 400);
  cols = floor(width / spacing)+1;
  rows = floor(height / spacing)+1;
  background(0);
  
  grid = new Spot[cols][rows];
  for(int i = 0; i < cols; i++)
  {
    for(int j = 0; j < rows; j++)
    {
      grid[i][j] = new Spot(i, j);
    }
  }
  spot = grid[0][0];
  path.add(spot);
  spot.visited = true;
}

void draw()
{

  spot = spot.nextSpot();
  if(spot == null)
  {
    ArrayList<Spot> stuck = new ArrayList<Spot>();
    for(int i = path.size()-1; i >= 0; i--)
    {
      path.remove(i);
    }
    
    for(Spot sp: path)
    {
      stuck.add(sp);
    }
    stuck.clear();
    
    for(int i = path.size()-1; i >= 0; i--)
    {
      spot = path.get(i);
    }
  }
  else
  {
    path.add(spot);
    spot.visited = true;
  }
  
  if(path.size() == cols*rows)
  {
    println("Solved!");
    noLoop();
  }
  
  stroke(250, 0, 160);
  strokeWeight(spacing*0.25);
  noFill();
  beginShape();
  for(int i = 0; i < path.size(); i++)
  {
    vertex(path.get(i).x, path.get(i).y);
  }
  endShape();
  
  stroke(250, 160, 0);
  strokeWeight(spacing * 0.5);
  point(spot.x, spot.y);

}

class Spot
{
  int x, y;
  int i, j;
  boolean visited;
  Step[] options;
  
  
  Spot(int _i, int _j)
  {
    i = _i;
    j = _j;
    x = i * spacing;
    y = j * spacing;
    options = new Step[allOptions.length];
    for(int i = 0; i < options.length; i++)
    {
      options[i] = allOptions[i];
    }
    visited = false;
  }

  void Clear()
  {
    visited = false;
    for(int i = 0; i < options.length; i++)
    {
      options[i] = allOptions[i];
    }
  }
  
   Spot nextSpot()
  {
    ArrayList<Step> validOptions = new ArrayList<Step>(); 
    for(Step option: options)
    {
      int newX = i + option.dx;
      int newY = j + option.dy;
      if(isValid(newX, newY) && !option.tried)
      {
        validOptions.add(option);
      }
      println("newX: "+newX, "newY: "+newY);
    }
    println("valid options.size: " + validOptions.size());
    if(validOptions.size() > 0)
    {
      int index = int(random(validOptions.size()-1));
      Step step = validOptions.get(index);
      step.tried = true;
      return grid[i+step.dx][j+step.dy];
    }
    return null;
  }
}

class Step
{
  int dx, dy;
  boolean tried;
  
  Step(int x, int y)
  {
    dx = x;
    dy = y; 
    tried = false;
  }
}

Hi @GoToLoop ,
Thanks for the reply!
I have read the p5js version, but I can not figure out to convert it to processing code. I definately make some mistakes, but I can not figure them out. I wonder if someone can help to change it to processing java.

In the original p5js version validOptions is a function which returns an array w/ 4 instances of Step:

But in your converted Java Mode version it is just an array not a function:

Also your attempt of emulating method Array::pop():

Using Java’s List::remove() mixing w/ loops doesn’t seem to be working.

BtW, I’ve ended up making my own conversion attempt and posted it online:

1 Like

Another version, this time named “Self Avoiding Walk II”, which implements a more aggressive backtracking based on the age of each Spot inside container path, so it has a better chance to unstuck itself:


“index.html”:

<script defer src=https://Unpkg.com/processing-js></script>

<canvas data-processing-sources=
  "Self_Avoiding_Walk_II.pde Functions.pde Spot.pde Step.pde">
</canvas>
1 Like

Hi @GoToLoop ,
Thanks for your replay and help.
Your code is absolutely so much help and it is incrediable. And the openprocessing web editor is brilliant and it can declare static method with in, my current process IDE can not, except adding .java files.
I don’t know much about javascript and am quite newbie, so as you point out my code drops some important idea of the original code on the conversion.
With your advice and help, I figure out my problem

And I borrowed your code

 static final Step[] allDirections() {
    return new Step[] {
      new Step(1, 0), new Step(-1, 0), new Step(0, 1), new Step(0, -1)
    };
  }

My one is finally working, but it seems it will be stuck at some point quite long :joy: it definately has other problems :joy:

// Self Avoiding Walk (Basic)
// The Coding Train / Daniel Shiffman
// https://thecodingtrain.com/CodingChallenges/162-self-avoiding-walk.html
// https://www.youtube.com/watch?v=m6-cm6GZ1iw

// Basic: https://editor.p5js.org/codingtrain/sketches/2_4gyDD_9
// With Backtracking: https://editor.p5js.org/codingtrain/sketches/dRWS3A9nq
// 3D: https://editor.p5js.org/codingtrain/sketches/D0ONOlCDT
// With Bezier: https://editor.p5js.org/codingtrain/sketches/KFbX0NWgh
// With Recursion: https://editor.p5js.org/codingtrain/sketches/UPxBk1YiB
// Random Walk with Alpha: https://editor.p5js.org/codingtrain/sketches/IEw2RkDnJ


Spot[][] grid;
int spacing = 40;
ArrayList<Spot> path = new ArrayList<Spot>();
int cols, rows;
Spot spot;

boolean isValid(int i, int j)
{
  if(i < 0 || i >= cols || j < 0 || j >= rows)
  {
    return false;
  }
  else
  {
    return !grid[i][j].visited;
  }
}

void setup()
{
  size(400, 400);
  cols = floor(width / spacing)+1;
  rows = floor(height / spacing)+1;
  background(0);
  //frameRate(1);
  
  grid = new Spot[cols][rows];
  for(int i = 0; i < cols; i++)
  {
    for(int j = 0; j < rows; j++)
    {
      grid[i][j] = new Spot(i, j);
    }
  }
  spot = grid[0][0];
  path.add(spot);
  spot.visited = true;
}

void draw()
{
  background(0);
  
  for(int i = 0; i < 5000; i++)
  {
    spot = spot.nextSpot();
    if(spot == null)
    {
      int len = path.size();
      path.remove(len-1).Clear();
      println("N_Path size: " + path.size());
      
      spot = path.get(len-2);
    }
    else
    {
      path.add(spot);
      spot.visited = true;
      println("Path size: "+path.size());
    }
    
    if(path.size() == cols*rows)
    {
      println("Solved!");
      noLoop();
      break;
    }
  }
  
  stroke(250, 0, 160);
  strokeWeight(spacing*0.25);
  noFill();
  beginShape();
  for(Spot sp: path)
  {
    vertex(sp.x, sp.y);
  }
  endShape();
  
  stroke(250, 160, 0);
  strokeWeight(spacing * 0.5);
  point(spot.x, spot.y);
}

Step[] allOptions()
{
  return new Step[] {new Step(1,0), new Step(0,1), new Step(0,1), new Step(0,-1)};
}

class Spot
{
  int x, y;
  int i, j;
  boolean visited;
  Step[] options = new Step[4];
  
  
  Spot(int _i, int _j)
  {
    i = _i;
    j = _j;
    x = i * spacing;
    y = j * spacing;
    options = allOptions();
    printArray(options);
    visited = false;
  }

  void Clear()
  {
    for(Step sp: options)
    {
      sp.tried = false;
    }
    visited = false;
  }
  
   Spot nextSpot()
  {
    ArrayList<Step> validOptions = new ArrayList<Step>(); 
    for(Step option: options)
    {
      int newX = i + option.dx;
      int newY = j + option.dy;
      if(isValid(newX, newY) && !option.tried)
      {
        validOptions.add(option);
        //println("validoptions.size: " + validOptions.size());
      }
      println("newX: "+newX, "newY: "+newY);
    }
    println("validoptions.size: " + validOptions.size());
    if(validOptions.size() > 0)
    {
      int index = int(random(validOptions.size()-1));
      Step step = validOptions.get(index);
      println("index: " + index);
      println("valid options.size: " + validOptions.size());
      step.tried = true;
      return grid[i+step.dx][j+step.dy];
    }
    else
    {
      println("F_validoptions.size: " + validOptions.size());
      return null;
    }
  }
}

class Step
{
  int dx, dy;
  boolean tried;
  
  Step(int x, int y)
  {
    dx = x;
    dy = y; 
    tried = false;
  }
}

 path.add(spot = grid[rows >> 1][cols >> 1]);

rows >> 1

cols >> 1

btw what does this kind of expression mean?

The bitwise right shift operator moves all bits of a value ‘x’ times:

Each right shifting halves the value; so >> 1 is equivalent to / 2, >> 2 is / 4, and so on.

The advantage of using the operator >> in place of / is that the former guarantees the result is always a whole number (truncated division) when the code is transpiled to run on the web from Java (Processing library) to JS (Pjs library).

1 Like

I’ve coded everything in Processing IDE (PDE) version 3.5.4.

So if you click the download icon from my online sketch and transfer those files to the offline PDE it should just run.

Inside “.pde” files all classes we create are nested.

In order to have static methods inside a nested class its class has to be declared static as well.

On the other hand, top-level classes inside “.java” files are naturally static already.

1 Like

Thanks for the reference link, much appreciated

sorry my mistake, I should say mix use of the static and non-static in the same class :joy: thanks for this

I got a question.

I understand that the backtracking algorithm is recursive.

In Java processing a recursive function wouldn’t update the screen throughout. How come it is updated here?

Is it that you can update the screen throughout in p5 or is it just not really recursive?

The approach taken by Daniel Shiffman in his Coding Challenge #162 YouTube video isn’t recursive.

In my 1st version of it (“Self Avoiding Walk I”), the main algorithm happens here:

void getNextSpot() {
  spot = spot.nextSpot(grid);

  if (spot != null) {
    path.add(spot);
    spot.visited = true;
  } else {
    final int len = path.size();
    path.remove(len - 1).clear();
    spot = path.get(len - 2);
  }

  if (path.size() == matrix) {
    println("Solved!");
    finished = true;
  }
}

As you can see, function getNextSpot() never calls itself as we woulda expected from a recursive 1.

The way it works is like a stack, pushing & popping from the container’s tail index:

  • Method Spot::nextSpot() attempts to find a valid non-visited Spot from within array grid[][].
  • If successful, that found Spot is add() to path’s tail; and its Spot::visited state becomes true.
  • Otherwise, the previous Spot is remove() from path’s tail and its state is reset by calling method Spot::clear(); and then variable spot is updated to point to the now current Spot tail:
  Spot clear() {
    for (final Step step : options)  step.tried = false;
    visited = false;
    return this;
  }

I believe callback draw() needs to finish before p5js sketch’s canvas is updated.

1 Like

Thank you so much for this good explanation!

:wink:

Decided to convert my sketch to Python Mode too: :snake:

“Self_Avoiding_Walk_II.pyde”:

"""
 * Self Avoiding Walk II [with Backtracking]
 * Coding Challenge #162
 * by The Coding Train / Daniel Shiffman
 *
 * https://TheCodingTrain.com/CodingChallenges/162-self-avoiding-walk.html
 *
 * Python Mode conversion by GoToLoop (2022/Feb/22) (v1.0.5)
 *
 * https://Discourse.Processing.org/t/
 * converting-coding-challenge-self-avoiding-walk-backtracing-
 * from-p5-js-to-processing-java/35047/15
 *
 * OpenProcessing.org/sketch/1475931
"""

from functions import *

removals = 0

def setup():
    size(650, 500)
    noFill()

    createGrid()
    states[BG] = randomColor()


def draw():
    if states[FINISHED]: return

    states[REMOVED] and removeTailSpotIfTooOld()
    states[REMOVED] or  getNextSpot()

    global removals
    removals += states[REMOVED] and 1 or -removals
    removals == Spot.MAX_STRAIGHT_REMOVALS and resetAllSpotsAgesFromPath()

    drawGridPath()
    drawTrailPoint()


def mousePressed():
    if mouseButton == LEFT:
        states[PAUSED] ^= True
        noLoop() if states[PAUSED] else loop()
    elif mouseButton == RIGHT:  states[BG] = randomColor()
    elif mouseButton == CENTER: createGrid()
    else: saveFrame()


def randomColor(): return int(random(Spot.ALL_COLORS))

“functions.py”:

from spot import Spot

REMOVED, PAUSED, FINISHED, BG = 'removed', 'paused', 'finished', 'bg'
states = { REMOVED: False, PAUSED: False, FINISHED: False, BG: 0 }

path = []

def createGrid():
    rows = height // Spot.SPACING
    cols = width  // Spot.SPACING

    global grid, spot, path, matrix

    matrix = rows * cols
    states[FINISHED] = states[REMOVED] = False

    grid = tuple(tuple(Spot(r, c) for c in range(cols)) for r in range(rows))

    spot = grid[rows >> 1][cols >> 1]
    spot.visited = True

    path *= 0
    path.append(spot)


def resetAllSpotsAgesFromPath():
    for spot in path: spot.age = frameCount


def removeTailSpotIfTooOld():
    states[REMOVED] = frameCount - spot.age >= Spot.AGE_THRESHOLD
    if states[REMOVED]: removeTailSpotFromPath(); rejuvenateAllSpotsFromPath()


def removeTailSpotFromPath():
    states[REMOVED] = len(path) >= 2
    states[REMOVED] and path.pop().clear()

    global spot
    spot = path[-1]


def rejuvenateAllSpotsFromPath():
    size = len(path) - 1
    if not size: return

    for i in range(size + 1):
        path[i].age += round(map(i, 0, size, 1, Spot.AGE_INCREASE))


def getNextSpot(DONE = 'Solved!'):
    global spot
    spot = spot.nextSpot(grid)

    if spot:
        path.append(spot)
        spot.visited = True
        states[REMOVED] = False

    else: removeTailSpotFromPath();

    if len(path) == matrix:
        print DONE
        states[FINISHED] = True


def drawGridPath():
    background(states[BG])
    translate(Spot.HALF_SPACE, Spot.HALF_SPACE)

    strokeWeight(Spot.QUARTER_SPACE)
    stroke(Spot.PATH_STROKE)

    with beginShape():
        for spot in path: vertex(spot.x, spot.y)


def drawTrailPoint():
    strokeWeight(Spot.HALF_SPACE)
    stroke(Spot.TRAIL_STROKE)
    point(spot.x, spot.y)

“spot.py”:

from step import Step

class Spot:
    AGE_THRESHOLD = 200
    AGE_INCREASE = 5
    MAX_STRAIGHT_REMOVALS = 200

    SPACING = 10
    HALF_SPACE = SPACING * .5
    QUARTER_SPACE = SPACING * .25

    PATH_STROKE = -1
    TRAIL_STROKE = 0xffFFA000
    ALL_COLORS = (0xff << 0o30) - (1 << 0o40)

    def __init__(s, row, col):
        s.x = col * s.SPACING
        s.y = row * s.SPACING

        s.c = col
        s.r = row

        s.visited = False
        s.age = frameCount

        s.options = Step.allDirections()


    def clear(s):
        for step in s.options: step.tried = False
        s.visited = False
        s.age = frameCount
        return s


    def nextSpot(s, grid, dirs = []):
        rr = len(grid)
        cc = len(grid[0])

        valid = Step.isValid2
        dirs *= 0

        for step in s.options:
            r = s.r + step.y
            c = s.c + step.x
            not step.tried and valid(grid, r, c, rr, cc) and dirs.append(step)

        size = len(dirs)
        if not size: return

        step = dirs[int(random(size))]
        step.tried = True

        return grid[s.r + step.y][s.c + step.x]

“step.py”:

class Step:
    def __init__(s, x, y):
        s.x = x
        s.y = y
        s.tried = False


    @staticmethod
    def allDirections():
        return Step(1, 0), Step(-1, 0), Step(0, 1), Step(0, -1)


    @staticmethod
    def isValid(grid, r, c):
        return\
        0 <= r < len(grid) and\
        0 <= c < len(grid[r]) and\
        not grid[r][c].visited


    @staticmethod
    def isValid2(grid, r, c, rows, cols):
        return 0 <= r < rows and 0 <= c < cols and not grid[r][c].visited
1 Like

This is brilliant !!!

Hi @GoToLoop

I wonder if this one

removals += removed? 1 : -removals;

is equivalent

if (removed) { removals += 1;}
else { removals -= 1; }

you can test it yourself.

My guess

if (removed) { 
   removals += 1;
}
else { 
  removals +=  -removals;   // which is 0 I guess
 }
2 Likes
  • I’m back w/ another “Self Avoiding Walk II” conversion.
  • This time I’m using the CoffeeScript language which directly transpiles to JavaScript.
  • Processing 2 used to have a CoffeeScript Mode a long time ago and I’ve ended up learning it.
  • When I later decided to learn Python Mode to help folks here I’ve relied on my previous CoffeeScript knowledge b/c they have similar syntax.
  • The old CoffeeScript Mode relied on the Pjs library in order to run its transpiled sketch on the web.
  • Which by the way is the same lib that transpiles a Java Mode sketch to JS.
  • But I also wanted to use p5js & even q5js to run my latest conversion.
  • So why not make the new CoffeeScript sketch compatible w/ all those 3 libraries?
  • That’s exactly what I did! Each time the sketch is refreshed it randomly picks 1 of the 3 libs:

Click here to download the full app project.
Also go to link below to view it fullscreen:

2 Likes

Well I couldn’t stop! I’ve found out a new language, RapydScript:

In the same vein as CoffeeScript is inspired by Ruby, RapydScript is inspired by Python.

It’s the same “Self Avoiding Walk II” CoffeeScript multi-flavor sketch, but now converted to RapydScript:

You can click here to download the full sketch so you can edit & run it somewhere else.
And go to link below to view it fullscreen:

2 Likes