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

p5.js Coding Questions
13

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