Reference
Shifts bits to the right. The number to the left of the operator is shifted the number of places specified by the number to the right. Each shift to the right halves the number, therefore each right s…
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:
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:
<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>
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 it definately has other problems
// 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?
BtW, what does this kind of expression mean?
The bitwise right shift operator moves all bits of a value ‘x’ times:
Shifts bits to the right. The number to the left of the operator is shifted the number of places specified by the number to the right. Each shift to the right halves the number, therefore each right s…
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).
And the OpenProcessing.org web editor is brilliant and it can declare
static
methods within; my current Processing IDE cannot, except by adding .java files.
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.
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 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?
I understand that the backtracking algorithm is 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:
true
. Spot clear() {
for (final Step step : options) step.tried = false;
visited = false;
return this;
}
Is it that you can update the screen throughout in p5…
I believe callback draw() needs to finish before p5js sketch’s canvas is updated.
Thank you so much for this good explanation!
Decided to convert my sketch to Python Mode too:
"""
* 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))
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)
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]
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
This is brilliant !!!
Hi @GoToLoop
I wonder if this one
removals += removed? 1 : -removals;
is equivalent
if (removed) { removals += 1;}
else { removals -= 1; }
removed? 1 : -removals;
you can test it yourself.
My guess
if (removed) {
removals += 1;
}
else {
removals += -removals; // which is 0 I guess
}
Click here to download the full app project.
Also go to link below to view it fullscreen:
Well I couldn’t stop! I’ve found out a new language, RapydScript:
Python-inspired, decluttered JavaScript. Contribute to atsepkov/RapydScript development by creating an account on GitHub.
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:
Python is now a full browser client language w/ PyScript:
Run Python code in your HTML.
So again I couldn’t resist converting my previous RapydScript sketch “Self Avoiding Walk II” to PyScript.
I’ve also added Python type hints to the whole code:
Python Enhancement Proposals (PEPs)
All 3 JS Processing flavors run on PyScript just like CoffeeScript & RapydScript previous versions:
You can click here to download the full sketch so you can edit & run it somewhere else.
And go to the link below to view it fullscreen: